For people not aware of how computer chess engines work or what a tablebase is. TLDR: chess would be fully solved if there existed a 64-piece tablebase. These guys have done the chess world a massive favour by computing the most important subset of the 8-piece tablebase and making it available to the world.
Long version: Chess engines normally work by doing a highly optimised search of the game tree to some depth, evaluating the board position in each state using some evaluation function and then propagating the evaluation backwards up the tree. Then it’s a matter of picking the moves that lead to the game trees with the most favourable board state assuming both opponents make the best possible moves from the current position. The strength of the engine depends on the available computation, the efficiency of any tree pruning you’re able to do and the accuracy of the evaluation function, which is always going to be somewhat subjective.
However when “few enough” pieces remain on the board (in the endgame), the number of possible game states is small enough that it’s possible to brute force solve the game from each state by enumerating all possible moves and resulting states so as to find the absolute optimal move for any given board position. Looking up the evaluation and best possible move for a given state if you had done all this computation beforehand is obviously much more efficient and accurate than the tree-search minimax thing I described initially, and being able to do this at the leaves of the game state during minimax evaluation massively improves the strength and accuracy of any engine. When you get to a state that’s in the tablebase, you can stop as you know the objective evaluation and best move so you can focus on computing evaluations of other states that aren’t fully solved.
A tablebase is the database containing these fully-solved positions and the corresponding objective evaluations and best moves, and all strong engines swap to a tablebase at some point. So this is a tablebase for an important subset of game positions where 8 pieces remain (which had not previously been computed by anyone as far as I know). It’s a massive amount of work to compute these so providing this for everyone is a huge contribution. But this is lichess, who literally provide a free chess website for anyone who wants to play or learn chess, so we sort of expect them to be awesome because they are.
>However when “few enough” pieces remain on the board (in the endgame), the number of possible game states is small enough that it’s possible to brute force solve the game from each state by enumerating all possible moves and resulting states so as to find the absolute optimal move for any given board position
You can basically never do that, even in the endgame, since you get always exponential blow up! Furthermore with less pieces on the board, they hamper each others movement less, therefore the branching factor really goes down only slightly.
If you want to compute all mate-in-n positions, you discover the theoretical values in tiers, by unmoving each tier twice:
If you know all mate-in-0,...,mate-in-n positions, unmove the mate-in-n set for the defender and filter out results, where he can avoid moving into the union of the known tiers. Then unmove for the attacker, to find mate-in-(n+1). Repeat until convergence. Repeat the whole process for the left over positions, to find more theoretical values.
omoikane 16 hours ago [-]
> chess would be fully solved if there existed a 64-piece tablebase
Is the 64-piece number meant to cover chess variants with more than standard number of pieces? I was expecting 32.
seanhunter 13 hours ago [-]
Omg I didn’t get enough sleep last night. Yes. 32 would be fully solved.
pimlottc 2 hours ago [-]
Clearly GP is playing 4d chess
Rendered at 22:42:30 GMT+0000 (Coordinated Universal Time) with Vercel.
Long version: Chess engines normally work by doing a highly optimised search of the game tree to some depth, evaluating the board position in each state using some evaluation function and then propagating the evaluation backwards up the tree. Then it’s a matter of picking the moves that lead to the game trees with the most favourable board state assuming both opponents make the best possible moves from the current position. The strength of the engine depends on the available computation, the efficiency of any tree pruning you’re able to do and the accuracy of the evaluation function, which is always going to be somewhat subjective.
However when “few enough” pieces remain on the board (in the endgame), the number of possible game states is small enough that it’s possible to brute force solve the game from each state by enumerating all possible moves and resulting states so as to find the absolute optimal move for any given board position. Looking up the evaluation and best possible move for a given state if you had done all this computation beforehand is obviously much more efficient and accurate than the tree-search minimax thing I described initially, and being able to do this at the leaves of the game state during minimax evaluation massively improves the strength and accuracy of any engine. When you get to a state that’s in the tablebase, you can stop as you know the objective evaluation and best move so you can focus on computing evaluations of other states that aren’t fully solved.
A tablebase is the database containing these fully-solved positions and the corresponding objective evaluations and best moves, and all strong engines swap to a tablebase at some point. So this is a tablebase for an important subset of game positions where 8 pieces remain (which had not previously been computed by anyone as far as I know). It’s a massive amount of work to compute these so providing this for everyone is a huge contribution. But this is lichess, who literally provide a free chess website for anyone who wants to play or learn chess, so we sort of expect them to be awesome because they are.
Here is a piece from Cornell about how stockfish (the world’s strongest chess engine) works if you’re interested https://blogs.cornell.edu/info2040/2022/09/30/game-theory-ho...
You can basically never do that, even in the endgame, since you get always exponential blow up! Furthermore with less pieces on the board, they hamper each others movement less, therefore the branching factor really goes down only slightly. If you want to compute all mate-in-n positions, you discover the theoretical values in tiers, by unmoving each tier twice: If you know all mate-in-0,...,mate-in-n positions, unmove the mate-in-n set for the defender and filter out results, where he can avoid moving into the union of the known tiers. Then unmove for the attacker, to find mate-in-(n+1). Repeat until convergence. Repeat the whole process for the left over positions, to find more theoretical values.
Is the 64-piece number meant to cover chess variants with more than standard number of pieces? I was expecting 32.