DOC PREVIEW
Duke CPS 108 - Games

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

GamesWhy Study Games?Why Are Games Good for AI?History of Games in AIGames TodayGame SetupZero Sum GamesCharacterizing GamesGame TreesSlide 10MinimaxMinimax ValuesMinimax PropertiesMinimax in the Real WorldEvaluation FunctionsDesiderata for Evaluation FunctionsSearch Control IssuesPruningAlpha-beta pruningHow to pruneMax node pruningImplementing alpha-betaAmazing facts about alpha-betaWhat About Probabilities?ExpectiminimaxExpectiminimax is nastyMultiplayer GamesConclusionsGamesCPS 170Ron ParrWhy Study Games?•Many human activities can be modeled as games–Negotiations–Bidding–TCP/IP–Military confrontations–Pursuit/Evasion•Games are used to train the mind–Human game-playing, animal play-fightingWhy Are Games Good for AI?•Games typically have concise rules•Well-defined starting and end points•Sensing and effecting are simplified–Not true for sports games–See robocup•Games are fun!•Downside: Getting taken seriously (not)–See robo search and rescueHistory of Games in AI•Computer games have been around almost as long as computers (perhaps longer)–Chess: Turing (and others) in the 1950s–Checkers: Samuel, 1950s learning program•Usually start with naïve optimism•Follow with naïve pessimism•Simon: Computer chess champ by 1967•Many, e.g., Kasparov, predicted that a computer would never be championGames Today•Computers perform at champion level–Backgammon, Checkers, Chess, Othello•Computers perform well–Bridge•Computers still do badly–Go, HexGame Setup•Most commonly, we study games that are:–2 player–Alternating–Zero-sum–Perfect information•Examples: Checkers, chess, backgammon•Assumptions can be relaxed at some expense•Economics studies case where number of agents is very large–Individual actions don’t change the dynamicsZero Sum Games•Assign values to different outcomes•Win = 1, Loss = -1•With zero sum games every gain comes at the other player’s expense•Sum of both player’s scores must be 0•Are any games truly zero sum?Characterizing Games•Two-player games are very much like search–Initial state–Successor function–Terminal test–Objective function (heuristic function)•Unlike search–Terminal states are often a large set–Full search to terminal states usually impossibleGame Treesxoxoxoxoxoxoxoxoxoxoxoxoxx xxoxoxoxxoxoxoxxoxoxoxxoxoxoxxoxoxoxxoxoxoxo oooooPlayer 1Player 2Player 1Game TreesMax nodesMin nodesTerminal NodesA1A2A3A11A12A21A22A31 A32Minimax•Max player tries to maximize his return•Min player tries to minimize his return•This is optimal for both (zero sum))(minimaxmax)(minimax)(succesorsmaxsnns)(minimaxmin)(minimax)(succesorsminsnnsMinimax ValuesMax nodesMin nodes3 12 2 4 1523 223Minimax Properties•Minimax can be run depth first–Time O(bm)–Space O(bm)•Assumes that opponent plays optimally•Based on a worst-case analysis•What if this is incorrect?Minimax in the Real World•Search trees are too big•Alternating turns double depth of the search–2 ply = 1 full turn•Branching factors are too high–Chess: 35–Go: 361•Search from start never terminates in non-trivial gamesEvaluation Functions•Like heuristic functions•Try to estimate value of a node without expanding all the way to termination•Using evaluation functions–Do a depth-limited search–Treat evaluation function as if it were terminal•What’s wrong with this?• How do you pick the depth?•How do you manage your time?•Iterative deepening, quiescenceDesiderata for Evaluation Functions•Would like to put the same ordering on nodes (even if values aren’t totally right)•Is this a reasonable thing to ask for?•What if you have a perfect evaluation function?•How are evaluation functions made in practice?–Buckets–Linear combinations•Chess pieces (material)•Board control (positional, strategic)Search Control Issues•Horizon effects–Sometimes something interesting is just beyond the horizon–How do you know?•When to generate more nodes?•If you selectively extend your frontier, how do you decide where?•If you have a fixed amount of total game time, how do you allocate this?Pruning•The most important search control method is figuring out which nodes you don’t need to expand•Use the fact that we are doing a worst-case analysis to our advantage–Max player cuts off search when he knows min player can force a provably bad outcome–Min player cuts of search when he knows max can force a provably good (for max) outcomeAlpha-beta pruningMax nodesMin nodes3 12 2 4 1523 223How to prune•We still do (bounded) DFS•Expand at least one path to the “bottom”•If current node is max node, and min can force a lower value, then prune siblings•If curent node is min node, and max can force a higher value, then prune siblingsMax node pruning2 424Max nodesImplementing alpha-betamax_value(state, alpha, beta)if cutoff(state) then return eval(state)for each s in successors(state) do alpha = max(alpha, min_value(s, alpha, beta)) if alpha >= beta the return betaendreturn alphamin_value(state, alpha, beta)if cutoff(state) then return eval(state)for each s in successors(state) do beta = min(alpha, max_value(s, alpha, beta)) if beta <= alpha the return alphaendreturn betaAmazing facts about alpha-beta•Empirically, alpha-beta has the effect of reducing the branching factor by half for many problems•This effectively doubles the horizon that can be searched•Alpha-beta makes the difference between novice and expert computer playersWhat About Probabilities?Max nodesMin nodesChancenodesP=0.5 P=0.5P=0.6P=0.4P=0.9P=0.1Expectiminimax•n random outcomes per chance node•O(bmnm) time)(eminimaxmax)(eminimax)(succesorsmaxsnns)(eminimaxmin)(eminimax)(succesorsminsnns)()(eminimax)(eminimax)(succesorschancespsnnsExpectiminimax is nasty•High branching factor•Randomness makes evaluation fns difficult–Hard to predict many steps into future–Values tend to smear together–Preserving order is not sufficient•Pruning is problematic–Need to prune based upon bound on an expectation–Need a priori bounds on the evaluation functionMultiplayer Games•Things sort-of generalize•We can maintain a vector of possible values for each player at each node•Assume that each player acts greedily•What’s wrong with this?Conclusions•Game tree search is a special kind of search•Rely heavily on heuristic evaluation functions•Alpha-beta is a


View Full Document

Duke CPS 108 - Games

Download Games
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 Games 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 Games 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?