3

Assume that we have weakly solved chess, in the sense that we have an algorithm that when used, allows us to force a win if possible, and if that is not possible, force a draw. Define a ply as optimal as one made in accordance with such an algorithm, and further define a game as optimal if every ply made by both players is optimal.

How many such games are there?

6
  • Maybe better to ask for percentage of games which are optimal?
    – Laska
    Mar 11 at 10:29
  • @Laska that would be a horrible question because of how little of the games possible are optimal. For every given position there's 1 optimal move (maybe 2 at times). The moment a non-optimal move is played the game is no longer a perfect game. This means out of the ~10^120 games maybe only 1,000 games would be optimal or around that range. That would give a percentage of no more than 1^-100. Such a small number that we can't fathom how small it is, making it useless.
    – ALK003
    Mar 16 at 2:24
  • @ALK003 - I see your point. This is always going to be an estimate. Maybe can ask for the average number of optimal moves in an optimal position? And whether mate has been reached?
    – Laska
    Mar 16 at 5:44
  • Can we solve this problem completely for the set of positions with at most 7 pieces?
    – Laska
    Mar 16 at 5:45
  • 1
    @Laska Yes. 7 man endgames are completely solved, so if you had access to a tablebase figuring this out would be 'trivial' in the sense that you just have count. Of course, this actually entails lots of computation, since you still have to, for each of ~4x10^14 positions, generate all legal moves as well as look up the optimal ones.
    – Nathan
    Mar 17 at 17:56
5

TL;DR

The answer is that it depends on whether we solve chess for White, Black, or a Draw. If one of the first two, probably very, very many. If instead chess is drawn, then we don't know, and it's not clear how we would go about figuring this out without actually solving chess in the first place.

Pedantic setup

First, the general strategy is the same as the one pursued by Shannon's number. Estimate the number of optimal plies available in a given position, O, and estimate the number of unforced plies in an optimal game of chess, p. The number of optimal games of chess is given by the expression O^p.

Define a winning ply as a ply that either (i) wins the game, or (ii) leads to a board state in which, no matter their opponent's reply, a winning ply exists. Similarly define a drawing ply. Finally, a losing ply is defined as a ply that, if made, leads to a board state in which her opponent has at least one winning ply. Note that because chess lasts a finite number of moves, these options are exhaustive. If all plies from a position are losing, then the player to move is in zugzwang.

Weakly solving chess entails being able to show that there exists either a winning or drawing ply from the starting position, or conversely that White is in zugzwang. Solving chess entails knowing that some particular ply is winning or drawing, or some particular reply from Black is winning.

Finally, note the the definition of optimal says nothing about what to do if a position is losing. The losing player is free to do whatever they wish, because within the context of optimal play, all plies are equally bad.

If White is winning

Suppose that we solve chess for White. Since White has access to a winning ply, all of Black's 20 legal replies are losing. Thus, there are at least 20 games of optimal chess. This argument applies recursively to each resulting board state, and the number of optimal games grows quite quickly. Even if White has access to only one winning ply on each of her turns, Black always has access to all legal plies from the position. We could stipulate that optimal play in a losing position is to resign, in which case there is either 1 optimal game of chess — the winning ply from the starting position — or 0, because no one ever agrees to a game. For comparison, think about whether you would agree to a game of Tic-tac-toe.

All that remains is to estimate the length of an optimal game. Strictly speaking, knowing this number requires solving chess in the first place. However, it seems quite unlikely to me that the average optimal game is short. Arguments to this effect are difficult, however. As pointed out by @wimi in the comments, if Chess is solved for White than the very short game — 1. e4 e5 2. Qh5 Ke2 2. Qe4# — is an optimal game.

For the purposes of this answer, suppose that an optimal game lasts 30 moves. Derive a lower bound by assuming that White only ever has one winning ply. Effectively, her turns don't contribute number of optimal games, since she only every has one option. As argued before, Black has access to all legal plies in any position. The number of legal plies in a position is estimated to be about 30. Thus, a conservative lower bound on the number of optimal games is 30^(30) = 2x10^44. Different estimates of the length of an optimal game will lead to correspondingly different answers.

It gets a tricky if we place further restrictions on optimal play. For instance, you could stipulate that if one is in a losing position, the optimal ply is the one that extends the game the longest. This raises the exponent of the estimate, since games last longer, but it also knocks down the number of optimal moves available in a losing position, since they won't all extend the game the same amount. The interaction between these two is unpredictable.

If White is losing

Exactly the same situation as before, but the positions reversed. This time, no matter which of the 20 opening moves she makes, White is guaranteed to lose.

If White is drawing

Suppose instead that chess is drawn. Based on the rate of draws seen at high level computer play, I deem this the most likely. This means that there exists at least one ply for White for which there exists at least one drawing reply, and all other plies are losing. How many drawing plies are there in the opening position? Strictly speaking, we don't know. We don't even know if there is one, and figuring this out would be a major advancement in our knowledge of the game.

For instance, it could be the case that there is only one drawing ply from the starting position, and all others are losing. Further, this could be true of all resulting positions, in which case there is 1 optimal game of chess. I think this is unlikely, but strictly speaking it is possible.

Instead, it could be the case that all of White's opening plies are drawing, and all of Black's replies are as well. Then there are probably many games of optimal chess. Of course, this has to stop being the case at some point, as evidenced by the existence of both the Scholar's Mate and the Fool's Mate, so a more precise estimate is difficult.

5
  • 2
    Very nice answer, but: why do you say "it seems quite unlikely to me that optimal games are short"? If chess is solved as a win for White, and if 1.e4 is a winning move, then the Scholar's mate is an optimal game with the definition given in the question. You yourself say that "within the context of optimal play, all plies [of the losing player] are equally bad."
    – wimi
    Mar 11 at 19:02
  • That is a wonderful observation, and another great example of the weird consequences of assuming perfect play. You've convinced me that my thinking on that point is wrong. For now, I'll edit my answer to reflect that, and I'll try to come up with something more informative on that point.
    – Nathan
    Mar 12 at 4:05
  • Yes, perfect play is weird. I guess that if chess is a win for White, then arguably the optimal game is 1. (any winning move) (resigns), as it minimizes the time wasted in reaching a result that is already known ;). But of course, if Black tries to maximize the length of the game (in the hope that White blunders), the analysis becomes more interesting.
    – wimi
    Mar 12 at 8:13
  • Scholar's Mate is not the shortest possible mate; that's Fool's Mate. There's also a three-move mate for white in the Wayward Queen Attack. Mar 13 at 2:33
  • The claim is "If chess is solved for White..." in which case Fool's Mate is not an optimal game. However, the Wayward Queen Attack is both a game in which White wins and which is shorter than the Scholar's Mate. I've updated my answer to reflect that.
    – Nathan
    Mar 13 at 2:46
3

Based on Zermelo's theorem:

There is at least one optimal game.

Let's see why. Zermelo's theorem applies to finite two-person games of perfect information in which the players move alternately and there is no influence of chance in choosing your moves. Chess is a game of this type:

  • There are two players.
  • There is a finite (albeit very large) number of legal positions.
  • All information relative to the game is on the board.
  • There is no throwing of dice, you can decide your next legal move.

Then, for all such games, Zermelo showed that with optimal play one of these results is true:

  • The first player can force a win; or
  • The first player can force a draw; or
  • The second player can force a win.

Since one and only one of these conditions is true, there is at least one optimal game.

PS: This article on Zermelo's theorem may also be of interest.

1
  • 1
    Very relevant reference, and provides clear justification for one of the claims that I made in my answer. Thank you!
    – Nathan
    Mar 13 at 23:22

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.