New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Intro Artificial Intelligence

by: Leland Swift

Intro Artificial Intelligence CS 580

Marketplace > George Mason University > ComputerScienence > CS 580 > Intro Artificial Intelligence
Leland Swift
GPA 3.66


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




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.

Similar to CS 580 at Mason

Popular in ComputerScienence


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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.