Search Algorithm

[Joost Buijs]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

With kings on the board there will be many repetitions in the tree and I wonder how effective it is in reducing tree-size to score them as a draw and cutoff that particular branch immediately.

[BertTuyt]

Magicians never reveal their secrets

Bert

[TAILLE]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

With kings on the board there will be many repetitions in the tree and I wonder how effective it is in reducing tree-size to score them as a draw and cutoff that particular branch immediately.

Hi Joost,

Your question is very interesting. Maybe by comparing the performance of our algorithms we will be able to answer it.
Let's take a significant example


White to play

We all know that the position above is a winning position but how efficient is our algorithms to analyse such position with only the 5p egdb ?
My new algorithm is able to detects all loops and I am also wondering if it it was a good idea to developped such functionnality!

By using only the 5p egdb Damy needs 4' to analyse completly the position in order to conclude that 7 moves are winning and 7 moves lead to a draw.

Depending of the performance of your algorithms we can perhaps have an idea of the interest to have a mechanism able to detect loops.
Are you able to perform a complete analyse of this position?

[Joost Buijs]

Magicians never reveal their secrets

Bert

Probably not, but it seems to me that it will help when there are kings on the board, so I will add repetition detection to find out what it does, at least with chess it helps a lot. The drawback is that it will slow down the engine somewhat, the more you add the slower it gets.

Joost

BTW I've added Ed's database to the program, when looking at Woldouby it start seeing the draw at 28 ply, the speed dropped by a factor of 4 but that was more or less expected, maybe I have to probe somewhat less by looking only when the previous move was a capture.
I also have to add printing the PV because it is very difficult right now to get a grasp of what the program is thinking.

Code: Select all

info depth 25  34-29  score  -100  time   1.22  nodes    23220054  nps  18981757
info depth 26  34-29  score  -100  time   1.66  nodes    32895659  nps  19801588
info depth 27  34-29  score  -100  time   2.25  nodes    47753961  nps  21217334
info depth 28  34-29  score     0  time   7.48  nodes   158490309  nps  21183242
info depth 29  34-29  score     0  time  10.60  nodes   235086490  nps  22183237
info depth 30  34-29  score     0  time  15.10  nodes   337709090  nps  22370904

[TAILLE]

Hi,

The same position but Black to play is also a losing position but far easier to analyse.


Black to play

Damy proves the loss in 5" (always with the relevant egdb already in cache).

BTW, with only the 7p db it is far more difficult and Damy needs almost 8' to prove the loss.

OK, now that the magic tricks have been shown, how about a little explanation of the methods that you use?

Hi Rein,

As you perfectly know I experimented for many years standard algorithms, alpha-beta first and then MTD-f procedure but I experiment now new ideas.

First idea:
From that experience I got the feeling that these procedures are nor "natural" and are not quite efficient to detect and explore the best moves. The main problem is the following: on a CUT node you explore only the previous "cutting move" and if it works your are happy not considering the other moves! In reality there is a main drawback with that: you do not have a reliable estimation of the value of the CUT node but only a bound value. As a consequence you may waste a lot of time in the following iterations because you will explore again and again only the "cutting move" where it may exist a far better move which would be handled far more rapidly.
My very first idea is to always give a node the best evaluation taking into account the time allowed to analyse this particular position.

Second idea:
Another strong idea is the following: by changing the order of moves you can reach a position via different variants. Especially if this position is on the PV you will reach this position and the following ones many times (several times during each iterations). That means in particular that you will generate this position, you will calculate its hash and you eventually generate the successors and all that many times. With the technology evolution you can avoid a great part of this job by keeping in memory millions of positions instead of handling a huge hash table.

I developped a lot of other ideas but these are my two main starting ideas. I imagine that you could be disturbed because that means abandonning standard alpha-beta procedure and I confess I hesitated a long time before daring exploring these new ideas.

My intention is certainly not to convince you but to show you an other approach. The first results are here but I have still a lot of work on the table!

[Joost Buijs]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

With kings on the board there will be many repetitions in the tree and I wonder how effective it is in reducing tree-size to score them as a draw and cutoff that particular branch immediately.

Hi Joost,

Your question is very interesting. Maybe by comparing the performance of our algorithms we will be able to answer it.
Let's take a significant example


White to play

We all know that the position above is a winning position but how efficient is our algorithms to analyse such position with only the 5p egdb ?
My new algorithm is able to detects all loops and I am also wondering if it it was a good idea to developped such functionnality!

By using only the 5p egdb Damy needs 4' to analyse completly the position in order to conclude that 7 moves are winning and 7 moves lead to a draw.

Depending of the performance of your algorithms we can perhaps have an idea of the interest to have a mechanism able to detect loops.
Are you able to perform a complete analyse of this position?

Gerard,

Unfortunately not yet, my program doesn't show a PV yet and multi-PV is something I don't care about, I will try to make it more user-friendly over the next few weeks.

Joost

Edit:

Very funny position this is BTW. The 6 piece db says immediately that it is won, but with 5 pieces db it cannot find a win within 32 plies, it makes you wonder why it is so difficult to force a win within 16 moves.
The problem with this position is that the program starts shuffling with the kings back and fort, I guess that with repetition detection the tree will become a lot smaller and that this enables you to look a lot deeper.

[TAILLE]

Magicians never reveal their secrets

Bert

Probably not, but it seems to me that it will help when there are kings on the board, so I will add repetition detection to find out what it does, at least with chess it helps a lot. The drawback is that it will slow down the engine somewhat, the more you add the slower it gets.

Joost

BTW I've added Ed's database to the program, when looking at Woldouby it start seeing the draw at 28 ply, the speed dropped by a factor of 4 but that was more or less expected, maybe I have to probe somewhat less.
I also have to add printing the PV because it is very difficult right now to get a grasp of what the program is thinking.

Code: Select all

info depth 25  34-29  score  -100  time   1.22  nodes    23220054  nps  18981757
info depth 26  34-29  score  -100  time   1.66  nodes    32895659  nps  19801588
info depth 27  34-29  score  -100  time   2.25  nodes    47753961  nps  21217334
info depth 28  34-29  score     0  time   7.48  nodes   158490309  nps  21183242
info depth 29  34-29  score     0  time  10.60  nodes   235086490  nps  22183237
info depth 30  34-29  score     0  time  15.10  nodes   337709090  nps  22370904

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

[Joost Buijs]

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

Well, I mean what I said it starts seeing the draw at depth 28, maybe I should have said it sees the draw at depth 28.
It remains at score 0, even with a lot of extra iterations so the draw is 100% certain (if there are no hidden bugs), I will add printing the PV to get a better idea what the program sees.

At the moment I probe the database every quiet position in quiescence (this slows the speed down 4 times), but it is probably enough to probe only when the previous move was a capture, this will hopefully increase the speed to what it was without probing.

Joost

[TAILLE]

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

Well, I mean what I said it starts seeing the draw at depth 28, maybe I should have said it sees the draw at depth 28.
It remains at score 0, even with a lot of extra iterations so the draw is 100% certain (if there are no hidden bugs), I will add printing the PV to get a better idea what the program sees.

At the moment I probe the database every quiet position in quiescence (this slows the speed down 4 times), but it is probably enough to probe only when the previous move was a capture, this will hopefully increase the speed to what it was without probing.

Joost

Hi Joost,

Oops I expected a reaction of Ed. on this point!
I am not aware of the last improvement in Kingsrow but I remember the following explanation of Ed. for an old version:
A evaluation of zero in the endgame does not mean a 100% sure draw because it may remain some variants which look disadvantageaous but in very very rare occasions they can be winning variants. For that reason Ed. suggested to let kingsrow make at least 2 or 3 other iterations to reduce this rather small risk.
Maybe for the newest version of Kingsrow this risk has totally disappeared but only Ed. can help us.

[Joost Buijs]

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

Well, I mean what I said it starts seeing the draw at depth 28, maybe I should have said it sees the draw at depth 28.
It remains at score 0, even with a lot of extra iterations so the draw is 100% certain (if there are no hidden bugs), I will add printing the PV to get a better idea what the program sees.

At the moment I probe the database every quiet position in quiescence (this slows the speed down 4 times), but it is probably enough to probe only when the previous move was a capture, this will hopefully increase the speed to what it was without probing.

Joost

Hi Joost,

Oops I expected a reaction of Ed. on this point!
I am not aware of the last improvement in Kingsrow but I remember the following explanation of Ed. for an old version:
A evaluation of zero in the endgame does not mean a 100% sure draw because it may remain some variants which look disadvantageaous but in very very rare occasions they can be winning variants. For that reason Ed. suggested to let kingsrow make at least 2 or 3 other iterations to reduce this rather small risk.
Maybe for the newest version of Kingsrow this risk has totally disappeared but only Ed. can help us.

My guess is that this has something to do with pruning, in my case (if the database is correct) it should be real, what beats me is that the database also gives values (win or draw) and (draw or lost) I ignore these values at the moment but it makes you wonder.

Joost

[TAILLE]

Magicians never reveal their secrets

Bert

Probably not, but it seems to me that it will help when there are kings on the board, so I will add repetition detection to find out what it does, at least with chess it helps a lot. The drawback is that it will slow down the engine somewhat, the more you add the slower it gets.

Joost

BTW I've added Ed's database to the program, when looking at Woldouby it start seeing the draw at 28 ply, the speed dropped by a factor of 4 but that was more or less expected, maybe I have to probe somewhat less by looking only when the previous move was a capture.
I also have to add printing the PV because it is very difficult right now to get a grasp of what the program is thinking.

Code: Select all

info depth 25  34-29  score  -100  time   1.22  nodes    23220054  nps  18981757
info depth 26  34-29  score  -100  time   1.66  nodes    32895659  nps  19801588
info depth 27  34-29  score  -100  time   2.25  nodes    47753961  nps  21217334
info depth 28  34-29  score     0  time   7.48  nodes   158490309  nps  21183242
info depth 29  34-29  score     0  time  10.60  nodes   235086490  nps  22183237
info depth 30  34-29  score     0  time  15.10  nodes   337709090  nps  22370904

Hi Joost,

Seeing your phrase "I will add repetition detection" I am wondering if I can help you on this difficult item.
Let's take a quite simple example:


White to play

Consider the following loop
1.7-1 46-5 2.1-7 5-46

Of course this is a loop but the four positions are really winning positions. The question is then the following: as soon as your algorithm build the sequence 1.7-1 46-5 2.1-7 5-46 and supposing you are able to detect the repetition, what kind of information will you store in your hashtable (or elsewhere?) in order to keep in mind this loop detection?

[TAILLE]

Well, I mean what I said it starts seeing the draw at depth 28, maybe I should have said it sees the draw at depth 28.
It remains at score 0, even with a lot of extra iterations so the draw is 100% certain (if there are no hidden bugs), I will add printing the PV to get a better idea what the program sees.

At the moment I probe the database every quiet position in quiescence (this slows the speed down 4 times), but it is probably enough to probe only when the previous move was a capture, this will hopefully increase the speed to what it was without probing.

Joost

Hi Joost,

Oops I expected a reaction of Ed. on this point!
I am not aware of the last improvement in Kingsrow but I remember the following explanation of Ed. for an old version:
A evaluation of zero in the endgame does not mean a 100% sure draw because it may remain some variants which look disadvantageaous but in very very rare occasions they can be winning variants. For that reason Ed. suggested to let kingsrow make at least 2 or 3 other iterations to reduce this rather small risk.
Maybe for the newest version of Kingsrow this risk has totally disappeared but only Ed. can help us.

My guess is that this has something to do with pruning, in my case (if the database is correct) it should be real, what beats me is that the database also gives values (win or draw) and (draw or lost) I ignore these values at the moment but it makes you wonder.

Joost

Here again Ed. can helps us but I think the values (win or draw) and (draw or lost) for kingsrow are only related to the partial 9p db. The point is the following : in a partial egdb it exists a lot of positions for which your are able to say for example that it could not be a losing position but for which you cannot say if it is a draw or a win.
For the 8p db I am sure you have the complete result.

[Joost Buijs]

Magicians never reveal their secrets

Bert

Probably not, but it seems to me that it will help when there are kings on the board, so I will add repetition detection to find out what it does, at least with chess it helps a lot. The drawback is that it will slow down the engine somewhat, the more you add the slower it gets.

Joost

BTW I've added Ed's database to the program, when looking at Woldouby it start seeing the draw at 28 ply, the speed dropped by a factor of 4 but that was more or less expected, maybe I have to probe somewhat less by looking only when the previous move was a capture.
I also have to add printing the PV because it is very difficult right now to get a grasp of what the program is thinking.

Code: Select all

info depth 25  34-29  score  -100  time   1.22  nodes    23220054  nps  18981757
info depth 26  34-29  score  -100  time   1.66  nodes    32895659  nps  19801588
info depth 27  34-29  score  -100  time   2.25  nodes    47753961  nps  21217334
info depth 28  34-29  score     0  time   7.48  nodes   158490309  nps  21183242
info depth 29  34-29  score     0  time  10.60  nodes   235086490  nps  22183237
info depth 30  34-29  score     0  time  15.10  nodes   337709090  nps  22370904

Hi Joost,

Seeing your phrase "I will add repetition detection" I am wondering if I can help you on this difficult item.
Let's take a quite simple example:


White to play

Consider the following loop
1.7-1 46-5 2.1-7 5-46

Of course this is a loop but the four positions are really winning positions. The question is then the following: as soon as your algorithm build the sequence 1.7-1 46-5 2.1-7 5-46 and supposing you are able to detect the repetition, what kind of information will you store in your hashtable (or elsewhere?) in order to keep in mind this loop detection?

Gerard,

It is my intention to return a draw value when this happens, if you keep moving around the result will always be draw, it is standard practice in chess programs, nothing fancy.

Joost

[TAILLE]

Probably not, but it seems to me that it will help when there are kings on the board, so I will add repetition detection to find out what it does, at least with chess it helps a lot. The drawback is that it will slow down the engine somewhat, the more you add the slower it gets.

Joost

BTW I've added Ed's database to the program, when looking at Woldouby it start seeing the draw at 28 ply, the speed dropped by a factor of 4 but that was more or less expected, maybe I have to probe somewhat less by looking only when the previous move was a capture.
I also have to add printing the PV because it is very difficult right now to get a grasp of what the program is thinking.

Code: Select all

info depth 25  34-29  score  -100  time   1.22  nodes    23220054  nps  18981757
info depth 26  34-29  score  -100  time   1.66  nodes    32895659  nps  19801588
info depth 27  34-29  score  -100  time   2.25  nodes    47753961  nps  21217334
info depth 28  34-29  score     0  time   7.48  nodes   158490309  nps  21183242
info depth 29  34-29  score     0  time  10.60  nodes   235086490  nps  22183237
info depth 30  34-29  score     0  time  15.10  nodes   337709090  nps  22370904

Hi Joost,

Seeing your phrase "I will add repetition detection" I am wondering if I can help you on this difficult item.
Let's take a quite simple example:


White to play

Consider the following loop
1.7-1 46-5 2.1-7 5-46

Of course this is a loop but the four positions are really winning positions. The question is then the following: as soon as your algorithm build the sequence 1.7-1 46-5 2.1-7 5-46 and supposing you are able to detect the repetition, what kind of information will you store in your hashtable (or elsewhere?) in order to keep in mind this loop detection?

Gerard,

It is my intention to return a draw value when this happens, if you keep moving around the result will always be draw, it is standard practice in chess programs, nothing fancy.

Joost

Joost,

Look at the "loop detection and hash table" subject I openned in 2010. You will see some issues and a reference to the famous GHI problem.

[Joost Buijs]

Hi Joost,

Seeing your phrase "I will add repetition detection" I am wondering if I can help you on this difficult item.
Let's take a quite simple example:


White to play

Consider the following loop
1.7-1 46-5 2.1-7 5-46

Of course this is a loop but the four positions are really winning positions. The question is then the following: as soon as your algorithm build the sequence 1.7-1 46-5 2.1-7 5-46 and supposing you are able to detect the repetition, what kind of information will you store in your hashtable (or elsewhere?) in order to keep in mind this loop detection?

Gerard,

It is my intention to return a draw value when this happens, if you keep moving around the result will always be draw, it is standard practice in chess programs, nothing fancy.

Joost

Joost,

Look at the "loop detection and hash table" subject I openned in 2010. You will see some issues and a reference to the famous GHI problem.

Gerard,

Discussions about subjects comparable to the one you mention have been going on for ages at the chess forums.

What i'm going to do is to keep track of al the hashes that appear during the game and during the search, secondly I have to maintain a counter that counts all the plies after the last irreversible move, with this information it is very simple to detect a repetition by scanning backwards through the table with hashes using 2 ply steps. This is only needed when there are kings on the board though, so I hope it doesn't have much impact on speed.

I know that in combination with the hash-table there can be an undesirable effect but engine development is always full of compromises.

Joost