Games & Adversarial SearchGames vs. search problemsGame tree (2-player, deterministic, turns)MinimaxProperties of minimaxPruningα-β pruning exampleSlide 8Slide 9Slide 10Slide 11Properties of α-βThe AlgorithmTry it yourselfPractical ImplementationEvaluation functionsDeterministic games in practiceChance Games.Expected MinimaxSummaryGames & Adversarial SearchChapter 6Section 1 – 4Games vs. search problems•"Unpredictable" opponent specifying a move for every possible opponent’s reply.•Time limits unlikely to find goal, one must approximateGame tree (2-player, deterministic, turns)How do we search this tree to find the optimal move?•Idea: choose a move to a position with the highest minimax value = best achievable payoff against a rational opponent. Example: deterministic 2-ply game:Minimaxminimax valueMinimax value is computedbottom up:-Leaf values are given.-3 is the best outcome for MIN in this branch.-3 is the best outcome for MAX in this game.-We explore this tree in depth-first manner.Properties of minimax•Complete? Yes (if tree is finite)•Optimal? Yes (against an rational opponent)•Time complexity? O(bm)•Space complexity? O(bm) (depth-first exploration)•For chess, b ≈ 35, m ≈100 for "reasonable" games exact solution completely infeasiblePruning1. Do we need to expand all nodes? 2. No: We can do better by pruning branches that will not lead to success.a b-α-β pruning exampleMAX knows that it can at least get “3” by playing this branchMIN will choose “3”, because it minimizes the utility (which is good for MIN)α-β pruning exampleMIN can certainly do as good as2, but maybe better (= smaller)MAX knows that the new branch will never be better than 2 for him.He can ignore it.α-β pruning exampleMIN will do at least as good as 14 in this branch(which is very good for MAX!) so MAX will wantto explore this branch more.α-β pruning exampleMIN will do at least as good as 5 in this branch(which is still good for MAX) so MAX will wantto explore this branch more.α-β pruning exampleBummer (for MAX): MIN will be ableto play this last branch and get 2. This is worse than 3, so MAX will play 3.Properties of α-β•Pruning does not affect final result (it is exact).•Good move ordering improves effectiveness of pruning (see last branch in example)•With "perfect ordering," time complexity = O(bm/2) doubles depth of searchThe Algorithm•Visit the nodes in a depth-first manner•Maintain bounds on nodes.•A bound may change if one of its children obtains a unique value.•A bound becomes a unique value when all its children have been checked or pruned.•When a bound changes into a tighter bound or a unique value, it may become inconsistent with its parent.•When an inconsistency occurs, prune the sub-tree by cutting the edge between the inconsistent bounds/values. This is like propagating changes bottom-up in the tree.Try it yourself3 4 1 2 7 856-which nodes can be pruned?-always try going right before going left.-maintain bounds!Practical ImplementationHow do we make this practical?Standard approach:•cutoff test: (where do we stop descending the tree) –depth limit –better: iterative deepening–cutoff only when no big changes are expected to occur next (quiescence search).•evaluation function –When the search is cut off, we evaluate the current state by estimating its utility. This estimate if captured by the evaluation function.Evaluation functions•For chess, typically linear weighted sum of featuresEval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s)•e.g., w1 = 9 with f1(s) = (number of white queens) – (number of black queens), etc.Deterministic games in practice•Checkers: Chinook ended 40-year-reign of human world champion Marion Tinsley in 1994. •Chess: Deep Blue defeated human world champion Garry Kasparov in a six-game match in 1997. •Othello: human champions refuse to compete against computers: they are too good.•Go: human champions refuse to compete against computers: they•are too bad.Chance Games. Backgammonyour element of chanceExpected Minimax( ) Minimax( )3 0.5 4 0.5 2chance nodesv P n n= �= � + ��Again, the tree is constructed bottom-up.Now we have even more nodesto search!Summary•Games are fun to work on!•We search to find optimal strategy•perfection is unattainable approximate•Chance makes games even
View Full Document
Unlocking...