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!
Which pruning technique to add to my engine?
-
- Posts: 24
- Joined: Wed Jun 01, 2016 3:52 pm
-
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
- Contact:
Re: Which pruning technique to add to my engine?
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.
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.
-
- Posts: 24
- Joined: Wed Jun 01, 2016 3:52 pm
Re: Which pruning technique to add to my engine?
Thanks for the short but clear answer!
-
- Posts: 24
- Joined: Wed Jun 01, 2016 3:52 pm
Re: Which pruning technique to add to my engine?
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![Smile :)](./images/smilies/icon_e_smile.gif)
I guess futility-pruning is up next!
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
![Smile :)](./images/smilies/icon_e_smile.gif)
I guess futility-pruning is up next!