This Year in Marienbad

Cartoon

Alain Resnais’ film L’Année dernière à Marienbad is generally praised as visually breathtaking and intellectually incomprehensible. Since this year, this film might also be called visionary.

A game is being played multiple times and one of the unnamed participants (called M in the script), states “Je peux perdre, mais je gagne toujours”. This sounds eerily familiar. And M does always win, making moves that don’t seem to follow any logic.

The similarities go much deeper. Both the actors as the viewers are not only left in doubt what is true or false (as in any good mystery), but also about what is real and unreal. The film takes place in a state of mind that has been dubbed hypernormality, a concept that Adam Curtis is using in his brilliant recent documentary HyperNormalisation to explain how our traditional perception of reality has been dismantled, with devastating consequences.

The game that is being played is called Nim, and it is at the center of the film for a reason. It is an impartial game, which means that both players have complete information (no hidden cards) and the same moves available (no black and white pieces owned by the players). Impartial games also must end with one player winning and the other player losing. This means in particular that either the first or the second player must have a strategy, proving M almost a lier, because he cannot have a strategy both as first and second player. He is, however, not claiming that he can always win, just that he does always win, thereby claiming access to a powers beyond those of reason.

Let’s have a closer look at Nim. It is played with a several heaps of tokens (matches in the film). At each turn, the player is allowed to take any positive number of tokens from a single pile. The player who takes the last token wins.

The simplest case is that of a single pile: The first player will win by taking the entire pile.

The second simplest case is that of two piles. Here, symmetry plays a fundamental role. If both piles have the same size, the player must necessarily take away from one pile, thus leaving two piles of different size. On the other hand, if the piles have different sizes, the player can take away tokens from the larger pile to make them equal.
This proves that there is a simple winning strategy that consists of making both piles equal in size.

We can visualize this using coordinates in the first quadrant: A game position with pile sizes x and y determines a square at coordinates (x,y).

TwoHeapNim

The olive green squares mark the positions where both heaps have the same size. To move means to decrease either the x or the y coordinate. We can clearly see that we can move from any white square to an olive square (winning move), and that we are forced to move from an olive square to a white square.

This is all very simple. However, as soon as the game is played with at least three heaps (the film uses four), things get much more complicated. Let’s see how the space of positions looks like. We can again use the first octant of space to indicate heap sizes x, y, z of three heaps by a little box at the point with coordinates (x,y,z). Below you see the boxes that indicate the losing positions for heap sizes 0 or 1 (left image) and heap sizes up to 3 (right image). A move again decreases precisely one of the three coordinates. Convince yourself that from one of the reddish boxes you have to move to a non-box, while from a non-box you can always move to a reddish box.

Nim 1 2

You can also see that you get from the left image to the right image by substituting a box by the entire left image. This persists, and what emerges with increasing heap sizes is a fractal called the Sierpinski Pyramid.

Nim 5

It is the full intention that this looks chaotic and complicated, because this is what a hypernormalised mind perceives. But behind this apparent chaos, there is a simple rule, except that its simplicity is not intuitively useful.

A position (x,y,z) is a losing position (and hence marked by a cube) precisely when the either-or sum of the binary representations of x, y, and z are zero. For instance, if the pile sizes are 1, 4, and 7, these decimal numbers have binary representation 001, 100, and 111. We obtain their either-or sum by adding these numbers in the binary system without carry, this gives 010. Because this is not 000, we are in winning position. The winning move takes 2 token from the third pile, changing its binary representation to 101.

This is computational very simple (and works for any number of piles), but there is no apparent way to make this intuitive. We humans do not feel that we are in a losing position in Nim. In this sense Nim becomes a perfect symbol for a world that appears detached from common sense, but can be controlled by algorithms.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s