Chess will never be solved, here's why

Split the Prize Money!
Plus Save the Time!
In world class tennis players sometimes agree in advance to even-split the prize money.
Like in finals. But they play the match. And 'tanking' not allowed.

@11952

"It assumes that the rate at which new positions is added is constant"
++ No, it reasons with an average non-transposing branching number.

"picks a random number of moves (40)"
++ It is no random number, it is the average number of moves in the 114 ICCF WC Finals draws.

"all the way to 40 moves then stops dead"
++ After average 40 moves an ICCF WC Finals game is over.

"there are positions that take over 60 moves" ++ Yes, but with a string of forced moves.

My agument still stands that 35 non-transposing choices per ply is impossible:
35^25 = 10^38
12.5 moves is clearly too small, thus 35 non-transposing choices is clearly too many.

"40 move positions in ICCF games usually have more than 8 pieces on the board"
++ 10 reached a 7-men endgame table base draw, 37 reached a 3-fold repetition, 57 ended in a clearly drawn position, with no point for either side in continuing, and 10 ended in death of Dronov in otherwise drawn positions.

"Here is an ICCF game with 9 pieces on the board on move 77"
++ Average 40 moves, standard deviation 11, minimum 15, maximum 73.
A 3-fold repetition is just as sure a draw as a 7-men endgame table base draw.
A known drawn position is just as sure as well.

"You need to exhibit 2 strategies" ++ No, 1 strategy for black to draw is enough.
Anyway, there already is a strategy for both sides to draw: follow an ICCF WC Finals draw for as long as possible and then switch to 2 servers of 90 million positions/s during 5 days per move guided by an ICCF (grand)master.

@11969

"theres over 10 to the 123rd power of chess moves"
++ No. There are between 10^29241 and 10^34082 possible chess games.
There are 4.82 * 10^44 legal chess positions, but most make no sense because of around 9 promotions to pieces not previously captured.
There are 3 * 10^37 legal chess positions without promotions to pieces not previously captured.
There are 3.3 * 10^38 legal chess positions possible from 1 luxury box of 32 chess men plus a white spare queen and a black spare queen.
Of these 1.8 * 10^17 are relevant to weakly solving chess.

Exactly as I predicted.
tygxc trying to square root the big number again. Crassly invalid.
And I don't think that 'game theory' is even needed to know that's garbage.
But tygxc forgot his invalid 'nodes per second' this time.
Temporarily he's off the 114 games. But he'll be back to that too.
The number is far over 10^44 positions to be solved.
By comparison - that part of the universe humanity can observe is 'only' 10^24 kilometers across.
--------------------
But tygxc looks like a saint compared to those climate science deniers and to the O-person.

Being bored of correcting the same errors by @tygxc repeatedly, let's look at some proper analysis - the calculation of the number of legal chess games after N moves. These are the values explicitly calculated by a brilliant programmer who works for NVIDIA and who was kindly donated some of their enormous computing resources for his hobby. This calculation is enormous and massively parallel.

This is the number of legal games up to white's 8th move (i.e. 15 ply), which is around 2 x 10^21.

Of course we are interested in how many transpositions there are. I have some numbers for the first few ply based on engine hash hits (the almost 100% reliable way engines detect transpositions)

EDIT: unfortunately the following numbers don't help. On reflection, they are well short of the transposition count for some reason.

You will see that it's scarcely significant up to this point. The reason is that the large majority of moves are expanding the tree rather than returning to existing positions. Intuitively, you won't get transpositions dominating until you have already expanded the tree to quite near its full size - up to that point there is always much more virgin state space than the small fraction already covered. More precisely, you can think of branches as "exploring" the tablebase for the current material balance, with the possibility of moving irreversibly into other tablebases by capture or promotion).

Note that the above numbers means there are well over 3^16 positions reached after 6 ply. Even if future branching (allowing for transposition was a constant 3), this would make @tygxc's estimates short by a factor of 3^10.

Note that by explicit calculation the mean branching factor is above 20 on all moves up to ply 6. There is no doubt it continues to stay high for many moves and takes a long time to get down to 3. It will happen eventually, but likely when the tree is approaching the set of all legal positions (over 10^44 of them) on a logarithmic scale.

hi

@11974

"There are 4.82 * 10^44 legal chess positions, but most make no sense"
++ As is clear just at first glance. Look at the 3 random samples displayed. I have even proven none of these can result from optimal play by both sides. They all look like that.

"Multiple promotions are as much part of legal chess" ++ Multiple underpromotions to pieces not previously captured are legal, but cannot result from optimal play by both sides. There are no such instances in millions of master games, representing reasonable play and there are no such instances in 104 ICCF WC Finals draws, perfect games with optimal play by both sides.

"Of these 1.8 * 10^17 are relevant" ++ @elroch still does not understand basic math.
Sqrt (3*10^37 * 10.9456 / 10,000) = 1.8 * 10^17

@11976

"the large majority of moves are expanding the tree rather than returning to existing positions"
++ No. This is nonsense. Chess is full of transpositions.
The number of chess games lies between 10^29241 and 10^34082, there are only 10^44 legal chess positions, most of these nonsensical.
If you divide you see there are between 10^664 and 10^775 ways to reach a position.

"you won't get transpositions dominating until you have already expanded the tree to quite near its full size"
++ No, this is nonsense, your intuition is wrong. There are massive transpositions.
Just from the ongoing ICCF WC Finals:
1 d4 d5 2 c4 e6 3 Nf3 Nf6
1 d4 d5 2 Nf3 Nf6 3 c4 e6
1 d4 Nf6 2 c4 e6 3 Nf3 d5
1 Nf3 Nf6 2 c4 e6 3 d4 d5

"there is always much more virgin state space than the small fraction already covered"
++ No. It is not only the covered state space, but also the inaccessible state space.
After 1 e4 all positions with a white pawn on e2 are inaccessible.
After 1... c5 all positions with a black pawn on c7 are inaccessible.
After 2 Nf3 d6 all positions with a black pawn on d7 are inaccessible.
After 3 d4 all positions with a white pawn on d2 are inaccessible.
After 3...cxd4 all 32 men positions are inaccessible.
After 4 Nxd4 all 31 men positions are inaccessible.
After 4...Nf6 5 Nc3 a6 all positions with a black pawn on a7 are inaccessible.
The accessible state space shrinks and shrinks.

"you can think of branches as exploring the tablebase for the current material balance"
++ Yes, even finer, the current material balance can be partitioned in classes of white and black pawn advancement, which is also irreversible.

"there are well over 3^16 positions reached after 6 ply" ++ No.

"explicit calculation the mean branching factor is above 20" ++ No, there are transpositions.
Assume a non transposing branching factor of 20.
10^38 = 20^29.
After 14.5 moves you would have the whole of chess.
14.5 is clearly too few, so 20 is clearly too many.

Here is a quote from a 2010 discussion that references calculations of the branching factor for early moves in chess (i.e. fully allowing for transposition. The hash hit count I referenced earlier did not do this). It indicates a plausible 9,132,484 distinct positions after 6 ply, which is an average branching factor of over 14 to that point.

"The number of distinct chess positions after White’s first move is 20 (16 pawn moves and 4 knight moves). There are 400 distinct chess positions after two moves (first move for White, followed by first move for Black). There are 5,362 distinct chess positions or 8,902 total positions after three moves (White’s second move). There are 71,852 distinct chess positions or 197,742 total positions after four moves (two moves for White and two moves for Black). There are 809,896 distinct positions or 4, 897,256 total positions after 5 moves. There are 9,132,484 distinct positions or 120,921,506 total positions after 6 moves (three moves for White and three moves for Black). The total number of chess positions after 7 moves is 3,284,294,545. "

@11984

"There are 400 distinct chess positions after two moves"
++ Yes, but in master games of all time controls only 12*12 = 144 are played.
In the 114 perfect games of the ongoing ICCF WC Finals only 7 are played:

1. e4 e6
2. e4 c5
3. e4 e5
4. d4 d5
5. d4 Nf6
6. Nf3 d5
7. Nf3 Nf6

"There are 5,362 distinct chess positions after three moves" ++ That includes nonsense like 1 Nf3 d5 2 Ng1, 1 g4 e6 2 f3, 1 e4 b5 2 Bc4, 1 e4 Nf6 2 Qh5 etc.

"There are 71,852 distinct chess positions after four moves"
++ That includes nonsense like 1 e4 e5 2 Qh5 Ke7 etc.

Jeez - the same blunderful thinking again. Ask Schaeffer for some tips.

You have no basis for claiming that 1. Nf3 d5 2. Ng1 is not tablebase-optimal. Most likely it is.

1 e4 e5 2 Qh5 Ke7 is simply a position that is easy to find the value of (win for white on move 3). Whether it needs to be considered depends whether it appears in one of the two strategies. This is unlikely, but it could (the white one).

You're using SF to process your "positions".

SFs understanding of "position" is different from yours. It corresponds to nodes in the game tree under competition rules (because that is what it must work with) while yours does not.

Your first position to SF corresponds to the UCI command

position fen rnbqkbnr/ppp2ppp/4p3/3p4/2PP4/8/PP2PPPP/RNBQKBNR w KQkq - 0 3 moves b1c3

This doesn't transpose with the rest which corresponds to the UCI command

position fen rnbqkb1r/ppp2ppp/4pn2/3p4/2PP4/2N5/PP2PPPP/R1BQKBNR w KQkq - 2 4

SF will evaluate any positions searched as 0 after 98 ply without a pawn move or capture from the first command, but only after 100 ply from the second. If you're using an off the shelf GUI it will probably terminate the game in a draw after 98 ply without a pawn move or capture from the first command, but only after 100 ply from the second. It should in any case terminate the game in a draw after 148 ply without a pawn move or capture from the first command, but only after 150 ply from the second.

If playing from the second command it will also repeat twice the positions considered the same under 9.2.3 as the FEN in the first command or after the first of the two moves following should these occur and evaluate to best both times, whereas when playing from the first command it will apply its triple move algorithm on the second occurrence and may avoid the repetition. It may also avoid the first repetition because the position no longer evaluates to best (evaluation is dependent on ply count).

The same will apply to any position played on from the final position in the two cases until the next irreversible move.

So your transpositions are transpositions of what you define as "position" (i.e the 9.2.3 criterion) but those "positions" don't determine the nodes in the game tree. They're not transpositions of nodes in the game tree which is what you're using them as.

You last three examples are genuine transpositions of each other but these will be relatively common at the start of the game because of the prevalence of irreversible pawn moves.

@11985

The rarity of underpromotions stems from the Laws of Chess. It is generally indicated to promote to a queen, except when the unique properties of the knight are needed, or when a rook or even a bishop is needed to prevent a draw by stalemate after queening. Underpromotions happen, but are rare. An underpromotion is like a sacrifice of a bishop or a rook. It only happens for very good reason.

The rarity of promotions to pieces not previously captured stems from the Laws of Chess. By the time a pawn reaches the back rank, pieces have been captured and usually the desired piece has already been captured. Promotion to a queen not previously captured happens, but is rare.
That is why luxury chess sets include a spare queen of both colors.

The combination of both: underpromotion and promotion to a piece not previously captured does not happen. Luxury chess sets include no 3rd knight, rook, or bishop.

An average position as counted by Tromp has 9 promotions to pieces not previously captured.
99.95% of positions as counted by Tromp has 3 to 16 promotions to pieces not previously captured. The count is massively increased by counting positions that never happen.
That is why Gourion's 3*10^37 is a better starting point: no promotions to pieces not previously captured.

It is a bit too restrictive, as promotions to queens not previously captured happen occasionally.
Therefore a factor
3.8*10^41/1.9*10^40/4 + 3.6 * 10^42/1.9*10^40/4/4/2 = 10.9456
is needed. That leaves
3*10^37 * 10.9456 = 1.8 * 10^38 positions
possible from 1 luxury box of 34 chess men.

@11988

"SFs understanding of position" ++ is the same as mine: a FEN without move#.

"nodes in the game tree" ++ A node is a position + history + provisional heuristic evaluation

"what you define as position (i.e the 9.2.3 criterion)" ++ Yes

"those positions don't determine the nodes in the game tree"
++ Node = position + history + provisional heuristic evaluation

its already been solved. we just hafta find it.

But did you work out why or learn it long ago?

i take it u had trubble w/that one ?