2
$\begingroup$

How can alpha-beta pruning be made safe for a chess program? Pruning away a certain set of nodes is safe when the tree is complete and it is known that no other new nodes can be found deeper in the tree, but obviously this is not the case in chess. If my program prunes away a move that looks bad because it sacrifices valuable material that may just be the sacrificial move that would have checkmated the opponent in another few additional ply (or just gain a material and/or tactical advantage)?

$\endgroup$
  • 6
    $\begingroup$ Alpha-beta cutoffs have nothing to do with what you're describing. The horizon effect afflicts all fixed depth minimax searches whether you use alpha-beta pruning or not. $\endgroup$ – Kyle Jones May 5 '13 at 6:08
  • $\begingroup$ Not research-level theoretical computer science. Migrating to Computer Science. $\endgroup$ – Dave Clarke May 5 '13 at 9:10
5
$\begingroup$

What you are describing is unrelated to alpha-beta pruning. The tendency of fixed-depth minimax searches to badly underestimate or overestimate positional scores in dynamic situations is known as the horizon effect. The problem is due to static evaluation being used on positions unsuited to such evaluation. Static evaluation scores a position based on things like material, pawn structure, and king mobility, properties that can be determined without extending the search tree. But some positions are transitional, needing more search to identify their nature.

The standard way to deal with this problem is to recursively apply a quiescence function to all terminal nodes that extends the search an extra ply if there are checks, forced captures or promotions available at that node. If no such moves are available, then the position is considered quiet and the usual static evaluation function is called.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy