Square++: Making a connection game win-lose complementary and playing-fair

A connection game called Square++ is designed, which is played by almost similar rules to that of Hex but on a square board. Square++ belongs to the category of random-turn games, which is little explored. As the two players in Square++ act on different roles, we apply a biased coin to make the game playing fair. That is, one player has p chance to go, the other player has (1 − p) chance to go.The challenging issue of this study is to find the exact value of p for a given size L of the board, such that both players have an equal chance to win by the best strategy. This p value is called fair probability p0.5(L). We first prove that the process of the game is equivalent to randomly filling the board by tossing the coin. We then design a dynamic programming algorithm to get high-accuracy values of p0.5(L) for L ⩽ 22, and estimate p0.5(L) for L > 22 by numerical methods. Finally, we discuss the implementation issues of Square++, and introduce some of its variants.

► A new connection game called Square++ is designed, which is win-lose playing complementary and playing-fair.
► Basic and advanced properties of Square++ are studied and proved.
► Two efficient methods are developed to accurately compute the fair probability of the game.
► Implementation issues of Square++ are discussed and some of its variants are introduced.