Page 1 of 1

Which pruning technique to add to my engine?

Posted: Sun Jun 26, 2016 3:08 pm
by sandermvdb
I am working on a chess-engine and am quite happy with the result. One area where I am a bit struggling is pruning nodes. Which of the following techniques should I add first to my engine (best result, least risk)?
- null-move pruning (verified or not?)
- aspiration window
- futility-pruning
- delta-pruning (is futility pruning in the quiescence-search?)
- principal-variation (is negascout?)
- SEE pruning? (reduce bad-captures?)
- other options?

My search is currently based on the following:
- negamax
- quiescence-search (captures and promotions, unlimited depth)
- killer-heuristic
- transposition-table
- sorting using MVV-LVA

Counted nodes (startposition, without TT), so every ply is *7 more nodes than previous ply...:
1 20
2 96
3 967
4 4054
5 30722
6 140274
7 1058345
8 3879406
9 38892632
10 163816787

Thanks!

Re: Which pruning technique to add to my engine?

Posted: Mon Jun 27, 2016 7:00 pm
by hyatt
Null-move has to be first. I don't use verification myself. Some do, although usually only at high remaining depth.

aspiration window is not a pruning technique, neither is PVS. It is just a slightly optimized alpha/beta search that typically searches fewer nodes than pure alpha/beta, but it doesn't do any sort of forward pruning.

I would start with null-move, then add LMR. Then futility pruning / late move pruning / etc.

Re: Which pruning technique to add to my engine?

Posted: Mon Jun 27, 2016 9:08 pm
by sandermvdb
Thanks for the short but clear answer!

Re: Which pruning technique to add to my engine?

Posted: Wed Jul 06, 2016 9:40 pm
by sandermvdb
Just added null-move pruning and LMR. Results:

1 20
2 96
3 968
4 4148
5 24753
6 47132
7 257359
8 510715
9 1563556
10 4997395

So every ply now is about 4 times more nodes than the previous ply. I'm happy with the result :)

I guess futility-pruning is up next!