Bene Factum

I’ve been playing Sid Sackson’s seminal classic Can’t Stop the last few days, in its new iPad form. Although I’d (shamefully) never played it until now, simply hearing it described was enough for it to serve as partial inspiration for my own Picnic Blitz, as some reviewers have noticed.

Although I found the AI a challenge for my first few attempts, I learned quickly and, as is often the case with board game AIs, was soon able to defeat it a large majority of the time in one-on-one games. Its biggest weakness, I’ve observed, is that it does not to give enough (or perhaps any, it is hard to tell) consideration to the likelihood that you will be able to win on your next move. It will make an otherwise-sensible preparatory move to improve its odds of completing a column on its next move, without realizing that it isn’t likely to get a next move, and should instead shoot for a win immediately, even if the odds of success are small.

The choice between attempting to win on one’s current move or instead building up power to try to win on a subsequent move is a common dilemma in games; it’s embodied in a very pure form in Can’t Stop (and other press-your-luck dice games such as Nada), but it occurs frequently in other games in a more complex, harder-to-quantify way; deciding when to stop building units and launch a final assault in a military game, or whether to call an opponent’s all-in in poker vs. folding and trying to find a better spot, or when to change gears from building power to going all-out for victory points in many Euro games.

The case of Can’t Stop is particularly easy to approach mathematically, at least for a first-order solution.

Let’s consider an endgame situation in a two-player game of Can’t Stop, in which the two players have chances of x and y respectively of winning on any given move, prior to their first roll, assuming they commit to continue rolling until they either win the game or fail in a roll and lose their turn. We can write the first player’s odds of winning on his turn in an iterative fashion as:

w(x,y) = x + (1-x)(1-y)w(x,y)

In other words, the player’s chance of winning are his chance of winning immediately, plus his total odds of winning if his next turn comes around and no one has won yet. Since nothing has changed in that case, those total odds of winning are the same as the total odds now.

Rearranging this equation, we can isolate the function w(x,y) and therefore write it non-iteratively:

w(x,y) = x / (x + y – xy)

On the second player’s turn, it’s clear that the first player’s odds of winning, which we will call w'(x,y), are simply multiplied by a factor of (1 – y), since the second player failing to win immediately reverts us to the first situation. I.e.

w'(x,y) = (1 – y)w(x,y)

If a player, therefore, has an opportunity to pass up a shot at the win in return for multiplying his odds on subsequent moves by a factor of A, we are comparing his basic chance of winning w(x,y) to his alternative chances w'(Ax,y). In order for him to choose to make his preparatory move, then, these latter odds must be greater:

w'(Ax,y) > w(x,y), or

(1-y)Ax / (Ax + y + Axy) > x / (x + y + xy)

Cancelling out the factors of x on both sides and multiplying the denominators across yields:

A(1-y)(x + y + xy) > (Ax + y + Axy)

Which, after some multiplication and simplification finally gives us:

A > 1 / (1 – x – y + xy)

Thus, knowing our own and our opponent’s chances of winning on a given move, we can figure out the minimum factor by which we’d need to improve our odds in order to be willing to allow the opponent to take the first crack at victory.

Example application: I believe my opponent has about a 25% chance of winning on his next move. I also think that I can approximately double my own chances of winning on my next move if I make a preparatory move now. How great must my chances of immediate victory be in order for me to take the shot now, rather than improving my position for next turn?

In words, if I have better than 1/3 odds of winning immediately, I should take my shot now. Any worse, and I should make my preparations and double my chances of winning on a later turn. For many players, this is likely counter-intuitive; the risk averse will often insist on a greater than 50% chance of winning before they take their shot, which is far from correct.

Now, there are a couple of interesting things about this equation:

First, it’s symmetric in x and y. It doesn’t matter whether we have a 20% chance of winning and our opponent has a 5% chance, or we have the 5% chance and our opponent has 20%; either way, the factor by which our odds would have to improve to make the preparatory move are the same. It’s important to remember, however, that A is a factor, not a straight percentage… for the 20%/5% situation, A = 1.27, so the player with 20% needs a minimum improvement of 5.4% (i.e. a 25.4% chance of winning on a given move after making the preparatory move), while the player with 5% only needs an improvement of 1.35%.

Second, although it appears to apply only to the two-player situation, it can in fact be easily adjusted to a multiplayer game, provided we don’t care which opponent wins if it isn’t us. Simply replace y by the probability that any opponent wins, i.e. y = 1 – (1-y1)(1-y2)…(1-yn) where y1…yn are the various opponents’ individual chances of winning on a given turn.

Third, it’s easy to see that for x >= 0.5, then there is no value for y which would make a preparatory move desirable; A would exceed 2, which given that x >= 0.5, would mean we would have to improve to x > 1, i.e. a greater-than-100%-chance of winning, which is impossible. This draws our attention to one of the limitations of the math, however; I did say this is only a first-order solution, by which I mean that it neglects the opponent’s potential for improvement.

Say, for instance, I have a 50% chance of winning on the current turn, while my opponent has only a 1% chance. If my opponent cannot improve his chances, then by shooting for an immediate win, my odds of victory are (0.5) / (1 – 0.5*0.99) = 99.01%, which are still slightly better than my 99% odds if I allow my opponent his 1% long-shot first in return for even a 100% chance of winning if he misses.

If, however, both my opponent and I have available to us a move that would increase our odds to 100%, then I have only a 66.7% chance of winning by going for it immediately (two 50/50 shots before he gets his second turn), whereas if I improve myself first, he is forced to take his 1% shot rather than doing likewise, giving me the aforementioned 99% chance of victory.

Still, barring extreme examples like the opponent who can improve from 1% to 100% odds with a single preparatory move, this first-order solution can still be very usefully applied to gain ballpark estimates for real, in-game situations. Moreover, the result is exact as long as the opponent’s potential for improvement (as a factor of their current chances) is similar to one’s own; due to the symmetry of the equation, if the players’ respective odds are such that one player should not be delaying his attempts to win any further, then the same likely goes for his opponent.