Last time: Simulated annealing algorithm Idea: Escape local extrema by allowing (cid:132) “bbaadd mmoovveess,,” bbuutt ggrraadduuaallllyy ddeeccrreeaassee their size and frequency. Note: goal here is to - maximize E. 1 Last time: Simulated annealing algorithm Idea: Escape local extrema by allowing (cid:132) “bbaadd mmoovveess,,” bbuutt ggrraadduuaallllyy ddeeccrreeaassee their size and frequency. Algorithm when goal - is to minimize E. < - 2 This time: Outline Game playing (cid:132) The minimax (cid:132) allgoriitthhm Resource limitations (cid:132) aallpphhaa-bbeettaa pprruunniinngg (cid:132)(cid:132) Elements of chance (cid:132) 3 What kind of games? Abstraction: To describe a game we (cid:132) must capture every relevant aspect of the game. Such as: Chess (cid:132) Tic-tac-toe (cid:132) … (cid:132) Accessible environments: Such (cid:132) ggaammeess aarree cchhaarraacctteerriizzeedd bbyy ppeerrffeecctt information 4 What kind of games? Search: game-playing then consists of (cid:132) a search through possible game positions Unpredictable opponent: introduces (cid:132) uunncceerrttaaiinnttyy tthhuuss ggaammee-ppllaayyiinngg mmuusstt deal with contingency problems 5 Searching for the next move Complexity: many games have a huge (cid:132) sseeaarrcchh ssppaaccee Chess: b = 35, m=100 ⇒ nodes =35 100 (cid:132) if each node takes about 1 ns to expplore then each move will take about 10 50 millennia to calculate. 6 Searching for the next move Resource (e.g., time, memory) limit: (cid:132) ooppttiimmaall ssoolluuttiioonn nnoott ffeeaassiibbllee//ppoossssiibbllee,, thus must approximate PPrruunniinngg:: mmaakkeess tthhee sseeaarrcchh mmoorree eeffffiicciieenntt 11. by discarding portions of the search tree that cannot improve quality result. Evaluation functions: heuristics to 2. evaluate utility of a state without exhaustive search. 7 Two-player games A game formulated as a search problem: (cid:132) Initial state: ? (cid:132) OOppeerraattoorrss:: ?? (cid:132) Terminal state: ? (cid:132) UUttiilliitty ffuncttiion: ?? (cid:132) 8 Game vs. search problem 9 Example: Tic-Tac-Toe Question: 1. b (branching factor) = ? 22. mm ((mmaaxx ddeepptthh)) == ?? 10