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

  • $\begingroup$ Volume 3 of Winning Ways has a fairly extensive discussion of $n$-in-a-row games. Have you seen that yet? $\endgroup$
    – MJD
    May 24 '13 at 21:13
  • $\begingroup$ @MJD Thanks for the responses, unfortunately the math library has closed for today, I will check that book out for a look tomorrow! $\endgroup$
    – Shuhao Cao
    May 24 '13 at 21:19
  • $\begingroup$ I would have said "make your 'ko' question a separate question" but I think the answer will probably be something soft like "the study of Go in combinatorial game theory focuses on late endgames, but we have no idea what score a perfectly played game would have except to guess based on pro games. Also, fair ko for groups of humans could be different than fair ko for perfect players because all the humans are using significantly bad strategy for one color or something." $\endgroup$
    – Mark S.
    May 25 '13 at 16:05

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.

  • 2
    $\begingroup$ +1 this is called the Pie Rule. It's the usual solution, and is actually pretty common in real-life board games (eg. Hex and TwixT have this rule; the wiki article also mentions Go, though this is not a normal rule for that game). $\endgroup$ May 24 '13 at 22:32
  • $\begingroup$ It works badly in asymmetric games like chess, however, because P1 can specialize in a weird opening like b3 that P2 doesn't know how to play as either White or Black. $\endgroup$
    – MJD
    May 24 '13 at 22:40
  • 1
    $\begingroup$ That could be true of any of the games mentioned; just because they're symmetric doesn't mean they don't have different openings. $\endgroup$ May 24 '13 at 22:41
  • $\begingroup$ It is less true. $\endgroup$
    – MJD
    May 24 '13 at 22:50

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.

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.

  • 1
    $\begingroup$ Until you posted this, I was able to resist mentioning the idea of having the two players play with a chess clock, and letting each player secretly bid, in seconds, for the privilege of going first. So if player A bids 90 seconds and player B bids 91, then player B goes first, but with 91 seconds removed from her clock before play begins. One must adopt some rule beforehand for deciding how much is actually paid by the winning player—if A bids 30s and B bids 90s, then B goes first, paying some $n$ between 30 and 90 seconds. $\endgroup$
    – MJD
    May 24 '13 at 21:30
  • 3
    $\begingroup$ @MJD This is actually done for the final tiebreak of the US Chess Championship (as has been necessary the last two years). Both players bid for how little time on their clock they will accept for the privilege of playing Black with draw odds (a draw on the board counts as a win for Black) against a White player who has 45 minutes. This year the two players bid 20:00 and 19:45. (Black lost, in part because White had an effective stalling strategy.) $\endgroup$
    – dfan
    May 25 '13 at 0:40
  • $\begingroup$ I had no idea that this was actually done. Thanks! $\endgroup$
    – MJD
    May 25 '13 at 1:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.