Intro Artificial Intelligence
Intro Artificial Intelligence CS 580
Popular in Course
Popular in ComputerScienence
This 8 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 580 at George Mason University taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/215124/cs-580-george-mason-university in ComputerScienence at George Mason University.
Reviews for Intro Artificial Intelligence
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
1ANm1PLAYING CHAPTER 5 SECTIONS 175 as 5m 1211 Kmeaka Chzybez 5 Sections 115 1 Games vs search problems quotUnpredictablequot opponent solution is a contingency plan Time limits unlikely to find goal must approximate Plan of attack 0 algorithm for perfect play Von Neumann 1944 o finite horizon approximate evaluation Zuse 1945 Shannon 1950 Samuel 1952 57 0 pruning to reduce costs McCarthy 1956 as 5m 1211 Kmeaka Chzybez 5 Sections 115 2 II MinimaX Perfect play for deterministic perfect information games Idea choose move to position with highest minimum value best achievable payoff against best play Eg 2 ply game MAX as 5m 1211 Kmeakg Chaptez 5 Sections 14 a MinimaX algorithm function MINIMAxeDECISIONgame returns an opemtor for each 0 in OPERATORSgame do VALUEop e MINIMAX7VALUEAPPLY0J7 game7 game end return the 0 with the highest VALUE0p function MINIMAX7VALUEstate game returns a utility value if TERMINALiTESTgamestate then return UTILITYgamestate else if MAX is to move in state then return the highest MINIMAxJALUE of SUCCESSORSstate e return the lowest MINIMAxJALUE of SUCCESSORsstate as 5m 1211 Kmeakg Chaptez 5 Sections 14 4 Properties of minimax Complete77 Yes if tree is finite chess has specific rules for this El Yes against an optimal opponent Otherwise77 Time complexity77 0bm Space complexity77 0bm depth first exploration For chess b m 35 m m 100 for quotreasonablequot games exact solution completely infeasible as 5m 1211 Kmeaka Chzybez 5 Sections 14 5 II Resource limits Suppose we have 100 seconds explore 104 nodessecond m nodes per move Standard approach 0 cuta test eg depth limit perhaps add quiescence search 0 evaluation function estimated desirability of position as 5m 1211 Kmeaka Chzybez 5 Sections 14 e II Evaluation functions Black to move White to move White slightly better Black winning For chess typically linear weighted sum of features EVAL5 w1f1s w2f2s wnfns eg wl 9 with f1s number of white queens number of black queens etc as 5m 1211 Kmeakg Chaptez 5 Sections 14 7 Cutting off search MINIMAXCUTOFF is identical to MINIMAXVALUE except 1 TERMINAL is replaced by CUTOFF 2 UTILITY is replaced by EVAL Does it work in practice b72106 b35 s m4 4 ply lookahead is a hopeless chess player 4 ply m human novice 8 ply m typical PC human master 12 ply m Deep Blue Kasparov as 5m 1211 Kmeakg Chaptez 5 Sections 14 a ai pruning example MAX gt3 MIN as 5m 1211 Kmeakg Chzybez 5 Sections 14 a ll Properties of ai Pruning does not affect final result Good move ordering improves effectiveness of pruning With perfect orderingquot time complexity 0bm2 doubles depth of search can easily reach depth 8 and play good chess A simple example of the value of reasoning about which computations are relevant a form of metar easanmg as 5m 1211 Kmeakg Chzybez 5 Sections 14 m Why is it called ai MAX MIN MAX MIN V 04 is the best value to MAX found so far off the current path If V is worse than a MAX will avoid it prune that branch Define similarly for MIN as 5m 1211 Kmeaka Chaptez 5 Sections 14 11 The ai algorithm Basically MINIMAX keep track of a prune function MAX7VALUEstate gamea returns the minimax Value of state inputs state current state in game game game description a the best score for MAX along the path to state 8 the best score for MIN along the path to state if CUTOFFiTESTstate then return EVALstate for each s in SUCCESSORSstate do a H MAXa MIN7VALUEs game a if a 2 5 then return 5 end return a function MIN7VALUEstate game 048 returns the mjnjmax Value of state if CUTOFFiTESTstate then return EVALstate for each s in SUCCESSORSstate do Be MIN6 MAX7VALUEs game 0413 if g a then return at end return 5 as 5m 1211 Kmeaka Chaptez 5 Sections 14 12 Deterministic games in practice Checkers Chinook ended 40 year reign of human world champion Marion Tinsley in 1994 Used an endgame database defining perfect play for all positions involving 8 or fewer pieces on the board a total of 443748401247 positions Chess Deep Blue defeated human world champion Gary Kasparov in a six game match in 1997 Deep Blue searches 200 million positions per second uses very sophisticated evaluation and undisclosed methods for extending some lines of search up to 40 ply Othello human champions refuse to compete against computers who are too good Go human champions refuse to compete against computers who are too bad In go b gt 300 so most programs use pattern knowledge bases to suggest plausible moves as 5m 1211 Kmeaka Chzybez 5 Sections 14 18 Nondeterministic games Eg in backgammon the dice rolls determine the legal moves Simplified example with coin flipping instead of dice rolling CHANCE as 5m 1211 Kmeaka Chzybez 5 Sections 14 14 Algorithm for nondeterministic games EXPECTIMINIMAX gives perfect play Just like MINIMAX except we must also handle chance nodes if state is a chance node then return average of EXPECTIMINIMAX VALUE of SUCCESSORsstate A version of cv pruning is possible but only if the leaf values are bounded Why77 cs 53m 1211 Kmeakg Chzybez 5 Sections 14 15 Nondeterministic games in practice Dice rolls increase I 21 possible rolls with 2 dice Backgammon m 20 legal moves can be 6000 with 1 1 roll depth 4 20 gtlt21gtlt 203 m 12 gtlt109 As depth increases probability of reaching a given node shrinks value of lookahead is diminished cv pruning is much less effective TDGAMMON uses depth 2 search very good EVAL m world champion level as 53m 1211 Kmeakg Chzybez 5 Sections 14 m
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'