Hex

Here is the board: a slanted diamond of hexagons. You are red, and the top and bottom edges are yours. Robo is blue and owns the left and right edges. You take turns placing one stone of your color on any empty cell. Stones never move and never come off. You win the moment an unbroken chain of red cells joins the top edge to the bottom edge. Robo wins with a blue chain from left to right. The four corner cells belong to both colors.

That is the whole game, and there is no such thing as a tie: fill the board and exactly one player has connected. The next section proves it.

One more thing. Robo cannot solve this game. Nobody can, once the board gets big, and even 6 by 6 is far beyond the look-at-every-game method from Chapter 7. So this Robo plays by imagination: before each move it plays thousands of random games in its head, some for every empty cell, and picks the cell that won most often. The last section explains the method. It is real, and it is beatable.

In tic-tac-toe the board fills up and nobody wins. Try to make that happen in Hex. Fill every cell with red and blue in any pattern at all, and there is always a winner. The button below fills a board at random; find the winning chain by clicking its cells, edge to edge. Or clear the board, paint it by hand, and try to build a full board with no winner. You will not manage it.

Half of the fact is easy. There can never be two winners: a red chain from top to bottom is a wall, and a blue chain from left to right would have to cross it, but no cell is both colors. The other half, that there is always at least one, is the surprise. Think of the red cells as land and the blue cells as water. If no dry path runs from the top shore to the bottom shore, the water must get all the way across from left to right. It feels obvious. It is true, but a real proof takes care, and the shape of the cells matters: on a board of squares, where cells that touch only at a corner do not count as connected, a checkerboard has no winner at all. Two hexagons that touch always share a whole edge.

In 1979 the mathematician David Gale proved something strange: this Hex fact is equivalent to a famous theorem of topology (say: tuh-POL-uh-jee) called Brouwer's fixed point theorem. Take two identical maps of Texas, crumple one up, and drop it on top of the flat one. Brouwer says some point on the crumpled map lies exactly above the same point on the flat map. Gale showed that each statement can be turned into the other.

Here is a strange fact about Hex. On a board of any size, the player who moves first can force a win. We know this for certain. And on the standard 11 by 11 board, nobody knows what the winning first move is, let alone the plan that follows it. The proof has the same shape as the one for Chomp in Chapter 8: strategy stealing.

Look at what the proof does not do. It never says which first move wins. It only shows that a winning plan for the second player is impossible. Step 4 is what makes it work, and it is the step that fails almost everywhere else. In chess an extra piece can block your own rook. In Hex an extra stone can only add chains, never remove them, and never a blue one.

For small boards, computers have gone the rest of the way and found the winning moves: every board up to 9 by 9 is solved. The 11 by 11 board is still out of reach: its winning first move exists, and nobody has found it.

Chapter 7's Robo solved tic-tac-toe by looking at every possible game. A 6 by 6 Hex board has 36 cells. Just the first ten moves can happen in 36 × 35 × 34 × ... × 27 ways, about 920 trillion (9.2 × 1014), and at that point the game has barely started.

So Robo does something different, much dumber, and surprisingly effective. For each empty cell, Robo imagines putting its stone there and then finishing the game at random: the remaining cells are filled with red and blue stones in a random order, and Robo checks who won (someone always has). It does this N times per cell, counts how many finishes it won, and plays the cell with the most wins. The strength control sets N: 50, 200, or 800 finishes per cell. This is the Monte Carlo method (say: MON-tee CAR-lo), named after the casino town, because it turns gambling into measurement.

Why would that work? A random finish is a terrible game; both sides play nonsense. But a genuinely strong cell wins a little more often even in nonsense games, and a nearly useless one loses a little more often. Robo cannot see a plan, only a rate. That is why you can beat it: a quiet plan, like the bridge in the Challenge below, is invisible to it until it is finished.