1
$\begingroup$

Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (not the optimal node itself), which means that in practice, a programmer must implement a method for identifying which of the root's children corresponds to the optimal value. For example, the results of the search may be stored in a tree structure that associates nodes with their values. The root node's optimal child can then by identified by finding the child whose value is the same as the root's value.

The return value of both alpha-beta and minimax should be independent of the order in which nodes are visited. However, in practice, multiple sibling nodes may have the optimal value, so we must implement a method for choosing between equally optimal children of the root. There are two main ways to do this:

  • With both algorithms, we can break ties in a way that depends on the order in which nodes were visited, for example by choosing the first or last optimal child that was visited.
  • With minimax, we can break ties in a way that is independent of the order in which nodes were visited, for example by choosing the optimal child whose bitboard representation is smallest.

Now, here is the crux of my question: Is it correct that alpha-beta terminates the search after finding an optimal child? If so, this would mean that there may be other optimal children that will not be identified by the search. If this is the case, then am I correct in thinking that with alpha-beta pruning, it is impossible to break ties between optimal nodes in a way that is independent of the order in which nodes are visited?

If this is correct, then it would mean that changing the order in which nodes are visited during alpha-beta search (for example, by visiting the more promising nodes first) will affect the moves chosen by a game engine, because it will affect which node the engine identifies as optimal at each game position. (This is not a problem, but it seems like something to be aware of when implementing and testing a game engine that uses alpha-beta pruning.)

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.