NEWS: FinalGen chess endgame tablebase generator.

[pPerez]

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

[Uri Blass]

I see no advantage of FinalGen relative to normal chess programs in the relevant positions of the last post.

Houdini1.5 with no tablebases can see forced mate in the first diagram and the last diagram
so it also can solve them.

[pPerez]

I have intentionally presented an example which is very easy to solve for a human or a chess computer and very difficult for a endgame generator.

My intention here was to compare FinalGen with other tablebase generators and describe how it works.

If my intention were to compare FinalGen to chess programs, I would rather present the following position.

[D]3k4/8/b7/1p6/p7/2K5/p7/3B4 w - - 0 22

FinalGen says that this is a draw. And what about Houdini?

[Arpad Rusz]

Some feature requests for FinalGen:

1.It would be useful to have the moves listed even when the value of the position is "Not available".
That way one can easily spot which move from the movelist leads to an unsolvable position (which maybe it is trivial to solve by other means).

2.It is enough to have piece buttons (K, Q, R, B, N, P) only for white.
E.g. one click on the board places a white piece, a double click places a black one, and a click with the right mouse button deletes the square. This way one can setup a position more quickly.

3.I would like to have visible both the WTM and BTM movelists and values in the same time. So no "White to move" and "Black to move" radio buttons...

[duncan]

I tried out this position as I was interested in how many months/years it would take
[D]4k3/2pppppp/8/8/8/8/2PPPPPP/4K3 w - - 0 1



and the program said 'this position is too complex'. is that a limitation of the software or my computer ?

[duncan]

I tried using the software for a rook against 5 pawns, to see whether it would be a draw. the following position should be a draw and it was.

[D]4k3/4r3/8/8/8/8/PPPPP3/4K3 w - - 0 1



there seems to be 3 conditions for white to win

(1)you need at least 2 pawns on the third rank (although only certain combinations)
(2)and the black king has to be on rank 8
(3)and the rook opposite a white pawn

so the following wins a queen in 27 moves

[D]4k3/4r3/8/8/8/1P1P4/P1PKP3/8 w - - 0 1


critter realises quite soon that white is ahead but after 5 hours is no where near finding the win
30/69 5:32:00 43,981,209,601 2,207,842 +1.35 c2-c4 Re7-b7 e2-e4 Ke8-d8 Kd2-c3 Rb7-f7 a2-a4 Rf7-f1 a4-a5 Rf1-c1+ Kc3-b2 Rc1-d1 Kb2-c2 Rd1-a1 b3-b4 Kd8-d7 Kc2-c3 Kd7-c8 Kc3-d4 Ra1-a3 c4-c5 Kc8-c7 e4-e5 Ra3-a1 e5-e6 Ra1-b1 Kd4-c4 Kc7-c6 a5-a6 Rb1-c1+ Kc4-b3 Rc1-b1+ Kb3-c3 Rb1-c1+ Kc3-b2 Rc1-e1 b4-b5+ Kc6-c7 Kb2-b3 Kc7-b8 b5-b6 Re1xe6 d3-d4 Re6-e3+ Kb3-c4 Re3-a3 a6-a7+ Kb8-a8 d4-d5 Ra3-a1 Kc4-d4 Ra1-a4+ Kd4-d3 Ra4-a5 Kd3-c4 Ra5-a1



the next 2 are draws as they violate one of the last 2 conditions

[D]4r3/4k3/8/8/8/1P1P4/P1PKP3/8 w - - 0 1
[D]4k3/6r1/8/8/8/1P1P4/P1PKP3/8 w - - 0 1

[pPerez]

The software performs a "pre-analysis", which converts the initial position into smaller pieces, and calculates the total number of positions and the required storage space.

When the position is too complex to be pre-analysed, a message is displayed.
It is not caused by a particular hardware limitation of your system. The software will behave the same way on any desktop.

[pPerez]

I know that the software has some graphical interface limitations.

Besides the ones you mentioned, you cannot, for example, enter a FEN position, you cannot flip the board, and you don't have a "back" button to undo moves on the chessboard.

At this moment, the enhancements to improve the generation itself take priority over the graphical user interface enhancements.

The problem is that the program has been developed in assembly language and these things are hard to implement.

However, the possibility of showing next moves after "not available" is not a graphical issue and it can be interesting.
I'll take a look. I think I had a good reason to not show them, but I don't remember why.

Remark: Please, use my email address finalgen@mtu-media.com to make suggestions. I am not sure I will be able to answer to questions on all forums.

[Arpad Rusz]

OK, thanks for your answer.

[IGarcia]

Jouni , the “unexpected error” you got has been caused because the antivirus removed some dll’s and the program could not work properly.

Regards
Pedro Pérez Romero

I have 2 zips:

Code: Select all

FinalGenSetup.zip ( md5= CD66CF1055A409E45961918D708F8AC2 ) Has inside...
FinalGenSetup.exe ( md5= 1CD899434C5436167890B2ECA33C12E2 ) Which installs...
the INFECTED dll ( Avir reports: TR/Kazy.43678 ) in file:
/Program Files/FinalGen/DA_D8.dll 

FinalGenSetup.zip ( md5= EBAC63C1B14629EFEE2C8E02C9104E15 )Has inside...
FinalGenSetup.exe ( md5= 6468FAA24F80551AEDA9B169E8AFA53F ) Which installs...
the  INFECTED dll ( Avir reports: TR/Malob.GX.16 ) in file:
/Program Files/FinalGen/CTDD1.dll 

So far, I don't know which is a false alarm, and which is the real trojan. Would be nice a better explanation. Thanks.

Ignacio