World Championship Draughts

[BertTuyt]

In the 3th game Jan Groenendijk - Roel Boomsma, the next position occurred after the 39. move from white (Groenendijk).
Kingsrow indicated -0.72 with as best move for black 12-18.
Is there one of the engines (also Damy) finding the theoretical outcome here?

Bert

[Rein Halbersma]

In the 3th game Jan Groenendijk - Roel Boomsma, the next position occurred after the 39. move from white (Groenendijk).
Kingsrow indicated -0.72 with as best move for black 12-18.
Is there one of the engines (also Damy) finding the theoretical outcome here?

Bert

Kingsrow finds a draw after a minute or so

[TAILLE]

In the 3th game Jan Groenendijk - Roel Boomsma, the next position occurred after the 39. move from white (Groenendijk).
Kingsrow indicated -0.72 with as best move for black 12-18.
Is there one of the engines (also Damy) finding the theoretical outcome here?

Bert

Hi,

When looking at the available analysis on the site of the championship it is clear that the recommended variant begins with
12-18 43-38 8-12

White to play

The site mentions here that 48-42? is a bad move but 45-40! allows to reach the draw.
The complete analysis of this position by Damy takes 25'30":
After 2'30" Damy proves that 45-40 is a draw
After 24'30" Damy proves that 48-42 is also a draw
and after 25'30" Damy completes the analysis and prove that all other moves are losing.

Seeing Kingsrow finds the draw in one minute or so in the position before 12-18 I confess I am very impressed! Could you give us is the corresponding PV up to the egdb?

[Joost Buijs]

In the 3th game Jan Groenendijk - Roel Boomsma, the next position occurred after the 39. move from white (Groenendijk).
Kingsrow indicated -0.72 with as best move for black 12-18.
Is there one of the engines (also Damy) finding the theoretical outcome here?

Bert

Hi,

When looking at the available analysis on the site of the championship it is clear that the recommended variant begins with
12-18 43-38 8-12

White to play

The site mentions here that 48-42? is a bad move but 45-40! allows to reach the draw.
The complete analysis of this position by Damy takes 25'30":
After 2'30" Damy proves that 45-40 is a draw
After 24'30" Damy proves that 48-42 is also a draw
and after 25'30" Damy completes the analysis and prove that all other moves are losing.

Seeing Kingsrow finds the draw in one minute or so in the position before 12-18 I confess I am very impressed! Could you give us is the corresponding PV up to the egdb?

Finding the draw in the position before 12-18 within a minute is very impressive indeed, my current program (with ED's 8P egdb on SSD added) does not find anything useful within a reasonable amount of time.

It takes my program on 10 cores about 96 seconds to reach depth 30 + qs on the position after 12-18 43-38 8-12 (3 plies less) and that is not enough to find a draw. I still didn't add pruning like Probcut and LMR, adding these will presumably gain another 6 to 10 plies maybe after this the draw will come within reach, something I will try pretty soon.

[TAILLE]

In the 3th game Jan Groenendijk - Roel Boomsma, the next position occurred after the 39. move from white (Groenendijk).
Kingsrow indicated -0.72 with as best move for black 12-18.
Is there one of the engines (also Damy) finding the theoretical outcome here?

Bert

Hi,

When looking at the available analysis on the site of the championship it is clear that the recommended variant begins with
12-18 43-38 8-12

White to play

The site mentions here that 48-42? is a bad move but 45-40! allows to reach the draw.
The complete analysis of this position by Damy takes 25'30":
After 2'30" Damy proves that 45-40 is a draw
After 24'30" Damy proves that 48-42 is also a draw
and after 25'30" Damy completes the analysis and prove that all other moves are losing.

Seeing Kingsrow finds the draw in one minute or so in the position before 12-18 I confess I am very impressed! Could you give us is the corresponding PV up to the egdb?

Finding the draw in the position before 12-18 within a minute is very impressive indeed, my current program (with ED's 8P egdb on SSD added) does not find anything useful within a reasonable amount of time.

It takes my program on 10 cores about 96 seconds to reach depth 30 + qs on the position after 12-18 43-38 8-12 (3 plies less) and that is not enough to find a draw. I still didn't add pruning like Probcut and LMR, adding these will presumably gain another 6 to 10 plies maybe after this the draw will come within reach, something I will try pretty soon.

Hi Joost,

Starting now from the initial position:

Black to play

After few seconds Damy shows of course an equal score but we all know perfectly that an equal score is not a sure draw.
In this case I have to wait 15'07" in order to see Damy claiming for a sure draw.

[Joost Buijs]

After few seconds Damy shows of course an equal score but we all know perfectly that an equal score is not a sure draw.
In this case I have to wait 15'07" in order to see Damy claiming for a sure draw.

Hi,

Yes, it is very difficult to find or claim a sure draw, even when the PV looks ok there is still a chance that the program missed something along the line.

At least I can see many problems, for instance the egdb does not contain positions with captures, this more or less forces you to continue with quiescence until there are no captures from either side anymore, if you don't do this you will surely miss things. Another thing is the GHI problem which is very difficult to tackle, especially in a multi-processor program it creates a lot of errors. It is solvable by hashing path information but that makes the transposition-table way less effective.
I spend many days trying to tackle these problems but there is no real solution, I guess I have to leave it alone for now and continue with other stuff like a game playing module and a user interface.

Since you are using BFS instead of DFS you will probably see different problems than the ones I mentioned above, but no matter what algorithm you choose there will always be difficulties (Murphy's Law).

Joost

[Rein Halbersma]

no matter what algorithm you choose there will always be difficulties (Murphy's Law).
Joost

Did you mean "There's no free lunch"? Murphy's Law means something different (anything that can go wrong, will go wrong).

[TAILLE]

After few seconds Damy shows of course an equal score but we all know perfectly that an equal score is not a sure draw.
In this case I have to wait 15'07" in order to see Damy claiming for a sure draw.

Hi,

Yes, it is very difficult to find or claim a sure draw, even when the PV looks ok there is still a chance that the program missed something along the line.

At least I can see many problems, for instance the egdb does not contain positions with captures, this more or less forces you to continue with quiescence until there are no captures from either side anymore, if you don't do this you will surely miss things. Another thing is the GHI problem which is very difficult to tackle, especially in a multi-processor program it creates a lot of errors. It is solvable by hashing path information but that makes the transposition-table way less effective.
I spend many days trying to tackle these problems but there is no real solution, I guess I have to leave it alone for now and continue with other stuff like a game playing module and a user interface.

Since you are using BFS instead of DFS you will probably see different problems than the ones I mentioned above, but no matter what algorithm you choose there will always be difficulties (Murphy's Law).

Joost

Hi,

It is the same with Damy egdb, the capture positions are not in the egdb. The originality of Damy egdb is the following: I have in reality two egdb : one tells me if a position is a winning one and the other tells me if a position is a losing one. You may think I have to make two db accesses if I encounter a draw position but in practice only one access is really interesting. As a consequence this conception is very efficient because I avoid putting in memory unuseful information.
Yes Joost when I was using my MTD-f algorithm I faced also a lot of difficulties with the GHI problem and with the potential loops in general. Now the problem is completely solved with my new algorithm. You are right I had of course to face other problems but because I managed to solve all of them I am now quite satisfied.

I continue to work on my new evaluation process.

[Joost Buijs]

Yes Joost when I was using my MTD-f algorithm I faced also a lot of difficulties with the GHI problem and with the potential loops in general. Now the problem is completely solved with my new algorithm. You are right I had of course to face other problems but because I managed to solve all of them I am now quite satisfied.

In the late nineties I've been experimenting with MTD(f) as well, it was developed bij Aske Plaat who was postdoc at the university where I worked at that time. In practice I never found it to perform better than PVS, after several experiments I abandoned it completely.

[Joost Buijs]

no matter what algorithm you choose there will always be difficulties (Murphy's Law).
Joost

Did you mean "There's no free lunch"? Murphy's Law means something different (anything that can go wrong, will go wrong).

Well, in my view this is more or less the same.

BTW can you show the line that leads to the 8P EGDB draw in the position we were talking about above? My program is not searching deep enough yet or maybe it misses the draw because there are many 8P nodes without EGDB information available.

After playing with it for some time I get the feeling that the distance to the EGDB draw is at least 38 ply or more, without pruning and Ed's EGDB enabled it takes my program several hours to reach that depth and that is a little bit too long to wait for. It is not clear to me whether 39. 12-18 is the best move for black, my program likes 12-17 better (the move that has been played in the actual game).

Probing the EGDB (on the above position) slows my program down by a factor 4 to 5, it goes down from ~100 mnps to 20 a 25 mnps, there probably is not much that can be done to improve this besides adding more memory for cache and a faster SSD on the PCI-E bus.

[Rein Halbersma]

no matter what algorithm you choose there will always be difficulties (Murphy's Law).
Joost

Did you mean "There's no free lunch"? Murphy's Law means something different (anything that can go wrong, will go wrong).

Well, in my view this is more or less the same.

Murphy's Law is way more pessimistic and cynical. If you were invited by someone to a free lunch, then No Free Lunch would mean that there is a hidden cost to paid somewhere else (eg the host might ask you for a favor). Murphy's Law would say that there is no lunch at all, or you would get food poisoning if there was.

But more seriously, I was alluding to a formal No Free Lunch Theorem in the search literature that roughly states that all search algorithms perform equivalently when averaged over the space of problems. So if depth-first search outperforms breadth-first search for a class of problems, there is a price to be paid for that, meaning that there is another class of problems were the performances are reversed.

BTW can you show the line that leads to the 8P EGDB draw in the position we were talking about above? My program is not searching deep enough yet or maybe it misses the draw because there are many 8P nodes without EGDB information available.

Will run it later today.

After playing with it for some time I get the feeling that the distance to the EGDB draw is at least 38 ply or more, without pruning and Ed's EGDB enabled it takes my program several hours to reach that depth and that is a little bit too long to wait for. It is not clear to me whether 39. 12-18 is the best move for black, my program likes 12-17 better (the move that has been played in the actual game).

Probing the EGDB (on the above position) slows my program down by a factor 4 to 5, it goes down from ~100 mnps to 20 a 25 mnps, there probably is not much that can be done to improve this besides adding more memory for cache and a faster SSD on the PCI-E bus.

There is a conditional lookup parameter that needs careful tuning. In your search you should have a function that computes this boolean for every position. The tuning depends on depth (lower remaining depth more likely conditional) current eval vs alpha/beta (how close is eval allready to a win/loss) and the size of ram vs speed of disk access. Perhaps Ed can elaborate.

[Joost Buijs]

Did you mean "There's no free lunch"? Murphy's Law means something different (anything that can go wrong, will go wrong).

Well, in my view this is more or less the same.

Murphy's Law is way more pessimistic and cynical. If you were invited by someone to a free lunch, then No Free Lunch would mean that there is a hidden cost to paid somewhere else (eg the host might ask you for a favor). Murphy's Law would say that there is no lunch at all, or you would get food poisoning if there was.

But more seriously, I was alluding to a formal No Free Lunch Theorem in the search literature that roughly states that all search algorithms perform equivalently when averaged over the space of problems. So if depth-first search outperforms breadth-first search for a class of problems, there is a price to be paid for that, meaning that there is another class of problems were the performances are reversed.

BTW can you show the line that leads to the 8P EGDB draw in the position we were talking about above? My program is not searching deep enough yet or maybe it misses the draw because there are many 8P nodes without EGDB information available.

Will run it later today.

After playing with it for some time I get the feeling that the distance to the EGDB draw is at least 38 ply or more, without pruning and Ed's EGDB enabled it takes my program several hours to reach that depth and that is a little bit too long to wait for. It is not clear to me whether 39. 12-18 is the best move for black, my program likes 12-17 better (the move that has been played in the actual game).

Probing the EGDB (on the above position) slows my program down by a factor 4 to 5, it goes down from ~100 mnps to 20 a 25 mnps, there probably is not much that can be done to improve this besides adding more memory for cache and a faster SSD on the PCI-E bus.

There is a conditional lookup parameter that needs careful tuning. In your search you should have a function that computes this boolean for every position. The tuning depends on depth (lower remaining depth more likely conditional) current eval vs alpha/beta (how close is eval allready to a win/loss) and the size of ram vs speed of disk access. Perhaps Ed can elaborate.

Indeed there is a boolean that tells the probe function to use cached only information, atm. I don't use it because for me there is no way to tell what is in the cache or not. When the evaluation function already shows values that resemble a likely win or loss there probably is no need to probe either, at least not in quiescence.

I spent a lot of time at improving my SMP search, although it is plain YBW it seems to scale well up until 20 cores or even more. I divided the search in a PV and non PV part which makes it somewhat easier to do things like Futility and LMR because I don't want to do these things in the PV and I would like to avoid as many conditionals as possible. I've added repetition-detection, unfortunately it does very little, maybe I'll decide to throw it out because I want to keep the program as simple and clean as possible. Next thing on my todo-list is Futility, Probcut and LMR.

[Rein Halbersma]

There is a conditional lookup parameter that needs careful tuning. In your search you should have a function that computes this boolean for every position. The tuning depends on depth (lower remaining depth more likely conditional) current eval vs alpha/beta (how close is eval allready to a win/loss) and the size of ram vs speed of disk access. Perhaps Ed can elaborate.

Indeed there is a boolean that tells the probe function to use cached only information, atm. I don't use it because for me there is no way to tell what is in the cache or not. When the evaluation function already shows values that resemble a likely win or loss there probably is no need to probe either, at least not in quiescence.

That you don't have access to what is in the cache is rather irrelevant. The default value for conditional lookup is false. This means that if your probe the db, it will first check the RAM cache, but if the position is not in RAM, then it will read its 4kb block from disk. So if you use the vanilla dblookup, you will take a big performance hit. Just prior to your dblookup call, you should compute a boolean based on the expected cost-benefit ratio of doing a disk query in case of a cache miss. That computation should involve depth (the shallower the costlier), the closeness of the eval score to a db value (I would expect that values near +/- 150 are the most interesting to probe), the size of your RAM and the speed of your disk (SSD vs HDD). If a dblookup is not likely to be beneficial, you should pass 1 to the "cl" parameter of dblookup. If the position is in RAM, you get it almost for free, but if it's not in RAM, you don't want to read it from disk.

[BertTuyt]

Probing the EGDB (on the above position) slows my program down by a factor 4 to 5, it goes down from ~100 mnps to 20 a 25 mnps, there probably is not much that can be done to improve this besides adding more memory for cache and a faster SSD on the PCI-E bus.

Joost, I know that Ed use a priority scheme (but I dont have the details), which in some cases (when a 4K DB Block is not loaded) does not read the info but uses a heuristic value. Again lacking details (so even this explanation my my flawed), but this certainly impacts performance in a positive way.

Bert

[Rein Halbersma]

BTW can you show the line that leads to the 8P EGDB draw in the position we were talking about above? My program is not searching deep enough yet or maybe it misses the draw because there are many 8P nodes without EGDB information available.

Will run it later today.

Just ran it again. Apparently my previous statement was based on a "hot" run where I had analyzed the position before, because from a "cold" start it takes almost 4 minutes to get the "=3" score. That is using 8 cores from a 3.5 Ghz Xeon E5, using 16Gb of RAM and a HDD. This searches 11Mnps (compared to 25Mnps when just out of the opening book, so slow down to 40% of full speed).

There's not easy way to find the pv all the way to the 8 db endgames because Kingsrow truncates it. I selected the best move after 5 second searches and it took 40+ plies to get to an 8 pc db. I doubt that was the original pv.