I understand that once endgame tablebases get checkmates, they do retrograde analysis and are able to calculate forced wins. However, how do they calculate the checkmate in the first place? Do they just use brute force?
Add a comment
|
2 Answers
Yes, endgame tablebases are calculated by brute force. That's why we only have complete 7-men tablebases today (which were published in 2012).
When stockfish finds a mate with more pieces than stockfish has calculated until only 7 men are on the board and the tablebases give stockfish the solution for the rest.
Roughly, yes. To build a tablebase for a certain material combination you will want to have every legal configuration of those pieces in memory. (in practice one can optimize that a bit) Then you check which of the positions are already checkmate. And yes, then you work backwards and find longer and longer wins. (and then all remaining positions that aren't wins for either side are draws)
-
Which algorithm are they using to calculate all legal configurations for certain material?I could not think of any which would be computable in a reasonable amount of time Jan 11, 2021 at 5:39
-
I see Stockfish getting to mates in 70 having many pieces on board. Obviously it cannot be brute force? Jan 11, 2021 at 22:55
-
@ShravanS what do you consider reasonable amount of time here? I mean, if you have for instance king + rook + rook + bishop vs king + rook + rook, you do have on the order of 64 * 63 * 62 * 61 * 60 * 59 * 58 positions. Yes, that is a lot, but there is a reason why we only have tablebases up to 7 pieces.– koedemJan 11, 2021 at 22:56
-
1@edit_profile well, this question is about tablebases, not about engines. Engines do not work by retrogarde analysis.– koedemJan 11, 2021 at 22:57
-
@koedem: ...which can be further brought down by storing all legal wK-bK positions first, and surely both K in check can also be calculated fast. Jan 14, 2021 at 16:49