Winning strategies in DarkHex: Hex with hidden stones

Abstract

Kriegspiel Hex (aka. DarkHex) is a variant of Hex in which players do not see the opponent’s stones. Due to incomplete information, there exist boards for which neither player has a (pure) winning strategy. The main contribution of this paper is a classification of small boards based on the outcome of the game for optimal players; (i) first player can win, (ii) second player can win, or (iii) neither player can win. For boards without winner, optimal players must follow mixed strategies that maximize their winning probabilities. In this context, solving the game means computing the corresponding Nash Equilibrium (NE). This paper provides then a brief introduction on how to compute these NEs and some preliminary results are given for the $4 \times 3$ board.

Keywords

Hex incomplete information kriegspiel Nash equilibrium pure/mixed strategy

1. Introduction

In 2016, during the “Computers and Games” conference held in Leiden, Ryan Hayward introduced us to DarkHex.1

¹
We thank him for interesting discussions during CG’16 and ACG’17.

Also known as Kriegspiel Hex, this game is the cross between Kriegspiel – a version of chess in which both players can see their own pieces but not the opponent’s – and Hex. Hex is the classic connection game invented by Piet Hein in Denmark (see Hein, 1942). Hex and Kriegspiel were both popular games among the game theory students in the mathematics department of Princeton University in the late 1940s (as reported in Nasar, 1998). In 1981, Mathematics Magazine published Duane Broline’s solutions to two Kriegspiel Hex problems posed by William A. McWorter Jr.: for

n \times n

Kriegspiel Hex, for

n = 3

, the first player has a pure winning strategy, while for

n ⩾ 4

, there is no pure winning strategy (see Broline, 1981).

Rules (informally). DarkHex is a two-player game played on two identical rhomboidal boards with hexagonal cells; one board for each player. There is also an umpire who can look at both boards. From the umpire point-of-view, the two boards are combined into a single one on which the usual rules of Hex apply: alternatively players add a stone to the board and try to create a path connecting two opposite sides. The first player to link his opposite sides wins the game.

In DarkHex, each player plays on his2

For brevity, we use “he” and “his” whenever “he or she” and “his or her” are meant.

own board, without telling the other player where he plays a stone. The umpire checks that the move is legal; i.e. the chosen cell does not contain yet a stone on the opponent’s board. If the move is illegal, the umpire informs the active player who then needs to select a new cell (until he executes a legal move).

Notations. Black denotes the first player and White is the second player. The $n \times m$ board corresponds to the board in which the first player owns sides of length m, and so has a distance of n between his two sides. Figure 1 depicts the $4 \times 3$ board as an example; on this board, the first player (i.e. Black) has to connect from top-left to bottom-right using (at least) four stones.

Fig. 1.

The $4 \times 3$ board.

Solving DarkHex. In regular Hex, the first player wins on the $n \times m$ board if $n ⩽ m$ and the second player wins otherwise. Proving the existence of winning strategies is simple, but there is no generic strategy for squared $n \times n$ boards. To the best of our knowledge, boards up to $10 \times 10$ have been investigated, but not larger boards (see Yang et al., 2002; Pawlewicz and Hayward, 2013).

In DarkHex, the situation is more complex. For some instances, there is no winner. More specifically, the boards can be partitioned in three groups:

Boards on which the first player wins,

Boards on which the second player wins,

Boards on which neither player has a winning strategy.

For boards belonging to the third category, there exists no optimal deterministic strategies, also known as pure strategies. Each optimal player must follow a mixed strategy – a probabilistic distribution of pure strategies – that maximizes his winning probability. The combination of both players’ strategies results in a Nash Equilibrium (NE), a concept introduced in Nash (1950). In this context, solving the game means (1) computing the value of the NE and (2) finding the associated optimal strategies. The NE value corresponds to the optimal winning probabilities of both players.

Contributions. Our contribution is twofold. First, we study boards on which one of the players has a deterministic winning strategy. After introducing some simple examples, Section 2 describes the algorithm used to check the existence of winning strategies, and summarizes our results. Second, we investigate boards on which no player is able to win. Section 3 illustrates the notions with an ad-hoc fictitious game and then presents some techniques to compute approximate NEs.

2. Solving DarkHex with a winner

This section describes first some simple results that can be easily obtained and verified by handmade computations. It also introduces visual representations of DarkHex strategies. Finally, it explains how to check the existence (or the lack) of winning strategies for a given board.

2.1. Winners on small boards

Trivially, the first player always wins on the $1 \times m$ boards for $m ⩾ 1$ and the second player always wins on the $n \times 1$ boards for $n > 1$ .

On the $2 \times 2$ board, the first player (Black) has a winning strategy by playing in one obtuse corner at his first turn. Then, at his second turn, he can win by connecting the opposite side; there are two possible moves that create a winning path and White can occupy only one of the two cells (see Fig. 2). To depict DarkHex strategies, we use numbers to indicate the probability of each move, given a current board. If such a move is illegal (as informed by the umpire), the player updates his board with an opponent’s stone and follow his next move. According to Fig. 2, on his second turn, Black tries to put a stone on the bottom-most cell, but if this cell is already occupied by a white stone, then he plays on the rightmost cell.

Fig. 2.

Winning strategy for the first player (Black) on the $2 \times 2$ board. For each board, the black 1 indicates that Black should play there with probability one.

Fig. 3.

Winning strategy for the second player (White) on the $3 \times 2$ board. For each board, the white 1 indicates that White should play there with probability one.

On the $3 \times 2$ board, the second player (White) has a winning strategy (see Fig. 3). This strategy is surprisingly already quite “complex” for such a small board. Instead of listing all moves, a better representation is to use a tree listing all possible executions of the game (see Fig. 4).

Since the first player (Black) wins on the $2 \times 2$ board, he can also win on the $2 \times m$ boards for $m > 2$ . Similarly, since the second player (White) wins on the $3 \times 2$ board, he can also win on the $n \times 2$ board for $n > 3$ .

Fig. 4.

Winning strategy for the second player (White) on the $3 \times 2$ board. The black (left) and red (right and dashed) arrows indicate the answer of the umpire, respectively Legal/Illegal move. After an illegal move, White has to play again. After a legal move, Black is playing (not represented here). Some moves are guaranteed to succeed (i.e. no risk of being illegal), such moves correspond to boards when White already knows the position of all black stones (board with k white stones and $k + 1$ black stones for some k, e.g. the bottom-most board with 3 black stones and 2 white stones).

2.2. Winner on the

3 \times 3

board

The first player (Black) has a winning strategy on the $3 \times 3$ board and therefore on all $3 \times m$ boards for $m ⩾ 3$ . His first move is in one of the obtuse angles. Note that all other initial moves (including the central cell) are not optimal and cannot guarantee a win. A winning strategy is given in Appendix, page 244. As mentioned earlier, a similar winning strategy has already been described in Broline (1981).

Fig. 5.

Pseudocode to check if Black wins on a given board.

2.3. Winner on larger boards

Algorithm. Figure 5 gives a recursive algorithm that checks if the first player (Black) has a winning strategy on a given board.3

³
A similar algorithm can be written for White. One needs to take into account that there may be one more black stones than the number of white stones.

The input board represents Black’s knowledge during the game. Initially, the function should be called with an empty board. In recursive calls, the input board may contain black and white stones. Note that, since White is the second player, the number of white stones is always bounded by the number of black stones.

For Black to have a winning strategy, there must be at least one cell c on which playing there leads to a winning board. In the algorithm, two cases need to be distinguished depending on the presence/absence of hidden white stones; i.e. stones played by White that are still unknown to Black. In the first case, Black knows all white stones and therefore his move cannot be rejected by the umpire. In the second case, there may be an hidden white stone on the considered cell c; Black should be able to win if the move is legal (no white stone) and if the move is illegal (white stone), hence the double test in the last if.

Results. We implemented the algorithm in C++ using standard hashtables (std::unordered_map) for transposition tables and ran our computations using a single thread on a Xeon E7-4830v4. For the $4 \times 7$ board, which is the largest instance with a winner, it took around 35 minutes using up to 15 GB of RAM to solve all opening moves; our program explored approximately 358 millions configurations. For the $5 \times 7$ and $8 \times 4$ boards, the largest boards without winner, it took 8–12 minutes and 62–68 millions configurations. Larger instances could not be solved due to memory constraints.

Table 1 summarizes the results computed so far. In the table, 1 means that the first player wins, 2 means that the second player wins, 0 means that neither player can win, empty cell means that result is still unknown. Red circled values denote the values that need to be computed; other values can be deduced. Gray arrows indicate reductions between boards.

Figure 6 depicts all initial winning moves for some boards. As expected, the winning moves are a subset of winning moves for regular Hex. The winning moves for the $6 \times 3$ board are somehow surprising and led us to the discovery of Theorem 1.

Table 1

Winner on the $n \times m$ board

Fig. 6.

Initial winning moves for some small boards.

Partition and reductions. We first state two simple lemmas whose proofs are omitted. Then we propose a theorem showing a reduction from a first player strategy to a second player strategy. Lemma 1 (Partition).

On the $n \times m$ board with $n ⩽ m$ , either the first player wins or there is no guaranteed winner (only 0 or 1 above the bold line in Table 1 ).

On the $n \times m$ board with $n > m$ , either the second player wins or there is no guaranteed winner (only 0 or 2 below the bold line in Table 1 ).

Lemma 2 (Simple reductions).

If the first player wins on the $n \times m$ board, then the first player wins on any board $n \times m^{'}$ for $m^{'} > m$ (horizontal arrows in Table 1 ).

If the second player wins on the $n \times m$ board, then the second player wins on any board $n^{'} \times m$ for $n^{'} > n$ (vertical arrows in Table 1 ).

Theorem 1.
If the first player wins on the $n \times m$ board, then the second player wins on the $2 m \times n$ board.
Proof.
(sketch of) Assuming the first player has a winning strategy S on the $n \times m$ board, let us consider the $2 m \times n$ board B and design a strategy for the second player. The second player splits the board into two disjoint $m \times n$ boards; $B^{1}$ and $B^{2}$ .

In order to win, the second player follows strategy S on $B^{1}$ , as if he was playing first. There are two possible outcomes: (1) either he wins on $B^{1}$ , which means a win on B, or (2) at some point, he cannot follow the strategy S due to a blocking stone. The second case may happen since he is not the real first player; there may be a black stone on $B^{1}$ that prevents following S. When this happens, the second player switches to $B^{2}$ and start following S on $B^{2}$ .

Since the first player cannot have an advantage on both $B^{1}$ and $B^{2}$ , it guarantees that the second player will be able to win on one of these sub-boards. □
Using this theorem, one can deduce that the second player wins on the $14 \times 4$ board since the first player wins on the $4 \times 7$ board.
3. Solving DarkHex without winner

To illustrate the notions introduced in this section, we first analyze an ad-hoc variant of the game. Then we describe techniques and algorithms that can be used to solve such type of no-winner boards. Finally, we present preliminary results for the $4 \times 3$ board.

3.1. Interesting variant on the $3 \times 3$ board

Rules. Let us assume that Black is forced to play in the center for his first move and both players are aware of this forced move. Except for the first forced move; players are free to play where they want. In this case, neither player has a winning strategy that would guarantee a certain win. For each player, the best possible strategy is a mixed strategy (i.e. including probabilistic moves).

Fig. 7.

Probabilistic strategy for the first player (Black).

Fig. 8.

Probabilistic strategy for the second player (White).

Strategies. Let consider the partial strategy for Black depicted on Fig. 7. It is partial in the sense that not all reachable boards are considered. If the game reaches a board not listed in the strategy, then Black plays randomly or resigns (it does not matter; he cannot win anymore if White plays correctly). Note that in the first board of Fig. 7, there are two possible moves; each of them should be played with probability 0.5.

Similarly, we consider the partial strategy for White depicted on Fig. 8. Again, if the game reaches a board not listed in the strategy, then White resigns.

Outcome. Assuming that Black and White play respectively the strategies of Fig. 7 and 8, then each player wins with probability 0.5. This can easily be checked by playing the four possible games (two choices for each player).

For both players, 0.5 is the best winning probability they can achieve. This pair of strategies corresponds to one4

⁴

There are other strategies leading to a NE, but the outcome is always the same: each player wins with probability 0.5.

of the Nash equilibrium of this game. It is possible to prove that this pair of strategies is indeed a NE in two steps: (1) compute the best (deterministic) strategy for White assuming that Black plays according to Fig. 7 and check that White cannot win more than half of the games, and (2) compute the best (deterministic) strategy for Black assuming that White plays according to Fig. 8 and check that Black cannot win more than half of the games.

Observation. There is no good pure (i.e. deterministic) strategy for any of the two players. If Black (resp. White) plays a pure strategy, White (resp. Black) can counter it and wins. Optimal play requires to follow mixed strategies.

3.2. Computing optimal strategies and Nash equilibrium

One way of computing exact Nash equilibrium is to consider all pure (i.e. deterministic) strategies for each player, then compute the payoff matrix (here only win/loss values), and finally solve a linear system to obtain the NE (as in Bonnet and Viennot, 2016, 2017).

Unfortunately, this approach is far from being practical for DarkHex. There are far too many strategies for each player. For example, for the $4 \times 3$ board, there are roughly $1.506 \times 10^{113}$ strategies for Black! Even if this number can be reduced,5

⁵
This can be reduced by considering symmetries and stopping strategies when there is a winner. The exact number of strategies for P1 is: 150 566 311 779 241 374 060 368 185 395 045 821 314 548 426 870 441 971 814 912 440 364 364 139 719 859 109 888 000 000 000 000 000 000 000 000 000 000. This is much larger than the number of strategies for regular Hex for the same board: $479 001 600 = 12!$ .

it is really impossible to compute the whole payoff matrix. Therefore, we need to use a different approach.

Guessing optimal strategies. For a given board, let us denote $p_{1}^{*}$ and $p_{2}^{*}$ the winning probabilities of Player 1 and Player 2 at the equilibrium. The probabilities exist, satisfy the equality $p_{1}^{*} + p_{2}^{*} = 1$ , but are unknown.

Let us assume that we can guess a pair of optimal strategies. It is then possible to check if these strategies are indeed optimal:

Considering $S_{1}$ a strategy for Player 1, it is possible to compute Player 2’s best response to $S_{1}$ : it is a (deterministic) strategy $S_{2}$ that maximizes the winning probability of Player 2 when Player 1 plays $S_{1}$ . Let $p_{1}$ be the winning probability of Player 1 when playing $S_{1}$ vs. $S_{2}$ . Then $p_{1}$ is a lower bound for $p_{1}^{*}$ : $p_{1} ⩽ p_{1}^{*}$ .

Conversely, let us fixed a strategy $S_{2}^{'}$ for Player 2. It is possible to compute Player 1’s best response to $S_{2}^{'}$ : it is a (deterministic) strategy $S_{1}^{'}$ that maximizes the winning probability of Player 1 when Player 2 plays $S_{2}^{'}$ . Let $p_{1}^{'}$ be the winning probability of Player 1 when playing $S_{1}^{'}$ vs. $S_{2}^{'}$ . Then $p_{1}^{'}$ is an upper bound for $p_{1}^{*}$ : $p_{1}^{*} ⩽ p_{1}^{'}$ .

If we can guess optimal strategies $S_{1}$ and $S_{2}^{'}$ , then the lower and upper bounds match: $p_{1} = p_{1}^{*} = p_{1}^{'}$ . In this case, it means that we found the optimal winning probability, and $(S_{1}, S_{2}^{'})$ is a Nash equilibrium.

Iterative guessing. Unfortunately, it is difficult to guess optimal strategies for non-trivial boards. However, it is possible to obtain successive approximations of optimal strategies following the iterative method described in Robinson (1951).

Informally, given a non-optimal pair $(S_{1}, S_{2})$ of strategies, it is be possible to use the best responses to $S_{1}$ (resp. $S_{2}$ ) to improve the strategy $S_{2}$ (resp. $S_{1}$ ).

3.3. DarkHex on the

4 \times 3

board

According to Table 1, the $4 \times 3$ board is the smallest instance for which no player can win. It is thus natural to investigate this board in more details. More specifically we are interested in the two following questions:

What is the value of the Nash equilibrium (optimal winning probabilities)?

What are the optimal strategies of both players?

Using our current implementation of the iterative method, we obtained the following bounds for the optimal winning probabilities:

\begin{matrix} 0.112 < p_{1}^{*} < 0.268 and 0.732 < p_{2}^{*} < 0.888 \end{matrix}

Given an improved implementation, additional running time, and/or more computational power, it is certainly possible to obtain better bounds. However, using the iterative method, it is unlikely that the execution will converge exactly to the Nash equilibrium. Indeed, Such approach usually lead to an approximate Nash equilibrium. Hopefully, it may be possible to “manually” guess the exact optimal strategies given the best approximations obtained.

4. Conclusions

This paper gives a first shot at the analysis of DarkHex. This is far from a complete study and there are still many problems to solve.

Open questions. In addition to solving more boards, there are some theoretical questions that remain open and are worth investigating:

For a given n, it seems natural to expect that there exists some value $m (n)$ such that the first player wins on any board $n \times m$ for $m ⩾ m (n)$ . Said differently, each row of Table 1 contains a finite number of 2 and 0, and then an infinite number of 1. Unfortunately, we could not prove formally this intuitive conjecture.

Considering the $n \times m_{1}$ and $n \times m_{2}$ boards $B_{1}$ and $B_{2}$ with $m_{1} < m_{2}$ , it seems natural to expect that the optimal winning probability of the first player are higher on $B_{2}$ than $B_{1}$ . Again, we could not prove formally this conjecture.

For boards without winner, it is yet unclear what would be the most efficient technique to compute optimal strategies, or at least some approximations of them. We think that it should be the main direction of focus for future researches related to DarkHex. A reasonable, but difficult, short-term objective would be to solve the

4 \times 3

and

4 \times 4

boards.

Footnotes

Acknowledgements

We would like to particularly thank one of the anonymous reviewers for helpful comments, and more specifically for the details about the history of DarkHex. The Introduction has been rewritten based on his or her review.

Winning strategy on the 3 × 3 board

References

Bonnet, F. & Viennot, S. (2016). Nash equilibrium in mastermind. In Proceedings of the 9th International Conference on Computers and Games (pp. 115–128).

Bonnet, F. & Viennot, S. (2017). Toward solving “EinStein würfelt nicht!”. In Proceedings of the 15th International Conference on Advances in Computer Games (pp. 13–25). doi:10.1007/978-3-319-71649-7_2.

Broline, D. (1981). Kriegspiel Hex: Solution 1084. Mathematics Magazine, 54(2), 84–87. doi:10.1080/0025570X.1981.11976904.

Hein, P. (1942). Vil de laere Polygon? Politiken.

Nasar, S. (1998). A Beautiful Mind: A Biography of John Forbes Nash, Jr. Simon and Schuster.

Nash, J.F. (1950). Non-cooperative games. PhD thesis, Princeton University.

Pawlewicz, J. & Hayward, R.B. (2013). Scalable parallel DFPN search. In Proceedings of the 8th International Conference on Computers and Games (pp. 138–150).

Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54, 296–301. doi:10.2307/1969530.

Yang, J., Liao, S. & Pawlak, M. (2002). New winning and losing positions for 7 × 7 Hex. In Proceedings of the 3rd International Conference on Computers and Games (pp. 230–248).