Improving search speed.

[hgm]

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

This is not the correct way to calculate branching factor. You would for instance not see any effect of reductions due to the null-move. NTN nodes will be dominated by the depth=1 nodes, and the tips of reduced branches would look exactly the same as any other branch tip.

What is relevant for engine depth is the effective branching factor, the number of nodes in an (N+1)-ply search dicided by the number of nodesin an N-ply search.

[Dann Corbit]

Do you use IID?

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

Right. If your move ordering is not good, it is a simple way to improve it. Look at what other people have done before you implement it, because there are a lot of fidgety things as to exactly what nodes need it and for which nodes it would be a waste of time.

[konsolas]

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

This is not the correct way to calculate branching factor. You would for instance not see any effect of reductions due to the null-move. NTN nodes will be dominated by the depth=1 nodes, and the tips of reduced branches would look exactly the same as any other branch tip.

What is relevant for engine depth is the effective branching factor, the number of nodes in an (N+1)-ply search dicided by the number of nodesin an N-ply search.

Here is my new attempt:

Code: Select all

ncounts[ply]++

on every call of searchAB, and

Code: Select all

printf&#40;"info string bf %d&#58;%f \n", currentdepth - 1, static_cast<double>&#40;board.nCounts&#91;currentdepth - 2&#93;) / static_cast<double>&#40;board.nCounts&#91;currentdepth - 1&#93;));

inside the iterative deepening loop. I've a feeling that I'm still calculating this incorrectly, as I'm getting a ridiculously good EBF:

Code: Select all

info depth 2 score cp 0 nodes 105 time 0 pv g1f3 g8f6
info depth 3 score cp 27 nodes 276 time 1 nps 276000 pv g1f3 g8f6 b1c3
info depth 4 score cp 0 nodes 514 time 2 nps 257000 pv g1f3 g8f6 b1c3 b8c6
info depth 4 score cp 2 nodes 3731 time 3 nps 1243666 pv b1c3 d7d5 g1f3 g8f6
info depth 5 score cp 25 nodes 7769 time 4 nps 1942250 pv b1c3 b8c6 d2d4 g8f6 g1f3
info depth 6 score cp 0 nodes 13558 time 6 nps 2259666 pv b1c3 b8c6 d2d4 g8f6 g1f3 d7d5
info depth 6 score cp 13 nodes 30358 time 10 nps 3035800 pv g1f3 g8f6 d2d4 e7e6 b1c3 b8c6
info string bf 5:1.252756
info depth 7 score cp 10 nodes 47979 time 13 nps 3690692 pv g1f3 g8f6 d2d4 d7d5 b1d2 b8c6 e2e3
info string bf 6:0.884412
info depth 8 score cp -5 nodes 354082 time 67 nps 5284805 pv g1f3 g8f6 e2e3 b8c6 d2d4 d7d5 b1c3 c8g4
info depth 8 score cp -4 nodes 1201600 time 217 nps 5537327 pv e2e3 b8c6 g1e2 d7d5 d2d4 e7e5 f2f4 f7f6
info depth 8 score cp 0 nodes 1617128 time 295 nps 5481789 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6e4 b1c3 d7d5 c3e4 d5e4
info string bf 7:0.739088
info depth 9 score cp 0 nodes 2079779 time 386 nps 5388028 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6e4 b1c3 d7d5 d2d4
info string bf 8:3.140635
info depth 10 score cp 3 nodes 2884879 time 549 nps 5254788 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6e4 b1c3 e4c3 d2c3 d7d5
info string bf 9:2.930321
info depth 11 score cp 6 nodes 5803673 time 1122 nps 5172614 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6e4 b1c3 d7d5 d2d4 c8f5 c3e4 f5e4
info string bf 10:4.581278
info string bf 11:3.479231

Do you use IID?

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

Right. If your move ordering is not good, it is a simple way to improve it. Look at what other people have done before you implement it, because there are a lot of fidgety things as to exactly what nodes need it and for which nodes it would be a waste of time.

Hmm, but wouldn't it be more useful to just write better move ordering? I'm finding it difficult to get my head around the fact that an entire new search just to get 1 move will create an improvement...

[kbhearn]

Hmm, but wouldn't it be more useful to just write better move ordering? I'm finding it difficult to get my head around the fact that an entire new search just to get 1 move will create an improvement...

1) if writing near-perfect static move ordering was an easy task it'd open up a lot of things... but the task of achieving that is very difficult.

2) so with the typical dynamic move ordering tricks... you arrive a cut node to be. the only move you need to search at it is a move that proves this is indeed a cut node. any other moves searched may well be wasted effort (some small hope they're useful elsewhere in the search maybe). if you don't have a TT move, you'd proceed through good captures and killers as normal perhaps. and maybe by the time you've searched 3 or 4 moves on average you find the cut. so the question is: did you waste more effort doing full depth search on a few moves, or by doing reduced depth IID search to catch the shallow refutation that probably exists and make sure when you're searching at full depth you search it first. Note that the IID search has also primed the TT for you for the search tree you're about to go through, not only do you now have a TT move for your current node, the nodes below it also most likely have TT moves and will not need an IID search.

[Evert]

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.

This is wrong. You should order captures ahead of quiet moves (at least winning captures; losing captures you can postpone, but you need SEE to tell them apart. MVV/LVA works fine too).
Also make sure that captures are not used to update killers and history.

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

Have you checked if the number of cut-offs by the first move is 90% or more? Have you checked that the engine doesn't become weaker by doing this? It's rather easy to reduce your branching factor, but the engine may play much worse.

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.

I think most people actually use effective branching factor, which requires no bookkeeping in the node.

[Sven]

Here is my new attempt:

Code: Select all

ncounts[ply]++

on every call of searchAB, and

Code: Select all

printf&#40;"info string bf %d&#58;%f \n", currentdepth - 1, static_cast<double>&#40;board.nCounts&#91;currentdepth - 2&#93;) / static_cast<double>&#40;board.nCounts&#91;currentdepth - 1&#93;));

inside the iterative deepening loop. I've a feeling that I'm still calculating this incorrectly, as I'm getting a ridiculously good EBF:

Most interesting is ncounts[N]/ncounts[N-1] if N is the number of the last iteration that has been completed. I hope you increment ncounts[ply] for qsearch nodes as well. An EBF of 3.47 or 4.58 might be realistic in your case.

Please check your nps calculation, it seems there is an unexpected jump from 3.69 Mnps to > 5 Mnps in iteration 8 in your example above. Maybe this is related to my remark regarding qsearch nodes?

When analyzing my node counting implementation I find it helpful to print another line of "info" output at the very end of each iteration. This ensures to use the correct numbers for EBF. However, you also need to be aware that sometimes your hash table might prevent an accurate EBF calculation. Therefore ncounts[N]/ncounts[N-1] taken from only one search might be misleading in some cases. It could also be calculated by doing two separate searches of the same position with fixed depth N-1 and fixed depth N.

[cdani]

Do you use IID?

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

When you don't have hash move.

Captures in alpha_beta search also should be ordered (you did not mentioned this). And probably bad captures tried later than quiets.

[Evert]

I've a feeling that I'm still calculating this incorrectly, as I'm getting a ridiculously good EBF:

Comparing node-counts and search time, it certainly looks incorrect. Your claimed EBF is <1 in many cases, which should only happen if you have a primed hash table containing a long(ish) PV.

Hmm, but wouldn't it be more useful to just write better move ordering? I'm finding it difficult to get my head around the fact that an entire new search just to get 1 move will create an improvement...

The search is to reduced depth. Searching a node to N-1 ply takes a much shorter (EBF shorter, in fact) time than searching the node to N ply. Reducing the depth even more increases the savings.

[bob]

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

Has to look like this:

hash move (which will include the PV moves if you do it right)
Captures that don't lose material
killer moves
counter moves
other ideas
rest of moves ordered by history heuristic

Branching factor does not change in chess, ever. (actually it changes as pieces are removed and whatever, but move ordering has absolutely no effect on this so it is effectively a constant.) It averages about 38. Effective branching factor is more vague and probably the best definition is

ebf = time for current iteration / time for previous iteration.

To be precise, the time for previous iteration is ONLY the time used for that depth, not the cumulative time from the start of the search until that depth was completed...

[konsolas]

Okay, my move ordering is now this:

Hash move (including the PV move if there is one
Winning captures (MVV/LVA)
Killer moves
Everything else ordered by history heuristic.

After searching around 5,000,000 nodes, My engine reaches depth 10 with a very reasonable PV (much better than before)

After comparing this to other engines, what I simply don't understand is how engines like Stockfish can search up to depth 10 in just 22466 nodes, whereas I need 5 million. What causes this huge difference?