Over and Under

Time for a game. You will need one or more decks of the following 16 triangular cards.

Cards 01

The first game is a puzzle and asks to tile a triangle with all cards from a complete deck so that the tiles match along their edges, like so,

Challenge 01

except that in my attempt above two triangles don’t match. No hints today.

Next we use one or more decks to play a 2-person game. All cards are shuffled and form a single deck, top card visible. You will need three special cards, each just marked with one of the three card colors on it. Both players draw one of these color cards and keep their color secret. 

Now they take turns picking the top card from the deck and placing it on the table so that it matches previously placed cards. However, this time the matching has to happen along half-edges. For instance, after using a 16 card deck, the table might look like this:

Game1 01

Each newly placed card has to border a previously placed card, and match along half edges on all sides where it borders another card.

When all cards are played, the players reveal their secret colors and score. Note that the colored arcs form chains of equal color. Suppose that player A is orange and player B purple. A looks at all orange chains of length at least 2. There are three orange chains of length 2 and one of length 3. For each of these chains, A counts how often they go over a purple arc. This happens 7 times, and A scores as many points. Similarly, B looks at all purple chains of length at least two. There are three, of lengths 2, 3, and 4. They go over an orange arc six times, so A wins by one point.

The idea is to arrange cards in chains of your color that go often over the snakes of your opponent’s color. The problem is, of course, that in the beginning you won’t know your opponent’s color. So you might want to put cards that have your arc go under both other arcs not into chains but out of the way. This, however, might give away your color…

Finally, here is a 3 person game played on a hexagonal board of edge length 4.

Board0 01

The three players are dealt a color card each, and again the colors are being kept secret. You will need six decks of cards, for a total of 96 cards. Shuffle all cards and let each player grab 32. Then the players put their cards onto the board so that they meet at least one previously placed card along an entire edge, and match the colors of all cards they meet. After all cards are played, the board will look similar to the one below, except that there will be crossings.

Board 01

When the board is completely tiled, the players reveal their colors and score: For each completed circle of their color, the player counts how often that circle stays above the other two colors. This can happen (for each circle) between 0 and 12 times. That number is squared, and all numbers for all full circles for each color are added up, giving the score for that player.

There is a little catch to be aware of: There are two colors with 12 full circles each, and one color with 13 circles (purple in the example). Clearly the player with 13 circles will have an advantage when scoring. The first player will decide which color has 13 circles, and is therefore likely to claim the advantage. But then the two opponents might unite…

Spring Cleaning II

This is a continuation of my previous post about this game. Because it is impartial and the rules are simple, one can write a computer program that computes for a given position of dirt pieces the size of the equivalent Nim heap (which is also called its Grundy number or its nimber). Because this is computationally prohibitive, one does this for simple shapes, discovers patterns, and proves these. We did this for rectangles the last time. To warm up, we do it for L-shapes today. Here is. (5,3)-L:

Sweep L53

The nimber of this position is 1, which means in particular that there is a winning move for the first player. You can for instance do vertical swipe in the second column, leaving the second player with two disconnected row/column of three dirt pieces each. From then on, we play symmetrically and win.

For the general (alb)-L, the nimbers are as follows:

a\b 2 3 4 5 6
2 0 4 4 0 3
3 4 1 0 1 0
4 3 0 3 0 3
5 0 1 0 1 0
6 3 0 3 0 3

In other words, the nimber of an L with legs at least 3 dirt pieces long behaves quite simple.
This is good, because if a player can easily memorize the nimbers of simple positions, and these nimbers are small, then the player can usually easily win against players who lack this knowledge.

But maybe all this talk about nimbers is just vain traditional mathematics, and there is an alternative way to understand this game and win easily, without any theory, just by being smart and tough?

Let’s look at at another type of Spring Cleaning positions which I call zigzags. Below are the zigzags Z(1) through Z(7),

Zigzags

and here is the table of the first few nimbers:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
nimber 0 0 1 2 0 1 2 3 1 2 3 4 0 3 4

Any pattern emerging? No? There is a solution: Whenever you have a sequence of integers you are clueless about, you had to the Online Encyclopedia of Integer Sequences, the best thing the internet has produced ever, and type it in.

It turns out that the sequence at hand is known as the sequence of nimbers of another impartial game which is called Couples are Forever. The rules are simple: The game is is being played with several piles of tokens. Both players take turns splitting any one pile of size at least three tokens into two piles. The game ends when no piles with more than two tokens are left. This impartial game, beginning with a pile of size n, has (with a shift of two) the same nimbers as the zigzags in Spring Cleaning.

Moreover, for Couples are Forever, the nimbers have been computed into the millions, and no pattern has been found whatsoever. It is not even known whether the nimbers remain bounded.

Couplesgraph

Above is the graph for the nimbers of Couples are Forever (or zigzags in Spring Cleaning) for pile sizes up to 25,000. At first (up to 10,000 or so), it looks like the nimbers are growing linearly, but then they appear to even out. Nobody knows. This is one of the famous open problems in combinatorial game theory.

It tells us also that there won’t be a tough&smart solution for this game, or for Spring Cleaning, or for reality. Which is a good thing.

Spring Cleaning I

Spring Cleaning is played on a rectangular array of randomly placed dirt pieces. A sweep consists of removing a single row or column of consecutive dirt pieces.

Sweep legal

Above are some example of legal sweeps, and below are illegal sweeps.

Sweep illegal

This is a game for two players, who take turns by doing exactly one sweep. The player who sweeps the last time is the winner. This is an impartial game which means that each position is equivalent to a single game of Nim. This is usually bad news, because playing Nim well requires us to perform exclusive or additions of binary numbers in our head, for which our brains are not (yet) well equipped.

The good news here is that many simple positions are equivalent to very small Nim piles, meaning that computations are easy. I will explain this using an example. No proofs (even though they are easy, too).

Sweep win1

It’s your turn to find a winning move in the position above. You know (because I promise) that rectangles completely filled with dirt pieces are easy positions, so you will look for moves that separate the dirt pieces into such rectangles. Here is such a move:

Sweep win1 sol

After that, we are left with four separate rectangles, all completely dirty. This means that this game is equivalent to a game of Nim with four Nim piles. The question is what the pile sizes are. The answer is simple: Any rectangle both of whose dimensions are odd corresponds to a Nim pile of size 1, if both dimensions are even, the Nim pile is empty (size 0), and otherwise, the Nim pile has size 2. In our example, we have a 1×1 rectangle, a 1×3 rectangle, and two 1×2 rectangles. They correspond to Nim piles of sizes 1, 1, 2, and 2. The exclusive or sum of these numbers is 0. This is what we want, because it means that after this move, the game is equivalent to an empty Nim pile. From now on it’s easy. Suppose that our opponent performs a vertical swipe on the 1×3 rectangle. What do we do to return the game to Nim-value 0?

Sweep 3 01

We can sweep away any of the isolated dirt pieces: From then on, the game is symmetrical and we can win easily without any Nim-theory. And we better leave the two 1×2 rectangles untouched. Suppose we remove one of them completely. Then we are left with three 1×1 rectangles and a single 1×2 rectangle, which exclusive or sums up to a Nim pile of size 3, in which case our opponent can win.

Sweep 4 01

The winning move would be to reduce the remaining 1×2 rectangle to a 1×1 rectangle with a horizontal sweep.

So, if we know how to deal with Nim positions that consist of Nim piles of sizes 1 and 2, we will be able to win Spring Cleaning by dissecting a given position eventually into rectangles.

Alchemy (From the Pillowbook X)

Here is a variation of the pillow theme. This time, the tiles are not based on squares as the regular pillows or on triangles as in an older post, but on 60 degree rhombi. I only use pieces with convex or concave edges, so there are seven different rhombic pillows up to symmetry, this time also not distinguishing between mirror symmetric pieces. The main diagonals of the original rhombi are marked white. For the purpose of the Alchemy game below, I call them elements.

Elements

These elements can be used to tile curvy shapes like the curvy hexagon below. Again, for the purpose of the game, I call such a tiled hexagon a Philosopher’s Stone.

Stone1

I leave going through the brain yoga to discuss tileability questions to the dear reader. Instead, here is the game I designed these pieces for.

Alchemy

A Game for 2-6 Players

Purpose

To complete the Magnum Opus by crafting a Philosopher’s Stone.

Material

  • The seven elements above in seven colors, colored on both sides, at least 4 of each kind for each player;
  • One transmutation card for each player;
  • One Philosopher’s Stone outline for each player;
  • Pencils and glue sticks.

Below is a template for the transmutation card. It shows a heptagon with the elements at its vertices, and all possible connections (transmutations, that is).

Transmutations

Preparation

All elements are separated into resource piles according to color/shape. Each players takes a transfiguration card and an outline of the Philosopher’s Stone.

Outline

Above is an outline of the Philosophers stone, with little notches to indicate where the corners of the elements have to go. The elements are shown next to it to scale so that you get the elements in the right size.

Completing the Magnum OpusGoals

The goal of the game is to accomplish the Opus Magnum by filling the outline of the Philosopher’s Stone with elements using as few transmutations as possible. Elements must be placed so that

  • at least one corner matches a notch or a corner of another element that has already been placed;
  • elements don’t overlap and don’t leave gaps;
  • no two equal elements may share a curved edge (but they may share a vertex).

Scoring

When a player has completed a Philosopher’s Stone, he or she determins the used transmutations:
A transmutation occurs in the Philosopher’s Stone when two elements share a curved edge.

The players record a transmutation on their transmutation card by drawing a straight red edge between two elements that share a curved edge in their completed Philosopher’s Stone.

The unused edges are then drawn black. The player with the largest number of black edges becomes the master alchemist.

Below is the completed transmutation card for the Philosopher’s Stone at the top. This was a pretty poor job, the player used all but three of all possible transmutations.

Transmutations2

One can turn this game also into a puzzle. Can you tile the Philosopher’s Stone with the seven elements that its transmutation card is the one below?

Transmutations puzzle

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.

Preparing for the Future

For a democracy to function properly, two things are essential: Firstly, the voting population must to some extent be able to identify with the entire population, meaning to be able to look beyond their own belly, and rather to use common sense. Secondly, at all times it must be the clearly stated intent of all candidates to protect the interests of all minorities.

Sadly, neither of these prerequisites were met in the US election. An excellent way to practice them is by playing games. It teaches you that you have to play by the rules, and that decisions based on rational thinking are usually better than those based on your guts.

Below is a slight modification of a game I made up for school age children a while ago, allowing us to experience some aspects of daily medieval life. Let’s prepare for the future.

MedievalopolyBoard 01

Material

  • The game board shows a track like in monopoly, ruled by lords and disgraced lords.
  • A deck of some 50 small cards showing loaves of bread. There should be cards showing 1 and 5 loaves. Make you own.
  • Standard die. If you want the game to be more realistic, get a loaded die.
  • Play figures for each player, all white. You know who you are.

Preparation

All players choose a play figure and put it onto Harvest. They each roll the die twice to determine the harvest: The total number of eyes is the number of bread each player receives. The player with the fewest breads begins. From then on, the game proceeds clockwise.

Turns

The player rolls the die and moves her figure clockwise as many fields forward as the die shows. Depending on the field, the player takes the associated action.

Property field

If the player lands on a property field, she can decide to seek employment or to steal something.
After this decision is made, she rolls the die.

Employment

The reward depends on the number of eyes the die shows:

  1. you obtain work and are paid with one bread.
  2. you obtain work and are paid with two breads.
  3. you are allowed to work without payment.
  4. you stay for the night and pay one bread.
  5. you are robbed and lose two bread.
  6. you are suspected of stealing. Move directly to ordeal. At your next turn you will be tried.

Stealing

The success depends on the number of eyes the die shows:

  1. you steal 1 bread and escape unrecognized.
  2. you steal 2 bread and escape unrecognized.
  3. you steal 3 bread and escape unrecognized.
  4. you are sent to jail and stay there for one turn.
  5. you are sent to jail and stay there for two turns.
  6. you are sent to jail and stay there for three turns.

Jail

If you land on jail, and the jail is empty, nothing else happens. If there are one or more prisoners in jail,
you free one of the prisoners of your choice but have to take her punishment instead. For instance, if a prisoner has to skip two rounds and you free her, she is moved to the white visitor spot in the prison while you are placed in the gray prison cell with number 2 in it. After you skipped two turns, you will continue.
When you are in jail already, each turn you move one step to the left to remind you of the number of turns still to skip.

Ordeal

If you land on Ordeal, you are accused of stealing. To find out whether your are guilty, you roll a die. Your punishment depends on the outcome of the die:

  1. Guilty: pay 1 bread
  2. Guilty: go immediately to Pilgrimage. Do not collect bread at Harvest.
  3. Guilty: go immediately to Crusade.
  4. Guilty: go immediately to Shaming.
  5. Not guilty. You may continue on your next turn.
  6. You accuse another player of your choice of witchcraft and go free on your next turn. The other player is put in jail and misses three turns.

Shaming

If you land on or pass shaming, you may give any of the other players on Shaming one bread out of mercy. This player will then go free on her next turn.
If you have been sent to shaming, you have to wait there until a player passes you and gives you one bread. You then keep the bread and are allowed to continue on your next turn.

Other Action Fields

These come with explanations:

  • Church: Pay one bread for penance
  • Broken Leg: Wait one round
  • Crusade: Wait two rounds
  • Dowry: Pay two bread for daughter
  • Pilgrimage: Wait one round
  • Treasure: You find gold worth five bread
  • Robbed: Pay one bread
  • Tuition: Pay one bread
  • Harvest: If a player lands on or passes Harvest, she rolls a die and obtains the corresponding number of bread.

Out of Bread?

If a player is out of bread but has to pay, she goes to Shaming. There she waits until another player passes her and gives her one bread.

End of Game

The game ends either after six rounds or when all players are stuck in Shaming.
In the first case, the player with the most bread wins. In the second case, all players lose.