Search Algorithm

[Wieger Wesselink]

white to move

I think this position is a nice challenge for draughts engines. White can win a piece with 32-28, but it takes a deep calculation to establish that it is only a temporary material advantage. To make things more precise: I don't believe 32-28 is the best move for white, but I wonder how many draughts engines are able to confirm that.

[Joost Buijs]

I observed the same, that when playing only with a material based function and endgame databases, I could sometimes draw against competition.
However when losing it was most related to long-term disadvantages far beyond the search horizon (like breakthrough, wing locks, and outposts).

Material only always looses, at least against the top programs. I tried a few times to play against Kingsrow with material only and after each move I see the score from Kingsrow go up and the game is over in less than 20 moves.

On the other hand i also belief when one (for example) constantly could reach 30 ply, than the evaluation knowledge which always should guarantee a draw, could be minimal.
In other words, there must be diminishing returns in the evaluation when search depth explodes.

With current hardware it is not doable to reach 30 ply during the midgame, 22 ply is reachable and with pruning like LMR you will get a few plies more but this is what I call fake depth, something out of one's own pocket, it helps a little because you examine the PV somewhat deeper but you can easily miss a refutation along the line. To get at 30 ply we need computers at least a 100 times faster than we have right now.

I have the impression that many lines in draughts are forced lines, very small paths, the PV almost never changes no matter how deep you look. For instance this is what I see when I look at the position above.

Code: Select all

    m  m  m  m  m
  m  m  m  m  m
    m  m  m  -  m
  -  m  m  -  -
    m  -  m  M  m
  -  -  -  M  -
    M  M  -  M  -
  M  M  M  M  -
    M  M  M  M  M
  M  M  M  M  M

info depth  1  score    34  time    0.00  nodes          25  nps   2096269   21-26
info depth  2  score    20  time    0.00  nodes         116  nps    975456   21-27 31x22
info depth  3  score   122  time    0.00  nodes         270  nps   1202412   23-28 32x23 21-27
info depth  4  score   122  time    0.00  nodes         516  nps   1347282   23-28 32x23 21-27 31x22
info depth  5  score   122  time    0.00  nodes        1194  nps   2052797   23-28 32x23 21-27 31x22 17x30
info depth  6  score   111  time    0.00  nodes        2221  nps   2116279   23-28 32x23 21-27 31x22 17x30 45-40
info depth  7  score   139  time    0.00  nodes        5227  nps   3306764   23-28 32x23 21-27 31x22 17x30 36-31 10-14
info depth  8  score   127  time    0.00  nodes        9163  nps   3607158   23-28 32x23 21-27 31x22 17x30 44-40 30-35 39-33
info depth  9  score   127  time    0.00  nodes       20388  nps   4699516   23-28 32x23 21-27 31x22 17x30 44-40 30-35 39-33
info depth 10  score   127  time    0.01  nodes       37119  nps   5598807   23-28 32x23 21-27 31x22 17x30 44-40 30-35 39-33
info depth 11  score   135  time    0.01  nodes       73721  nps   6042077   23-28 32x23 21-27 31x22 17x30 44-40 30-35 39-33
info depth 12  score   137  time    0.02  nodes      147604  nps   6630008   23-28 32x23 21-27 31x22 17x30 44-40 10-14 37-31
info depth 13  score   138  time    0.04  nodes      293878  nps   6582256   23-28 32x23 21-27 31x22 17x30 45-40 10-14 40-35
info depth 14  score   132  time    0.09  nodes      661227  nps   7341795   23-28 32x23 21-27 31x22 17x30 44-40 10-14 37-32
info depth 15  score   136  time    0.15  nodes     1213086  nps   8256232   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 16  score   129  time    0.23  nodes     2445233  nps  10664527   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 17  score   135  time    0.31  nodes     5047768  nps  16350136   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 18  score   131  time    0.37  nodes     9816334  nps  26331942   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 19  score   136  time    0.60  nodes    27964746  nps  46517172   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 20  score   129  time    0.81  nodes    46266014  nps  57061703   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 21  score   130  time    1.10  nodes    70860855  nps  64145878   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 22  score   131  time    1.71  nodes   124061777  nps  72423342   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 23  score   127  time    3.02  nodes   239948226  nps  79335806   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 24  score   127  time    4.77  nodes   396015913  nps  82967064   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 25  score   127  time    7.95  nodes   680145502  nps  85537166   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 26  score   123  time   18.88  nodes  1673693929  nps  88660482   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 27  score   126  time   29.90  nodes  2660314561  nps  88961789   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 28  score   124  time   62.84  nodes  5596364835  nps  89062791   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 29  score   123  time  112.39  nodes 10057648407  nps  89487688   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 30  score   122  time  211.20  nodes 18962371747  nps  89784704   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 31  score   123  time  361.23  nodes 32575815922  nps  90181268   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 32  score   121  time  772.74  nodes 69914708720  nps  90476713   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 33  score   123  time 1346.77  nodes 121652659669  nps  90329011   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 34  score   121  time 2808.52  nodes 251428779302  nps  89523521   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37
info depth 35  score   122  time 5634.75  nodes 497460485349  nps  88284428   23-28 32x23 21-27 31x22 17x30 37-32 10-14 41-37

But it has often stated here, not losing is not the problem, the challenge is winning....

Maybe the game is not winnable at all when the opponent doesn't make gros mistakes. When I see that I can get several draws against the top engines with a basic search and a simple evaluation function it makes me wonder how large the draw margin is.

Joost

[Fabien Letouzey]

Material only always looses, at least against the top programs. I tried a few times to play against Kingsrow with material only and after each move I see the score from Kingsrow go up and the game is over in less than 20 moves.

I did the test at some point; it was around 500 Elo. Nothing else in the program, pruning included, comes remotely close. I think draughts is more or less "eval only".

Maybe the game is not winnable at all when the opponent doesn't make gros mistakes. When I see that I can get several draws against the top engines with a basic search and a simple evaluation function it makes me wonder how large the draw margin is.

It's enormous. As a rule of thumb, I suggest dividing the Elo scale by 3 compared to other games (including Killer draughts). So a change that "should" gain 60 Elo only gives you 20; it's wearing in the long run. I call that a "black hole" that sucks in anything you could do, but maybe "running in the water" would be a better analogy.

[BertTuyt]

Joost, I think you did the test with black to move.

Bert

[BertTuyt]

I also see that material only does (almost) not work.
But I still believe that with huge search depth, only a limited simple evaluation might be sufficient.
Things like an even distribution of material over left/right wing and middle , not going to early into enemy territory (like 24 and 22 for white), might already work.
And add a simple breakthrough detection, and maybe just piece-square tables.
I need to test this one day, but I would not be surprised with those and ultra deep search one already could play reasonable.
Not enough for winning, but already an interesting draw ratio.

Bert

[Joost Buijs]

Joost, I think you did the test with black to move.

Bert

Bert,

You are right. I didn't notice because I saw the score go up to 1 stone and overlooked 32-28 vs 23-28, of course a draughts player would have noticed, I am used to E2-E4. For fun I will run the test again to see what happens.

Joost

[Joost Buijs]

Material only always looses, at least against the top programs. I tried a few times to play against Kingsrow with material only and after each move I see the score from Kingsrow go up and the game is over in less than 20 moves.

I did the test at some point; it was around 500 Elo. Nothing else in the program, pruning included, comes remotely close. I think draughts is more or less "eval only".

Maybe the game is not winnable at all when the opponent doesn't make gros mistakes. When I see that I can get several draws against the top engines with a basic search and a simple evaluation function it makes me wonder how large the draw margin is.

It's enormous. As a rule of thumb, I suggest dividing the Elo scale by 3 compared to other games (including Killer draughts). So a change that "should" gain 60 Elo only gives you 20; it's wearing in the long run. I call that a "black hole" that sucks in anything you could do, but maybe "running in the water" would be a better analogy.

Your figures are right I guess, no matter what I change in the search and how deep I look the PV almost always remains the same. Yesterday I played a game where I mistakenly gave Kingsrow 10 minutes and my own program 1 minute and surprisingly the game was a draw. With chess this time difference will be ~200 Elo worth but with draughts it doesn't seem to matter much.

I still have to add several things to my evaluation function and tune it, for instance wing-balance is missing and the program has a tendency to move his pieces towards one side of the board which often causes troubles, fortunately this is easy to add but tuning it is a different story.

Joost

[TAILLE]

white to move

I think this position is a nice challenge for draughts engines. White can win a piece with 32-28, but it takes a deep calculation to establish that it is only a temporary material advantage. To make things more precise: I don't believe 32-28 is the best move for white, but I wonder how many draughts engines are able to confirm that.

Hi

Undoubtedly a good challenge for us. I do not know if 32-28 is the best move or not but the primary challenge is the following: are our engines able to see that 32-28 leads only to a temporary advantage?
For the time being the answer is NOT for Damy but I am motivated by this challenge I will study in the context of building my new eval function. Of course I do not know if I will be really able to find something interesting but at least I will try to find a better compromise between exploration and evaluation.

[Joost Buijs]

It's enormous. As a rule of thumb, I suggest dividing the Elo scale by 3 compared to other games (including Killer draughts). So a change that "should" gain 60 Elo only gives you 20; it's wearing in the long run. I call that a "black hole" that sucks in anything you could do, but maybe "running in the water" would be a better analogy.

Ed was very generous to provide me with a version of KingsRow, this enables me to test my engine somewhat easier. Most of the tests I did were at 90 moves an 90 sec. for the whole game with EGDB disabled. At first my engine scored from 25% to 38% depending on the test run, I expected a bug and indeed my root-sort sometimes destroyed the root-movelist. After fixing this the score became more steady in the region of 37.5%, finally I added a very simple version of ProbCut, after this the score is around 45% or higher, the strange thing is that the pruning doesn't seem give much extra depth (maybe 1 or 2 ply) but it is clearly noticeable in playing strength.

After this I tried a match where my program used 45 sec. per move and KingsRow 1 sec. per move, strange enough all games were a draw and my program could not win a single game with a 45 times speed advantage. It makes me wonder why, this is so unusual.

[BertTuyt]

Joost, unless a bug is part of the mystery, I would say that a program draws when it doesnt make the wrong moves, and a program wins when it only makes the best moves against a strong opponent...

Bert

[Joost Buijs]

Joost, unless a bug is part of the mystery, I would say that a program draws when it doesnt make the wrong moves, and a program wins when it only makes the best moves against a strong opponent...

Bert

Maybe I'm used too much to chess, in chess each speed/time advantage clearly helps to win games, and there is of course the possibility that draughts programs are already at the highest level you can achieve with draughts but personally I doubt this. I can clearly see when playing Kingsrow that his evaluation is better, often my program gets into troubles when there are less than 20 discs on the board but most of the time he can calculate his way out.

I played these test matches without EGDB because this seems to me the right way to do it, using EGDB will level the playing field even more, maybe I'm wrong on this and will the use of EGDB help Kingsrow to win the positions where he is clearly better.

When I find some time today to add real time-controls and to add some kind of polling mechanism to stop the search when it stays away for too long I will mail you a link to download the source. It still needs PEXT and PDEP so you have to run it on your 5960X PC, I have some emulation routines inside but these make the program real slow. It uses VS2017, but it seems VS2015 reads the project without problem.

Joost

[Ed Gilbert]

Joost, unless a bug is part of the mystery, I would say that a program draws when it doesnt make the wrong moves, and a program wins when it only makes the best moves against a strong opponent...
Bert

Bert, I agree with the first part of your statement, but not necessarily the second part. I think for a program to win the opponent has to make a mistake. If you play perfectly, but your opponent does not make a bad move, then you cannot win. This is certainly true in 8x8 checkers, and I think it is also true in 10x10.

-- Ed

[BertTuyt]

Ed, think your phrasing is correct.
As Draughts is extremely drawish, the opponent has to make a mistake.
But sometimes the mistake is far from obvious, and you need to play a sequence of very best moves to finally convert to a win.

Bert

[Joost Buijs]

Another problem is how to tune the evaluation function, usually you need win/loss information but if all games you play are drawn there is not much information you will get out of this.

[Ed Gilbert]

Another problem is how to tune the evaluation function, usually you need win/loss information but if all games you play are drawn there is not much information you will get out of this.

I used games played at very fast TC, around 0.1 sec/mv. With those quick searches there are more mistakes made. I think around 20% of the games were decisive.