1

I understand that chess is pretty complex regarding the game tree complexity (Shannon number) or number of possible positions. If we were trying to solve chess (whuch I know is impossible for practical reasons), however we might not be interested in all positions. For instance I remember reading that for the 7 men tablebase they excluded positions where one side had a bare king.

Is there an estimate for the complexity of chess if clearly won positions are excluded?

2

The problem every time you have such enormous number of configurations, is that any "simple-minded" description of configurations to discard will remove an insignificant portion of the total.

In the case at hand, there are trillions upon trillions of positions with a bare king (for instance), but they represent a small fraction of a percent of all positions.

You still have to deal with the bulk of configurations that make chess hard, so the difficulty of the original problem is still there.

  • Indeed it still remains rather intangible. The only work I've seen touching on such questions is sequencing chess on arXiv: arxiv.org/abs/1609.04648 – Phonon Dec 28 '17 at 15:28
1

It's hard to see if a position is clearly won or not, especially when just counting material:

[FEN "3N2rk/4K1bb/4nn2/8/8/8/7q/qqqqqqqq w - - 0 1"]

1. Nf7#

or the various positions with pawn chains all over the board, which can't be broken by rooks or a bishop of the wrong color.

So I doubt exclusion of clearly won positions is going to make much of a difference in terms of complexity; it's even likely to make it more complex.

  • Agreed. I am not looking for an exact number, but rather an estimate. – user1583209 Dec 26 '17 at 9:31
1

I'm guessing that by complexity, you mean an estimate for the number of legal positions that aren't 'clearly' lost by some measure (otherwise the answer is exponential, despite the addition of your constraint), as if to build a tablebase that can play through non-trivially lost/won positions (ignoring the technicalities of the missing tablebase problem that would arise...).

One estimate of the number of 'sensible' chess games; 3^(40*2) ~ 10^40 seems reasonable; however, this answer doesn't work in this setting, because of the way your question is phrased.

I claim that our hypothetical 32-man, 'non-trivial' tablebase is composed mostly of positions arising from games that would have otherwise been drawn. I argue as follows: 60% of grandmaster games are draws; let's say (an arbitrary guess) that a third of this are agreed draws i.e. 20% of games at move 30. Another arbitrary assumption: let's say material is equal at these positions at move 30, 3 pawns and 3 pieces having been exchanged. Each side has to trade off 9 more pawns/pieces to get to bare kings. Assuming an exchange every 4 or 5 moves, again with 3 'sensible' moves in each position, the number of games concluding in this manner would be approximately 3^(30*2) * 0.2 * 3(40*2) = 0.2 * 3^160 ~ 10^80, which dwarfs the estimated number of 'sensible' chess games.

This highlights the significance of exponential growth: the percentage of agreed draws doesn't really matter (as long as it's not zero), and neither does 'clearly' won/lost positions in the setting of a '32-man' tablebase.

My main point is, a fairly reasonable estimate to your required answer would still be of the form n^m where n is the average number of 'sensible' moves in a position, and m is the expected number of half-moves to get down to bare kings.

Also, to be precise, the number of positions (double/triple/multiple-counting transpositions) is closer to m*(n^m).

Now of course, if you include trivially drawn positions, things become really tricky, but we have to draw the line somewhere...

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.