Help reducing branching factor of Yaka

[vittyvirus]

So I've tried using relative history heuristics, killer moves, MVVLVA based move ordering, and even transposition tables. Besides, I do use Principal Variation search and null move pruning. But I can't get a reasonable branching factor. I get an average branching factor of 6.2 if I do NOT use relative history heuristics, and a branching factor of 7.3 if I use it. My other chess engine Chesser (which is based on someone else's work), doesn't use killer moves or MVVLVA or Transposition tables, uses a very basic version of history heuristics, and has a branching factor of around 4 or even less! That said, I've heard that programs using nullmove pruning can go upto depth 10 easily, even without Transposition Tables!

The code is available to you in case you want to help on this site (download the file 07052016.zip). I use Visual Studio 2015, but I think the 2013 version should work well. I haven't yet checked whether it compiles fine with g++. Here are some other pointers:
=> By default Relative history heuristics are not used, since they actually increase the branching factor in my case, change this in file movepicker.h line #27
=> The default null move reduction depth is 2. A reduction depth of 3, even at higher depths, leads to a larger branching factor and node count (is it bug?)
=> If a hash move is found, it is given a bonus score in move ordering framework so that it will be put first in the list. I haven't researched on how Transposition Tables are used for move ordering, and I really don't get a lot of benefit from doing this, so I might be doing it wrong.
=> The search command is "search <depth> <hash_table_size>". The <hash_table_size> must be a small number (20 to 25), since <hash_table_size> of 24 almost 500MB on my system.
=> If you have a list of fen positions, separated by a newline, then you can use the command "testsearch <depth> <hash table size> <input filename (without spaces)> <output filename (without spaces)>" to search them all and write the output.
=> I would not swear that my program has no search bugs. I can swear it has a correct move generator and a symmetrical evaluation function.

Here is the output from the engine for the starting position:

Code: Select all

Yaka 0.0 x64 by Syed Fahad
search 10 20
info depth 1 score cp 38 nodes 1 nps 1000 tthits 0 pv b1a3
info depth 1 score cp 79 nodes 2 nps 2000 tthits 0 pv b1c3
info depth 1 score cp 88 nodes 9 nps 9000 tthits 0 pv e2e3
info depth 2 score cp 0 nodes 44 nps 44000 tthits 0 pv e2e3 e7e6
info depth 3 score cp 79 nodes 571 nps 571000 tthits 0 pv e2e3 e7e6 b1c3
info depth 4 score cp 0 nodes 2793 nps 2793000 tthits 7 pv e2e3 e7e6 b1c3 b8c6
info depth 4 score cp 53 nodes 2985 nps 2985000 tthits 26 pv b1c3 e7e6 e2e3 b8c6

info depth 5 score cp 62 nodes 17309 nps 5769000 tthits 627 pv b1c3 e7e6 e2e3 b8
c6 g1f3
info depth 5 score cp 128 nodes 21848 nps 1986000 tthits 951 pv e2e3 e7e6 b1c3 b
8c6 g1f3
info depth 6 score cp -98 nodes 62211 nps 4785000 tthits 3530 pv e2e3 e7e6 b1c3
b8c6 g1f3 g8f6
info depth 6 score cp -94 nodes 67700 nps 5207000 tthits 3790 pv e2e4 e7e6 d2d4
b8c6 b1c3 c6d4
info depth 6 score cp -73 nodes 101257 nps 1426000 tthits 7653 pv c2c3 e7e6 d2d4
 b8c6 g1f3 c6d4
info depth 6 score cp -27 nodes 108020 nps 6751000 tthits 8171 pv d2d3 e7e6 g1f3
 g8f6 b1c3 b8c6
info depth 7 score cp 80 nodes 239116 nps 5832000 tthits 23080 pv d2d3 e7e6 g1f3
 g8f6 b1c3 b8c6 c1f4
info depth 7 score cp 87 nodes 443969 nps 1039000 tthits 51712 pv e2e4 e7e6 d2d4
 b8c6 b1c3 c6d4 d1d4
info depth 7 score cp 146 nodes 510885 nps 3702000 tthits 63365 pv b1c3 e7e6 e2e
3 b8c6 g1f3 g8f6 d2d4
info depth 8 score cp -65 nodes 980585 nps 6809000 tthits 140344 pv b1c3 e7e6 e2
e3 b8c6 g1f3 g8f6 d2d4 c6d4
info depth 9 score cp 122 nodes 3962993 nps 1295000 tthits 513707 pv b1c3 e7e6 e
2e3 b8c6 g1f3 g8f6 d2d4 c6d4 d1d4
info depth 9 score cp 124 nodes 5014084 nps 2145000 tthits 652304 pv d2d4 e7e6 g
1f3 b8c6 b1c3 d7d5 c3d5
info depth 10 score cp -37 nodes 29175537 nps 3170000 tthits 2038167 pv d2d4 e7e
6 g1f3 b8c6 b1c3 d7d5 c3d5
bestmove d2d4 nodes 78014875

Any questions are more than welcomed. Thank you in advance!

[vittyvirus]

Oh, the nps is buggy in Yaka. I've uploaded the fix. The nps seem to wildly vary.

[cdani]

I saw that Yaka lacks Quiescence search. Without it, search is not stable, as for example finishes a line thinking that wins material when is for example a bad or equal exchange.

Without minimum stable search, hash table, reductions, null move and related stuff many times just go wrong because what seems a good move, in the next iteration results as a bad one, and move ordering ends destroyed.

So better before trying anything other, you should/must have a good qsearch.

[vittyvirus]

I saw that Yaka lacks Quiescence search. Without it, search is not stable, as for example finishes a line thinking that wins material when is for example a bad or equal exchange.

Without minimum stable search, hash table, reductions, null move and related stuff many times just go wrong because what seems a good move, in the next iteration results as a bad one, and move ordering ends destroyed.

So better before trying anything other, you should/must have a good qsearch.

I'd take your advice. But I'm troubled with what goes wrong with Yaka's EBF.

[Evert]

I saw that Yaka lacks Quiescence search. Without it, search is not stable, as for example finishes a line thinking that wins material when is for example a bad or equal exchange.

Without minimum stable search, hash table, reductions, null move and related stuff many times just go wrong because what seems a good move, in the next iteration results as a bad one, and move ordering ends destroyed.

So better before trying anything other, you should/must have a good qsearch.

I'd take your advice. But I'm troubled with what goes wrong with Yaka's EBF.

Fix your quiescence search first. Even if there is another problem, fixing it is not worth it. It's even possible that this is the cause for the problems you're seeing.

[vittyvirus]

It's even possible that this is the cause for the problems you're seeing.

Thank you for your advice.
I think I get the idea how.

[AndrewGrant]

Out of curiosity I ran a few test positions with and without quiescence search on my engine. Obviously more nodes were searched with a qSearch enabled, but I found that my branching factor went from about 2 with qSearch to 2.5 without qSearch.

added the qSearch won't solve all your problems here, but I would not be surprised if it slightly improved your EBF

[vittyvirus]

Out of curiosity I ran a few test positions with and without quiescence search on my engine. Obviously more nodes were searched with a qSearch enabled, but I found that my branching factor went from about 2 with qSearch to 2.5 without qSearch.

added the qSearch won't solve all your problems here, but I would not be surprised if it slightly improved your EBF

As Evert and Daniel have pointed out, qsearch leads to a more stable search. I think this is because of the horizon effect. The same move can get a score of, say, +1.0 at depth 5, -1.0 at depth 6, +1.0 at depth 7 and so on. This affects the move ordering severely, since seemingly bad moves (at that depth) are searched before seemingly good ones (at that depth).