Search Algorithm

[Krzysztof Grzelak]

Due to limited resources here in Switzerland, Im only able to resolve some bugs in the GUI.

But maybe that's also good, as I'm adding too much GUI functionality, and it would be welcome to create a stable GUI.
At least I have now solved the bug (I hope) that no pieces are displayed when you start the GUI in maximum mode.

Krzysztof if you want I can provide access to the latest GUI for testers like you, so you can verify on your system that the bug has disappeared. Just drop me a PM post and I will provide you with the link.
This weekend I will also continue with debugging the GUI DXP implementation.

Bert

Thank you, Bert. I sent a request to PM.

[BertTuyt]

During Xmas vacation I was doing some calculations on possible draughts positions in the draughts universe.
A topic which we have discussed several times.

This occasion I was focused on practical positions where all the material from one side is only in the first X rows.
In the attached picture the number of unique positions for a 20man - 20man position.
The number of rows in the calculation starts with the bottom row for every side.
The theoretical maximum is calculated as 2 * combin(5 * row, 20) * combin( 5 * row,20).

For the initial position (and all 20m-20m positions) the factor 2 can be (basically) omitted (but not done in this formula), but as the game processes (and symmetry is broken) many positions can be realized with both colors.
Also the combin * combin is basically a simplification , and only true for 5 rows.

In general already quite some interesting positions occur when all material is in the first 5 rows (from each color perspective), and maximal 1 piece in the 6th row.
If I have time I will do this math (and simulation/calculation) for 20 - 20.

The interesting question for me is the number of position (with same boundary conditions) for 19-19, 18-18 ---> 10-10.
My initial guess for every group around 10^11 to 10^12, which seems to be still unpractical.

Bert

[BertTuyt]

Fast calculation/simulation: if one adds to the 5 possible rows square 25 for white and square 26 for black (so both have 26 possible locations), then the count (excluding captures and capture threads) become 32.690.082 = 3.3E+07.

Bert

[BertTuyt]

I was able to count (hope without errors) the number of positions for a 19 man - 19 man configuration, with the next boundary conditions:
1) All black pieces on squares 1 - 25.
2) All white pieces on squares 26 - 50.
3) A piece can only move to an illegal squares (so outside his territory) through a capture.
4) The positions counted in the end, are static (so no capture or capture thread).

In below picture the number of 19m-19m possibilities.
I was not able to test, if based on these conditions, board configurations can occur with the same material position but opposite colors to move, or that equal positions occur at another breadth first depth.
So for now this number is a maximum.

During the breadth first search the maximum number of positions in the queue was 407M.
With this method I'm not (yet) able to calculate the size for 18m -18m.
But if one assumes that the ratio between theoretical maximum (based on combination calculation) certainly does not reduce, then the lower bound for 15m-15m is around 4.4 E+11.
I hope that I'm also able to calculate the 19m-19m expanded with the 26 square for black and the 25 square for white, as many practical positions are known from actual games.

Bert

[TAILLE]

Hi,

It is a good motivation for all programmers to see that a lot of progress can still be made.

After having used for many years the very classical alpha-beta and MTD-f procedure, with numerous and various improvments, I have worked these last months on a totally different algorithm and I am wondering if my approach can be a good alternative.

Can you test your programm on the following position?


Black to move

For Damy new algorithm the result is the following (I use a quad and the 8 pieces db)
Damy find the good move after 3'15"
Damy prove the win after 12'

Thank you for your answer

Gérard

[Rein Halbersma]

For Damy new algorithm the result is the following (I use a quad and the 8 pieces db)
Damy find the good move after 3'15"
Damy prove the win after 12'

Thank you for your answer

Gérard

Did you try it with Kingsrow? By how much percent does the new Damy algorithm improve on Kingsrow's solution?

[TAILLE]

Hi Rein,

I did not really manage to test Kingsrow on this position because I installed Kingsrow on another machine and I suspect that I have some ununderstandable performance problems on this machine. As a consequence Kingsrow is not able to find the good move.

Of course I know that in the draughts community it exists many strong machines on which Kingsrow or other strong program runs.

I addressed here my previous post for two reasons. Firstly to let you know that I continue to work and test new ideas and secondly to have some return in order to compare Damy to other programs.

Gérard

[Krzysztof Grzelak]

Analysis of programme Kingsrow.

Opinion of position 336 on depth 29 as well as the variant.

20-9 29-24 9-4 24-20 25x14 27-22 14-20 22-17 20-25 33-28 26-31.

Opinion what some time oneself enlarges.

[BertTuyt]

First of all , welcome back Gerard!

As I live and work abroad these days, I only have a slow and old notebook here.
And only with a 6P DB.
After 94.64 seconds it finds 20-3, but still not decisive.
Is your time in minutes or seconds?
So whats the right move?

Bert

[TAILLE]

Hi Bert,

No Bert, 20-3 is not the right move and leads to the draw after 29-24!
For your information the winning move is 20-9!

I do not know the algorithm you use but I confess I will be very impressed i you can demonstrate the win with a small machine and only the 6 pièces db!

[TAILLE]

Oops I forgot to tell you that my figures are in minutes so:
3 minutes 15s to find the right move 20-9!
12 minutes to prove the win

[TAILLE]

Analysis of programme Kingsrow.

Opinion of position 336 on depth 29 as well as the variant.

20-9 29-24 9-4 24-20 25x14 27-22 14-20 22-17 20-25 33-28 26-31.

Opinion what some time oneself enlarges.

This sequence is correct.
My initial question concerned the time to prove the win. Can you tells the number of minutes needed by Kingrow to prove the win?

[Krzysztof Grzelak]

This sequence is correct.
My initial question concerned the time to prove the win. Can you tells the number of minutes needed by Kingrow to prove the win?

He movement 20-9 was indicated by programme in 35,5 second. And variant in 116 second.

[TAILLE]

This sequence is correct.
My initial question concerned the time to prove the win. Can you tells the number of minutes needed by Kingrow to prove the win?

He movement 20-9 was indicated by programme in 35,5 second. And variant in 116 second.

I clearly understand that Kingsrow found the sequence in 116 second. Is it a good understanding that Kingsrow not only found this sequence but at the same time Kingsrow prove the win?

[Rein Halbersma]

Hi Rein,

I did not really manage to test Kingsrow on this position because I installed Kingsrow on another machine and I suspect that I have some ununderstandable performance problems on this machine. As a consequence Kingsrow is not able to find the good move.

Of course I know that in the draughts community it exists many strong machines on which Kingsrow or other strong program runs.

I addressed here my previous post for two reasons. Firstly to let you know that I continue to work and test new ideas and secondly to have some return in order to compare Damy to other programs.

Gérard

I found more or less the same result that Krzysztof reported. But I have some doubts regarding the usefulness of search algorithms designed to solve particular endgames. It is well known that there exist algorithms (such as proof-number search) that are more efficient to prove results than the alpha-beta family. In regular game play, however, these solvers are not as strong. So question to you: how much ELO did you gain from your special purpose algorithm?