Search Algorithm

[BertTuyt]

Joost,

thanks.
Fully recognize this.
I mainly want to program in the weekend, limited time during the week.
But this hobby and social obligations do not always match
As I need also to catch up with (business) work, I hope I have time to test a few things.
Will keep you posted...

Bert

[BertTuyt]

Joost, I had almost not time for programming this weekend.
Anyway I implemented also PVS, with a write always hashtable (including flags for PV-Node, All-Node, and Cut-Node).
I didnt test the implementation is details.
The HashTable has 2M entries.
No sort, No history, No Killers, only the best Move from the hash.

If you switch off aforementioned options (which I did not include) are results (on a relatively slow notebook) than comparable with your program?

Note: I also dont use an aspiration window (the initial window is -5000, 5000), and I have iterative deepening, where I dont clear the node counter in between iterations.

Bert

Code: Select all

id name Dwarf 0.0
id author Draughts Community
ready
HashTable Allocated, Entries = 2097152
pos XW XB 10 10
info D 1 S 0 N 17 T 0 knps 0
info D 2 S 0 N 96 T 0.015 knps 6
info D 3 S 0 N 152 T 0.015 knps 10
info D 4 S 0 N 231 T 0.021 knps 11
info D 5 S 0 N 446 T 0.031 knps 14
info D 6 S 0 N 773 T 0.032 knps 24
info D 7 S 0 N 1461 T 0.033 knps 44
info D 8 S 0 N 2480 T 0.034 knps 72
info D 9 S 0 N 4846 T 0.042 knps 115
info D 10 S 0 N 7721 T 0.049 knps 157
info D 11 S 0 N 13614 T 0.051 knps 266
info D 12 S 0 N 24480 T 0.053 knps 461
info D 13 S 0 N 39149 T 0.057 knps 686
info D 14 S -100 N 118970 T 0.069 knps 1724
info D 15 S -100 N 190156 T 0.081 knps 2347
info D 16 S -100 N 399803 T 0.112 knps 3569
info D 17 S -100 N 665481 T 0.148 knps 4496
info D 18 S -120 N 1305722 T 0.229 knps 5701
info D 19 S -100 N 1633240 T 0.272 knps 6004
info D 20 S -100 N 2107611 T 0.333 knps 6329
info D 21 S -100 N 3036040 T 0.451 knps 6731
info D 22 S -100 N 13500240 T 1.693 knps 7974
info D 23 S -100 N 22578102 T 2.77 knps 8150
info D 24 S -100 N 81028295 T 9.636 knps 8408

[Joost Buijs]

Bert,

At the moment I'm not at home, tomorrow I can do the comparison, I guess in that case I have to turn of promotions in quiescence.
I also count all nodes and don't clear the counter between iterations, my window is initially (-15000, 15000) and I switch to score + (-50, 50) after the first iteration, when I find a fail-high or a fail-low I have to research that node with a wider window, at the moment it is very simple (-15000, score + 50) or (score - 50, 15000);
Of course this has to be improved, but for the time being I will leave it like this because I first want to get my engine playing.

Joost

[BertTuyt]

Joost, thanks for a honest comparison you should also turn off Killers and History.

Bert

[Joost Buijs]

Joost, thanks for a honest comparison you should also turn off Killers and History.

Bert

Bert,

Here are my results on Woldouby at 4GHz., 2 GB hash with single entries, no killers, no history and no large pages, window (-5000, 5000).
I disabled the positional evaluation, the only difference is that I use a value of 300 for kings instead of 320, of course this has some effect.
I think the results are quite comparable, you will always have small differences in hashing and order of generating moves and that has influence on tree-size.

Joost

Code: Select all

info depth  1  score     0  time   0.00  nodes         17  nps  1285656
info depth  2  score     0  time   0.00  nodes         97  nps   492105
info depth  3  score     0  time   0.00  nodes        157  nps   699393
info depth  4  score     0  time   0.00  nodes        244  nps   954845
info depth  5  score     0  time   0.00  nodes        511  nps  1736414
info depth  6  score     0  time   0.00  nodes        880  nps  2541490
info depth  7  score     0  time   0.00  nodes       1772  nps  4206175
info depth  8  score     0  time   0.00  nodes       3011  nps  5525750
info depth  9  score     0  time   0.00  nodes       5953  nps  7979750
info depth 10  score     0  time   0.00  nodes      10090  nps  9364213
info depth 11  score     0  time   0.00  nodes      18934  nps 11506722
info depth 12  score     0  time   0.00  nodes      30808  nps 11774140
info depth 13  score     0  time   0.00  nodes      58487  nps 13616620
info depth 14  score  -100  time   0.01  nodes     147217  nps 13332852
info depth 15  score  -100  time   0.02  nodes     235035  nps 14351591
info depth 16  score  -100  time   0.03  nodes     372465  nps 14321980
info depth 17  score  -100  time   0.05  nodes     720600  nps 15565411
info depth 18  score  -100  time   0.07  nodes    1051606  nps 14956234
info depth 19  score  -100  time   0.16  nodes    2496796  nps 15322515
info depth 20  score  -100  time   0.34  nodes    4733065  nps 14065303
info depth 21  score  -100  time   1.54  nodes   21844880  nps 14190422
info depth 22  score  -100  time   2.25  nodes   31534729  nps 13994712
info depth 23  score  -100  time   3.25  nodes   46712754  nps 14374957
info depth 24  score  -100  time   4.37  nodes   61828098  nps 14138063

With the value of a king at 320 (man = 100) my tree is larger than yours:

Code: Select all

info depth  1  score     0  time   0.00  nodes         17  nps  1228515
info depth  2  score     0  time   0.00  nodes         97  nps   697875
info depth  3  score     0  time   0.00  nodes        157  nps   956098
info depth  4  score     0  time   0.00  nodes        244  nps  1267534
info depth  5  score     0  time   0.00  nodes        511  nps  2230534
info depth  6  score     0  time   0.00  nodes        880  nps  3090408
info depth  7  score     0  time   0.00  nodes       1772  nps  4954824
info depth  8  score     0  time   0.00  nodes       3011  nps  6403943
info depth  9  score     0  time   0.00  nodes       5953  nps  8908824
info depth 10  score     0  time   0.00  nodes      10090  nps 10065092
info depth 11  score     0  time   0.00  nodes      19558  nps 11928299
info depth 12  score     0  time   0.00  nodes      33364  nps 12357420
info depth 13  score     0  time   0.00  nodes      59381  nps 13936504
info depth 14  score  -100  time   0.01  nodes     127415  nps 13520444
info depth 15  score  -100  time   0.02  nodes     221531  nps 14272294
info depth 16  score  -100  time   0.03  nodes     363339  nps 14234477
info depth 17  score  -100  time   0.08  nodes    1190051  nps 15029260
info depth 18  score  -120  time   0.18  nodes    2694289  nps 14789926
info depth 19  score  -100  time   0.25  nodes    3627462  nps 14751466
info depth 20  score  -100  time   0.30  nodes    4300479  nps 14395025
info depth 21  score  -100  time   0.41  nodes    5946280  nps 14472550
info depth 22  score  -100  time   2.57  nodes   36193333  nps 14084529
info depth 23  score  -100  time   5.34  nodes   76220990  nps 14276916
info depth 24  score  -100  time   7.01  nodes  100455577  nps 14322654

What strikes me is that there is already a difference in node count at low depth, possibly we count nodes differently or one of us has a bug, when I enter search or quiescence I increment the node counter by one, this is how I count at the moment.
Another possibility is that we generate moves in a different order which has an effect with plain alpha-beta, the difference at ply 4 is already 13 nodes and that seems quite large to me.

[BertTuyt]

Joost, I will post all Dwarf sources via Dropbox in the weekend.
Basically it is the MoveGen with a Dwarf Main file
So you could have a look.
Maybe there are bugs, which I didnt find so far.

Bert

[Joost Buijs]

Bert,

Since I use the hash-move before move-generation and use the killers before sorting, I had to be careful that everything works as it should.
What I did is generating a checksum of all the moves on a node, and after the sorting process and picking all the moves the checksum has to be the same, I my case this seems to work out fine, I'm almost 100% certain that I don't miss a move or have a double move after my sorting process.

Joost

[Joost Buijs]

Bert,

I've been playing a little with my SMP search and it seems the performance is really hampered by the shared killer and history table (false sharing), I have made them thread local and now I can easily surpass 100 mnps (at 4 GHz.).
It might be a good idea to have shared tables close to the root and to switch to thread-local tables closer to the leaves, this is certainly something I'm going to try.

With chess I never noticed this because chess is more complex, move-generation and evaluation are several times slower compared to draughts and in this case a bit of false sharing has not such a big impact.

Joost

Code: Select all

info TT: bucket_size: 64  num_buckets: 33554432, total_size: 2147483648
info Pages can be locked in memory!
info Allocated transposition table with size 2147483648 in large pages.
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          9  nps   221724
info depth  2  score     0  time   0.00  nodes         38  nps   169745
info depth  3  score     0  time   0.00  nodes        242  nps   858203
info depth  4  score     0  time   0.00  nodes        584  nps  1763361
info depth  5  score     0  time   0.00  nodes       1615  nps  3698524
info depth  6  score     0  time   0.00  nodes       3352  nps  3599916
info depth  7  score     0  time   0.00  nodes       8795  nps  6051825
info depth  8  score     0  time   0.00  nodes      17711  nps  9253749
info depth  9  score     0  time   0.00  nodes      43298  nps 15965874
info depth 10  score     0  time   0.00  nodes      87572  nps 22175673
info depth 11  score     0  time   0.01  nodes     194567  nps 31721782
info depth 12  score     0  time   0.01  nodes     392135  nps 39489794
info depth 13  score     0  time   0.02  nodes     835156  nps 49906058
info depth 14  score     0  time   0.03  nodes    1691698  nps 60032537
info depth 15  score     0  time   0.05  nodes    3728385  nps 73648050
info depth 16  score     0  time   0.09  nodes    7688777  nps 81542494
info depth 17  score     0  time   0.18  nodes   17494573  nps 95978786
info depth 18  score     0  time   0.35  nodes   36775309  nps 103653849
info depth 19  score     0  time   0.75  nodes   85490047  nps 114722177
info depth 20  score     0  time   1.53  nodes  179772381  nps 117780352
info depth 21  score     0  time   3.40  nodes  423357789  nps 124599417
info depth 22  score     0  time   7.12  nodes  881497141  nps 123739512
info depth 23  score     0  time  16.43  nodes 2077823919  nps 126440838
info depth 24  score     0  time  35.15  nodes 4311875205  nps 122682124

[BertTuyt]

Joost, think this is a world record for speed........

Although partly cloning, it would be interesting to see what ELO you would get by a short-cut implementation based upon the tables of Fabien and the Databases of Ed.

I know that you will inject in the end 100% own code, but just as a yardstick.
Especially as we had a discussion some time ago, when we would believe perfect play would (more or less) take place.
Balpark figure 250 - 300 ELO points to gain compared with Kingsrow.

It would already be an achievement if you could prove that with this speed, one would grow +30 compared (and against Scan, 158 match 5-10 minutes game).

Note: In Damage I use a global Hash (with a Hyatt-type of lock) and Local History tables.

Bert

[Joost Buijs]

Joost, think this is a world record for speed........

Although partly cloning, it would be interesting to see what ELO you would get by a short-cut implementation based upon the tables of Fabien and the Databases of Ed.

I know that you will inject in the end 100% own code, but just as a yardstick.
Especially as we had a discussion some time ago, when we would believe perfect play would (more or less) take place.
Balpark figure 250 - 300 ELO points to gain compared with Kingsrow.

It would already be an achievement if you could prove that with this speed, one would grow +30 compared (and against Scan, 158 match 5-10 minutes game).

Note: In Damage I use a global Hash (with a Hyatt-type of lock) and Local History tables.

Bert

Bert,

It would not be very difficult to convert the evaluation values of Scan for use in my program, in this case I also have to use the same interpolation as Scan does, the point is that I use a different indexing scheme so converting this will take time and it might be wiser to spend this time on my own ML.

My hash-tables also use a Hyatt type of lock-free scheme, I xor the key with the data-field to verify that the read or write was atomic or not. Intel CPU's have an instruction for 128 bit atomic loads and stores 'CMPXCHG16B', that is another possibility.
C++11 has build-in atomics which I use for SMP, there is a possibility when you define a 128 bit atomic they will use the CPU instruction, another possibility is that they use a lock and that is something you don't want.

Joost

Edit:

I've been optimizing the SMP somewhat more and the speedup (time to depth) is now in the region of 5.3 to 5.8 on 8 cores, it depends a little bit upon the complexity of the position.
A split-depth of 6 or 7 seems to work best and the number of moves available before splitting should at least be 3, another restriction is that I never let more then 4 cores work together on the same split-point and that I never allow more than 4 split-points in the same thread (this will never happen with <= 8 cores though).
I tried several things like splitting only on all-nodes and splitting only when there are no captures etc. these things don't work at all, the branching factor in draughts is very low and that makes it difficult to keep the processors working, so you have to grab every opportunity to keep them busy.

[BertTuyt]

Herewith Dwarf Output for the Woldouby, again main difference with the implementation of Joost, only 2M HashTable entries (no bucket structure), no killers, history, and no aspiration window (and no SMP).

Code: Select all

id name Dwarf 0.0
id author Draughts Community
ready
HashTable Allocated, Entries = 2097152
pos XW XB 10 10
info D 1 S 0 N 17 T 0 knps 0
info D 2 S 0 N 96 T 0 knps 0
info D 3 S 0 N 152 T 0.001 knps 152
info D 4 S 0 N 231 T 0.002 knps 115
info D 5 S 0 N 426 T 0.004 knps 106
info D 6 S 0 N 745 T 0.004 knps 186
info D 7 S 0 N 1354 T 0.005 knps 270
info D 8 S 0 N 2334 T 0.006 knps 389
info D 9 S 0 N 4487 T 0.007 knps 641
info D 10 S 0 N 7231 T 0.008 knps 903
info D 11 S 0 N 12269 T 0.01 knps 1226
info D 12 S 0 N 22457 T 0.012 knps 1871
info D 13 S 0 N 35070 T 0.015 knps 2338
info D 14 S -100 N 108628 T 0.025 knps 4345
info D 15 S -100 N 172774 T 0.036 knps 4799
info D 16 S -100 N 364395 T 0.064 knps 5693
info D 17 S -100 N 604647 T 0.098 knps 6169
info D 18 S -120 N 1188892 T 0.181 knps 6568
info D 19 S -100 N 1486388 T 0.224 knps 6635
info D 20 S -100 N 1914628 T 0.287 knps 6671
info D 21 S -100 N 2763988 T 0.406 knps 6807
info D 22 S -100 N 12215082 T 1.642 knps 7439
info D 23 S -100 N 20454036 T 2.746 knps 7448
info D 24 S -100 N 73142078 T 9.611 knps 7610
info D 25 S -100 N 180050130 T 23.647 knps 7614
info D 26 S -100 N 433811049 T 56.744 knps 7645
info D 27 S -100 N 938272148 T 123.343 knps 7607
info D 28 S -100 N 2182447135 T 285.753 knps 7637

Will Implement also a simple aspiration window, to measure effect...
Node definition differences still to be resolved (to avoid comparing apples and .....)

Bert

[BertTuyt]

And herewith the results with a simple (Joos alike) aspiration window.

Code: Select all

id name Dwarf 0.0
id author Draughts Community
ready
HashTable Allocated, Entries = 2097152
pos XW XB 10 10
info D 1 S 0 N 17 T 0 knps 0
info D 2 S 0 N 71 T 0.001 knps 71
info D 3 S 0 N 127 T 0.002 knps 63
info D 4 S 0 N 206 T 0.002 knps 103
info D 5 S 0 N 400 T 0.003 knps 133
info D 6 S 0 N 713 T 0.02 knps 35
info D 7 S 0 N 1295 T 0.021 knps 61
info D 8 S 0 N 2263 T 0.022 knps 102
info D 9 S 0 N 4408 T 0.023 knps 191
info D 10 S 0 N 7151 T 0.025 knps 286
info D 11 S 0 N 12177 T 0.026 knps 468
info D 12 S 0 N 22365 T 0.029 knps 771
info D 13 S 0 N 34978 T 0.031 knps 1128
info D 14 S -100 N 183725 T 0.051 knps 3602
info D 15 S -100 N 248439 T 0.061 knps 4072
info D 16 S -100 N 417398 T 0.084 knps 4969
info D 17 S -100 N 569367 T 0.107 knps 5321
info D 18 S -120 N 924635 T 0.157 knps 5889
info D 19 S -100 N 1221248 T 0.199 knps 6136
info D 20 S -100 N 1652973 T 0.258 knps 6406
info D 21 S -100 N 2483799 T 0.374 knps 6641
info D 22 S -100 N 9583598 T 1.294 knps 7406
info D 23 S -100 N 17068824 T 2.273 knps 7509
info D 24 S -100 N 60989389 T 7.941 knps 7680
info D 25 S -100 N 150967481 T 19.574 knps 7712
info D 26 S -100 N 376415597 T 48.568 knps 7750
info D 27 S -100 N 796811901 T 102.704 knps 7758
info D 28 S -100 N 1894393560 T 244.208 knps 7757

Till ply 13 the aspiration search need less nodes.
At ply 14 somewhat more, due to a score change outside the aspiration window.
From ply 17 onwards , the aspiration search is again better.

At higher ply depths it yields a 17%-18% reduction in nodes.

Bert

[BertTuyt]

Joost,

what puzzles me a little is that your SMP search requires less nodes (according to your output) compared with the normal search.

At 24 ply 1-core 15118089, 8-core 15042329.
My experience is that parallel search has a negative impact on number of nodes.
It could be related to the 0-score evaluation, but again I do not fully understand this.
But maybe it is apples and peares, and you introduced (parallel ) to the SMP additional search improvements.

Bert

[Joost Buijs]

Bert,

This can be the result of several things, first of all adding promotions to the quiescence had the effect that the branching factor went down instead of up (what you would expect) and I improved the function that I use to update the history, now it resembles more or less a sigmoid and that helped to get the branching factor down as well.

The aspiration window can be improved quite a lot, it was just a quick fix to test the program.
Normally you would make the window smaller and increase it in several steps on a fail-low or a fail-high. Without positional evaluation this not very useful because the values in the tree are very coarse.

The last version with the bug fixed (I talked about this afternoon) does even better.
This is still without additional pruning on 3600 MHz., no hyper-threading, no PGO, no Large Pages and 1GB. hash.

Code: Select all

info Starting threads  0  1  2  3  4  5  6  7
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.

    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          9  nps    585938
info depth  2  score     0  time   0.00  nodes         38  nps    662668
info depth  3  score     0  time   0.00  nodes        236  nps   2367832
info depth  4  score     0  time   0.00  nodes        590  nps   3824154
info depth  5  score     0  time   0.00  nodes       1662  nps   6857953
info depth  6  score     0  time   0.00  nodes       3712  nps   8972783
info depth  7  score     0  time   0.00  nodes       9839  nps  12392618
info depth  8  score     0  time   0.00  nodes      20350  nps  15021217
info depth  9  score     0  time   0.00  nodes      51633  nps  23613602
info depth 10  score     0  time   0.00  nodes      99940  nps  27981013
info depth 11  score     0  time   0.01  nodes     235826  nps  40453031
info depth 12  score     0  time   0.01  nodes     438486  nps  45620529
info depth 13  score     0  time   0.02  nodes     999972  nps  59372332
info depth 14  score     0  time   0.03  nodes    1798934  nps  63247138
info depth 15  score     0  time   0.06  nodes    4288369  nps  77368238
info depth 16  score     0  time   0.10  nodes    7881014  nps  76581996
info depth 17  score     0  time   0.21  nodes   19605445  nps  93285437
info depth 18  score     0  time   0.41  nodes   36153457  nps  87914237
info depth 19  score     0  time   0.87  nodes   89560938  nps 102625570
info depth 20  score     0  time   1.78  nodes  165351692  nps  92857118
info depth 21  score     0  time   3.97  nodes  420978199  nps 106120252
info depth 22  score     0  time   8.26  nodes  778737195  nps  94298189
info depth 23  score     0  time  18.90  nodes 1995257019  nps 105576036
info depth 24  score     0  time  40.22  nodes 3751786733  nps  93270493

Edit:

The strange difference in nps between odd and even plies had something to do with history, so I changed the algorithm once again. Now the results are less irregular and the 24 ply search went down from 40 sec. to 25 sec.
I'll leave it like this for the time being and start working on getting the program to play actual games.

Code: Select all

info Found 8 physical cores.
info Starting threads  0  1  2  3  4  5  6  7
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.

    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           9  nps    775506
info depth  2  score     0  time   0.00  nodes          38  nps    595338
info depth  3  score     0  time   0.00  nodes         236  nps   2181093
info depth  4  score     0  time   0.00  nodes         590  nps   3638981
info depth  5  score     0  time   0.00  nodes        1626  nps   6402786
info depth  6  score     0  time   0.00  nodes        3669  nps   8767557
info depth  7  score     0  time   0.00  nodes       10106  nps  17283962
info depth  8  score     0  time   0.00  nodes       20089  nps  23655347
info depth  9  score     0  time   0.00  nodes       49239  nps  37159945
info depth 10  score     0  time   0.00  nodes       96520  nps  45778450
info depth 11  score     0  time   0.00  nodes      210704  nps  61766758
info depth 12  score     0  time   0.01  nodes      403637  nps  68859866
info depth 13  score     0  time   0.01  nodes      835106  nps  81694939
info depth 14  score     0  time   0.02  nodes     1615857  nps  88226268
info depth 15  score     0  time   0.04  nodes     3394534  nps  95678563
info depth 16  score     0  time   0.07  nodes     6739338  nps  93845514
info depth 17  score     0  time   0.14  nodes    14254166  nps  99226954
info depth 18  score     0  time   0.30  nodes    28945988  nps  96506765
info depth 19  score     0  time   0.61  nodes    60561238  nps  99309763
info depth 20  score     0  time   1.32  nodes   126612932  nps  95967506
info depth 21  score     0  time   2.70  nodes   262309973  nps  97028046
info depth 22  score     0  time   5.65  nodes   538411239  nps  95282519
info depth 23  score     0  time  11.80  nodes  1124568144  nps  95318458
info depth 24  score     0  time  25.22  nodes  2327607007  nps  92305845

[BertTuyt]

Although I did not implement move sorting in Dwarf, there is an implicit move ordening.
For both white as black I use (at least for the man moves) a BITSCANFORWARD to occupy the movelist.
When one thinks about it, this is absolutely asymmetrical.

The black moves in the back of the black position are so on the top of the move list, for white the front moves.
So I tested what the effect was in using a forward (F) and reverse (R) scan.
All at ply 25 for the (famous) Woldouby.

Code: Select all

White	Black	Nodes
F		F		150.967.354
R		F		342.237.097
R		R		345.962.328
F		R		160.613.611

So max a factor 2 difference.
In very quiet positions I would expect that it is safe to populate the movelist first with (defending) moves at the back of the position.
So White R and Black F, but here (for whatever reason) most optimal seems to be F F and F R.

Remaining questions, what is the effect for the initial position, and is there an (significant) effect when move sorting (history) is used.....

Bert