[Math] Modify the rules of Gomoku (Five-in-a-row) or Connect Four type games to enforce the fairness among players

card-gamescombinatorial-game-theoryreference-request

One colleague and me were discussing this problem during lunch today, and I did a little bit digging for several hours after returning to my office.

Fact: For an $(m,n,k)$-game, there does not exist a strategy that assures that the second player will win. For example, in Five-in-a-row, first player wins with perfect play.

Now our question is: How to modify the rules to make the game fair for both players?

I googled a bit more, found an MSE question that addresses the fairness of this kind of games.

I think the fairness in that question can be strenghthen by the following definition: A game is fair if and only if that two players play with perfect strategy, the game will always be a draw. This is fair in that this game favors player with less mistakes. For example, Tic-tac-toe is fair.

Several proposals to modify the rules to enforce the fairness:

  1. Impose more restrictions on the player who plays first. For example, Five-in-a-row bans black to play "three and three", "four and four", and "overlines".

  2. Change the $(m,n,k)$-game to an $(m,n,k,p,q)$-game: $k$-in-a-row on an $(m\times n)$-board, first player put $p$ stones on board, in subsequent moves, players put $q$ stones on board. For example, [Connect 6].

  3. Go to higher dimension. For example, Five-in-a-row played in a $19\times 19\times 19$ "board".

I am no expert in combinatorial game theory or computational complexity in board games, but it is always nice to learn some new things in summer time. My question is: Any papers or treatises dealing the fairness of this kind of games? or more specifically, any proof of the fairness using above three modifications of rules? especially, for Five-in-a-row, do those additional rules make the game fair?

Any analysis of fairness on simpler cases like Connect 4 is welcome too.

Lastly just out of curiousity, as an avid Go player myself, I wonder is there any mathematical analysis on addressing the fairness using komi in the Go game? Or Go is just too complex to analyze…

Best Answer

Here's one option of a type you didn't suggest.

Take any symmetric game. Modify the game as follows: After the first player's first move, give the second player the option to continue the game as usual, or to switch places, taking the first player's position and giving the (former) first player the next move as second player.

Assuming that ties are possible, best play on both sides must produce a tie. The first player will not make a first move that guarantees him a win, since if he did, the second player would just switch places and take the winning position. And nor will the first player hand the second player a win by making a bad first move. Best play for the first player is to play into a position that he can tie but not win, and then play for the tie. If the second player switches with him, he can still play for the tie.

Related Question