In most practical tasks it is necessary to reduce the size of the search space somehow: even with tic-tac-toe the first few turns take minimax too long. There is a method built upon minimax, which can prune some parts of the searched space (i.e. they do not have to be searched) and find the provably optimal action even so. It is called alfa-beta search – by the two new variables it introduces [essentials, aima]:

  • Alpha: the greatest value of a max node found so far under the current branch of the tree;
  • Beta: the smallest value of a min node found so far under the current branch of the tree.

Using these two variables, some sub-trees can be pruned. They do not need to be searched, because they provably have no impact on the value.

Literature

  1. [essentials] Leyton-Brown, K. and Shoham, Y., 2008. Essentials of game theory: A concise multidisciplinary introduction. Synthesis lectures on artificial intelligence and machine learning, 2(1), pp.1-88.
  2. [aima] Russell, S. and Norvig, P., 2002. Artificial intelligence: a modern approach.