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


by: Allie West II


Allie West II

GPA 3.51


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 20 page Class Notes was uploaded by Allie West II on Thursday October 29, 2015. The Class Notes belongs to CSCI 5582 at University of Colorado at Boulder taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/231991/csci-5582-university-of-colorado-at-boulder in ComputerScienence at University of Colorado at Boulder.




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: 10/29/15
Trees and Adversarial Search Winston Chapter 6 Michael Eisenberg and Gerhard Fischer TA Ann Eisenberg Al Course Fall 1997 EisenbergFischer 1 AI Course Fall97 Why Study Games in Al problems are formalized real world knowledge common sense knowledge is not too important rules are fixed adversary modeling is of general importance eg in economic situations in military operations opponent introduces uncertainty programs must deal with the contingency problem complexity of games number of nodes in a search tree eg 1 legal positions in chess specification is simple no missing information welldefined problem 040 EisenbergFischer 2 Al Course Fall97 Game Playing Overview games as search problems perfect decisions in two person games imperfect decisions alphabeta pruning games with a Chance stateoftheart game programs EisenbergFisoher 3 AI Course Fall97 Examples Nim TicTacToe Checkers Arthur Samuel classic papers on tree pruning heuristics adaptive parameter improvement OthelloReversi see program in Norvig Al Programming and Boecker Eden Fischer Interactive Problem Solving Using LOGO Chess programs play at Grandmaster level Deep Blue beat Kasparov Go Backgammon program has beaten the world champion but was lucky Blackjack strategies for playing in casinos Thorp How To Beat the Dealer EisenbergFischer 4 Al Course Fall97 Example Nim rules 2 person game players alternate one move take 1 2 or 3 objects player who takes the last object will loose 27 26 25 24 25 24 23 24 23 22 23 22 21 Example Modified Version of Nim O EisenbergFisoher 5 AI Course Fall97 EisenbergFischer 6 AI Course Fall97 Formal Definition of Games as Search Problems initial state board position whose move a set of operators defining the legal moves of a player terminal test determining when the game is over utility function giving a numeric value for the outcome of a game chess 1 0 and 1 backgammon 192 to 192 EisehbergFischer 7 Al Course Fall97 Game Tree 0 A game tree is a representation that is a semantic tree In which nodes denote board configurations Branches denote moves 0 With writers that Establish that a node is for the maximizer or for the minimizer Connect a board configuration with a board configuration description 0 With readers that Determine whether the node is for the maximizer or minimizer Produce a board configuration39s description EisenbergFischer 8 AI Course Fall97 Search Procedures MINIMAX gt static evaluation conclusions about what to do at the deeper nodes of the search tree percolate up to determine what should happen at higher nodes ALPHABETA there is no need to explore disastrous moves any further can be augmented by a number of heuristic pruning procedures danger optimal moves may not be selected 0 general tradeoff lookahead operations patterndirected play EisenbergFischer 9 Al Course Fall97 Minimax Algorithm To perform a minimax search using MINIMAX o If the limit of search has been reached compute the static value of the current position relative to the appropriate player Report the result 0 Otherwise if the level is a minimizing level use MINIMAX on the children of the current position Report the minimum of the results 0 Otherwise the level is a maximizing level Use MINIMAX on the children of the current position Report the maximum of the results EisenbergFischer 10 Al Course Fall97 Heuristic Evaluation Functions allow us to approximate the true utility of a state without doing a complete search 0 changes utility function is replaced by an heuristic evaluation function terminal test is replaced by a cutoff test example for TicTacToe and Number Scrabble static value associated with each field 4 center corners 3 middle field of a row 2 chess material value pawn1 knight or bishop3 rook5 queen9 other features good pawn structure king safety mobility EisehbergFischer 11 Al Course Fall97 AlphaBeta Pruning basic idea it is possible to compute the correct minimax decision without looking at every node in the search tree gt pruning allows us to ignore portions of the search tree that make no difference to the final choice 0 general principle consider a node n somewhere in the tree such that a player has a chance to move to this node if player has a better chance m either at the parent node of n or at any choice point further up then n will never be reached in actual play effectiveness depends on the ordering in which the successors are examined try to examine first the successors that are likely to be best EisenbergFischer 12 Al Course Fall97 ALPHABETA Procedure To perform minimax search with the ALPHABETA procedure 0 If the level is the top level let alpha be 00 and let beta be 00 o lfthe limit of search has been reached compute the static value ofthe current position relative to the appropriate player Report the result lfthe level is a minimizing level Until all children are examined with ALPHABETA or until alpha is equal to or greaterthan beta Use the ALPHABETA procedure with the current alpha and beta values on a child note the value reported Compare the value reported with the beta value if the reported value is smaller reset beta to the new value Report beta 0 Otherwise the level is a maximizing level Until all children are examined with ALPHABETA or alpha is equal to or greater than beta Use the ALPHABETA procedure with the current alpha and beta value on a child note the value reported Compare the value reported with the alpha value ifthe reported value is larger reset alpha to the new value Report alpha EisenbergFischer 13 AI Course Fall97 Game Playing Case Study Othello Questions to Think about how would you write a game playing program for Othello what kind of evaluation function would you use or would you not use what is the most difficult aspect of playing the game well if you are an experienced Othello player articulate some of your Othello knowledge EisenbergFischer 14 Al Course Fall97 Rules each player takes 32 discs and chooses one color 64 discs are available to play move quotoutflankingquot your opponent gt then flipping the outflanked discs to your color definition of quotoutflankquot establishing a domain vocabulary black moves first gt then take turns if legal moves are available if a move is available gt one must take it outflanking occurs in all directions horizontally vertically diagonally all discs outflanked in any one move must be flipped even if it is to the player39s disadvantage end of game when it is no longer possible for either player to move either because all squares are filled or no legal move is available EisenbergFischer 15 Al Course Fall97 Incremental Development of Game Playing Programs let humans play against each other the program serves as a representational media the program checks for legal moves humans against program legal moves by the program good moves by the program humans against program the program being in the role of a coach program against program learning component program improve its play by playing games EisehbergFischer 16 AI Course Fall97 Humans against Program Incremental Additions to the quotSmartnessquot of the Program play randomly but legal may involve a nontrivial amount of knowledge computation have a static value associated with each square on the board have a dynamically value associated with each square on the board have an evaluation function taking other factors into account eg number of pieces search lookahead exploring alternatives using the evaluation function look one move ahead look several moves ahead using minimax alphabeta EisenbergFischer 17 AI Course Fall97 Strategy goal is clear but how can we achieve the goal corners are special they can never be outflanked gt question how do we get one of our pieces into the corner backward reasoning squares next to corners are not good border squares are desirable they can only be outflanked in only two directions squares next to border squares are not desirable get control of the game have many possible moves to choose from try to have as pieces of your color at any time in the game as possible EisenbergFischer 18 Al Course Fall97 Rules themselves may be changed original setup can va ry b w or b w EU 6 0 turn one direction all directions let the player decide an extended version of the program could handle all strategies in Chess many variations EisenbergFisoher 19 Al Course Fall97 Other Issues Othello as a computer game claim bruteforce search based on a good evaluation function can yield excellent play number of legal moves is small in most Situations humans have difficulties to quotvisualizequot the long range consequences of a move knowledge elicitation acquisition techniques two humans play the game against each other and think aloud thin spread of domain knowledge claim any amount of programming knowledge eg in Lisp C will not allow you to write a program which plays Othello well EisenbergFischer 20 Al Course Fall97


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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

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.