Search Algorithm

[Joost Buijs]

Joost, impressive results.

Think if you would add the 8P DB from Ed and DB-handler, you would end up with a 0 score
Would be interested what the current computer draughts world record is for solving Woldouby, think that ED has the record but I dont know timing involved.

As Im travelling, I will next weekend implement minimal window search, to compare with your results.

Bert

Yes, my program reaches a nice depth on the Woldouby, on the starting position it is less, I still have to implement pruning to get some additional plies.
I'm almost finished with the SMP implementation but it was getting too warm in my attic (36 deg. C) so I had to quit programming, last year my airco broke down and I didn't replace it yet, these temperatures are very unusual for mid September.

It is very easy to add Ed's data-base to my program, in fact I already did this a couple of weeks ago, I removed it because it generates many Microsoft deprecated function warnings that I first want to resolve, I can tell the compiler that it should not show these warnings but it is neater to change the code, I also want to replace the locks by SRW locks because they are clearly faster.

I don't know anything about Woldouby, I read somewhere that it is not solved yet but that is probably old information, when the SMP is finished I will add Ed's database again and let it run for some time. With a > 30 ply search and 8 piece EGDB it should not be difficult to find the right continuation, it would be very strange if it doesn't.

The branching factor is < 2, I expect that with SMP and 8 cores I will get an additional 3 to 4 plies.

Joost

It is very peculiar what the 4 tier bucket system in the TT implementation does, with 1 tier (write always) I get this:

Code: Select all

info depth 24  score  -100  time   1.44  nodes   15364306  nps 10691630
info depth 25  score  -100  time   2.68  nodes   28063383  nps 10488339
info depth 26  score  -100  time  84.53  nodes  842612743  nps  9967866
info depth 27  score  -100  time 134.98  nodes 1335957637  nps  9897798

Probably it sees a lot of promotions on ply 26 which widen the tree.

With 4 tiers I get this:

Code: Select all

info depth 24  score  -100  time   1.47  nodes   15118089  nps 10253791
info depth 25  score  -100  time   2.47  nodes   24968491  nps 10092773
info depth 26  score  -100  time   4.29  nodes   44160165  nps 10296567
info depth 27  score  -100  time   8.20  nodes   82264946  nps 10037523
info depth 28  score  -100  time  16.05  nodes  162871427  nps 10145752
info depth 29  score  -100  time  29.57  nodes  292194146  nps  9882417
info depth 30  score  -100  time  52.17  nodes  519372911  nps  9955528

Several different positions seem to map to the same index, the Zobrist numbers and hash function have a very big influence on this, I can calculate my index in a different way to get as much variety as possible, this will effectively lower the key-size to 56 bits because I store the depth information in the lower 8 bits.

I've added promotions to the quiescence search and now it finds the loss of that one stone at ply 13 instead of ply 14.

I replaced the C++11 built in Mersenne-twister with my own implementation of a 64 bit Marsaglia-kiss random generator and that performs a little bit better.

Code: Select all

info depth 24  score  -100  time   1.43  nodes   15118089  nps 10541958
info depth 25  score  -100  time   2.41  nodes   24968498  nps 10372101
info depth 26  score  -100  time   4.18  nodes   44160271  nps 10552695
info depth 27  score  -100  time   7.75  nodes   79842189  nps 10299995
info depth 28  score  -100  time  14.97  nodes  155627410  nps 10393390
info depth 29  score  -100  time  27.98  nodes  283075258  nps 10115454
info depth 30  score  -100  time  50.54  nodes  513950980  nps 10169328

With a few exceptions I don't like that C++11 library stuff at all, it is nice for portability but you are always depending on bad implementations of RTL, and I have no interest in programming for Linux either. Maybe I'm old school.

[BertTuyt]

It is very peculiar what the 4 tier bucket system in the TT implementation does, with 1 tier (write always) I get this:

Joost, just for curiousity, did you also increase the hashtable with a factor 4, to maintain the same number of entries?

Bert

[Joost Buijs]

It is very peculiar what the 4 tier bucket system in the TT implementation does, with 1 tier (write always) I get this:

Joost, just for curiousity, did you also increase the hashtable with a factor 4, to maintain the same number of entries?

Bert

Bert,

No, the size of the hash-table remains the same, the difference is that with more then 1 entry per bucket you have a means of replacing the worst entry in the bucket by an other one and with a single entry system you can only decide to write or not to write.
When the entry that I want to write is already in the bucket I have to update it, I do this in two ways, I remember the pointer from the previous load on the same node, if the pointer is valid I write to that address immediately or in the second case I have to check the 4 entries in the bucket for a match and to determine the worst one to replace which I can use in case there is no match at all.

I have SMP working , the results are not very good yet, the speedup is 4.5 to 5, the branching factor is low compared to chess, this makes it difficult to keep the processors busy, I still have to optimize it, maybe omitting splitting on nodes with captures or a low number of moves will help, at least I hope to get it better than it is now.
On the starting position the speedup is somewhat better (about 5.5 to 6), this is probably due to the branching-factor.
There is also some false-sharing which can be improved, maybe I have to put some stuff in TLS.

While playing with it I found that on the Woldouby at depth 31 you loose a second men, score goes down to -200, very interesting to examine this a little further.

Joost

Code: Select all

info TT: bucket_size: 64  num_buckets: 16777216, total_size: 1073741824
info Pages can be locked in memory!
info Allocated transposition table with size 1073741824 in small pages.
info size of position_t: 64
info size of thread_t: 64
info sizeof splitpoint_t: 1152
info size of smp_t: 1
info Starting threads  0  1  2  3  4  5  6  7

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

info depth  1  score     0  time   0.00  nodes         16  nps   312500
info depth  2  score     0  time   0.00  nodes         72  nps   308840
info depth  3  score     0  time   0.00  nodes        142  nps   481499
info depth  4  score     0  time   0.00  nodes        242  nps   712547
info depth  5  score     0  time   0.00  nodes        503  nps  1158516
info depth  6  score     0  time   0.00  nodes        863  nps  1703720
info depth  7  score     0  time   0.00  nodes       1625  nps  2462877
info depth  8  score     0  time   0.00  nodes       2749  nps  3264576
info depth  9  score     0  time   0.00  nodes       5761  nps  5083713
info depth 10  score     0  time   0.00  nodes      10692  nps  7069333
info depth 11  score     0  time   0.00  nodes      20645  nps  9900702
info depth 12  score     0  time   0.00  nodes      34566  nps 11965918
info depth 13  score  -100  time   0.01  nodes     194586  nps 21064778
info depth 14  score  -100  time   0.01  nodes     232181  nps 21586673
info depth 15  score  -100  time   0.01  nodes     306215  nps 23783513
info depth 16  score  -100  time   0.02  nodes     411386  nps 25410222
info depth 17  score  -100  time   0.02  nodes     593435  nps 27572418
info depth 18  score  -100  time   0.03  nodes     781341  nps 28308883
info depth 19  score  -100  time   0.06  nodes    2067603  nps 31941730
info depth 20  score  -100  time   0.08  nodes    2753554  nps 32853256
info depth 21  score  -100  time   0.11  nodes    3871379  nps 33801614
info depth 22  score  -100  time   0.17  nodes    5850064  nps 35255706
info depth 23  score  -100  time   0.26  nodes    9175566  nps 35649446
info depth 24  score  -100  time   0.40  nodes   15042329  nps 37346973
info depth 25  score  -100  time   0.63  nodes   24596721  nps 38814616
info depth 26  score  -100  time   1.01  nodes   43276178  nps 42946103
info depth 27  score  -100  time   1.84  nodes   77092694  nps 42002669
info depth 28  score  -100  time   3.02  nodes  139800876  nps 46237893
info depth 29  score  -100  time   6.10  nodes  271898763  nps 44561416
info depth 30  score  -100  time  10.26  nodes  495022051  nps 48264752
info depth 31  score  -200  time  33.38  nodes 1430640198  nps 42854428
info depth 32  score  -200  time  57.53  nodes 2659921633  nps 46236742

[ildjarn]

While playing with it I found that on the Woldouby at depth 31 you loose a second men, score goes down to -200, very interesting to examine this a little further.

According to Ed, Woldouby is a draw: viewtopic.php?p=56259&highlight=woldouby#56259
And a later discussion on Meijer-Jansen: viewtopic.php?f=53&t=2586&start=30
And a game from 2015 which ended in a fast draw: http://www.ericsdamsite.com/damrubriek_ ... r_2015.htm

[Joost Buijs]

While playing with it I found that on the Woldouby at depth 31 you loose a second men, score goes down to -200, very interesting to examine this a little further.

According to Ed, Woldouby is a draw: viewtopic.php?p=56259&highlight=woldouby#56259
And a later discussion on Meijer-Jansen: viewtopic.php?f=53&t=2586&start=30
And a game from 2015 which ended in a fast draw: http://www.ericsdamsite.com/damrubriek_ ... r_2015.htm

If the data-base is correct and the search doesn't throw variations away by pruning it is a draw, I've not added a function to show the principal variation yet, so for me it is very hard to tell what my program sees at depth 31.

With kings on the board there will be repetitions as well, my program does not detect this yet, I still have to implement the things below:

6.1. A game is considered a draw when the same position occurs for the third time, with the same player having to move.
6.2. If during 25 successive moves, only the kings have moved, without any man moving or without any capture, the game is considered drawn.
6.3. If only three kings remain, two king plus a man, one king and two men, against one king, the game shall be considered a draw when the players have each played another sixteen moves maximum.
6.4. The end game with two kings, one king and a man, or one king against one king will be considered a draw when the players have each played another five moves maximum.

I will only implement the first two rules, the last two seem very fuzzy to me.

[ildjarn]

6.3. If only three kings remain, two king plus a man, one king and two men, against one king, the game shall be considered a draw when the players have each played another sixteen moves maximum.
6.4. The end game with two kings, one king and a man, or one king against one king will be considered a draw when the players have each played another five moves maximum.

I will only implement the first two rules, the last two seem very fuzzy to me.

Databases have shown that the maximum win depth for these two endgames is 16 and 5. See e.g. https://mdgsoft.home.xs4all.nl/draughts ... index.html

[Ed Gilbert]

According to Ed, Woldouby is a draw: viewtopic.php?p=56259&highlight=woldouby#56259

When I did that analysis a few years ago kingsrow did not reach the search depths that it does now. I had to play down a few plies in each continuation to see the draw. Now it can see a database draw from the start position in about a minute. But only using the 8-piece db. Using the 7-piece db it cannot see a database draw.

-- Ed

[Ed Gilbert]

It is very easy to add Ed's data-base to my program, in fact I already did this a couple of weeks ago, I removed it because it generates many Microsoft deprecated function warnings that I first want to resolve, I can tell the compiler that it should not show these warnings but it is neater to change the code

Microsoft can call functions like sprintf and fopen deprecated, but they are part of the C standard library and they aren't going away. IMO they are complaining excessively. There's no problem with these functions when used properly. I also think the replacements that they suggest are not portable. The macro that turns off the warnings is in the example program's project file, but maybe I will move this to the egdb library project header file so that other users wont have to add it to their projects.

-- Ed

[Joost Buijs]

It is very easy to add Ed's data-base to my program, in fact I already did this a couple of weeks ago, I removed it because it generates many Microsoft deprecated function warnings that I first want to resolve, I can tell the compiler that it should not show these warnings but it is neater to change the code

Microsoft can call functions like sprintf and fopen deprecated, but they are part of the C standard library and they aren't going away. IMO they are complaining excessively. There's no problem with these functions when used properly. I also think the replacements that they suggest are not portable. The macro that turns off the warnings is in the example program's project file, but maybe I will move this to the egdb library project header file so that other users wont have to add it to their projects.

-- Ed

These warnings are indeed very annoying and with each new compiler release they get more aggressive, they have added it to their headers with a deprecated pragma, so you have to define _CRT_SECURE_NO_WARNINGS and _CRT_SECURE_NO_WARNINGS_GLOBALS somewhere before you load the headers.

Another reason that I temporary removed your EGDB code is that it is rather large and it take quite some time to compile, even with /MP, at the moment I'm busy debugging my SMP code, although SMP works there are still some glitches I have to resolve and then it really makes a difference if I can compile the program in 1 second or 10 seconds.

Joost

[BertTuyt]

Joost, could you also post search results for the initial position, than I can compare this with my implementation so far when I have time during the weekend to program.

Bert

[Joost Buijs]

Joost, could you also post search results for the initial position, than I can compare this with my implementation so far when I have time during the weekend to program.

Bert

Bert,

This is at the starting position, single core, SMP is broken at the moment because I'm working on it.
There is no pruning yet, only the hash-table, 2 killers and history, and I added promotions to QS.

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  M  M

info depth  1  score     0  time   0.00  nodes         10  nps   321944
info depth  2  score     0  time   0.00  nodes         40  nps   178639
info depth  3  score     0  time   0.00  nodes        245  nps   866876
info depth  4  score     0  time   0.00  nodes        588  nps  1719218
info depth  5  score     0  time   0.00  nodes       1620  nps  3515624
info depth  6  score     0  time   0.00  nodes       3358  nps  5142650
info depth  7  score     0  time   0.00  nodes       8802  nps  8262450
info depth  8  score     0  time   0.00  nodes      17542  nps  9606088
info depth  9  score     0  time   0.00  nodes      42082  nps 11839728
info depth 10  score     0  time   0.01  nodes      81997  nps 12255780
info depth 11  score     0  time   0.01  nodes     181113  nps 13411971
info depth 12  score     0  time   0.03  nodes     354842  nps 13554501
info depth 13  score     0  time   0.05  nodes     758354  nps 14240462
info depth 14  score     0  time   0.11  nodes    1480268  nps 13807127
info depth 15  score     0  time   0.24  nodes    3343835  nps 13933416
info depth 16  score     0  time   0.51  nodes    6751733  nps 13305466
info depth 17  score     0  time   1.13  nodes   15280816  nps 13573343
info depth 18  score     0  time   2.38  nodes   31180357  nps 13119177
info depth 19  score     0  time   5.30  nodes   70936054  nps 13393410
info depth 20  score     0  time  11.26  nodes  145297647  nps 12908006
info depth 21  score     0  time  25.23  nodes  328207950  nps 13008404
info depth 22  score     0  time  54.42  nodes  672132716  nps 12350025

[BertTuyt]

Joost, thanks.

For my understanding, with/without aspiration window (as a 1, -1 window is very effective when score is always 0)?
And how many 4-entry hash buckets. (thought total size was 1 GByte for the total hash table).

Bert

[Joost Buijs]

Joost, thanks.

For my understanding, with/without aspiration window (as a 1, -1 window is very effective when score is always 0)?
And how many 4-entry hash buckets. (thought total size was 1 GByte for the total hash table).

Bert

Yes that is true, I count material so inside the three the scores are not always zero, when I add small random values to my evaluation table it makes a difference of about 1 ply less on Woldouby and 2 ply less on the initial position, random values are probably the worst case scenario.

Since it PVS I search the first move on a PV-node usually with a wider window (alpha, beta) and later moves with (alpha, alpha+1),
when you find a score > alpha and < beta you have to research with (alpha, beta) or (score, beta), I research with (alpha, beta), a tiny bit less efficient but in practice it gives less search instability. For negamax the windows are of course (-beta, -alpha) and (-(alpha+1), -alpha) etc.

In my case an entry is 16 bytes a bucket is 64 bytes, a total of (1024 MB / 64) = 16777216 buckets.

Joost

[Joost Buijs]

Bert,

SMP is more or less stable now but I still have to clean it up because it is rather messy, the speedup is around 5 on 8 cores, with hyper-threading it is even better and it does over 80 mnps, but the time to depth with HT is not that much better.
I guess that with a core i7-6950X or with a dual Xeon it will be possible to surpass 100 mnps.

It is difficult to get a good speedup with draughts, many nodes have just a few moves available and they are not worth splitting on, so it is difficult to keep the processors busy all the time.

Code: Select all

info TT: bucket_size: 64  num_buckets: 16777216, total_size: 1073741824
info Pages can be locked in memory!
info Allocated transposition table with size 1073741824 in large pages.
info size of position_t: 64
info size of thread_t: 64
info sizeof splitpoint_t: 1152
info size of smp_t: 1
info Starting threads  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

    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  M  M

info depth  1  score     0  time   0.00  nodes         10  nps   430836
info depth  2  score     0  time   0.00  nodes         40  nps   186012
info depth  3  score     0  time   0.00  nodes        245  nps   319863
info depth  4  score     0  time   0.00  nodes        588  nps   369193
info depth  5  score     0  time   0.00  nodes       1620  nps   781893
info depth  6  score     0  time   0.00  nodes       3358  nps  1325681
info depth  7  score     0  time   0.00  nodes       8802  nps  2801422
info depth  8  score     0  time   0.00  nodes      17696  nps  4815056
info depth  9  score     0  time   0.00  nodes      44311  nps  9567900
info depth 10  score     0  time   0.01  nodes      89874  nps  9336306
info depth 11  score     0  time   0.01  nodes     202038  nps 15024563
info depth 12  score     0  time   0.02  nodes     408515  nps 23741723
info depth 13  score     0  time   0.02  nodes     856988  nps 35375493
info depth 14  score     0  time   0.04  nodes    1663082  nps 46231641
info depth 15  score     0  time   0.06  nodes    3799404  nps 61497212
info depth 16  score     0  time   0.12  nodes    7699783  nps 66728211
info depth 17  score     0  time   0.22  nodes   17324238  nps 77415073
info depth 18  score     0  time   0.46  nodes   35353235  nps 76409557
info depth 19  score     0  time   0.98  nodes   81853765  nps 83248743
info depth 20  score     0  time   2.18  nodes  171390410  nps 78521409
info depth 21  score     0  time   4.66  nodes  405023489  nps 86886534
info depth 22  score     0  time  10.31  nodes  846668716  nps 82112794
info depth 23  score     0  time  23.28  nodes 2024310305  nps 86969487
info depth 24  score     0  time  55.11  nodes 4424729841  nps 80292590

[Joost Buijs]

Bert,

The rest of this month I don't have much time to spend on draughts, a pity because I really want to continue with the program, the last few weeks I spent a lot of time on it and neglected other obligations, the SMP-search is working now so it is time to catch up with other things.
Usually I take a peek here every day, if you have questions or want to compare things this is always possible.

Joost