Games like chess are already decided; they just haven't been computed

Here's a fact that sounds wrong: chess is already decided. If both sides play perfectly, it is a forced win for White, a forced win for Black, or a draw, and which one was fixed the moment the rules were written. That struck me as absurd at first. A game feels open, because nobody can see where it ends.

The trick is to start from the end instead of the beginning. Give every finished game a score: +1 if White wins, −1 if Black wins, 0 for a draw. White wants the score high, and Black wants it low.

Now step back one move. Whoever is to move just picks the best result for their side, so that position gets a score too. Step back again and do the same, all the way to the first move. That's backward induction, and the score each position ends up with is its minimax value. Try it on a small game:

Backward induction, step by stepOne game tree, three moves deep, filled in one step at a time. At the start only the eight finished games have scores: -1, +1, 0, -1, -1, -1, +1, 0. Step 1 fills White's last move with the larger of each pair: +1, 0, -1, +1. Step 2 fills Black's move with the smaller: 0 and -1. Step 3 fills White's first move with the larger: 0, a draw. The final step marks the line of play: White left, Black right, then the draw.Startthe rules score each finished game-1+1?0-1??-1-1?+10???

+1 White wins · 0 draw · −1 Black wins

A game three moves deep: White, then Black, then White. Try to predict each layer before you click.

The score at the top is how the game ends with perfect play. Notice what the climb never needed: skill, luck or cleverness. It only needed the game to be finite, so the climb reaches the top; to have no dice, so each position gets one score rather than odds; and to hide nothing, so each player knows where they are. Every such game is decided before the first move. That's Zermelo's theorem [1].

Game theorists call these games determined, and solved once someone actually does the computation. Checkers, with about 5×10205 \times 10^{20} positions, was solved in 2007: with perfect play, it's a draw [2]. Chess has on the order of 104310^{43} positions by Claude Shannon's classic estimate [3], and Go, determined too under the superko rules that keep it finite, about 2×101702 \times 10^{170} [4]. Both are far too large to fill in, so their outcomes are determined but unknown. The rules settle it; only computation stands between us and the answer.

References

  1. Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels
    Zermelo, E., 1913. Proceedings of the Fifth International Congress of Mathematicians, Vol 2, pp. 501–504. Cambridge University Press.

  2. Checkers Is Solved
    Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P. and Sutphen, S., 2007. Science, Vol 317(5844), pp. 1518–1522. DOI: 10.1126/science.1144079

  3. Programming a Computer for Playing Chess
    Shannon, C. E., 1950. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, Vol 41(314), pp. 256–275. DOI: 10.1080/14786445008521796

  4. The Number of Legal Go Positions
    Tromp, J., 2016. Computers and Games (CG 2016), pp. 183–190. Springer. DOI: 10.1007/978-3-319-50935-8_17