Hi again,
How does FinalGen work? Let’s show an example:
[D]3k4/8/PpK5/1Pp3p1/2P3P1/8/8/8 w - - 0 1
What is the best way to win for White?
A human player or even a chess program would play 1. a7 and force a checkmate easily with both the queen and the king.
An endgame generator does not proceed in this way. These programs do not have any intelligence, and must build all the positions resulting from the initial position (by retrograde analysis), including promotions. Black can also promote, and minor promotions can occur.
For example, to solve the above position, the endgames generators must solve the following positions first:
[D]Q7/4k3/2K5/8/8/1q6/8/2q3q1 w - - 0 1
[D]Q7/5k2/2K3N1/8/3r4/1q6/8/8 w - - 0 1
That is, it must generate a complete 6-men pawnless database to solve a simple pawn endgame which can be easily won. In fact, it must generate more positions than the whole complete Nalimov 6-men tablebase currently available.
Don’t you believe me? I can guarantee that it is true.
FinalGen can generate the tablebase in a few hours. It promotes a pawn only once, and sets a win result if white can force a win with only one promotion, this is faster than generating the complete Nalimov tablebase set.
FinaGen uses other heuristics to determine draws but all of them are based on the same idea. We reduce the number of positions after a promotion to make the process faster, because only a few positions are needed from the astronomical total.
Why may some positions not be solved?
Because they are “out of heuristics”, FinalGen can not determine the result from these few positions (“ a few” here means millions, billions or trillions, depending on the position). These unsolvable positions are discarded and flagged as “not available”.
That occurs in the example below:
[D]8/6K1/8/5PPP/p7/1k6/8/8 w - - 0 1
White and Black promote simultaneously, and after that, White can win by promoting a second pawn.
Here White needs 2 promotions, not one, to win, so the algorithm does not find the win.
However, those positions can be solved if the winning side can force checkmate or a queen exchange just after the promotion. For instance, the following endgame can be solved.
[D]8/8/8/1p2KP2/5P2/2k5/8/8 b - - 0 15
1... b4 2. f6 b3 3. f7 b2 4. f8=Q b1=Q 5. Qc5+ Kd2 6. Qf2+ Kc3 7. Qd4+ exchanges queens and wins.
So not all the possibilities are explored. This is why the way to win may not be the shortest one (for example, Nalimov can show mate in 10 where FinalGen has found a checkmate in 12).
And finally, why the “one piece per side” limitation? This is due to memory RAM requirements. Each additional piece would multiply the required RAM memory by 64, so I had decided to work only with 2 pieces + pawns. The source code has been specifically designed for 2 or less pieces and cannot be adapted. For more pieces, the whole program should be re-designed.
I hope these explanations have been useful to you.
Best Regards.
Pedro Pérez Romero
