Minimax algorithm function MINIMAX-DECISION(state)returns an action v←MAX-VALUE(state) return the action in SUCCESSORS(state)with value v function MAX-VALUE(state)returns a utility value if TERMINAL-TEST(state)then return UTILITY(state) U←-00 for a,s in SUCCESSORS(state)do MAX(v,MIN-VALUE(s)) return v function MIN-VALUE(state)returns a utility value if TERMINAL-TEST(state)then return UTILITY(state) U←0∞ for a,s in SUCCESSORS(state)do MIN(v,MAX-VALUE(s)) return v
Minimax algorithm
Properties of minimax Complete?Yes (if tree is finite) Optimal?Yes (against an optimal opponent) ● Time complexity?O(bm) Space complexity?O(bm)(depth-first exploration) ● 。For chess,b≈35，m≈100for"reasonable"games exact solution completely infeasible
Properties of minimax • Complete? Yes (if tree is finite) • • Optimal? Yes (against an optimal opponent) • • Time complexity? O(bm) • • Space complexity? O(bm) (depth-first exploration) • • For chess, b ≈ 35, m ≈100 for "reasonable" games → exact solution completely infeasible •