Yeah. Print the money. Institute 10,000 dollar bills.
For a 10,000 billions of year 'project' regarding motions of chess pieces.
Chess will never be solved, here's why
But still nobody seems to have noticed that the time and space could be reduced by a huge factor if "chess" (whatever version) is a win in a modest number of moves (though not with @tygxc's approaches).
Also checkers has 500,995,484,682,338,672,639 positions under basic rules if you equate positions with nodes in the state space, but vastly more than that under tournament rules (assuming resignations, agreed draws, time controls and forfeit rules are ignored; like chess the game is insoluble with checkers tournament rules as stated in the link). The increase is because the tournament rules include 40 move and triple repetition rules.
Similarly the number of nodes in the state space for competition rules chess is vastly more than 4.82 * 10^44, but the salient point is the ratio between the number of nodes in the state space for competition rules chess and that for tournament checkers is also vastly more than 10^24 (or 10^27 for that matter - three orders of magnitude wouldn't be significant in the context).
The solution for checkers hugely restricted the search space (as opposed the state space) by incorporating the Kishimoto-Müller algorithm into the Chinook program, but this doesn't appear to have been implemented in any Stockfish version so far as I can see.
#3621 Given that we don't play perfectly, a computer does not need to play perfectly to beat us. If a computer solved chess it wouldn't give an advantage of about half a pawn from the starting position, but instead would either give an advantage of 0.0 or of mate in some number of moves.
#3617
"Start saving"
++ The number of legal positions only matters to strongly solve chess, i.e. a 32-men table base.
Schaeffer has weakly solved checkers considering 10^14 positions.
Chess has 10^17 legal, sensible, reachable, and relevant positions, that is a factor 1000.
Computer power costs less now than in 1989 - 2007.
3 cloud engines and 3 (ICCF) (grand)masters during 5 years would cost 3 million $.
That is still the impeding factor and the only reason why chess has not yet been solved
and may not be solved soon.
Chess has 10^17 legal, sensible, reachable, and relevant positions

If there were merely 4 table-base correct moves leading to novel positions this number of positions would be reached in 30 half moves. So either 15 moves for both sides or no more than 30 moves if one side uses a deterministic strategy.
I am not sure if you've heard but it is not the exception for chess games to last a lot longer than this.
#3625
"this number of positions would be reached in 15 moves"
++ That is not true because chess has so many transpositions:
different move orders that lead to the same position. E.g.
1 e4 e5 2 Nf3 Nc6 3 Bc4 Bc5 4 d3 Nf6
1 e4 e5 2 Nf3 Nc6 3 Bc4 Nf6 4 d3 Bc5
1 e4 e5 2 Bc4 Nf6 3 d3 Nc6 4 Nf3 Bc5
etc. etc.
Those don't lead to the same game states under competition rules. They lead to the same positions under basic rules only.
The term "position" is used in different senses, but "game state" would seem to be the only sensible meaning if it's to relate to a proposed solutions based on a forward search by some version of Stockfish.
#3627
That does not matter. The same position per Laws of Chess 9.2.2 has the same evaluation.
Besides often there are not even 2 viable moves. If I take your queen, then often the only reasonable move is to recapture my queen.
In the Candidates' Madrid 2022 the average game length past a predecessor was 34 moves.
For weakly solving it is only necessary to look at all reasonable alternatives for 1 side.
#3625
"this number of positions would be reached in 15 moves"
++ That is not true because chess has so many transpositions [ . . . ]
So if you prune all but 4 candidates for White and one for Black (so you said) and search only 10¹⁷ different positions, what are the average branching factor and depth of the tree? We have already asked you several times to translate in pseudocode, with the same level of details, the algorithm you described in your obscurantistic language, but you never did. With the very strict constraints you give, you cannot simply get away with a convenient: "we will know only when the search will be concluded", or with a guess out of nowhere, as you did before.
#3627
That does not matter. The same position per Laws of Chess 9.2.2 has the same evaluation.
No it doesn't. I keep trying to tell you that.
Besides often there are not even 2 viable moves. If I take your queen, then often the only reasonable move is to recapture my queen.
In the Candidates' Madrid 2022 the average game length past a predecessor was 34 moves.
Is the preceding meant to be relevant to the size of the state space in some way? It's not at all obvious how.
For weakly solving it is only necessary to look at all reasonable alternatives for 1 side.
What you think is reasonable has no connection with the size of the state space or solving chess. Indeed your meaning of "reasonable" is ill defined as @Elroch pointed out a few posts ago.
#3629
If there were no transpositions, then width w = 4 and depth d = 34 would lead to
1 + w + w² + w³ + ... + w^d = (w^(d+1) - 1) / (w - 1) positions
If all moves were interchangeable, then that would lead to
1 + w + w²/2 + w³/3! + ... ~= e^w positions , with d! = d*(d-1)*...*3*2*1 and e = 2.718281828...
The truth lies between the two.
While "it" obviously does matter (see discussion above), in a way which is not comfortable to my pure mathematicians desire for neatness and simplicity, even for basic chess transposition surely only moderately reduces the exponent (the growth in the number of positions with depth of thorough analysis) for a long way from the opening position.
Part of the reason is the large number of irreversible moves that can occur in an optimal chess game. Recall that the set of legal basic chess positions is split into equivalence classes of positions by the ordering defined by the existence of a legal path of moves between two positions. Every pawn move, every capture and more, kind of "resets the transposition clock" (classes of positions which are "earlier" in the tree of legal paths cannot ever be reached again). So transpositions are localised to the equivalence classes. It's also worth remembering that the number of legal positions is relatively small compared to the number of legal games partly because of transpositions. So, enlighteningly, transpositions are already taken account of to get the number of legal positions in basic chess (~10^43 or whatever). And the version with official rule sets has an enormously greater number of states, however much of a pain I find that to be, making the point virtually moot.
#3633
"transposition surely only moderately reduces the exponent (the growth in the number of positions with depth of thorough analysis) for a long way from the opening position."
++ The reduction is massive.
"Part of the reason is the large number of irreversible moves that can occur in an optimal chess game." ++ That is no reason. You can have reversible and irreversible moves that lead to the same position. See counterexamples below.
"the set of legal basic chess positions is split into equivalence classes of positions by the ordering defined by the existence of a legal path of moves between two positions."
++ Usually there are many legal paths between two legal positions. There are even billions of paths between the initial position and the position after 1 e4 e5. Most of these make no sense.
1 e4 e5
1 e3 e6 2 e4 e5
1 e3 e5 2 e4
1 e3 Nf6 2 Nf3 e6 3 Ng1 e5 4 e4 Ng8
"Every pawn move, every capture and more, kind of "resets the transposition clock""
++ No, that is not true. Counterexamples:
1 e4 d5 2 exd5 Qxd5 3 Nc3 Qd6 4 d4 c6 5 Ne4 Qc7 is exactly the same as
1 e4 c6 2 d4 d5 3 Nc3 dxe4 4 Nxe4 Qc7
1 e4 c5 2 Nf3 Nc6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 e5 6 Ndb5 d6 7 Bg5 is exactly the same as
1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 Nc6 6 Ndb5 d6 7 Bf4 e5 8 Bg5
1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 a6 5 Nc3 Nc6 6 Be3 Nf6 7 Bd3 d5 8 exd5 exd5 9 O-O Bd6 10 Nxc6 bxc6 11 Bg5 O-O is exactly the same as
1 e4 e5 2 Nf3 Nf6 3 Nc3 Nc6 4 d4 exd4 5 Nxd4 Bb4 6 Nxc6 bxc6 7 Bd3 d5 8 exd5 cxd5 9 O-O c6 10 Bg5 Bd6
"transpositions are localised to the equivalence classes"
++ No, transpositions go past equivalence classes. See counterexamples above.
"the number of legal positions is relatively small compared to the number of legal games partly because of transpositions." ++ Yes, that is true.
"transpositions are already taken account of to get the number of legal positions in basic chess (~10^43 or whatever)." ++ 10^44 legal, but 10^17 sensible, reachable, and relevant. However, some people tend to go back to games and then forget about the major impact of transpositions and thus arrive at numbers of positions that are way higher.
#3629
If there were no transpositions, then width w = 4 and depth d = 34 would lead to
1 + w + w² + w³ + ... + w^d = (w^(d+1) - 1) / (w - 1) positions
If all moves were interchangeable, then that would lead to
1 + w + w²/2 + w³/3! + ... ~= e^w positions , with d! = d*(d-1)*...*3*2*1 and e = 2.718281828...
The truth lies between the two.
How is w=4 and d=34 related to solving chess?
Moves that transpose to positions that are considered the same for the purposes of 9.2.2 don't generally produce the same game state under competition rules, so what, in fact, is the calculation supposed to be related to at all?
#3635
w = 4 is a reasonable width. As shown earlier this would make 1 error in 10^20 positions.
d = 34 is an everage depth after a predecessor game
The calculation shows the number of positions with 0 transpositions and with full permutation.
#3629
If there were no transpositions, then width w = 4 and depth d = 34 would lead to
1 + w + w² + w³ + ... + w^d = (w^(d+1) - 1) / (w - 1) positions
If all moves were interchangeable [ . . . ]
As @Elroch already mentioned, if there are 10⁴⁴ legal different positions (but he and @MARattigan correctly note that the the same position can produce different states, depending on the rules used), and one intends to search only a subset of 10¹⁷ of them, these are different positions too, and one already has to rely on transposition tables to not expand the same node twice. Now, if using TT the branching factor is 4, only a depth of 28 plies, i.e. 14 full moves, can be reached after a search of 10¹⁷ nodes; if, again using TT, the branching factor is 2, you can more or less double the depth, no more.
A typical engine can reach great depths thanks to late move reductions and other techniques, which make the engine actually very selective: it is not unusual that at the end of the search they check only one candidate move. That is obviously inadequate for a game-solving program.
Checkers and antichess have been solved after a relatively small search because captures are compulsory, so often players have just one legal move to play.
#3633
...
++ No, that is not true. Counterexamples:
1 e4 d5 2 exd5 Qxd5 3 Nc3 Qd6 4 d4 c6 5 Ne4 Qc7 is exactly the same as
1 e4 c6 2 d4 d5 3 Nc3 dxe4 4 Nxe4 Qc7
1 e4 c5 2 Nf3 Nc6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 e5 6 Ndb5 d6 7 Bg5 is exactly the same as
1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 Nc6 6 Ndb5 d6 7 Bf4 e5 8 Bg5
1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 a6 5 Nc3 Nc6 6 Be3 Nf6 7 Bd3 d5 8 exd5 exd5 9 O-O Bd6 10 Nxc6 bxc6 11 Bg5 O-O is exactly the same as
1 e4 e5 2 Nf3 Nf6 3 Nc3 Nc6 4 d4 exd4 5 Nxd4 Bb4 6 Nxc6 bxc6 7 Bd3 d5 8 exd5 cxd5 9 O-O c6 10 Bg5 Bd6
...
None of those "counterexamples" produce the same game state under competition rules.
The ratio is 10^24
That's ok then.
If solving checkers costs a cent (underestimate, in case you haven't noticed), solving chess will cost $10,000,000,000,000,000,000,000.
Start saving.
That's starting to seem very doable. With the current boneheads in charge it wont take long before one of your numbers equals the other.