Increasing Search Depth

[jordanbray]

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

[Angrim]

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.

[jordanbray]

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.

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 &#40;i < 6&#41;
                reductions = 1;
            else
                reductions = &#40;depth+1&#41;/3;
        &#125;

        if &#40;search->in_pv&#41;
            reductions = &#40;reductions * 2&#41; / 3;
        reductions += search->reductions&#91;search->in_pv&#93;&#91;0&#93;&#91;search->depth_index&#93;&#91;move_count > 63 ? 63 &#58; move_count&#93;;

[op12no2]

Hi Jordan,

Are you perhaps counting horizon nodes and QSearch nodes?

[jordanbray]

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.

[op12no2]

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

[Ferdy]

[...]
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

Run from a script, here are some sample depth 10 nodes of some uci engines on 1 thread.
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

Sorted by nodes in ascending order.

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)

[xmas79]

Tune your evaluation function.

[cdani]

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.

[asanjuan]

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

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.