6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games

Next: Static Board Evaluator (Evaluation Previous: Examples

Minimax Properties

  • Complete, if tree is finite
  • Optimal, if play against optimal opponent (or opponent with same strategy)
  • Time complexity is \(O(b^m)\)
  • Space complexity is \(O(bm)\) (depth-first exploration)
  • If we have 100 seconds to make a move and we can explore \(10^4\) nodes/second, then we can consider \(10^6\) nodes per move

Standard approach is

  • Apply a cutoff test (depth limit, quiescence)
  • Evaluate nodes at cutoff (evaluation function estimates desirability of position)