Winning strategies in DarkHex: Hex with hidden stones

Article type: Research Article

Authors: Bonnet, François^{; *; **}

Affiliations: School of Computing, Tokyo Institute of Technology, Tokyo, Japan

Correspondence: [**] Corresponding author. E-mail: bonnet@c.titech.ac.jp.

Note: [*] E-mail: bonnet@c.titech.ac.jp.

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×3 board.

Keywords: Hex, incomplete information, kriegspiel, Nash equilibrium, pure/mixed strategy

DOI: 10.3233/ICG-180057

Journal: ICGA Journal, vol. 40, no. 3, pp. 234-245, 2018