Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

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).

Winning strategies in DarkHex: Hex with hidden stones

Abstract

Keywords

Get full access to this article

References