Unformatted text preview:

Search Space Size ReductionsWorst Case: In an ordering where worst options evaluatedfirst, all nodes must be examined.Best Case: If nodes ordered so that the best options areevaluated first, then what?Slide CS472 – Adversarial Search 13The Need for Imperfect DecisionsProblem: Minimax assumes the program has time tosearch to the terminal nodes.Solution: Cut off search earlier and apply a heuristicevaluation function to the leaves.Slide CS472 – Adversarial Search 14Static Evaluation FunctionsMinimax depends on the translation of board quality into asingle, summarizing number. Difficult. Expensive.• Add up values of pieces each player has (weighted byimportance of piece).• Isolated pawns are bad.• How well protected is your king?• How much maneuverability to you have?• Do you control the center of the board?• Strategies change as the game proceeds.Slide CS472 – Adversarial Search 15Design Issues for Heuristic MinimaxEvaluation Function: Need to be carefully crafted anddepends on game! What criteria should an evaluationfunction fulfill?Slide CS472 – Adversarial Search 16Linear Evaluation Functions• w1f1+ w2f2+ ... + wnfn• This is what most game playing programs use• Steps in designing an evaluation function:1. Pick informative features2. Find the weights that make the program play wellSlide CS472 – Adversarial Search 17Design Issues for Heuristic MinimaxSearch: search to a constant depthWhat are problems with constant search depth?Slide CS472 – Adversarial Search 18Backgammon – Board123456 7 8 9 10 11 1224 23 22 21 20 19 18 17 16 15 14 13025Slide CS472 – Adversarial Search 19Backgammon – Rules• Goal: move all of your pieces off the board before youropponent does.• Black moves counterclockwise toward 0.• White moves clockwise toward 25.• A piece can move to any position except one where thereare two or more of the opponent’s pieces.• If it moves to a position with one opponent piece, thatpiece is captured and has to start it’s journey from thebeginning.Slide CS472 – Adversarial Search 20Backgammon – Rules• If you roll doubles you take 4 moves (example: roll 5,5,make moves 5,5,5,5).• Moves can be made by one or two pieces (in the case ofdoubles by 1, 2, 3 or 4 pieces)• And a few other rules that concern bearing off and forcedmoves.Slide CS472 – Adversarial Search 21123456 7 8 9 10 11 1224 23 22 21 20 19 18 17 16 15 14 13025White has rolled 6-5 and has 4 legal moves: (5-10,5-11),(5-11,19-24), (5-10,10-16) and (5-11,11-16).Slide CS472 – Adversarial Search 22Game Tree for BackgammonDICEMINMAXDICEMAX. . .. . .. . .B2 1 −1 1−1. . .6,66,51,11/361,21/18TERMINAL6,66,51,11/361,21/18.......................................CSlide CS472 – Adversarial Search 23Exp ectiminimaxExpectiminimax (n) =utility(n) for n, a terminal statemaxs∈Succ(n)expectiminimax(s) for n,aMaxnodemins∈Succ(n)expectiminimax(s) for n,aMinnodes∈Succ(n)P(s) * expectiminimax(s) for n, a chance nodeSlide CS472 – Adversarial Search 24Evaluation functionCHANCEMINMAX2233 114423 14.9 .1 .9 .12.1 1.320 20 30 30 1 1 400 40020 30 1 400.9 .1 .9 .121 40.9A1A2A1A2Slide CS472 – Adversarial Search 25State of the Art in Backgammon• 1980: BKG using two-ply (depth 2) search and lots ofluck defeated the human world champion.• 1992: Tesauro combines Samuel’s learning method withneural networks to develop a new evaluation function(search depth 2-3), resulting in a program ranked amongthe top 3 players in the world.Slide CS472 – Adversarial Search 26State of the Art in Checkers• 1952: Samuel developed a checkers program that learnedits own evaluation function through self play.• 1990: Chinook (J. Schaeffer) wins the U.S. Open. At theworld championship, Marion Tinsley beat Chinook.• 2005: Schaeffer et al. solved checkers for “WhiteDoctor” opening (draw) (about 50 other openings).Slide CS472 – Adversarial Search 27State of the Art in GoLarge branching factor makes regular search methodsinappropriate.Best computer Go programs ranked only “weak amateur”.Employ pattern recognition techniques and limited search.$2,000,000 prize available for first computer program todefeat a top level player.Slide CS472 – Adversarial Search 28History of Chess in AI500 legal chess1200 occasional player2000 world-ranked2900 Gary KasparovEarly 1950’s Shannon and Turing both had programs that(barely) played legal chess (500 rank).1950’s Alex Bernstein’s system, (500+).1957 Herb Simon claims that a computer chess programwould be world chess champion in 10 years...yeah, right.Slide CS472 – Adversarial Search 291966 McCarthy arranges computer chess match, Stanfordvs. Russia. Long, drawn-out match. Russia wins.1967 Richard Greenblatt, MIT. First of the modern chessprograms, MacHack (1100 rating).1968 McCarthy, Michie, Papert bet Levy (rated 2325) thata computer program would beat him within 10 years.1970 ACM started running chess tournaments. Chess 3.0-6(rated 1400).1973 By 1973...Slate:“It had become too painful even tolook at Chess 3.6 any more, let alone work on it.”1973 Chess 4.0: smart plausible-move generator rather thanSlide CS472 – Adversarial Search 30speeding up the search. Improved rapidly when put onfaster machines.1976 Chess 4.5: ranking of 2070.1977 Chess 4.5 vs. Levy. Levy wins.1980’s Programs depend on search speed rather thanknowledge (2300 range).1993 DEEP THOUGHT: Sophisticated special-purposecomputer; α − β search; searches 10-ply; singularextensions; rated about 2600.1995 DEEP BLUE: searches 14-ply; iterative deepeningα − β search; considers 100–200 billion positions perSlide CS472 – Adversarial Search 31move; regularly reaches depth 14; evaluation functionhas 8000+ features; singular extensions to 40-ply;opening book of 4000 positions; end-game database for5-6 pieces.1997 DEEP BLUE: first match won againstworld-champion (Kasparov).2002 IBM declines re-match. FRITZ played worldchampion Vladimir Kramnik. 8 games. Ended in a draw.Slide CS472 – Adversarial Search


View Full Document
Download Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?