Answers.Body: <p>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)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-11T05:39:09.220Z
Answers.Text: 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
Answers.UserDisplayName: Shravan S
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-11T22:55:52.453Z
Answers.Text: I see Stockfish getting to mates in 70 having many pieces on board. Obviously it cannot be brute force?
Answers.UserDisplayName: Yash Jain
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-11T22:56:36.217Z
Answers.Text: @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.
Answers.UserDisplayName: koedem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-11T22:57:11.853Z
Answers.Text: @edit_profile well, this question is about tablebases, not about engines. Engines do not work by retrogarde analysis.
Answers.UserDisplayName: koedem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-14T16:49:44.403Z
Answers.Text: @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.
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-11T02:38:06.307Z
Answers.LastActivityDate: 2021-01-11T02:38:06.307Z
Answers.UserDisplayName: koedem
Answers.Body: <p>Yes, endgame tablebases are calculated by brute force. That's why we only have complete 7-men tablebases today (which were published in 2012).</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-13T12:04:13.180Z
Answers.LastActivityDate: 2021-01-13T12:04:13.180Z
Answers.UserDisplayName: Tore Winter
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-23T00:26:59.797Z
Comments.Text: My understanding is that they have to first do retrograde for given mate positions, for example. So, the question about how are those generated, and how complete are they, are they restricted to legal mate positions. I don't think we know to list all the mates that are legal continuation from any of the 960 setups, including the standard initial. So, I also wonder the same as op. Which might be putting 2 conflicting questions in one. The "forcing" paths to checmate class how is that found, but how are the very inputs to retrograde, generated/restricted among all EPDs. –
Comments.UserDisplayName: dbdb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-23T00:28:33.120Z
Comments.Text: I mean the second question of brute force might be confused with a forward logic computation, as it follows the notion of forces wins, as output. I might be not understanding.
Comments.UserDisplayName: dbdb
Tags: <engines><software><tablebases>
Title: How do endgame tablebases calculate checkmates to do retrograde analysis on?
ThreadText: # How do endgame tablebases calculate checkmates to do retrograde analysis on?
  
  (Asked by: username_0 on 2021-01-10)
  
  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?
  
  **Tags:** engines, software, tablebases
  
  > **Comments:**
  > **username_1**: My understanding is that they have to first do retrograde for given mate positions, for example. So, the question about how are those generated, and how complete are they, are they restricted to legal mate positions. I don't think we know to list all the mates that are legal continuation from any of the 960 setups, including the standard initial. So, I also wonder the same as op. Which might be putting 2 conflicting questions in one. The "forcing" paths to checmate class how is that found, but how are the very inputs to retrograde, generated/restricted among all EPDs. –  
  > **username_1**: I mean the second question of brute force might be confused with a forward logic computation, as it follows the notion of forces wins, as output. I might be not understanding.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2021-01-13. Score: 4 | Accepted answer
  
  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.
  
  
  ---
  
  ### Answer by username_2 on 2021-01-11. Score: 2
  
  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)
  
  > **Comments:**
  > **username_0**: 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  
  > **username_3**: I see Stockfish getting to mates in 70 having many pieces on board. Obviously it cannot be brute force?  
  > **username_2**: @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.  
  > **username_2**: @edit_profile well, this question is about tablebases, not about engines. Engines do not work by retrogarde analysis.  
  > **username_4**: @username_2: ...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.  
  
  ---
  
  