Lesson 1

For some games, it can be non-constructively shown that the second player cannot have a winning strategy. This is done roughly as follows: assuming that the second player has a winning strategy, we show that the first player also has a winning strategy, and we arrive at a contradiction. If it can also be shown that there are no draws in the game, then we immediately get that the first player has a winning strategy. At the same time, constructing an explicit strategy for the first player can be difficult.

We will illustrate this with the game of Hex. This is a game with relatively simple rules, invented by Piet Hein in 1942 and reinvented by John Nash in 1948. It turns out that in this game, the first player has a winning strategy, but no one knows it!