idea to estimate the percentage of drawn positions in chess

[towforce]

To estimate the percentage of drawn positions from random games, you must:

1. For the first 5-10 moves, check that positions have not been duplicated in another game

2. Work out what engine position evaluation indicates a drawn position (approximately -1 < eval < 1)

3. Have a top engine evaluate all the positions in the sample, scoring them as either won or drawn

Of all the methods discussed, this would actually be the easiest to do by a long way.

However, you'd be relying on the engine being wrong in the "win" direction as often as it is wrong in the "draw" direction. Two things would minimise this error:

1. Test the truth of this assumption against a database of strong games

2. Get the win/lose dividing eval as accurate as you can (in the database of high quality games, the number of winds this eval predicted would be a draw is equal to the number of draws this eval predicted to be a win): that way, the errors in either direction will balance each other out.

[chesskobra]

1) Generate a lot of legal random positions (e.g. by generating random games)

Using random games to generate random positions is problematic because you won't get a sample from uniform distribution on all legal positions. A lot of positions will be very deep and won't have a realistic chance of arising in a random game starting from the standard position. I think how to sample uniformly from all legal positions is the main problem. Maybe the work that showed the estimate of 10^44 has ideas about how to sample uniformly.

[petero2]

1) Generate a lot of legal random positions (e.g. by generating random games)

Using random games to generate random positions is problematic because you won't get a sample from uniform distribution on all legal positions. A lot of positions will be very deep and won't have a realistic chance of arising in a random game starting from the standard position. I think how to sample uniformly from all legal positions is the main problem. Maybe the work that showed the estimate of 10^44 has ideas about how to sample uniformly.

Yes, even though there is no known fully automatic way to sample uniformly, that work also produced a uniform sample of random legal positions of size 112754. You can get a list of those positions like this:

Code: Select all

$ git clone https://github.com/tromp/ChessPositionRanking.git
$ cd ChessPositionRanking/
$ cat Texel.out.????? | grep ' legal:' | wc -l
112754
$ cat Texel.out.????? | grep ' legal:' | sed -e 's/ legal:.*//' | shuf >legal_sample.fen

Note that even though the sample is uniform, it has been sorted, so if you plan to use a subset of those positions for statistical purposes, you should get a random subset, not the N first positions. That's why I added the "shuf" command in the example above.

[towforce]

Using random games to generate random positions is problematic because you won't get a sample from uniform distribution on all legal positions..

Hmmm... you could generate random positions, but then, for each position generated, you'd have to prove that it's reachable. I think someone has actually written a program to prove reachability of a given position.

However, I wouldn't go overboard on this: the thread title is only asking for an estimate.

[jefk]

fkarger wrote:
To confidently solve this you basically need a 32 men table base (otherwise: how to prove?).

Although off topic:
so to (weakly) solve checkers you would need a 24 men table base ???
Otherwise how to prove ????
Well, njet, sir,
google Schaeffer and checkers and have a look.

btw there exists an infinite number of positive integers.
There also exists an infinite number of negative integers.
Do you have to count them all to understand there there is a balance,
there are -arguably (for the math boys) just as many positive numbers
as there are negative numbers. Do you need a 'proof' for that ?
In chess there also is a balance (an equilibrium, a drawing margin), but i'm
not going to elaborate on that here coz it's indeed off topic (of this thread).

For a weak solution of a game you don't have to explore all the options
but only show what the outcome is with best play (and how to play).
example:
https://news.ycombinator.com/item?id=38 ... 20position.

there's a lot of drivel written usually about 'solving' games
(and chess); not to mention some opinions in this foruml the article
below is an exception:
https://www.cs.utexas.edu/~marijn/publi ... _games.pdf
and this article (phd thesis) is a bit longer
http://fragrieu.free.fr/SearchingForSolutions.pdf

[syzygy]

I think we have to distinguish at least two meanings of "percentage of drawn positions in chess".

1) Percentage after 'normal' play from the starting position
2) Percentage after any kind of play from the starting position

It seems to me the question is asking for the percentage of all legal (and thus reachable) positions that are drawn (with best play from both sides). [Admittedly this is almost certainly not the number that Uri is really interested in.]

The way to estimate this number is to randomly pick 1000 positions (from a uniform distribution) and try to determine for each position whether it is drawn or won for white or black. Most positions will be clear wins for one of the sides. The remaining positions will need some heavy computation to get a good enough estimate of the probability that it is a draw.

[fkarger]

fkarger wrote:
To confidently solve this you basically need a 32 men table base (otherwise: how to prove?).

Although off topic:
so to (weakly) solve checkers you would need a 24 men table base ???
Otherwise how to prove ????
Well, njet, sir,
google Schaeffer and checkers and have a look.

The idea Schaeffer used is based on an endgame table base for 10 stones.
Then they use standard tree search and have enough table hits to solve the game.

In principle this could work in chess too but I think there is an important difference.
Chess has many closed positions where you have a slow maneuvering game for a long time
(e.g. in the KID or in the Ruy Lopez).
You could observe that on TCEC between top engines.
For this kind of position - which is not too uncommon - the search depth you need to hit
the tables is probably much too deep especially if you start the search (like Schaeffer)
from the starting position.

In checkers pieces have to move forward which provokes capturing of stones
and promotes table hits. Therefore you have no slow maneuvering in checkers.

[Michel]

The way to estimate this number is to randomly pick 1000 positions (from a uniform distribution) and try to determine for each position whether it is drawn or won for white or black. Most positions will be clear wins for one of the sides. The remaining positions will need some heavy computation to get a good enough estimate of the probability that it is a draw.

I wonder if it is possible to get a sensible estimate at all. The random positions will be exotic and scores by chess engines are likely to be very unreliable. One idea could be to use an LC0 style engine with a net trained on uniform random legal positions.

[syzygy]

The way to estimate this number is to randomly pick 1000 positions (from a uniform distribution) and try to determine for each position whether it is drawn or won for white or black. Most positions will be clear wins for one of the sides. The remaining positions will need some heavy computation to get a good enough estimate of the probability that it is a draw.

I wonder if it is possible to get a sensible estimate at all. The random positions will be exotic and scores by chess engines are likely to be very unreliable. One idea could be to use an LC0 style engine with a net trained on uniform random legal positions.

That is indeed a very valid point.

[Uri Blass]

The way to estimate this number is to randomly pick 1000 positions (from a uniform distribution) and try to determine for each position whether it is drawn or won for white or black. Most positions will be clear wins for one of the sides. The remaining positions will need some heavy computation to get a good enough estimate of the probability that it is a draw.

I wonder if it is possible to get a sensible estimate at all. The random positions will be exotic and scores by chess engines are likely to be very unreliable. One idea could be to use an LC0 style engine with a net trained on uniform random legal positions.

That is indeed a very valid point.

I think that we can get a good estimate because in most cases we probably know it is not drraw based on forced mate and there may be cases we can prove a forced draw because there is a line that the sides have to play not to lose.
first position is an easy mate verfied by chest.
1qNN4/b2rn3/2K4r/r1Q4r/3bQB1k/q1Q2qn1/N5b1/r4nQb w - - 0 1 white claim mate in 7 against itself and play Kxd7 vefirided by chest

second position is harder but slowchess see forced mate in at most 13 moves against the side to move.

FEN: K1B1q2R/Np3n1p/1rP5/1Q2b1k1/3p2nn/3NN2q/5N1r/1qr1b3 w - - 0 1

Slow64-avx2 [001]:
2/2 00:00 690 0 -21.00 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1
3/4 00:00 1k 0 -21.00 Nf2xh3+ Rh2xh3 Qb5xb1 Rb6xb1 Rh8xe8
4/6 00:00 3k 0 -21.00 Nf2xh3+ Rh2xh3 Qb5xb1 Rb6xb1 Rh8xe8 Rh3xe3 Nd3xc1 Rb1xc1
5/8 00:00 14k 0 -22.76 Nf2xh3+ Rh2xh3 Qb5xb1 Qe8xc8+ Na7xc8 Rb6xb1
5/8 00:00 27k 2,665k -21.08 Qb5xb1 Rh2xf2 Qb1xb6 Qe8xh8 Nd3xe5 d4xe3 c6xb7 Qh8xe5 b7-b8Q
6/9 00:00 69k 3,455k -20.91 Qb5xb1 Be1xf2 Qb1xb6 Qe8xh8 Nd3xe5 Nf7xe5 c6xb7 d4xe3 b7-b8Q
6/9+ 00:00 69k 3,462k -20.78 Nf2xh3+
7/9 00:00 122k 4,080k -22.72 Qb5xb1 Ng4xf2 Qb1xc1 Nf2xd3 Rh8xe8 Nd3xc1 Bc8xh3 d4xe3 c6xb7 Rh2xh3
8/11 00:00 169k 5,639k -26.32 Qb5xb1 Rc1xb1 Nf2xh3+ Rh2xh3 Rh8xe8 b7xc6 Bc8-b7 Rb6xb7 Nd3xe5 Ng4xe5 Ne3-c2
8/11+ 00:00 172k 4,290k -26.31 Nf2xh3+
8/11 00:00 181k 4,514k -25.97 Nf2xh3+ Rh2xh3 Rh8xe8 Rb6xb5 Ne3xg4 Rh3xd3 Re8-g8+ Nh4-g6 Ng4xe5 Nf7xe5 c6xb7 Rb5-b4
9/14 00:00 321k 5,355k -26.32 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Bc8-b7 Rb6xb7 Nd3xe5 Ng4xe5
10/15 00:00 546k 6,068k -27.08 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Bc8-b7 Rh3xe3 Nd3-c5 Be5-d6 Nc5-e4+ Re3xe4 Re8xe4 Rb6xb7 Na7xc6
10/15+ 00:00 593k 5,929k -27.07 Qb5xb6
11/21 00:00 1,017k 6,358k -29.04 Nf2xh3+ Rh2xh3 Rh8xe8 Rb6xb5 c6xb7 Qb1xd3 Ne3xg4 Rb5xb7 Bc8xb7 Kg5xg4 Re8-g8+ Nh4-g6 Bb7-d5 Nf7-h6
11/21+ 00:00 1,193k 6,279k -29.03 Rh8xe8
11/21 00:00 1,286k 6,431k -28.40 Rh8xe8 Rb6xb5 Ne3xg4 Be1xf2 Ng4xe5 Nf7xe5 Bc8xh3 Qb1xd3 c6xb7 Rb5xb7 Re8xe5+ Kg5-f4
12/22 00:00 2,171k 6,385k -29.56 Rh8xe8 Rb6xb5 Nf2xh3+ Rh2xh3 Nd3xe5 Nf7xe5 Re8-g8+ Nh4-g6 c6xb7 Rb5xb7 Bc8xb7 d4xe3 Bb7-d5
12/22+ 00:00 2,172k 6,387k -29.55 Nf2xh3+
13/24 00:01 6,465k 6,277k -31.68 Rh8xe8 Rb6xb5 Nf2xh3+ Rh2xh3 Re8-g8+ Nh4-g6 Bc8-f5 d4xe3 Nd3xe5 Kg5xf5 Ne5xf7 b7xc6 Na7xb5 c6xb5 Nf7-d6+ Kf5-f4
13/24+ 00:01 6,466k 6,277k -31.67 Nf2xh3+
13/24 00:01 6,496k 6,246k -30.92 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Bc8-b7 Rb6xb7 Nd3xe5 Ng4xe5 Ne3-c2 d4-d3 Nc2-a3 d3-d2
14/24 00:01 7,122k 6,303k -31.80 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Bc8-b7 Rb6xb7 Nd3xe5 Ng4xe5 Ne3-c2 d4-d3 Nc2-a3 d3-d2 Na3xb1 Rb7xb1 Re8-e7 d2-d1Q
15/30 00:02 17,532k 6,493k -36.12 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Re8-g8+ Nh4-g6 Bc8-b7 Rb6xb7 Nd3xe5 Nf7xe5 Ne3-c2 d4-d3 Nc2-b4 Rb1xb4 Na7xc6 d3-d2 Nc6xb4 Rb7xb4 Rg8xg6+ h7xg6
15/30+ 00:02 17,613k 6,499k -36.11 Rh8xe8
15/30 00:03 21,110k 6,397k -35.40 Rh8xe8 Rb6xb5 Nf2-e4+ Kg5-h6 Ne4-c3 d4xc3 Ne3xg4+ Qh3xg4 Bc8xg4 Qb1xd3 Re8-e6+ Kh6-g7 Re6xe5 Nf7xe5 c6-c7 Rh2-a2 c7-c8Q Ra2xa7+ Ka8xa7 Ne5-c6+ Qc8xc6 Be1-f2+ Ka7-b8 b7xc6+
15/30+ 00:03 22,566k 6,393k -35.39 Ne3xg4
15/30+ 00:03 23,874k 6,366k -35.39 Nf2-e4+
15/30 00:03 24,215k 6,356k -33.80 Nf2-e4+ Kg5-h6 Nd3xe5 Qe8xe5 Ne3xg4+ Qh3xg4 Qb5xe5 Nf7xe5 Bc8xg4 Qb1xe4 c6-c7 Rc1xc7 Bg4-c8 d4-d3 Rh8-d8 Nh4-g6
16/30 00:04 26,467k 6,332k -35.52 Nf2-e4+ Kg5-h6 Nd3xe5 Qe8xe5 Ne3xg4+ Qh3xg4 Qb5xe5 Nf7xe5 Bc8xg4 Qb1xe4 c6-c7 Rc1xc7 Bg4-c8 Ne5-c6 Rh8-f8 Kh6-g7 Na7xc6 Kg7xf8
17/30 00:19 117,416k 6,131k -41.24 Nf2-e4+ Kg5-h6 Rh8xe8 Rb6xb5 Re8-e6+ Kh6-g7 Re6xe5 Nf7xe5 Ne4-d6 b7xc6 Na7xb5 c6xb5 Nd3xc1 d4xe3 Nd6-e8+ Kg7-g6 Ne8-c7 Qb1xc1 Ka8-b8 Rh2-a2 Nc7xb5 Ne5-c6+ Kb8-b7
17/30+ 00:20 122,981k 6,131k -41.23 Nf2xh3+
17/30 00:20 123,017k 6,129k -40.12 Nf2xh3+ Rh2xh3 Rh8xe8 Rb6xb5 c6-c7 Qb1xd3 Re8-g8+ Nh4-g6 Bc8-f5 Qd3xe3 Na7xb5 Be5xc7 Nb5xc7 Kg5xf5 Nc7-b5 Rc1-a1+ Ka8-b8 Be1-g3+ Nb5-c7 Bg3xc7+ Kb8xc7 Qe3-e5+
18/30 00:31 192,955k 6,034k -38.40 Nf2xh3+ Rh2xh3 Qb5xb1 Rc1xb1 Rh8xe8 b7xc6 Re8-g8+ Nh4-g6 Na7-b5 Rb1-a1+ Bc8-a6 Rb6xa6+ Ka8-b7 c6xb5 Ne3xg4 Ra6-a7+ Kb7-c6 Rh3xd3 Rg8xg6+ h7xg6 Ng4xe5 Ra1-a6+ Kc6-d5 Ra6-d6+ Kd5-c5 Rd3-c3+ Kc5xb5 Nf7xe5
19/32- 00:51 313,985k 6,058k -M21 Nf2xh3+ Rh2xh3
19/32+ 00:51 314,195k 6,057k -95.00 Nf2-e4+
19/32 02:04 724,788k 5,841k -47.56 Nf2-e4+ Kg5-h6 Rh8xe8 Rb6xb5 Re8-e6+ Kh6-g7 c6-c7 Rh2-a2 Nd3-c5 Be5xc7 Ne3-f5+ Nh4xf5 Ne4-f6 Ng4xf6 Nc5-a6 Nf7-d8 Re6xf6 Kg7xf6 Bc8xf5 Rb5xf5
19/32+ 02:07 742,842k 5,838k -47.55 Ne3xg4
19/32+ 02:09 756,968k 5,834k -47.55 Rh8xe8
19/32+ 03:01 1,052,313k 5,807k -47.55 Qb5xb1
19/32+ 03:07 1,086,105k 5,801k -45.95 Qb5xe5+
20/33- 05:48 2,000,107k 5,732k -M24 Nf2-e4+ Kg5-h6
20/33+ 05:49 2,001,594k 5,732k -95.00 Qb5xe5+
20/33+ 06:02 2,075,615k 5,730k -95.00 Qb5xb1
20/33+ 06:04 2,089,441k 5,728k -95.00 Rh8xe8
20/33+ 06:25 2,203,298k 5,717k -95.00 Ne3xg4
20/33+ 06:27 2,213,051k 5,716k -95.00 Nd3xe5
20/33+ 06:33 2,249,775k 5,712k -95.00 Nd3-c5
20/33 07:00 2,394,123k 5,691k -M14 Nf2-e4+ Kg5-h6 Rh8xe8 Rb6xb5 Nd3xe5 Rb5xe5 Ne3xg4+ Qh3xg4 Ne4-f6 Qg4-f3 Nf6-g8+ Kh6-g7 Ng8-e7 b7xc6 Re8-g8+ Kg7-h6 Rg8-g6+ h7xg6 Ne7-g8+ Kh6-g7 Ng8-e7 Re5xe7 Bc8-a6 c6-c5+ Na7-c6 Qf3xc6+ Ba6-b7 Qc6xb7+
20/33+ 07:00 2,394,230k 5,691k -M15 Nd3-c5
20/33+ 07:08 2,433,874k 5,678k -M15 Nd3xe5
20/33+ 07:09 2,436,169k 5,678k -M15 Rh8xe8
20/33+ 07:12 2,452,594k 5,673k -M250 Rh8xe8
21/33 07:16 2,473,897k 5,666k -M16 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Ne4-f6+ Be5xf6 c6-c7 Qh3xd3 Rg8-g7 Rc1xc7 Rg7xh7+ Kh5-g5 Nf5-d6 Rc7xc8+ Na7xc8 Rh2xh7 Nd6-e8 Qd3-a3+ Ka8-b8 Bf6-e5+ Ne8-c7 Be5xc7+ Kb8xc7 Be1-g3+ Kc7-d7 Qb1-f5+ Kd7-e8 Qf5xc8+
22/33 07:20 2,496,086k 5,661k -M16 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 c6-c7 Qh3xd3 Nf5-g7+ Be5xg7 Rg8xg7 Rc1xc7 Rg7xh7+ Ng4-h6 Rh7-h8 Nf7xh8 Ne4-f6+ Kh5-g5 Bc8-e6 Kg5xf6 Be6-g4 Qd3-a3 Ka8-b8 Nh6xg4 Kb8xc7 Be1-g3+ Kc7-d7 Qa3-d6+ Kd7-e8 Qd6-e7+
23/33 07:45 2,627,351k 5,640k -M14 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Nd3xe5 Rb5xe5 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh3 Rh2xh3 Ka8-b8 Re5xf5 Bc8xf5 Be1-g3+ Kb8xb7 Rc1-b1+ Na7-b5 Rb1xb5+ Kb7-a7 Bg3-b8+ Ka7-a8 Qe4xc6+
23/33+ 07:47 2,634,820k 5,639k -M15 Qb5xb1
24/33 07:48 2,643,560k 5,639k -M14 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Nd3xe5 Rb5xe5 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh3 Rh2xh3 Ka8-b8 Re5xf5 Bc8xf5 Be1-g3+ Kb8xb7 Rc1-b1+ Na7-b5 Rb1xb5+ Kb7-a7 Bg3-b8+ Ka7-a8 Qe4xc6+
25/33 07:49 2,645,536k 5,639k -M14 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Nd3xe5 Rb5xe5 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh3 Rh2xh3 Ka8-b8 Re5xf5 Bc8xf5 Be1-g3+ Kb8xb7 Rc1-b1+ Na7-b5 Rb1xb5+ Kb7-a7 Bg3-b8+ Ka7-a8 Qe4xc6+
26/33 07:49 2,645,987k 5,639k -M14 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Nd3xe5 Rb5xe5 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh3 Rh2xh3 Ka8-b8 Re5xf5 Bc8xf5 Be1-g3+ Kb8xb7 Rc1-b1+ Na7-b5 Rb1xb5+ Kb7-a7 Bg3-b8+ Ka7-a8 Qe4xc6+
27/34 07:50 2,655,252k 5,639k -M14 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h4 Ne3-f5+ Kh4-h5 Nd3xe5 Rb5xe5 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh3 Rh2xh3 Ka8-b8 Re5xf5 Bc8xf5 Be1-g3+ Kb8xb7 Rc1-b1+ Na7-b5 Rb1xb5+ Kb7-a7 Bg3-b8+ Ka7-a8 Qe4xc6+
28/34 09:59 3,322,566k 5,542k -M13 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h5 Nd3xe5 Ng4xe5 Bc8xh3 Rb5-a5 Bh3-g4+ Ne5xg4 Ne3-c4 Rc1xc4 Rg8-g7 Qb1xe4 Rg7xh7+ Kh5-g5 Rh7xh2 Qe4xc6 Rh2-h5+ Kg5xh5 Ka8-b8 Qc6-c7+ Kb8-a8 Qc7-c8+
29/34 10:06 3,362,628k 5,540k -M13 Rh8xe8 Rb6xb5 Re8-g8+ Nh4-g6 Nf2-e4+ Kg5-h5 Nd3xe5 Ng4xe5 Bc8-g4+ Ne5xg4 Ne3-f5 Rb5xf5 Rg8-g7 Qb1xe4 Rg7xh7+ Ng4-h6 c6-c7 Qe4-e8+ c7-c8Q Qe8xc8+ Na7xc8 Rc1xc8+ Ka8xb7 Rh2-b2+ Kb7xc8 Rf5-c5+