Gale's Game

Here's a charming pen and paper game in the style of hex, but easier to play without specialist equipment. I came across it in a Martin Gardner article (I'm in a Gardner sort of phase at the moment) and I'm including it mostly because of the extroidanary work that has been done to produce an AI opponent that is capable of winning with very basic apparatus.

But I get ahead of myself. Two players play on two 6x5 grids which are slightly offset from each other like this:

Filled dots and empty circles are an easy substitute when you only have one colour of pen

Play starts with the black player and they can draw any line connecting two black dots, then the red player can do the same joining two red dots. Here is the game four moves in:

Again, with one colour of pen these are best done with solid and dashed lines

The object of the game for the black player is to connect the top and the bottom of the grid, while the red player aims to connect the left and the right. This is not a balanced game because the black player gets to go first, but it is important to make a distinction between games which have a vague advantage to the first player like chess and those that definitely have a win like this one. To see this first realise that a draw is impossible because only one player makes a move each turn so wins can't happen simulatanously and if the other player hasn't yet connected their two sides then there must be at least one path for you to win. The first player must have a win because if the second player has a win then the first player could just play any random move and then follow the winning strategy for the second player. I'll leave it as an exercise to you to see why this logic doesn't apply to chess.

Let's carry on with the sample game and see it evolve:

Black tries to connect to the top and Red holds the stream off.

Black can just continue this line down and if Red just follows it down then Black will win by having a straight line down, so eventually Red has had to attempt to stop it at the top. This forces Black to start playing down the right hand side:

Eventually Black has forced a win.

Now here comes my favourite part of the story. Below is the idea of a very simple AI which was designed in the 50s from MIT which plays the game almost perfectly. The computer will be playing the black dots and will start off with a grid of resistors with a power supply linking the top to the bottom. Whenever the human player makes a move the corresponding wire that the Red move crosses over is removed which increases the resistance on the remaining routes. On the computer's move it picks the highest resistence (made easier if you use bulbs rather than resistors by picking the brightest) as the move to make. Of the first 100 tests with the computer making the first move it won 98. I love the simplicity!