Minimax search

Description:

• In a State-space Search Tree
• Player alternate turn
• Compute each node’s minimax value
  • meaning the min or max value depends on who is taking the turn
• Search with DFS, with b moves each layer and m layers
  • Time: $O(b^m)$
  • Space: $O(bm)$

Optimizing:

• Game tree pruning/Alpha-Beta Pruning:
  • Metareasoning
  • Has no effect on minimax value at root
  • If MAX agent knows that MIN agent will choose based on his situation, we can ignore the paths that is not going to be used
    • ex:
    • Given the choice at E, MAX agent knows that MIN Agent has value 3 at B
    • Then when MAX agent found 5 under E, there is no point going for more as other is bigger 5 will not be picked
    • At F, MAX will choose 1 but knowing C will pick smaller or equal to 1, so MAX prune G
    • So we prune the whole E
  • Algorithm is more effective with the right child ordering:
    • with perfect ordering → $O(b^{m/2})$
• → Depth Limiting Search

Uncertainty minimax search:

• Expectimax Search and Expectiminimax Search