Breakthrough Draughts

[BertTuyt]

Gerard, as you also mentioned, I have a index function without gaps.
So you need to use slightly more difficult mathematics (but doable).
I started with the same approach as you, but with large P DBs the number of illegal positions explode (which is not so relevant when one has 7P - 8P on 10x10).

Bert

[TAILLE]

Gerard, as you also mentioned, I have a index function without gaps.
So you need to use slightly more difficult mathematics (but doable).
I started with the same approach as you, but with large P DBs the number of illegal positions explode (which is not so relevant when one has 7P - 8P on 10x10).

Bert

You are right Bert now I understand and I will change my formula accordindly.
Thank you for your help.

[BertTuyt]

Gerard, did you already generate 10x10 BT DBs?
If so what did you already generate, and how long did it take?

I try to understand if my DB Generator is fast, or needs some clever speed updates.

Bert

[TAILLE]

Gerard, did you already generate 10x10 BT DBs?
If so what did you already generate, and how long did it take?

I try to understand if my DB Generator is fast, or needs some clever speed updates.

Bert

Not yet Bert, I have a lot of coding work before beginnig the generation, even if my experience in international draugths helps!
In order to not be restricted in the future my implementation will allow to handle up to 8G blocks of 4K bytes i.e. up to 32T bytes but I know perfectily that I will be restsricted by the memory available and by the time available!!!

Be sure I will let you know when I will begin a generation.

[Rein Halbersma]

[...] with checkers men can't capture backwards, so a breakthrough is a lot easier to force:



With checkers, white can simply walk through here with h6-g7. With Brazilian draughts (international rules on 8x8 board), it's not possible as black can capture backwards f6xe8.

There's another source of "search inefficiency" in draughts variants with backwards captures:


Here, white-to-move can play b4-c5 d6xb4 a5xc3! and this will make the game a handful of plies longer. Such backward captures do not exist in checkers.

[Rein Halbersma]

Herewith an example.



The following position is obtained after: 1. 23-18 12-16 2. 24-20 10-15 3. 21-17 9-13 4. 26-23 8-12 5. 25-21 5-9

(not sure if this is the official notation,)

The program now finds the win for white:

17-14 15-19 14x5 19x7 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-29 7-10 30-25 3-7 32-28 2-6 22-18 14-17 25-21 17-22 18x25 10-14 31-26 6-10 26-22 12-16 19x12 (DB)

Bert

Bert, may I suggest the following path to attack your end goal?

1) disable both backward captures and majority capture precedence in your 8x8 engine (this reduces the game to Checkers). Just compute your 12P databases as before and then do the forward search. You are much more likely to find a solution in this game then, because of the much stronger convergence (only forward moves and captures).

Extra credits : check Martin Fierz's opening book using his CheckerBoard GUI to see if all the opening moves give the same result as your search. This would confirm the correctness of your search algorithm (or maybe it finds a bug in Martin's solution!).

2) now enable majority capture precedence in your 8x8 engine, but still leave backward capture out (this reduces the game to Italian/Spanish, these games are identical for breakthrough). You should also be able to solve this game in a similar time to Checkers. My hypothesis is that majority capture alone will not have much influence on the solution depth.

3) now enable both majority capture precedence and backward captures (you have back your old International 8x8 engine).

If your program can't yet find a solution to 1) (8x8 checkers BT) then perhaps you might want to rethink your forward search algorithm. Alpha-beta is not the most efficient algorithm for solving games. Martin Fierz used dropout-expansion, a well-documented technique for opening book generation. Ed also uses this technique sometimes to solve very hard middle game positions.

One advantage of dropout-expansion is that it builds a tree in memory and then only does alpha-beta searches on the leaf nodes, propagating the results up to the root. This means that all duplicate positions from the early plies are completely eliminated. This is the same strategy that Aart Bik used to compute his very deep perfts a few years ago. But note that dropout-expansion has a few parameters that you need to tune to give the right shape of the tree that it builds.

[BertTuyt]

Rein, thanks for your suggestions.
In first instance I will anyway focus on the 14P DB. Background of the activity is also to develop a DB Generator which uses all cores, and can deal with very large DBs.
So for the 14P DB, I need to optimize my DB Generator again.

I expect (during holiday now), that I might have something up and running this week, so will keep you all informed.

Bert

[Fabien Letouzey]

Hi Rein,

One advantage of dropout-expansion is that it builds a tree in memory and then only does alpha-beta searches on the leaf nodes, propagating the results up to the root. This means that all duplicate positions from the early plies are completely eliminated. This is the same strategy that Aart Bik used to compute his very deep perfts a few years ago. But note that dropout-expansion has a few parameters that you need to tune to give the right shape of the tree that it builds.

I thought we had been through this. DoE is just one way of doing BFS and they all share the properties that you mention. Unless you use the term dropout expansion in a general sense (that I call BFS).

I know that draughts programmers have DoE in high esteem but I don't; to me its design looks well below average in the (very large) BFS family. The formula to pick the next leaf to expand is ad-hoc (no interpretation) and, if I recall, maximising the expected number of "book plies" fails to follow forced lines deeper (compared to nodes with multiple good moves).

I think the reason for sub-par design is that authors of opening-book construction algorithms missed the connection with BFS for a long time, and kept reinventing the wheel instead. By contrast some BFSs from the 80's-90's are extremely advanced, like BPIP (which is too advanced, believe it or not). And of course, many of them have been created especially to solve games. I think PN-Search is still the go-to algorithm for games without draws, but if I recall it relies on mobility being an important factor.

Fabien.

[Rein Halbersma]

Hi Rein,

One advantage of dropout-expansion is that it builds a tree in memory and then only does alpha-beta searches on the leaf nodes, propagating the results up to the root. This means that all duplicate positions from the early plies are completely eliminated. This is the same strategy that Aart Bik used to compute his very deep perfts a few years ago. But note that dropout-expansion has a few parameters that you need to tune to give the right shape of the tree that it builds.

I thought we had been through this. DoE is just one way of doing BFS and they all share the properties that you mention. Unless you use the term dropout expansion in a general sense (that I call BFS).

I know that draughts programmers have DoE in high esteem but I don't; to me its design looks well below average in the (very large) BFS family. The formula to pick the next leaf to expand is ad-hoc (no interpretation) and, if I recall, maximising the expected number of "book plies" fails to follow forced lines deeper (compared to nodes with multiple good moves).

I don't know what draughts programmers in general think of DOE. It has been used to great effect in Cake/Kingsrow in 8x8 checkers. Ed has also used it in Kingsrow 10x10 draughts. The original paper by Thomas Lincke was very well aware of general BFS strategies. In fact, his PhD thesis has a special section on it (3.4) that discusses the trade-off between best-first and breadth-first, with DOE as a way to interpolate between the two. He specifically didn't design DOE for solving games, only for generating an opening book that makes a tradeoff between best-first and breadth-first, so that the opponent is either kept in book or he has to pay a small eval price to drop out of it.

The use (abuse?) of DOE to solve positions came later when Ed (or maybe others) found that is more efficient than alpha-beta in reaching endgame databases for difficult positions.

I think the reason for sub-par design is that authors of opening-book construction algorithms missed the connection with BFS for a long time, and kept reinventing the wheel instead. By contrast some BFSs from the 80's-90's are extremely advanced, like BPIP (which is too advanced, believe it or not). And of course, many of them have been created especially to solve games. I think PN-Search is still the go-to algorithm for games without draws, but if I recall it relies on mobility being an important factor.

You are absolutely right that the PN family is more suited for solving these type of games. I was suggesting DOE only because Bert has already implemented it and because at least it should be more efficient than plain alpha-beta in trying to solve 8x8 BT. It DOE fails to solve BT in a reasonable time, maybe breaktthrough patterns + PN search will do the job. Who knows

[Fabien Letouzey]

I don't know what draughts programmers in general think of DOE. It has been used to great effect in Cake/Kingsrow in 8x8 checkers. Ed has also used it in Kingsrow 10x10 draughts. The original paper by Thomas Lincke was very well aware of general BFS strategies. In fact, his PhD thesis has a special section on it (3.4) that discusses the trade-off between best-first and breadth-first, with DOE as a way to interpolate between the two. He specifically didn't design DOE for solving games, only for generating an opening book that makes a tradeoff between best-first and breadth-first, so that the opponent is either kept in book or he has to pay a small eval price to drop out of it.

There was a historical accident about the BFS name that is still hurting us today. The "algorithm" cited by Lincke: best-first min-max; let's call it BFMM. I claim that it's not an algorithm, let alone of the BFS family. It becomes stuck if the main line leads to a draw and all deviations have negative heuristic scores; this happened in Othello. Furthermore "Best" in BFS never meant playing the move with highest score at every level. Instead it is related to the additional heuristic function that we have to provide, and will be used to select the next leaf to expand. Maybe "promising" would have been a better term, but it's too late to change that.

Anyway so BFMM was absolutely terrible, a rare mistake by Korf who was usually very interesting (including about evaluation). Lincke improved on it, but that doesn't mean much. Any real BFS algorithm will have all the properties that you have cited, including that "deep vs. wide" tradeoff. So it's not a legitimate DOE selling point IMO (not obvious, because some BFS algorithms like PNS have the tradeoff parameter hardwired into the algorithm). If one looks at the real BFS algorithms (from B* to MCTS) rather than the BFMM accident, the picture is completely different.

[TAILLE]

Herewith an example.



The following position is obtained after: 1. 23-18 12-16 2. 24-20 10-15 3. 21-17 9-13 4. 26-23 8-12 5. 25-21 5-9

(not sure if this is the official notation,)

The program now finds the win for white:

17-14 15-19 14x5 19x7 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-29 7-10 30-25 3-7 32-28 2-6 22-18 14-17 25-21 17-22 18x25 10-14 31-26 6-10 26-22 12-16 19x12 (DB)

Bert

Hi Bert,

Seeing your progress on breakthrough 8x8 I have just built a Damy version for this game.

In order to debug this new version I looked on your sequence (but I do not have any db) and I have a question:
After 17-14 15-19 14x5 19x17 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-19 7-10 30-25 3-7 32-28
you reach (if I do not make a mistake!) the following position


Black to play

How do you win if, instead of 2-6, black plays 11-16 ?

[TAILLE]

Herewith an example.



The following position is obtained after: 1. 23-18 12-16 2. 24-20 10-15 3. 21-17 9-13 4. 26-23 8-12 5. 25-21 5-9

(not sure if this is the official notation,)

The program now finds the win for white:

17-14 15-19 14x5 19x7 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-29 7-10 30-25 3-7 32-28 2-6 22-18 14-17 25-21 17-22 18x25 10-14 31-26 6-10 26-22 12-16 19x12 (DB)

Bert

Hi Bert,

Seeing your progress on breakthrough 8x8 I have just built a Damy version for this game.

In order to debug this new version I looked on your sequence (but I do not have any db) and I have a question:
After 17-14 15-19 14x5 19x17 21x14 6-10 29-25 10x17 25-21 11-15 18x11 17-22 21-17 7-10 17x26 16x7 26-22 4-8 28-24 8-11 27-23 10-14 24-19 7-10 30-25 3-7 32-28
you reach (if I do not make a mistake!) the following position


Black to play

How do you win if, instead of 2-6, black plays 11-16 ?

After some effort I manage to find a bug and now Damy see the win for white after 11-16.

I tried to go backward in the game but I still saw some other bad results. Anyway the prrogress are here!

[TAILLE]

Hi,

After having fixed various bugs my breakthrough 8x8 Damy version seems to work properly.

Let's take the following position from the sequence given by Bert:


Black to play

Damy is able to prove the black loss in 7 minutes (without any db).
I do not know if it is a promising result but of course some more tuning would certainly improve this result.

Anyway I think it is now time to work on db generation program. My intention is not to imitate Bert approach (raw db) but on contrary to work on a strong compression in order to put almost all the db in memory : in other word I would like to replace access time to SSD by a decompression calculation. Who knows what is best ?

[BertTuyt]

Im now in the process of debugging my updated DB-Generate() program.
It is now designed to be scalable from 2P towards 24P, independent of the physical memory, but with the boundary condition that sufficient storage (disk or SSD) is available.
So keep you posted....

Bert

[BertTuyt]

The modified (scalable) DB Generator seems to work now (at least it does not crash anymore).
The 14P DB has been generated (although not yet verified).

A test with selfplay and a 32-ply search, revealed a white win after:
1. 22-18 10-15 2. 25-22 7-10 3. 23-19 9-13 4. 27-23 (and white win detected).

I have now started an infinite search to check if (around ply 40-42) a DB win/loss will be found already at the starting position.

Bert