How to speed up my engine Part 2

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
lauriet
Posts: 198
Joined: Sun Nov 03, 2013 8:32 am
Contact:

How to speed up my engine Part 2

Post by lauriet » Tue Jul 12, 2016 5:23 am

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.

User avatar
hgm
Posts: 25044
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to speed up my engine Part 2

Post by hgm » Tue Jul 12, 2016 5:41 am

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
Posts: 198
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: How to speed up my engine Part 2

Post by lauriet » Tue Jul 12, 2016 9:41 am

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

Dann Corbit
Posts: 11625
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: How to speed up my engine Part 2

Post by Dann Corbit » Tue Jul 12, 2016 12:51 pm

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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

konsolas
Posts: 182
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Re: How to speed up my engine Part 2

Post by konsolas » Tue Jul 12, 2016 5:54 pm

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

Perhaps PVS would be a useful thing to test.

lauriet
Posts: 198
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: How to speed up my engine Part 2

Post by lauriet » Tue Jul 12, 2016 10:40 pm

Move ordering is:

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

lauriet
Posts: 198
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: How to speed up my engine Part 2

Post by lauriet » Wed Jul 13, 2016 11:26 am

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

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

Post Reply