How to speed up my engine Part 2

[lauriet]

I have been implementing and testing search techniques and thought it may be of interest to other newbies.
Here is some results from adding different methods into my program.
Yes the times and the depth is not state of the art, but the reduction in search time and nodes travelled do
show how effective things are.

This position is from a late opening/early middle game.


[d] r1bqr1k1/ppp2pbp/6p1/3pn3/6n1/2P1PN2/PPBN1PPP/R1BQR1K1 w



Fixed depth 8 ply search.
-------------------------

Vanilla Alpha/Beta:
Nodes: 37,447,578
Time: 504 seconds
Best move: E3E4
Score: -44 cp

Vanilla + Transposition Table
Nodes: 16,352,506
Time: 200 seconds
TT hits: 284,044
Best move: E3E4
Score: -45 cp

Vanilla + Null Move
Nodes: 8,811929
Time: 124 seconds
Null cuts: 6662
Best move: E3E4
Score: -44 cp

Vanilla + LMR
Nodes: 2,531,644
Time: 42 seconds
Best move: E3E4
Score: -44 cp

Vanilla + TT + Null
Nodes: 9,403,102
Time: 114 seconds
Null cuts: 5605
TT hits: 135,712
Best move: E3E4
Score: -44 cp

Vanilla + TT + LMR
Nodes: 1,474,213
Time: 21 seconds
TT hits: 20,856
Best move: E3E4
Score: -46 cp

Vanilla + Null + LMR
Nodes: 1,814,707
Time: 30 seconds
Null cuts: 192
Best move: E3E4
Score: -44 cp

Vanilla + TT + Null + LMR
Nodes: 1,499,700
Time: 21 seconds
Null cuts: 73
TT hits: 20530
Best move: E3E4
Score: 46 cp


It seems like LMR is a big winner. My implementation only reduces moves that are > 4 and
are not checks or captures. The search reduction is one.
Null + TT together obviously are not addative, so there must be major overlap in what they
are doing.
LMR seems to provide a good result with any other method.
Null moves seem to do less when combined with other methods, although they may be cutting out whole
chunks of the tree ?


Would anyone like to comment, make an observation, point out an error or expand on this ?

Regards
Laurie.

[hgm]

Just a caveat for newbies: LMR indeed usually is a big winner in terms of tree size. Unfortunately it often makes the engine also weaker, even if you search the same number of nodes.

[lauriet]

Yes, I should have qualified that I have done zero testing on the resultant strength of play.
I am only looking at speed of search, hoping that this will correlate with better play.
Of course as you point out,this is not necessarily true. I will have to speed some time time now playing games............unless Bob can send me his "Quantium" cluster for a while.

[Dann Corbit]

TT saves previous work, good and bad, so it does not have to be repeated. You can even think of it as a sort of pruning because you are not performing a search that you would have performed if you did not have a hash.

Null move produces cutoffs which prunes greatly for certain kinds of moves only. The test for null move is cheap, which is its big advantage, along with the reduction typically being large.

LMR prunes a broader range of moves than null move but the criteria are different so you do not have 100% overlap. Generally also, the reductions are not quite as large as null move reductions.

So I think that all of your results are exactly as expected.

[konsolas]

What sort of move ordering are you using (relevant to LMR)?

Perhaps PVS would be a useful thing to test.

[lauriet]

Move ordering is:

The PV move.
Reply to capture.
Other Captures....good and bad.
Quiet moves ordered by history heuristic.

[lauriet]

IF I add killer moves to my move ordering (after captures) the program gains about another 20% in time/nodes.
So with all these methods I am now getting about 4 extra ply of search.

Of course no strength result yet.....Bob still hasn't offered his cluster for testing.