Improving search speed.

[konsolas]

I'm completely new to the chess engine scene, and I'm currently writing my first one.

I've completed a bitboard move generator, and alpha-beta PVS search for my engine. Everything works and appears to be bug-free, and I'm getting around 2 million nodes per second (single thread i7 4790k). My evaluation function is just material, pcsq tables, and a pawn structure evaluator.

I've noticed that the top chess engines can reach depths of 20-30 within seconds, even when only using a single thread. From some research, I've seen that this is due to small branching factors (under 2?!).

I have null move pruning and futility pruning, but from testing, my average branching factor (all nodes / non terminal nodes) is about 8: (bf = branching factor)
go
info depth 2 score cp 9 bf 16.666667 nodes 98 time 0 pv d2d4 d7d5
info depth 3 score cp 36 bf 3.977273 nodes 325 time 1 nps 325000 pv d2d4 d7d5 c1f4
info depth 4 score cp 5 bf 8.055901 nodes 2520 time 2 nps 1260000 pv d2d4 d7d5 c1f4 c8f5
info depth 4 score cp 18 bf 5.445351 nodes 6497 time 4 nps 1624250 pv e2e4 d7d5 f1b5 c7c6
info depth 5 score cp 44 bf 6.058791 nodes 22727 time 11 nps 2066090 pv e2e4 d7d5 e4d5 d8d5 d2d4
info depth 6 score cp 22 bf 5.973206 nodes 122214 time 46 nps 2656826 pv e2e4 d7d5 e4d5 d8d5 d2d4 c8f5
info depth 7 score cp 42 bf 7.046007 nodes 735069 time 261 nps 2816356 pv e2e4 d7d5 e4d5 d8d5 d2d4 g7g5 c1e3
info depth 7 score cp 46 bf 7.710517 nodes 1503032 time 523 nps 2873866 pv d2d4 d7d5 c2c4 d5c4 b1c3 c8g4 c1f4
info depth 8 score cp 11 bf 7.433348 nodes 2414498 time 866 nps 2788103 pv d2d4 d7d5 c2c4 c7c5 c4d5 d8d5 g1f3 b8c6

From what I can see, branching factor majorly determines the depth the engine can search at, and hence the tactical awareness. What's the best way I can go about reducing the branching factor of my engine? (I already have transposition tables)

[hgm]

With good move ordering and R=2 null move you should be able to better than 8; 6 is more usual.

Branching factor can be improved by lots of reductions and pruning. Like very aggressive LMR. The trick is to know what you can savely prune/reduce, otherwise you search will be so full of holes that the large depth means nothing. A goot evaluation to judge this is very important in this respect.

[konsolas]

How much of an improvement could I expect to get with better ordering? I'm currently ordering PV move, then captures, then history heuristic. I've already got R=2 null move.

I've seen the LMR implementation in stockfish; Wouldn't this possibly compromise tactics?

[bob]

I'm completely new to the chess engine scene, and I'm currently writing my first one.

I've completed a bitboard move generator, and alpha-beta PVS search for my engine. Everything works and appears to be bug-free, and I'm getting around 2 million nodes per second (single thread i7 4790k). My evaluation function is just material, pcsq tables, and a pawn structure evaluator.

I've noticed that the top chess engines can reach depths of 20-30 within seconds, even when only using a single thread. From some research, I've seen that this is due to small branching factors (under 2?!).

I have null move pruning and futility pruning, but from testing, my average branching factor (all nodes / non terminal nodes) is about 8: (bf = branching factor)
go
info depth 2 score cp 9 bf 16.666667 nodes 98 time 0 pv d2d4 d7d5
info depth 3 score cp 36 bf 3.977273 nodes 325 time 1 nps 325000 pv d2d4 d7d5 c1f4
info depth 4 score cp 5 bf 8.055901 nodes 2520 time 2 nps 1260000 pv d2d4 d7d5 c1f4 c8f5
info depth 4 score cp 18 bf 5.445351 nodes 6497 time 4 nps 1624250 pv e2e4 d7d5 f1b5 c7c6
info depth 5 score cp 44 bf 6.058791 nodes 22727 time 11 nps 2066090 pv e2e4 d7d5 e4d5 d8d5 d2d4
info depth 6 score cp 22 bf 5.973206 nodes 122214 time 46 nps 2656826 pv e2e4 d7d5 e4d5 d8d5 d2d4 c8f5
info depth 7 score cp 42 bf 7.046007 nodes 735069 time 261 nps 2816356 pv e2e4 d7d5 e4d5 d8d5 d2d4 g7g5 c1e3
info depth 7 score cp 46 bf 7.710517 nodes 1503032 time 523 nps 2873866 pv d2d4 d7d5 c2c4 d5c4 b1c3 c8g4 c1f4
info depth 8 score cp 11 bf 7.433348 nodes 2414498 time 866 nps 2788103 pv d2d4 d7d5 c2c4 c7c5 c4d5 d8d5 g1f3 b8c6

From what I can see, branching factor majorly determines the depth the engine can search at, and hence the tactical awareness. What's the best way I can go about reducing the branching factor of my engine? (I already have transposition tables)

LMR is the next obvious thing to do. Then forward pruning, commonly called late move pruning. And of course I assume you have a hash table implementation and are using good move ordering?

[Evert]

If your move ordering is good, you should get a cut-off from the first move in >90% of cases. The first three moves you search should produce 95% or so of the cut-offs.

You can improve on move ordering through things like history heuristics, or by ordering quiet moves by PST improvement. That only helps in non-QS nodes though.

How do you handle QS nodes? Does the stand-pat work correctly? Do you sort captures by MVV/LVA? How do you sort equal captures? Do you use SEE to prune losing captures?

Another thing to look at is extensions. Can you ever extend by more than a ply? Do you do futility pruning?

[bob]

How much of an improvement could I expect to get with better ordering? I'm currently ordering PV move, then captures, then history heuristic. I've already got R=2 null move.

I've seen the LMR implementation in stockfish; Wouldn't this possibly compromise tactics?

You should certainly add killer moves before the history heuristic. And the counter-move heuristic also works pretty well.

But you did not mention hash table moves, which suggests you are not hashing at all...

[konsolas]

Apologies, looks like I wasn't clear.

My move ordering is currently:
- PV move if there is one
- Hash move if there is one
- 2 Killer moves if they exist
- Rest ordered by history heuristic.

I've just tried to add LMR with a reduction of 1. My branching factor appears to have gone down to about 6.

I'm not actually sure if I'm calculating branching factor correctly; it feels like I should be searching much further with my node count and branching factor.

Code: Select all

	ANodes++;

	if &#40;depth <= 0&#41; &#123;
		return qsearch&#40;ply, alpha, beta&#41;;
	&#125; else &#123;
		NTNodes++;
	&#125;

And then I divide ANodes by NTNodes. This happens before everything else (null move, futility, etc.)

[Dann Corbit]

Do you use IID?

[konsolas]

With quiescence search nodes, I order captures based on SEE, discarding any losing captures. I don't order equal captures at all.

I do the standard if standpat >= beta return standpat.

I do futility pruning, but no extensions at the moment. I will see if I can improve my move ordering based on your advice.

[konsolas]

Do you use IID?

Nope, as far as I understand it, it's a mini-search to improve move ordering.