Combinatorial Games (Part II): Different Moves for Left and Right
This raises the following interesting question: When the board is filled with stones, must there be a chain of stones for one of the players? It turns out that the answer is yes. Thus, it is not possible for a game of Hex to end in a draw, that is, result in a position at the end of the game where neither player has won. The result follows from ideas in topology related to the Brauer fixed point theorem! You can try playing Hex here, but note the restriction, not in the usual rules, that one can not play in the center hexagon on this particular board!
Anatol Beck (University of Wisconsin) considered this intriguing variant of Hex: If the first player is known to have an advantage, perhaps it would be "fair" to allow the second player to specify a first move for the first player to make the game more "fair." Beck proved that if the second player chooses the cell to force the first player to move to, then the "forced" win is transferred to the second player. However, again, there is no known set of instructions which informs the second player how to achieve this forced win (for large boards)! The difficulty of determining a winning strategy for Hex is related to the fact that finding such a strategy is known to be P-Space Complete, which means that finding a solution which uses only a polynomial amount of space for keeping track of the solution is not likely.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance