Hi all,
I'm having problems reducing the size of my search tree.
Maybe some of you would have some insight where I could improve.
In search, I first check for a TT cutoff.
Now I do null move pruning if we're not in check and if this is not a PV node and if depth > 3.
Next I generate all moves.
Next I check for a draw or mate.
Next I do some move ordering based on hash move and capture value with MVV-LVA. I sort the move list.
I loop through the moves.
If we're at depth 2 and we're not in check and not in a PV node, do futility pruning. Then razoring.
Then LMR at depth > 2 and moves searched > 2.
Then PVS if we're in a PV node.
Regular AB call otherwise.
If score >= beta save to the TT and return.
If score > alpha alpha = score.
Outside move loop, save to TT and return alpha.
Does it look like I'm doing anything wrong here? I'd prefer not to post my long search function
Is anything out of order? i.e. does it matter if any of the steps is done before the others?
Thanks for your thoughts,
David Cimbalista
Order of search techniques
Moderators: hgm, Rebel, chrisw
-
- Posts: 893
- Joined: Mon Jan 15, 2007 11:23 am
- Location: Warsza
Re: Order of search techniques
You can check for draw by repetition or by 50 move rule (or possibly by insufficient material) before checking for TT cutoff.
Pawel Koziol
http://www.pkoziol.cal24.pl/rodent/rodent.htm
http://www.pkoziol.cal24.pl/rodent/rodent.htm
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Order of search techniques
What do you do for ordering quiet moves? Do you use killers/counter-move/history?
Do you use a check extension?
Your reduction scheme looks quite aggressive. Perhaps too aggressive. If that triggers a fail high or fail low at the root it can slow down your search too (due to the overhead of researching).
Do you use a check extension?
Your reduction scheme looks quite aggressive. Perhaps too aggressive. If that triggers a fail high or fail low at the root it can slow down your search too (due to the overhead of researching).
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Order of search techniques
Evert:
Unfortunately I have not implemented any extensions or killers. Would you mind explaining the very basics to me?
Thanks
David Cimbalista
Unfortunately I have not implemented any extensions or killers. Would you mind explaining the very basics to me?
Thanks
David Cimbalista
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Order of search techniques
I believe the only extension in common use today is the check extension.theturk1234 wrote:Evert:
Unfortunately I have not implemented any extensions or killers. Would you mind explaining the very basics to me?
The idea is this: if a move gives check, extend the search by 1 ply. You can refine this a bit, say by not extending checking moves with negative SEE. That's a refinement that can wait though.
Other common extensions are the recapture extension and the singular extension. In all cases the idea is that forced moves are extended because not doing so just eats plies and pushes threats over the horizon. Recognising such forced moves is hard, and being too generous with awarding extensions just blows up the search tree for no reason.
Killers are quiet moves that cause a cut-off: if a quiet move (not a capture, not a promotion, not a check evasion) causes a beta cut-off, store it in an array indexed by ply (ie, killer[ply] = move). Use these for move ordering: killers should be sorted ahead of other quiet moves, and can be sorted ahead of losing captures too. Important: don't reduce (LMR) a killer move.
Most programs use two killer slots per ply level, some use only one. You need to figure out what works best for you.
Another important consideration: do you use a verification search? If you apply LMR, the expectation is that the search fails low. If it does not, there is some threat that you may need to counter. Researching the move to normal depth may be a good idea in this case.
Many of these ideas (including example code) can be found on the chess programming wiki (https://chessprogramming.wikispaces.com/).
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Order of search techniques
I hope you do PVS in the way it is intended:theturk1234 wrote:Then PVS if we're in a PV node.
Regular AB call otherwise.
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Order of search techniques
Yes, I'm doing it that way.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Order of search techniques
If we are using PVS, can we define a PV node as a node where beta>alpha+1?Sven Schüle wrote:I hope you do PVS in the way it is intended:theturk1234 wrote:Then PVS if we're in a PV node.
Regular AB call otherwise.
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high
I realize this question is enough of a tangent that perhaps it should be in its own thread, but I expect a single answer will do, and perhaps it will be informative to other people reading this thread.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Order of search techniques
Yes, we can. But I would write "beta != alpha+1", even though it is practically the same.AlvaroBegue wrote:If we are using PVS, can we define a PV node as a node where beta>alpha+1?Sven Schüle wrote:I hope you do PVS in the way it is intended:theturk1234 wrote:Then PVS if we're in a PV node.
Regular AB call otherwise.
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high
I realize this question is enough of a tangent that perhaps it should be in its own thread, but I expect a single answer will do, and perhaps it will be informative to other people reading this thread.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Order of search techniques
If beta < alpha + 1, wouldn't you want to throw an exception or something?Sven Schüle wrote:Yes, we can. But I would write "beta != alpha+1", even though it is practically the same.AlvaroBegue wrote:If we are using PVS, can we define a PV node as a node where beta>alpha+1?Sven Schüle wrote:I hope you do PVS in the way it is intended:theturk1234 wrote:Then PVS if we're in a PV node.
Regular AB call otherwise.
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high
I realize this question is enough of a tangent that perhaps it should be in its own thread, but I expect a single answer will do, and perhaps it will be informative to other people reading this thread.