Minimax algorithmfunction MINIMAx-DECISION(state)returns an actionUMAX-VALUE(state)returntheactioninSUCCESSORs(state)withvaluefunction MAx-VALUE(state)returns a utility valueif TERMINAL-TEST(state)then return UTILITY(state)V←-8fora,sinSuCCESSORs(state)doU← MAX(u,MIN-VALUE(s)return yfunction MIN-VALUE(state) returns a utility ualueif TERMINAL-TEST(state)then return UTILITY(state)u←8fora,s inSucCEsSORs(state)doU MIN(u,MAX-VALUE(s)returnu6
6 Minimax algorithm
Another Example (From Nilsson“Principles of Al")SEARCHSTRATEGIESOOSMartNodNATNoN区OFORDECOMPOSABLEPRODUCTIONSYSTEMS###部#p#Fig toMinimatapphiedto tic.irttaerD7
7 Another Example (From Nilsson “Principles of AI”)
Properties of minimaxComplete? Yes (if tree is finite)Optimal? Yes (against an optimal opponentTime complexity? O(bm)Space complexity? O(bm) (depth-first exploration)Forchess,b=35,m~100for"reasonable"games→ exact solution completely infeasible8
8 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 •