World Championship Draughts

[Ed Gilbert]

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.

If your egdb files are on a HDD then you definitely do not want the driver to do disk reads in qsearch, as the speed hit is worse than the benefit of having better information. I haven't done any experiments since I acquired an SSD, but I suspect it is the same for those also. It is not necessary to have a db WLD value for every position visited in the search with <= 8 pieces. Alphabeta seems to work fine with the incomplete information. Indeed half of the 8 piece positions visited will not have values in the db because of captures. As long as you probe the db at some or most interior nodes using unconditional (cl = 0) probing, the cache will get loaded with the most useful blocks of data. You should probably experiment with the cl param to lookup() to see what works best for your engine.

-- Ed

[Joost Buijs]

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.

Of course I understand all this, the point is that either reading the database from disk (SSD) or decompressing the database takes the most time, if decompressing takes the most time there is not much you can do besides using a larger cache, if reading from SSD takes the most time a faster SSD on the PCI-E bus could certainly help. SSD's on the PCI-E or M.2 bus have a 3 to 7 times faster data-transfer compared to SSD's on the SATA port, since the database of Ed is rather small a 64 or 128 GB SSD will do. For instance the Samsung SM961 128 GB costs less than 100 bucks and has a read transfer-rate of 3100 MB/s with 330000 IOPS this is ~6 times as fast as the one I'm using now.

[Rein Halbersma]

Of course I understand all this, the point is that either reading the database from disk (SSD) or decompressing the database takes the most time, if decompressing takes the most time there is not much you can do besides using a larger cache, if reading from SSD takes the most time a faster SSD on the PCI-E bus could certainly help. SSD's on the PCI-E or M.2 bus have a 3 to 7 times faster data-transfer compared to SSD's on the SATA port, since the database of Ed is rather small a 64 or 128 GB SSD will do. For instance the Samsung SM961 128 GB costs less than 100 bucks and has a read transfer-rate of 3100 MB/s with 330000 IOPS this is ~6 times as fast as the one I'm using now.

Well, apparently locating the position in RAM takes quite a bit less time than reading it from disk, and there is quite a bit you can do by careful tuning of the "cl" parameter. Because with my HDD, Kingsrow only gets a slowdown to 40% of base compared to your slowdown to 20-25% of base with a SSD.

[Joost Buijs]

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.

If your egdb files are on a HDD then you definitely do not want the driver to do disk reads in qsearch, as the speed hit is worse than the benefit of having better information. I haven't done any experiments since I acquired an SSD, but I suspect it is the same for those also. It is not necessary to have a db WLD value for every position visited in the search with <= 8 pieces. Alphabeta seems to work fine with the incomplete information. Indeed half of the 8 piece positions visited will not have values in the db because of captures. As long as you probe the db at some or most interior nodes using unconditional (cl = 0) probing, the cache will get loaded with the most useful blocks of data. You should probably experiment with the cl param to lookup() to see what works best for your engine.

-- Ed

When I use the data-base there are clearly unwanted effects which are gone when I continue with quiescence till the no capture for both sides criterion is met. For instance when I look at the Woldouby my program finds an EGDB draw at depth 29 but when I continue iterating the draw is suddenly gone, I'm quite sure that these effects are caused by incomplete information. Probing at interior nodes will help to improve this, this is easy to add but I haven't tried it yet. Chess endgame-databases are usually complete, then there is no need to probe at interior nodes at all, this is the situation I was used to before.

I will try to play with the cl parameter to find out when it is useful to probe unconditional (which I use now) or not. It sounds reasonable to probe unconditional at interior nodes and to only use cached values in quiescence.

Most SSD's on the M.2 bus are 3 to 6 times faster than the Samsung 850 Pro I currently use for table-bases, since I already had plans to buy an M.2 SSD I will order one to find out what kind of influence it has on probing your EGDB. Increasing the cache will also help, momentarily I use 16 GB, I can increase this to 48 GB but it makes preloading the database very time consuming (with 16 GB it already takes 66 sec.), I didn't look at the documentation yet to see if there is an option to turn off preloading, probably there is.

Joost

[Joost Buijs]

Of course I understand all this, the point is that either reading the database from disk (SSD) or decompressing the database takes the most time, if decompressing takes the most time there is not much you can do besides using a larger cache, if reading from SSD takes the most time a faster SSD on the PCI-E bus could certainly help. SSD's on the PCI-E or M.2 bus have a 3 to 7 times faster data-transfer compared to SSD's on the SATA port, since the database of Ed is rather small a 64 or 128 GB SSD will do. For instance the Samsung SM961 128 GB costs less than 100 bucks and has a read transfer-rate of 3100 MB/s with 330000 IOPS this is ~6 times as fast as the one I'm using now.

Well, apparently locating the position in RAM takes quite a bit less time than reading it from disk, and there is quite a bit you can do by careful tuning of the "cl" parameter. Because with my HDD, Kingsrow only gets a slowdown to 40% of base compared to your slowdown to 20-25% of base with a SSD.

Yes, I agree that things can be improved, but you have to compare apples to apples. I don't know Kingsrow and what kind of machine you have but from your figures I get the impression that Kingsrow is slower to begin with, if this is true the slow-down will be less because the average DB access-time is more or less constant. I haven't tried HDD at all, maybe the difference is not that big when the cache is large enough and the data is already (pre)loaded, I have no idea but I can try it of course.

Like Ed already suggested it might help to probe in quiescence from the cache only and at interior-nodes to probe unconditionally, in the hope that the data-blocks loaded at the interior nodes are still valid at the quiescence nodes. You will always loose information no matter how careful you tune the cl parameter, for game-play it is probably beneficial to have a somewhat larger depth with less information and for analysis the opposite holds, this is why I personally feel that it is a pity that the data-base doesn't contain positions with captures in it.

Joost

[Ed Gilbert]

Probing at interior nodes gives a lot of early cutoffs. It makes your search more efficient, in addition to getting the egdb cache primed. If you see a db draw, you can return a draw score immediately. Similarly, if you see a db win and beta is less than a db win score, or if you see a db loss and alpha is greater than a db loss score, you can return immediately.

Increasing the cache will also help, momentarily I use 16 GB, I can increase this to 48 GB but it makes preloading the database very time consuming (with 16 GB it already takes 66 sec.), I didn't look at the documentation yet to see if there is an option to turn off preloading, probably there is.

There isn't a lot to be gained by increasing the cache beyond 16gb. You will fill the cache up with more positions having several kings that are not often hit. There is not an option to disable preloading of the cache, but of course it wouldn't be difficult to do if you want to experiment with it. Preloading is most beneficial with a HDD as the data blocks are read sequentially, vs the somewhat random accesses during a search.

for game-play it is probably beneficial to have a somewhat larger depth with less information and for analysis the opposite holds, this is why I personally feel that it is a pity that the data-base doesn't contain positions with captures in it.

Version 1 of the db had more capture information, and was nearly 400gb. I ran a lot of experiments comparing the 2 versions, and in most tests the smaller db resulted in shorter search times to get to a db win, loss, or draw search result. Those tests were with a 16gb cache and HDD. I still have both dbs on my machine, but I never use the larger one anymore except when I am testing the driver.

-- Ed

[Joost Buijs]

Probing at interior nodes gives a lot of early cutoffs. It makes your search more efficient, in addition to getting the egdb cache primed. If you see a db draw, you can return a draw score immediately. Similarly, if you see a db win and beta is less than a db win score, or if you see a db loss and alpha is greater than a db loss score, you can return immediately.

Of course I agree with this, in my Chess program I probe at the interiors as well, what I was trying to say is that with complete information there is no need to probe at the internal nodes because (besides efficiency) it won't alter the outcome of the search, with incomplete information like the missing positions with captures there will be a big difference in the outcome. I will add probing at the interior nodes (just a matter of copy pasting a few lines) and check at the Woldouby if that strange effect seeing a draw at some plies and at others not is gone.

For me it ain't easy to express myself well in English, it is almost 50 years ago that I last had English lessons.

There isn't a lot to be gained by increasing the cache beyond 16gb. You will fill the cache up with more positions having several kings that are not often hit. There is not an option to disable preloading of the cache, but of course it wouldn't be difficult to do if you want to experiment with it. Preloading is most beneficial with a HDD as the data blocks are read sequentially, vs the somewhat random accesses during a search.

Ok, I will leave this like it is, hopefully when I have the M.2 SSD pre-loading the database will be comparably faster.

Version 1 of the db had more capture information, and was nearly 400gb. I ran a lot of experiments comparing the 2 versions, and in most tests the smaller db resulted in shorter search times to get to a db win, loss, or draw search result. Those tests were with a 16gb cache and HDD. I still have both dbs on my machine, but I never use the larger one anymore except when I am testing the driver.

Maybe the additional overhead of the larger TB outweighs the benefits of the more complete information. I don't know if you are willing to share the larger database but I would certainly like to experiment with it if possible.

Joost

[Joost Buijs]

After adding probing the EGDB at interior nodes that strange effect that I saw at the Woldouby is gone like expected and it shows the draw at 28 ply like it should. I changed the unconditional probe-dept to be 5 minimal, remaining depths and quiescence are now cache only, this helps considerably, the slowdown is now a factor ~two. Probing unconditional at smaller depths in the PV only is another option which I want to try.

Atm. my program solves the Woldouby in ~12 seconds (with full evaluation), this is not so bad considering the fact that I have no other means of pruning besides the TT yet.

Code: Select all

info depth 24  score  -114  time    0.35  nodes    12792820  nps  36347799   34-29 23x34 30x39 18-23 39-34 13-18 28-22 23-28 22x13 28x30 25x34 19x08
info depth 25  score  -107  time    0.83  nodes    28311804  nps  34192779   34-29 23x34 30x39 18-23 39-34 13-18 28-22 23-28 22x13 28x30 25x34 19x08
info depth 26  score  -153  time    1.55  nodes    54099792  nps  35013643   34-29 23x34 30x39 18-23 39-34 13-18 28-22 23-28 22x13 28x30 25x34 19x08
info depth 27  score  -119  time    7.45  nodes   286341483  nps  38434538   34-29 23x34 30x39 18-23 39-34 13-18 28-22 23-28 22x13 28x30 25x34 19x08
info depth 28  score     0  time   11.82  nodes   479768402  nps  40593289   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 29  score     0  time   13.81  nodes   569218736  nps  41221183   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 30  score     0  time   16.62  nodes   680551658  nps  40949865   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 31  score     0  time   22.82  nodes   927591095  nps  40646662   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 32  score     0  time   31.30  nodes  1235313004  nps  39471394   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 33  score     0  time   50.22  nodes  1931133700  nps  38456484   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info depth 34  score     0  time   77.94  nodes  2829628526  nps  36303857   34-29 23x34 30x39 12-17 35-30 24x35 33-29 35-40 29-24 19x30 25x45 14-19
info bestmove: 34-29
info pondermove: 23x34
Press any key to continue . . .

[Ed Gilbert]

I don't know if you are willing to share the larger database but I would certainly like to experiment with it if possible.

It's too large to put on the file server. I'm willing to put it on a portable USB hard drive if you want to pay for the drive and shipping.

For me it ain't easy to express myself well in English, it is almost 50 years ago that I last had English lessons.

:-) I know you're kidding because your English is perfect!

-- Ed

[Ed Gilbert]

I changed the unconditional probe-dept to be 5 minimal, remaining depths and quiescence are now cache only, this helps considerably, the slowdown is now a factor ~two. Probing unconditional at smaller depths in the PV only is another option which I want to try.

Yes, I imagine that must work better than your earlier tests. My search is MTD-f so I cannot try the PV idea, but it is something I have always thought would be sound, and in fact I do do something along those lines, but it is so bizarre I don't even want to try to explain it.

-- Ed

[Joost Buijs]

I don't know if you are willing to share the larger database but I would certainly like to experiment with it if possible.

It's too large to put on the file server. I'm willing to put it on a portable USB hard drive if you want to pay for the drive and shipping.

For me it ain't easy to express myself well in English, it is almost 50 years ago that I last had English lessons.

I know you're kidding because your English is perfect!

-- Ed

Strange, I sent you a reply and I went shopping when I came back the reply was gone, this BB automatically logs you out after several minutes of inactivity, I probably missed this.

No I'm not kidding it is 50 years ago since I had English lessons at highschool.

I'm certainly interested in the larger database, later today I will send you a PM.

Joost

[Joost Buijs]

I changed the unconditional probe-dept to be 5 minimal, remaining depths and quiescence are now cache only, this helps considerably, the slowdown is now a factor ~two. Probing unconditional at smaller depths in the PV only is another option which I want to try.

Yes, I imagine that must work better than your earlier tests. My search is MTD-f so I cannot try the PV idea, but it is something I have always thought would be sound, and in fact I do do something along those lines, but it is so bizarre I don't even want to try to explain it.

-- Ed

PV nodes are very sparse in comparison with non PV nodes, probing unconditional in quiescence in the PV probably does not hurt at all, I will try this later on. The same holds for pruning like Futility or LMR, it is usually better to leave the PV nodes untouched and to prune at non PV nodes only, at least with Chess this works very well.

Joost

[Joost Buijs]

Like expected unconditionally probing the EGDB at full dept and quiescence at PV nodes doesn't hurt performance at all, the only thing I have to do now is to determine the best condition when probing at non PV nodes, maybe I have to incorporate evaluation values in the equation. I'm very happy with it as it is right now.

[Rein Halbersma]

Like expected unconditionally probing the EGDB at full dept and quiescence at PV nodes doesn't hurt performance at all, the only thing I have to do now is to determine the best condition when probing at non PV nodes, maybe I have to incorporate evaluation values in the equation. I'm very happy with it as it is right now.

Impressive results! Congrats

[Joost Buijs]

Like expected unconditionally probing the EGDB at full dept and quiescence at PV nodes doesn't hurt performance at all, the only thing I have to do now is to determine the best condition when probing at non PV nodes, maybe I have to incorporate evaluation values in the equation. I'm very happy with it as it is right now.

Impressive results! Congrats

Thanks! Of course all of the work has been done by Ed and I'm just using his database. Basically my search is ready and now I have to add Futility and LMR which are mainly small additions. The point is that I have no understanding of Draughts at all, I don't know anything about piece combinations, combinations that are almost always won or lost, normally you can extract this data from game databases but there seems to be much secrecy with respect to downloading Draughts games. There is the database of Klaas Bor, probably in a proprietary format and I don't know if it is possible to export all of these games to PDN in an easy way.

This thread started about game 3 at WC 2016, yesterday I let my spare 8 core PC run for many hours on the position before 12-18 and stopped it after it reached depth 41 still without a draw score, I will give it another try after I have added pruning because the line that leeds to a 8P EGDB draw seems to be longer than expected.