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

Question

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

Answer 1

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.

Answer 2

Going to higher dimension will not help; it makes the problem worse. The Hales-Jewett theorem implies that for any fixed $p$ and $n$, the first player can win the $p$-in-a-row game on the $n^d$ board for all sufficiently large $d$. So adding dimensions makes these games less fair, not more fair.

For example:

• The first player obviously wins 2-in-a-row on a $2^n$ board for $n>1$, but when $n=1$ he cannot do better than a tie.
• Standard $3\times 3$ tic-tac-toe is an easy tie. The first player easily wins tic-tac-toe on a $3^n$ board for $n \gt 2$.
• The 4-in-a-row game on a 4×4 board is tied, by an easy strategy. The 4-in-a-row game on a 4×4×4 board is a first-player win, but the strategy is complicated enough to be a good game anyway. The 4-in-a-row game on a $4^n$ board for $n\gt 3$ is an easy first-player win with straightforward play.

Answer 3

In response to your last question, Elwyn Berlekamp has introduced the concept of Coupon Go (video lecture - the intro stops around 16:15 and the interesting discussion starts there). In Coupon Go, in addition to the board there is a stack of cards ranging from 20 (on top) to 0.5 (on the bottom). When it is your turn, you are allowed to take and keep the top card (worth that many points) rather than making a move on the board. Among other things, this effectively allows the two players to bid on the komi value instead of having it chosen for them.

Answer 4

One other option is to modify that game so that there are two stages:

• Randomly determine who is the first player
• Play the game as usual

This skirts the question.