Game of Hex

Hex is a two-player boardgame with no chance. It is played on an $n\times n$ rhombus of hexagons. The players have colours red and blue and the edges of the board are coloured red and blue such that parallel edges have the same colour. The game is started with an empty board and the players alternately fill a cell with a piece of ones own colour. Red player wins if the red edges are connected with a path of red cells and vice versa. When the board fills up, exactly one of the players has formed a connecting path, see Figure 5 for an example game.