is impossible for the game to end in a draw (see above), either the first or second player must win. As Hex is a perfect information game, there must be a winning strategy for either the first or second player. Let us assume that the second player has a winning strategy. The first player can now adopt the following strategy. They make an arbitrary move. Thereafter they play the winning second player strategy assumed above. If in playing this strategy, they are required to play on the cell where an arbitrary move was made, they make another arbitrary move. In this way they play the winning strategy with one extra piece always on the board. This extra piece cannot interfere with the first player's imitation of the winning strategy, for an extra piece is always an asset and never a handicap. Therefore, the first player can win. Because we have now contradicted our assumption that there is a winning strategy for the second player, we conclude that there is no winning strategy for the second player. Consequently, there must be a winning strategy for the first player. Computational complexity In 1976, Shimon Even and Robert Tarjan proved that determining whether a position in a game of generalized Hex played on arbitrary graphs is a winning position is PSPACE-complete. A strengthening of this result was proved by Reisch by reducing the quantified Boolean formula problem in conjunctive normal form to Hex. In computational complexity theory, it is widely conjectured that PSPACE-complete problems cannot be solved with efficient (polynomial time) algorithms. This result limits the efficiency of the best possible algorithms when considering arbitrary positions on boards of unbounded size, but it doesn't rule out the possibility of a simple winning strategy for the initial position (on boards of unbounded size), or a simple winning strategy for all positions on a board of a particular size. Game tree of 11 by 11 Hex In 11×11 Hex, there are approximately 2.4×1056 possible legal positions; this compares to 4.6×1046 legal positions in chess. Computed strategies for smaller boards In 2002, Jing Yang, Simon Liao and Mirek Pawlak found an explicit winning strategy for the first player on Hex boards of size 7×7 using a decomposition method with a set of reusable local patterns. They extended the method to weakly solve the center pair of topologically congruent openings on 8×8 boards in 2002 and the