2/05/2013

Thoughts about selective search

Because the branching factor affects the search so much, it makes sense to spend some time examining the different strategies used for pruning off some moves. Terminating the search before the search horizon might be risky, but on the other hand, some lines must be examined beyond the horizon in the quiescence search. The search depth will then be position-dependent in any case.

Null-move pruning is one technique often used in chess engines. It is based on the assumption that if a position is failing high after one passes a move and lets the opponent move twice, then the position is likely to fail high also if the move were actually made and a complete search performed. This is usually a safe assumption. An exception are the so-called zugzwang positions, where the obligation to move is actually a disadvantage. Zugzwangs occur most likely in the endgame, so the null-move should not be used there, unless one is extremely careful. The null-move search can be done with a shallower depth, so it will save a lot of time when the remaining depth is still large. One should not allow consecutive null-moves, because that would reduce the search to nothing.

Another widely used technique is pruning the branches near the horizon. If the position is quiet and the position would fail high with a clear margin if terminated at the current depth, the search can be terminated. This is usually safe only one or two plies from the horizon. Otherwise there are too many opportunities to get the score below beta. Also, the margin must be set high enough and the position must be quiet (not in the middle of a capturing sequence).

Quiescence search is launched at the horizon depth. If the position is quiet it will call the evaluation function directly. Otherwise, it will search through capturing sequences and probably some checks to see if the score would be different from the positional evaluation. One must be careful to choose only relevant moves to the search or otherwise the search tree can explode.

These ideas could be brought one step further by adding some expert knowledge into the move selection. The choice of moves at each depth would depend on the potential of those moves. A full search would be done only for the first few plies. The rest of the search would be like quiescence search. Then there would be two kinds of evaluation functions: one for positional evaluation and another for move selection. The quality of the evaluation functions is then critical to the quality of the search.

But these ideas are still just ideas. I will experiment with selective search strategies after an implementation of the alpha-beta search is runnning on the GPU.

No comments:

Post a Comment