Order of search techniques

[theturk1234]

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

[PK]

You can check for draw by repetition or by 50 move rule (or possibly by insufficient material) before checking for TT cutoff.

[Evert]

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

[theturk1234]

Evert:
Unfortunately I have not implemented any extensions or killers. Would you mind explaining the very basics to me?

Thanks
David Cimbalista

[Evert]

Evert:
Unfortunately I have not implemented any extensions or killers. Would you mind explaining the very basics to me?

I believe the only extension in common use today is the check extension.

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

[Sven]

Then PVS if we're in a PV node.
Regular AB call otherwise.

I hope you do PVS in the way it is intended:
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high

[theturk1234]

Yes, I'm doing it that way.

[AlvaroBegue]

Then PVS if we're in a PV node.
Regular AB call otherwise.

I hope you do PVS in the way it is intended:
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high

If we are using PVS, can we define a PV node as a node where beta>alpha+1?

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.

[Sven]

Then PVS if we're in a PV node.
Regular AB call otherwise.

I hope you do PVS in the way it is intended:
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high

If we are using PVS, can we define a PV node as a node where beta>alpha+1?

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.

Yes, we can. But I would write "beta != alpha+1", even though it is practically the same.

[jwes]

Then PVS if we're in a PV node.
Regular AB call otherwise.

I hope you do PVS in the way it is intended:
- full window for subtree of first move,
- zero window for all other subtrees, researching with full window in case of fail-high

If we are using PVS, can we define a PV node as a node where beta>alpha+1?

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.

Yes, we can. But I would write "beta != alpha+1", even though it is practically the same.

If beta < alpha + 1, wouldn't you want to throw an exception or something?