One Tile Is All It Takes

surt91 invited me to write a guest post and left the topic up to me. I went looking for something that needs almost no code and still earns a second look — and landed on Truchet tiles.

There is exactly one tile. It is a square carrying two quarter-circle arcs, each joining the midpoints of two adjacent edges. That is the entire inventory. The only freedom is how it sits on the grid, and there are exactly two options:

The two orientations of the single tile: the arcs hug either the top-left and bottom-right corners or the other two

Drop many copies onto a grid and flip a coin for each one. Out of this almost insultingly simple rule falls this:

Truchet tiling of randomly rotated quarter circles

It gets me every time. Nothing in the rule knows anything about loops, symmetry or closed curves, and yet the arcs reach across the tile boundaries and weave into a tidy fabric. The idea is old: the Dominican friar Sébastien Truchet worked through the patterns a single square produces in all its rotations back in 1704. His original tile was still a square split diagonally into a black and a white half; the smooth arc variant that gives these flowing lines is due to Cyril Stanley Smith, who dug the Truchet tiles back up in 1987.

The whole trick fits into a handful of lines of Python that print an SVG directly — no numpy, no plotting framework, just a bit of geometry and random:

import random

def truchet(filename, n=16, s=40, seed=42, stroke_ratio=0.18):
    random.seed(seed)
    w = h = n * s
    r, sw = s / 2, s * stroke_ratio
    paths = []
    for j in range(n):
        for i in range(n):
            x, y = i * s, j * s
            tm = (x + r, y)      # top middle
            rm = (x + s, y + r)  # right middle
            bm = (x + r, y + s)  # bottom middle
            lm = (x, y + r)      # left middle
            if random.random() < 0.5:
                # arcs hug the top-left and bottom-right corners
                arcs = [(tm, lm, 1), (bm, rm, 1)]
            else:
                # ... or the top-right and bottom-left ones
                arcs = [(tm, rm, 0), (lm, bm, 1)]
            for (ax, ay), (bx, by), sweep in arcs:
                paths.append(f'M{ax:.1f} {ay:.1f} '
                             f'A{r:.1f} {r:.1f} 0 0 {sweep} {bx:.1f} {by:.1f}')
    body = '\n'.join(f'  <path d="{d}"/>' for d in paths)
    svg = (f'<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 {w} {h}" '
           f'width="{w}" height="{h}">\n'
           f'<g fill="none" stroke="#000" stroke-width="{sw:.1f}" '
           f'stroke-linecap="round">\n{body}\n</g>\n</svg>\n')
    with open(filename, 'w') as f:
        f.write(svg)

truchet('truchet.svg')

Per tile we draw two quarter-circle arcs as an SVG path, and the only decision is the coin flip picking which pair of corners they hug. The 1 or 0 is the arc’s sweep flag; all it does is make the arc bulge inward instead of outward. That was the entire algorithm.

Look closely and the tangle turns out not to be a tangle at all: at every edge midpoint exactly two arcs meet — one from each of the two neighbouring tiles. So every stroke has precisely two neighbours, and the whole mess comes apart cleanly into a handful of closed loops. Give each of them its own colour — a short union-find over the edges does the job — and you can see how wildly their lengths differ:

The same tiling, each closed loop in its own colour

Some loops meander all the way across the image, others have shrivelled down to a single small circle. Which of the two is decided entirely by the seed.

When I showed surt91 the finished tiling, his first reaction was that it reminded him of percolation. He is right — the random arc tiling is in fact one of the standard ways to draw critical percolation. Because every tile always carries two arcs, the coloured loops from before are nothing but the hulls of percolation clusters. And the fair coin with probability $1/2$ lands, thanks to self-duality, exactly on the critical point $p_c = 1/2$ of the square lattice. That is precisely why loops appear on every scale — at the phase transition the system is scale invariant.

So the loop-size distribution inherits everything we know about critical percolation. The loops are fractals of dimension $7/4$ — the percolation counterpart to the $187/96$ that already turned up here for the Ising model (a German post). The number of loops enclosing an area larger than $A$ is even known exactly and universally, namely $\frac{1}{8\pi\sqrt{3}}\,\frac{1}{A}$, a pretty result of Cardy and Ziff. And the best part, because it confirms surt91’s hunch outright: bias the coin so that one orientation comes up more often, and you step off the critical point. The big loops meandering across the image vanish in favour of a characteristic maximum size — only at exactly $1/2$ does the spectrum reach all the way to the edge of the picture. In the generator that is a one-line change: random.random() < p instead of < 0.5.

There is no point in a GitHub repo for any of this; the full code is already up there in the post. A different number in the seed, and you have your next wallpaper. Which makes this guest post fit neatly into this blog’s well-documented fondness for black-and-white pictures of lines and circles — a German post, but the pictures need no translation.

Nightmare before Easter

Easter is a holiday whose time is determined with an unnecessarily complicated rule. The first Sunday after the first full moon in Spring. Most people have no other choice than to look its date up in a calendar and trust in the calendar manufacturer. But not anymore! I will stick it to Big Calendar and reveal the secret formula to calculate the date of easter!

from datetime import date

def easter(year: int) -> date:
    y = year
    g = y % 19 + 1                    # golden number
    c = y // 100 + 1                  # century
    x = (3 * c) // 4 - 12             # correction: dropped leap years
    z = (8 * c + 5) // 25 - 5         # correction: synchronize with moon's orbit
    d = (5 * y) // 4 - x - 10         # find sunday
    e = (11 * g + 20 + z - x) % 30    # epact
    if e == 25 and g > 11 or e == 24:
        e += 1
    n = 44 - e                        # full moon in march
    if n < 21:
        n += 30
    n = n + 7 - (d + n) % 7           # advance to next sunday
    month, day = (4, n - 31) if n > 31 else (3, n)

    return date(year, month, day)

My favorite thing about it is that each line becomes more horrendous than the previous.

This algorithm was developed by Lilius and Clavius at the end of the 16th Century. I became aware of it through a mention in an exercise in Donald Knuth’s The Art of Computer Programming 1 (Third edition, p. 159f).

Perfect Snake

I like the game snake — not so much playing it, but implementing it. The natural consequence is an autopilot. This way I can just watch instead of playing. On the German version of this blog, there are already quite a few implementations with different heuristics, but nothing particularly good at playing Snake.

But now I present an autopilot which can (at least sometimes) play a perfect game of Snake.

A perfect game of Snake

In case this gif does not convince you, this autopilot can run directly in the browser at snake.schawe.me.

So, how does it work?

Neural Networks

If one does not know how to solve something, try to make a neural net come up with a solution. One example of this applied to classic Atari games was this paper, from ten years ago. We will apply this idea of reinforcement learning to snake in this post (but of course others have done this already [8, 9]).

The fundamental idea of reinforcement learning is quite simple. Just reward the model for good decision, such that it may learn to make good decisions. So here we will use the score defined as the length of the snake at the end of the game as the objective which is maximized by good decisions.

Fortunately, there is already a lot of literature how reinforcement learning can be implemented. We will use the actor-critic approach. So we construct a neural network which takes the current state of the game as input and splits into two heads. One head is the Actor with 3 outputs, which correspond to the next action to take: “right”, “left” or “straight ahead”. The other head is the Critic with one output representing an estimate of how long the snake can grow from the current situation.

For training a full game is played by following the advice of the Actor plus a bit of noise to explore new strategies. Then the Critic is trained with all encountered game states to produce estimates for the final score, which should predict the score that was indeed reached. For training the Actor, we take states of the game, make a different decision and ask the Critic how good the resulting situation is. Depending on the estimated quality, we teach the actor to make this decision more or less often. So Actor and Critic help each other at getting better and the common part of the neural net should gain an “Understanding” of the game which both can base their output on. Ingenious!

Technical Trivialities

My Implementation uses the Python libraries Keras and Tensorflow for training and multiJSnake (German post) as the environment. It is a strange decision to implement the environment in Java. The reason is that it already existed and the combination offered the opportunity to write a post on the blog of my employer.

For this post, we will just treat the environment as a black box, which enforces the rules of Snake.

Lokal Information

One of the most important decisions when designing the model is to determine the nature of the input. The simplest option, which is quite suited for testing, is using the local information around the head of the snake: three neurons (0 or 1) indicating whether the field right, left and ahead are occupied by a wall or the snake body (and eight more for the diagonals and two fields, left, right, ahead and behind for a bit more farsightedness). Also we have to indicate where the food is, which we solve with 4 further neurons (0 or 1) representing whether the food is left, right, in or against the direction of the snake’s movement.

Behind the input we build a fully connected layer and behind that we connect directly the two heads.

Layout of the local neural network (Visualisierung: netron)

And after a few thousand training games the snake moves directly towards the food and avoids itself. But it is not yet clever enough to avoid catching itself in loops. Well, even the heuristic of rsnake (German post) was better.

A few games with local information

Global Information

To avoid the snake trapping itself, we should give it global information of the playing field — it is only fair, since humans do see the whole field, too. But even with a $10 \times 10$ field, there would be at least 100 input neurons, such that fully connected layers would lead to very large models. Instead, convolutional neural networks seem like a very good fit to solve this problem, especially since our input is of two-dimensional nature. To make life for our artificial intelligence a bit easier, we split our playing field in three channels

  1. the Head: only the position of the head has a 1, otherwise 0
  2. the body: the positions of the body have a value corresponding to the number of timesteps they will be occupied
  3. the food: only the position of the food has a 1, otherwise 0

The human view and what we show our neural net

This is not even an advantage for the snake, since a human player also sees with three color channels.

And to make life for our snake even easier, we change the output of the actor from three relative (left, right, ahead) to four absolute (north, east, south, west) directions.

Layout of the convolutional neural networks (Visualisierung: netron)

This model layout deserves to be called deep learning. The other model parameters can be looked up at github.com/surt91/multiJSnake.

And after a few tenthousand training games this model works well enough to routinely play perfect games on a $10 \times 10$ field. And since I only trained it on a $10 \times 10$ field, it fails on every other size.