Last time: Simulated annealing algorithm Idea: Escape local extrema by allowing “bad moves,”but gradually decreasebad moves, but gradually decrease their size and frequency.Note: goal here is tomaximize E.-1Last time: Simulated annealing algorithm Idea: Escape local extrema by allowing “bad moves,”but gradually decreasebad moves, but gradually decrease their size and frequency.Algorithm when goalis to minimize E.<-2-This time: Outline Game playing The minimaxlithalgorithm Resource limitationsalpha-beta pruning3alphabeta pruning Elements of chanceWhat kind of games? Abstraction: To describe a game we must capture every relevant aspect of the game. Such as: Chess Tic-tac-toe … Accessible environments: Such games are characterized by perfect4games are characterized by perfect informationWhat kind of games? Search: game-playing then consists of a search through possible game positions Unpredictable opponent: introduces uncertaintythus game-playing mustuncertainty thus gameplaying must deal with contingency problems5Searching for the next move Complexity: many games have a huge search spacesearch space Chess:b = 35, m=100⇒nodes = 35 100if each node takes about 1 ns to explorepthen each move will take about 10 50millennia to calculate.6Searching for the next move Resource (e.g., time, memory) limit: optimal solution not feasible/possible,optimal solution not feasible/possible, thus must approximate1Pruning:makes the search more efficient1.Pruning:makes the search more efficient by discarding portions of the search tree that cannot improve quality result.2. Evaluation functions: heuristics to evaluate utility of a state without exhaustive 7search.Two-player games A game formulated as a search problem: Initial state: ?Operators: ?Operators: ? Terminal state: ?Utilit f ti ?Utility function: ?8Game vs. search problem9Example: Tic-Tac-ToeQuestion:1. b (branching factor) = ?2m (max depth) = ?2.m (max depth) = ?10Type of games11The minimax algorithm Perfect play for deterministic environments with perfect information Basic idea: choose move with highest minimax value= best achievable payoff against best playpy12The minimax algorithmAlgorithm:1. Generate game tree completely2. Determine utility of each terminal state3. Propagate the utility values upward in the three by applyingMINandMAXoperators on the nodes inapplying MINand MAXoperators on the nodes in the current level4. At the root node use minimax decision to select the move with the max (of the mins) utility valueSteps 2 and 3 in the algorithm assume that13Steps 2 and 3 in the algorithm assume that the opponent will play perfectly.Generate Game Tree14Generate Game Treex1 ply1 moveoxxoxoxo15A subtreexxowinlosexxoooxlosedrawxxoooxxxoooxxxxoooxxxoooxxxxooxxxxooxxxxooxxxooxxxooxxxooxoooo oxoxoxoxooo oxxooxxxxooxxxxooxoxxooxoxxxoox16ooxxox xxxooxxoooxxoooxxoxooxxoWhat is a good move?xxowinlosexxoooxlosedrawxxoooxxxoooxxxxoooxxxoooxxxxooxxxxooxxxxooxxxooxxxooxxxooxoooo oxoxoxoxooo oxxooxxxxooxoxxooxoxxxoox17ooxxox xxooxxoooxxoxooxxoMinimax3812 4 6 14 252Mi i i t’ h•Minimize opponent’s chance•Maximize your chance18minimax = maximum of the minimum1stply2ndply2ply19JavaApplet-Minimx java appletdddd20Minimax: Recursive implementationp21Complete: ?Optimal: ?Time complexity: ?Space complexity: ?1. Move evaluation without complete search Complete search is too complex and impractical Evaluation function: evaluates value of state using heuristics and cuts off search New MINIMAX: CUTOFF-TEST: cutoff test to replace the termination condition (e.g., deadline, depth-limit, etc.)lf llf EVAL: evaluation function to replace utility function (e.g., number of chess pieces taken)22Do We Have To Do All That Work?MAXMIN381223Evaluation functions Weighted linear evaluation function:to combinenheuristics:f= w1f1 + w2f2 + + wnfnto combine nheuristics: f w1f1 + w2f2 + … + wnfnE.g,w’s could be the values of pieces (1 for prawn, 3 for bishop)24p(p, p) f’s could be the number of type of pieces on the boardNote: exact values do not matterOrdering is preserved25Minimax with cutoff: viable algorithm?Assume we have 100 seconds, evaluate 104nodes/s; cannodes/s; can evaluate
View Full Document
Unlocking...