Hey All,
I'm writing a chess engine and was wondering what the most significant method of increasing the depth would be.
I have implemented null move pruning and razoring, but that's about it. Otherwise its a full NegaScout search. Move ordering has helped performance quite a bit (using last best move, killers, history heuristic, recaptures and captures in that order), but otherwise I think it still needs some help.
I've also added LMR, but it seems like it's still kinda iffy.
One last question. At a depth of 10 i search 5.1 million nodes. Is there something I can compare that to? Stockfish seems to only search a few thousand nodes at a depth of 10, which is kinda confusing, and makes me think I must be reading the results wrong.
Thanks,
Jordan
Increasing Search Depth
Moderators: hgm, Rebel, chrisw
-
- Posts: 97
- Joined: Mon Jun 25, 2012 10:16 pm
- Location: Forks, WA
- Full name: Ben Nye
Re: Increasing Search Depth
add a hash table. Both for move ordering and transpositions. I don't see any mention of your engine having that, and it's more important than most of the things that you mentioned.
-
- Posts: 52
- Joined: Mon Aug 11, 2014 3:01 am
Re: Increasing Search Depth
I did not mention it, but I do in fact have a transposition table. I also do use the transposition tables move in move ordering.
I'm also using iterative deepening framework (with aspiration windows) to seed the values in the TT for future searches.
As an aside, I have added the following naive implementation of search reductions. The search->reductions array is a shameless copy of the Reductions[] array defined in stockfish/src/search.cpp.
I also do not have a way to determine if the position is 'improving', so I can't even use my plagiarism to the fullest extent.
"i" is the current move index, moves[] are the encoded moves, move_info[] allows me to undo moves (and has info about captures and the like). search->in_pv is set iff this is the first search of the root node. search->depth_index == 0 if root node, == 1 if first child, etc.
This code seemed to increase the depth quite a bit, but I'm wondering how artificial it is now. I'm getting a testing framework set up.
I'm also using iterative deepening framework (with aspiration windows) to seed the values in the TT for future searches.
As an aside, I have added the following naive implementation of search reductions. The search->reductions array is a shameless copy of the Reductions[] array defined in stockfish/src/search.cpp.
I also do not have a way to determine if the position is 'improving', so I can't even use my plagiarism to the fullest extent.
"i" is the current move index, moves[] are the encoded moves, move_info[] allows me to undo moves (and has info about captures and the like). search->in_pv is set iff this is the first search of the root node. search->depth_index == 0 if root node, == 1 if first child, etc.
This code seemed to increase the depth quite a bit, but I'm wondering how artificial it is now. I'm getting a testing framework set up.
Code: Select all
int reductions = 0;
board_move(board, moves[i], &move_info[i]);
if (!board->pin_info.checked && !move_info[i].captured_piece) {
if (i < 6)
reductions = 1;
else
reductions = (depth+1)/3;
}
if (search->in_pv)
reductions = (reductions * 2) / 3;
reductions += search->reductions[search->in_pv][0][search->depth_index][move_count > 63 ? 63 : move_count];
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Increasing Search Depth
Hi Jordan,
Are you perhaps counting horizon nodes and QSearch nodes?
Are you perhaps counting horizon nodes and QSearch nodes?
-
- Posts: 52
- Joined: Mon Aug 11, 2014 3:01 am
Re: Increasing Search Depth
I am not counting horizon or qsearch nodes. I count qsearch with a separate counter. I count a node as any board_move call within the nega_scout function.
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Increasing Search Depth
Long shot, but if you count like that && filter pseudo-legal moves (using your move/unmove funcs) to get legal moves && then iterate the legal moves in the search, you'll get an artificially high node count...
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Increasing Search Depth
Run from a script, here are some sample depth 10 nodes of some uci engines on 1 thread.jordanbray wrote: [...]
One last question. At a depth of 10 i search 5.1 million nodes. Is there something I can compare that to? Stockfish seems to only search a few thousand nodes at a depth of 10, which is kinda confusing, and makes me think I must be reading the results wrong.
Thanks,
Jordan
Sorted by engine name.
Code: Select all
Engine id name Andscacs 0.64
depth 10, nodes 36826
Engine id name Arasan 17.1
depth 10, nodes 48713
Engine id name Atlas 3.50 x64
depth 10, nodes 162108
Engine id name BlackMamba_1.2c x64
depth 10, nodes 28883
Engine id name Bobcat 3.25
depth 10, nodes 37112
Engine id name cheng4 0.36c
depth 10, nodes 60902
Engine id name Critter 1.6a 64-bit
depth 10, nodes 109137
Engine id name Deuterium v14.2.33.276
depth 10, nodes 85827
Engine id name Fire 3.0 x64
depth 10, nodes 14033
Engine id name Fruit reloaded 2.1
depth 10, nodes 53791
Engine id name Glass 2.0 PERSONALITY
depth 10, nodes 770389
Engine id name GNU Chess 5.50-64
depth 10, nodes 67417
Engine id name Godel 2.3.7
depth 10, nodes 105146
Engine id name GreKo 12.0
depth 10, nodes 699748
Engine id name Gull 2.2 x64
depth 10, nodes 69249
Engine id name Hamsters 0.7.1
depth 10, nodes 47240
Engine id name Hannibal 1.4x64
depth 10, nodes 32551
Engine id name HIARCS 14 WCSC
depth 10, nodes 73759
Engine id name Houdini 4 x64
depth 10, nodes 43142
Engine id name Komodo 6 64-bit
depth 10, nodes 37991
Engine id name MadChess 1.4
depth 10, nodes 376875
Engine id name Maverick 0.51 x64
depth 10, nodes 4809452
Engine id name MinkoChess 1.3 x64
depth 10, nodes 61628
Engine id name Murka 3 x64 UCI
depth 10, nodes 44009
Engine id name Nebula 2.0
depth 10, nodes 608355
Engine id name Nemo SP64o 1.0.1 Beta
depth 10, nodes 74410
Engine id name Nirvanachess 1.8
depth 10, nodes 40578
Engine id name Pawny 1.0.x64.SSE4.2
depth 10, nodes 169613
Engine id name Quazar 0.4 x64
depth 10, nodes 13771
Engine id name RedQueen 1.1.4
depth 10, nodes 66636
Engine id name Rhetoric 1.4.1 x64
depth 10, nodes 77455
Engine id name Rodent 1.5 (build 15)
depth 10, nodes 119181
Engine id name Rotor 0.8
depth 10, nodes 72084
Engine id name Ruffian 1.0.5
depth 10, nodes 2263568
Engine id name Rybka 2.3.2a mp
depth 10, nodes 35199
Engine id name Senpai 1.0
depth 10, nodes 30111
Engine id name SmarThink 1.70
depth 10, nodes 129419
Engine id name SOS 5 for Arena
depth 10, nodes 476191
Engine id name spark-1.0
depth 10, nodes 150765
Engine id name Stockfish 5 64 SSE4.2
depth 10, nodes 37880
Engine id name Strelka 5.5
depth 10, nodes 82394
Engine id name Twisted Logic 20100131x
depth 10, nodes 54303
Engine id name Texel 1.04 64-bit
depth 10, nodes 88941
Engine id name TJchess 1.1U-x64
depth 10, nodes 509006
Engine id name Toga II 3.0
depth 10, nodes 174917
Engine id name Ufim 8.02
depth 10, nodes 1977918
Engine id name Umko 1.1 x64
depth 10, nodes 66187
Engine id name Vajolet2 1.45
depth 10, nodes 85726
Code: Select all
1 id name Quazar 0.4 x64 (nodes 13771)
2 id name Fire 3.0 x64 (nodes 14033)
3 id name BlackMamba_1.2c x64 (nodes 28883)
4 id name Senpai 1.0 (nodes 30111)
5 id name Hannibal 1.4x64 (nodes 32551)
6 id name Rybka 2.3.2a mp (nodes 35199)
7 id name Andscacs 0.64 (nodes 36826)
8 id name Bobcat 3.25 (nodes 37112)
9 id name Stockfish 5 64 SSE4.2 (nodes 37880)
10 id name Komodo 6 64-bit (nodes 37991)
11 id name Nirvanachess 1.8 (nodes 40578)
12 id name Houdini 4 x64 (nodes 43142)
13 id name Murka 3 x64 UCI (nodes 44009)
14 id name Hamsters 0.7.1 (nodes 47240)
15 id name Arasan 17.1 (nodes 48713)
16 id name Fruit reloaded 2.1 (nodes 53791)
17 id name Twisted Logic 20100131x (nodes 54303)
18 id name cheng4 0.36c (nodes 60902)
19 id name MinkoChess 1.3 x64 (nodes 61628)
20 id name Umko 1.1 x64 (nodes 66187)
21 id name RedQueen 1.1.4 (nodes 66636)
22 id name GNU Chess 5.50-64 (nodes 67417)
23 id name Gull 2.2 x64 (nodes 69249)
24 id name Rotor 0.8 (nodes 72084)
25 id name HIARCS 14 WCSC (nodes 73759)
26 id name Nemo SP64o 1.0.1 Beta (nodes 74410)
27 id name Rhetoric 1.4.1 x64 (nodes 77455)
28 id name Strelka 5.5 (nodes 82394)
29 id name Vajolet2 1.45 (nodes 85726)
30 id name Deuterium v14.2.33.276 (nodes 85827)
31 id name Texel 1.04 64-bit (nodes 88941)
32 id name Godel 2.3.7 (nodes 105146)
33 id name Critter 1.6a 64-bit (nodes 109137)
34 id name Rodent 1.5 (build 15) (nodes 119181)
35 id name SmarThink 1.70 (nodes 129419)
36 id name spark-1.0 (nodes 150765)
37 id name Atlas 3.50 x64 (nodes 162108)
38 id name Pawny 1.0.x64.SSE4.2 (nodes 169613)
39 id name Toga II 3.0 (nodes 174917)
40 id name MadChess 1.4 (nodes 376875)
41 id name SOS 5 for Arena (nodes 476191)
42 id name TJchess 1.1U-x64 (nodes 509006)
43 id name Nebula 2.0 (nodes 608355)
44 id name GreKo 12.0 (nodes 699748)
45 id name Glass 2.0 PERSONALITY (nodes 770389)
46 id name Ufim 8.02 (nodes 1977918)
47 id name Ruffian 1.0.5 (nodes 2263568)
48 id name Maverick 0.51 x64 (nodes 4809452)
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Increasing Search Depth
Tune your evaluation function.
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Increasing Search Depth
Hi!
Some ideas.
* May be you are doing a lot of extensions. In Andscacs I do only check extensions and capture extensions, but only in some cases.
* Limit the quiescence depth. From depth -5 I do only recaptures.
* Are you returning when you find a Hash that it's ok for it?
* Eval pruning
* Futility pruning.
* Null move with adaptative reduction and detecting if there is a thread if it does not work.
* As Natale Galioto has told, the evaluation function it's critical to remove a lot of nonsense lines and also helping move order.
* SEE.
To arrive to some thousands moves at depth 10, you need that all is ok and bug free.
For those 36826 nodes of Andscacs, I count every time I enter on alpha_beta of qsearch.
Some ideas.
* May be you are doing a lot of extensions. In Andscacs I do only check extensions and capture extensions, but only in some cases.
* Limit the quiescence depth. From depth -5 I do only recaptures.
* Are you returning when you find a Hash that it's ok for it?
* Eval pruning
* Futility pruning.
* Null move with adaptative reduction and detecting if there is a thread if it does not work.
* As Natale Galioto has told, the evaluation function it's critical to remove a lot of nonsense lines and also helping move order.
* SEE.
To arrive to some thousands moves at depth 10, you need that all is ok and bug free.
For those 36826 nodes of Andscacs, I count every time I enter on alpha_beta of qsearch.
Daniel José - http://www.andscacs.com
-
- Posts: 214
- Joined: Thu Sep 01, 2011 5:38 pm
- Location: Seville, Spain
Re: Increasing Search Depth
The move ordering looks strange. You are putting all captures at the end of the list. Note that bad moves are usually refuted with a capture, so put them first.jordanbray wrote:Hey All,
I'm writing a chess engine and was wondering what the most significant method of increasing the depth would be.
I have implemented null move pruning and razoring, but that's about it. Otherwise its a full NegaScout search. Move ordering has helped performance quite a bit (using last best move, killers, history heuristic, recaptures and captures in that order), but otherwise I think it still needs some help.
I've also added LMR, but it seems like it's still kinda iffy.
One last question. At a depth of 10 i search 5.1 million nodes. Is there something I can compare that to? Stockfish seems to only search a few thousand nodes at a depth of 10, which is kinda confusing, and makes me think I must be reading the results wrong.
Thanks,
Jordan
The "standard" way to order the moves is:
- hash move
- good captures determined by SEE function
- killers 1 and 2. Killers must be quiet moves, not captures
- the rest of the quiet moves ordered by history, (or pst,... or whatelse with some sense)
- bad captures determided by SEE.
Trying to implement an aggresive LMR without proper ordering is a waste of time.
Regards.
Still learning how to play chess...
knigths move in "L" shape ¿right?
knigths move in "L" shape ¿right?