Pruning

[Jorma Nieminen]

In one of the posts here the writer mentioned that commercial engines are very selective in the first few plies. Does anyone know how this is achieved? Well, I don't expect authors of commercial engines to reveal their trade secrets, but would authors of amateur engines be willing to tell how they prune the tree. Since I am the one asking this maybe I should be the first to tell about the insides of my engine. I use what I call "full gamma pruning". This means that each move is statically evaluated. If the value is worse than any other search result of same color at lower plies the move is pruned. Sounds risky, but works quite well in practice. Anybode else willing to share how they prune the search tree?

Jorma

[zamar]

Stockfish uses:

* Null move pruning
* Razoring
* Value based futility pruning
* Move count based pruning (also known as history pruning)

For a list of different kind of techniques:
http://chessprogramming.wikispaces.com/pruning

Also of great interest are different kind of extenstions and reductions:
http://chessprogramming.wikispaces.com/reductions
http://chessprogramming.wikispaces.com/Extensions

[MattieShoes]

I think Null move pruning is by far the most ubiquitous and best forward pruning system in chess. The basic idea:

At some point in the tree other than the root, skip your move so opponent makes two consecutive moves. Now search this at a reduced depth. If the score is still worse than what you've already found, don't bother to do a full depth regular search on that move.

The only major hurdle after that is to avoid getting the wrong answers in zugzwang positions (which mainly happen in the endgame with few pieces on the board)

There are other schemes usually used in addition to null move pruning, but I think null move is the forward-pruning heavy hitter in most all strong engines.

[metax]

I have not really understood your description of 'full gamma pruning' and I cannot find it anywhere on the internet...

[Jorma Nieminen]

Gamma algorithm is very simple : you do a static evaluation of the move. If the value is less than the score of the best move so far the move is pruned away with the expectation that since it will be the opponent moving next the score will just get worse. Is this sound? Well, not really, but then all forward pruning methods carry a risk. Full gamma pruning is an idea that I developed myself, so you won't find it in the Internet. The idea is that we have a global array with all best scores at all plies. After static evaluation we don't just compare it to the best move of the same ply, but against all moves of the same color. In other words if the program is considering move at ply 7, it will compare it against the best score at plies 1,3 ,5 and 7. Again, this is of course not theoretically sound, but in my test games it has pruned the tree fairy well without making bad blunders.

Jorma

[Gian-Carlo Pascutto]

I use what I call "full gamma pruning". This means that each move is statically evaluated. If the value is worse than any other search result of same color at lower plies the move is pruned. Sounds risky, but works quite well in practice.
Jorma

.

So, if you're winning, you don't prune anything, and if you're losing, you prune everything?

I don't believe that can really work.