Susanne Tak

Hackenbush

Hackenbush is a two-player game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.

The game starts with the players drawing a "ground" line (conventionally, but not necessarily, a horizontal line at the bottom of the paper or other playing area) and several line segments such that each line segment is connected to the ground, either directly at an endpoint, or indirectly, via a chain of other segments connected by endpoints. Any number of segments may meet at a point and thus there may be multiple paths to ground.

On his turn, a player "cuts" (erases) any line segment of his choice. Every line segment no longer connected to the ground by any path "falls" (i.e., gets erased). According to the normal play convention of combinatorial game theory, the first player who is unable to move loses. (source)

In the simulation below you can make and play your own Hackenbush game (original, Blue-Red or Blue-Red-Green). First, draw some lines. You can draw up to five lines between point pairs. In edit mode you can move points or delete lines. When you press play Blue can make the first move.

- Green lines can be removed by both players, use only green lines for the original (one-player) game.
- Switching to play mode will clear up all unconnected lines.
- I don't recommend going back to draw mode and making changes while you are playing, particularly when there are multiple lines between a point pair.

Solver for subtraction game

The subtraction game is a simple take-away game (also known as one-heap Nim^source). In this two-player game, you start with a pile of objects, e.g. matches. The players alternate turns and each turn the player must remove some matches from the pile. How many matches can be removed is specified by the subtraction set. For example, a relatively simple variant has subtraction set {1,2,3}. In other words, each turn the player must remove either 1, 2 or 3 matches from the pile.

In the Normal variant, the last player to move wins (i.e., the player that takes the last match). In the Misère variant, the last player to move loses.

The game can be analyzed in terms of so-called N- and P-positions. A game is in a P-position if it secures a win for the Previous player (the one who just moved). A game is in an N-position if it secures a win for the Next player (these are winning positions from an egocentric perspective). For example, in the Misère variant with subtraction set {1,2,3}, 1 is a P-position, 2, 3 and 4 are N-positions, as you can put your opponent in a losing position (you force the other player to take the last match), but 5 is a P-position, as, no matter what you do, you'll put your opponent in a N-position. For the Misère {1,2,3}-game, this pattern is all there is to it, PNNNPNNNPNNN... and so forth.

The pattern has been proven^source to always become periodical. However, to predict the length and structure of the period directly from the subtraction set is still an open problem.

The tool below analyzes first 1000 positions, and attempts to find the repeating pattern. NOTE: when the smallest move in the subtraction set is greater than 1, in the Normal variant all postions below the smallest move are considered P-positions (as the previous player has made the last possible move). Vice versa for the Misère variant.

Partial solver for 'princess and the roses' problem

Similar to the subtraction problem described above, the princess and the roses is another take-away problem. It's quite similar to Nim^source, but with a twist.

The princess lives in castle with a beautiful rose garden. The princess has two admirers. The admirers take turns to bring the princess roses. They can either bring 1 rose, or 2 roses of different colour. Whoever brings the princess the final rose from the garden wins.

Once again, the tool analyzes winning and losing positions. A winning position is, of course, the situation where there is one rose, or two roses of different colour. A losing position is one where you can only put the other player in a winning position. A winning position is, besides the obvious ones already mentioned, one where you can put your opponent in a losing position. Unfortunately, the tool tends to take a very long time when the number of different rose colours is 8 or more (7 takes a while as well). According to this source, the problem is still open for 6 or more colours.

Lights Out game

The Lights Out game is traditionally played on a grid of five rows by five columns with a total of 25 lights. Some of the lights are on at the start of the game. The point of Lights Out, as can be seen from the name, is to switch off all the lights. You can click on lights (they are in fact buttons with a light in them). If you click on a light, you toggle the state it's in (so if the light was on, it goes off; if it was off, you switch it on). If you toggle a light by clicking on it, you will also toggle its direct neighbours (left, right, top, bottom).

In this online version of Lights Out I've added some more features. You can pick different board sizes and board shapes: a torus shape where the top and bottom row are also 'connected', as are the left and right column, and a ring shape where the left and right column are connected.

You can also pick any start configuration you like in edit mode (beware though that for some board sizes not all start configurations are solvable!).

Open in a new window