President (Impeachment Games I)

Time for another little game. It’s called President, and it is also about democracy and taxes. Good for 4-12 players.

Material:

  • Paper money (any currency will do)
  • sets of six tokens in as many different colors as there are players,
  • a tax board for each player, i.e. a sheet of paper with the numbers from 0 to 60 in a row,
  • an extra counter to mark the current tax rate, 
  • 2-4 game figures representing political parties.

Money4 2a

Setup: 

Each player gets $100 in small bills, picks a color and gets three tokens of that color,
sets the tax rate counter on her or his tax board to $10.
The political parties are placed in the center of the board.

The game proceeds in years. Each year consists of an election phase and and ruling phase.

Before the game begins, the players decide for how many years they want to play. 

Money4 2b

Voting:

First, all players pay their taxes.
For the first year, these are $10, and each player places them into the center of the table.
If in a later round a player cannot pay the taxes, that’s ok. The poor are tax exempt. But see the variation below.

Next, each player votes for political parties by placing their tokens next to the party figures. Votes can be split, and not all votes need to be used. In the first round, a player is selected randomly to begin the voting, and then it continues clockwise.

After all votes have been cast, the winning party is determined by counting all votes. If more than one party  has the same highest number of votes, the winning party is determined randomly. You can place the tied parties in a bag and draw one, for instance.

The player who cast the most votes for the winning party is declared president. If there are more than one player with the same highest number of votes, the president is determined randomly among all players with the highest number of votes for the leading party.

All used voting tokens are returned to the players, which ends the voting phase.

Variation: If a player cannot pay taxes, he/she loses one voting counter.

Money4 2c

Ruling:

In the ruling phase, the elected president must make a few decisions:

  • Adjust taxes: The president can adjust how much taxes each player pays. He or she does so by moving the tax counter on each player’s tax board up or down by at most $2. The taxes cannot exceed $60 and must be at least $10. The total amount of taxes paid must remain equal to $10 times the number of players. This means that if the president lowers taxes somewhere, he/she must increase them somewhere else.
  • Adjust the number of votes: For each player, the president can increase or decrease the number of voting tokens the player has by at most one. The number of voting tokens cannot exceed 6, and must be at least 1.
  • Distribute tax income: Finally, the president distributes all of this year’s tax income to all players as he or she desires, including him or herself.

The game ends when the number of years the players agreed on has passed. Then the plaeyrs vote on one of the following three winning conditions:

  • The richest player wins
  • The player who was most often president wins
  • The player who has the most voting tokens wins

Money4 2d

That was a lot of text. I like to invent games, and I like to watch how people play games. So I programmed a little simulation to see how this game would perform while tweaking the parameters. All players in my simulation behave opportunistic. They begin with equal preferences for the political parties. When somebody’s income increases, they start favoring the ruling party in the next vote. The president uses his/her power to give more votes and more money to those who voted for his/her party.

In contrast to humans, the computer was willing to play for an extended period of time. I was expecting that the game would quickly stabilize to a single rich dictator with the rest of the population living in poverty. The pictures above show the wealth/time graph of a 4-person game with just two parties. While presidents often rule for long periods of time (50,000 years for the blue president…), the situations is all but stable. That it can take so long is only because the underlings in my simulation do not cooperate. Below are mere 5,000 years with eight players and four parties. I have run several such simulations, and it appears that change happens more often when there are more parties involved.

Money8 4a

 

Advertisements

Eraserhead (Games on Circles I)

This is not about the film by David Lynch. Eraserhead is played by two players on finite graph with some vertices occupied by erasers. At each turn, the player chooses one eraser, moves it to an unoccupied adjacent edge, thereby erasing the connecting edge. The player who moves last wins.

Let’s analyze this for cycle graphs.
Eraserhead1 01

If played with just one eraser, the first player chooses the direction, and all other moves are forced, until the eraser has erased all edges. So the first player wins if the cycle graph has an odd number of vertices. That was boring.

For two erasers, it gets slightly more interesting, but the outcome is the same: The first player can win if the number of vertices is odd. The two erasers divide the graph into two components whose number of vertices have different parity (3 and 4 in the example below).
Moving an eraser into the even component would be a mistake, as the second player will then move into the same component with the other eraser. This leaves an even number of moves for both players, and the second player will win.

But a winning move for the first player consists of moving one eraser into the odd component. This leaves the second player with two choices: Moving the other eraser either way leaves an odd number of moves for both players, and the first player wins. If the second player moves the first eraser again, the first player can move either way and will win.

Eraserhead2 01

So while a little harder, this was still easy. Does this even/odd pattern for winning and losing persist with more erasers? At first, it seems so. For any number of erasers (except the cases of no erasers and erasers everywhere, which leave no moves to begin with), the first (resp. second) player can always win with if the cycle graph has an odd (resp. even) number of vertices — up to cycle graphs with 8 vertices. For the following position with three erasers, the first player has no winning move. There are three essentially different moves, and the diagram give winning responses for the second player.

Eraserhead3 01

The first line is interesting. With the first player to move again, there are still 8 edges to delete (possibly). If the first player moves with the topmost eraser right, this will actually happen, and the first player will loose. To prevent this, s(he) must move that eraser to the left. This leaves all erasers in one component with a total of four edges left. This looks like a good thing, but no matter how they play, only three edges will be deleted, and the second player must win.

So the game does get complicated. What helps is to know the nimbers for simple subpositions, like chains with or without erasers at the end. For instance, the line graph with n vertices and one eraser at the end has nimber 1 for odd even n and 0 for odd n. Similarly, the line graph with n vertices and erasers at both end has nimber 0 for odd even n and 1 for odd n. This is quite trivial, of course, as all moves are forced. More surprisingly, for the line graph with two erasers at the end and a third eraser in between, the nimbers are again 1 for n odd, and 0 for n even, except when n=3 or n=4. Then the nimbers are 0 and 2, respectively. So things start off with promising simple patterns, but then deviate. Below I have, for line graphs of length 12 and 13, respectively a unit cube at coordinate (x,y,z) if the position with erasers at x, y, and z is a lost position for the first player.

Lost12 13

Finally, below, the corresponding images for cycle graphs, viewed diagonally to emphasize the symmetry. The discrepancy is baffling.

Lostcycle3 12

Parking Garages

The first examples of periodic minimal surfaces with helicoidal ends (besides the helicoid itself) are Hermann Karcher’s twisted Scherk surfaces from 1988.
Here are a few of them, rendered with Bryce back in 1999.

Hst

As you can see, these can be twisted more and more so that they appear to become two helicoids glued together. In this case, the two helicoids turn the same way. A few years later, Martin and I were looking at more general ways of gluing helicoids together to obtain new minimal surfaces. The model case is what we called a parking garage structure: You can describe them mathematically as superpositions of complex argument functions, like so:

Arg

Here the numbers z(k) designate the location of the axis viewed from above, and the ε(k) can be +1 or -1, depending on the spin of the helicoid.
Note that the graph of the multivalued function arg(z) is half of a helicoid (that stays on one side of the vertical axis).

An example with three helicoidal columns of the same spin, placed at -1, 0, and 1, looks like this:

Ks3a

If you alternate the spin, you get surfaces that untwist to higher genus helicoids, we believe.

Heli3a

It is also possible to place the columns off a common line, like so:

Exotic2

Nobody knows what minimal surfaces these untwist to.

The images above were made with Mathematics in 2001. Later I found a simple way to do this in PoVRay, which I might explain next time. Here an image from 2002:

1 3 a slice 025 m

Most people get easily lost in parking garages that have only two columns. It would be cool to have a computer game where one can walk around these more complicated structures, with the location of the columns moving in time …

Magnetism

Magnetism is played by two players on a strip of squares, who take turns placing + and – tokens onto the strip. The only rule is that no two tokens with the same parity can be placed next to each other. For instance, there are three legal moves in the following position:

Legal

The player who moves last, wins. This makes Magnetism an impartial game, so that each position is equivalent to a Nim-pile. It turns out that Magnetism is very simple.
First we notice that any position is the sum of simpler positions that have tokens just at the end of a strip. (A sum of games is played by first choosing a game summand, and then making a move in that summand).

Sum 01

Therefore we will know everything about Magentism if we can determine the size of the Nim-piles (the “nimbers”) of the 9 elementary positions:

Nine 01

Things get even simpler. Because of the symmetry of things, there are only four truly different boards to consider.

Four 01

Let’s denote the nimbers of a board of n empty squares (thus not counting the tokens at the end when present) by G(n), G+(n), G++(n), and G+-(n).

n 0 1 2 3 4 5 6
G(n) 0 1 0 1 0 1 0
G+(n) 0 1 2 3 4 5 6
G++(n) 1 1 1 1 1 1
G+-(n) 0 0 0 0 0 0 0

Now you can win in a position with a positive nimber by moving to a position with zero nimber. For instance, on a board with a single + at one end, one possible winning move is to put a – at the other end.

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.