Which pruning technique to add to my engine?

Code, algorithms, languages, construction...

Which pruning technique to add to my engine?

Postby sandermvdb » Sun Jun 26, 2016 3:08 pm

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!
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Which pruning technique to add to my engine?

Postby hyatt » Mon Jun 27, 2016 7:00 pm

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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Which pruning technique to add to my engine?

Postby sandermvdb » Mon Jun 27, 2016 9:08 pm

Thanks for the short but clear answer!
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Which pruning technique to add to my engine?

Postby sandermvdb » Wed Jul 06, 2016 9:40 pm

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!
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest

cron