Adversarial Search

Occasionally, some problems (i.e. games) have multiple opposing players. For zero sum games, using adversarial search can help you find the optimal strategy that you can make in a game.

Minimax Algorithm

There are 2 players, each player tries to maximise their utility at the cost of the other player. It works by doing a complete depth first search of the state space and returns the strategy with the highest utility. Minimising players (opponents) will choose strategies that will minimise your expected utility.

function MINIMAX-SEARCH (game,state) returns strategy
 let optimalExpectedUtility,optimalStrategy = MAX-VALUE(game,state)
 return optimalStrategy

function MAX-VALUE (game,state) returns (utility,strategy) pair
 if game.IsTerminal(state) then return game.Utility(state),null
 let maxUtility = -∞
 for each action in game.Actions(state) do
  let currentUtility,currentStrategy = MIN-VALUE(game,game.GenerateNextState(state,action))
  if currentUtility > maxUtility then
   maxUtility,optimalStrategy = currentUtility,currentStrategy
 return maxUtility,optimalStrategy

function MIN-VALUE (game,state) returns (utility,strategy) pair
 if game.IsTerminal(state) then return game.Utility(state),null
 let minUtility = ∞
 for each action in game.Actions(state) do
  let currentUtility,currentStrategy = MAX-VALUE(game,game.GenerateNextState(state,action))
  if currentUtility < minUtility then
   minUtility,optimalStrategy = currentUtility,currentStrategy
 return minUtility,optimalStrategy

The Minimax algorithm is complete and optimal only for finite problems and against rational opponents. It has a time complexity of O(bd) and a space complexity of O(bd) or O(d) (depending on implementation). The downside of this algorithm is that the whole game tree must be explored, which will take a long time for complex games such as chess.

Alpha Beta Pruning

Prune branches of the game tree that are obsolete.

Explain pruning

Pruning does not affect the solution but lowers the time complexity of minimax (but not space complexity). The order of strategies matter and with perfect ordering, the time complexity can be reduced to O(bd/2).

How To Improve Minimax

There are 2 main ways to improve minimax search. One is to use evaluation functions and the other is to use expectiminimax when dealing with irrational opponents.

Evaluation Functions

Evaluation Functions are a type of heuristic that is used to estimate the utility of a strategy. Better evaluation functions will take into account more data and adjust the expected utility accordingly. For example, in chess taking a queen will have a larger impact on the game than taking a pawn, so a good evaluation function will prioritise the taking of queens over pawns.

Evaluation functions may also reduce the complexity of a search problem when combined with iterative deepening depth first search. It does this by heuristically cutting off low utility branches before they are fully explored.

Expectiminimax

If we assume that our opponent does not act rationally, we can increase our utility even further.