Cognitive Game Theory Inductive Adversary Modeling Evolutionary Chess Alpha-Beta minimax search Jennifer Novosad, Justin Fox and Jeremie Pouly Our lecture topic is cognitive game. We are interested in this subject because games are a simple representation of reality on which we can test any concept developed in artificial intelligence. For this reason games have always been considered as an attractive framework for new developments. Our talk in divided in three parts: • Jeremie will first give a quick review of the minimax search and present a few improvements including alpha-beta cutoffs, transposition table and move ordering. He will also introduce the two demonstrations of the lecture. • Jennifer • Justin 1Motivation • Good benchmark • Computer can beat humans • Fun • $ – Similar to military or financial domains 2Reasoning Techniques for Games Games Search Statistical Inference Bayesian Nets Hidden Markov Models Minimax/ Evolutionary Algorithms … … Adversary modelAlpha-Beta 3Cognitive Game Theory • • • Alpha/Beta Search – Jeremie Adversary Modeling – Jennifer Evolutionary Algorithms – Justin We return to the outline to note that the next section of this talk will now focus on a still small, but more detailed and less abstract example of how evolutionary algorithms may be applied to create chess players. This example can be found in the paper: Kendall and Whitwell. An Evolutionary Approach for the Tuning of a Chess Evaluation Function using Population Dynamics, Proc. 2001 IEEE Congress on Evolutionary Computation. 4Cognitive Game Theory • Alpha/Beta Search • Adversary Modeling • Evolutionary Algorithms – Minimax search – Evaluation function – Alpha-Beta cutoffs – Other improvements – Demo We return to the outline to note that the next section of this talk will now focus on a still small, but more detailed and less abstract example of how evolutionary algorithms may be applied to create chess players. This example can be found in the paper: Kendall and Whitwell. An Evolutionary Approach for the Tuning of a Chess Evaluation Function using Population Dynamics, Proc. 2001 IEEE Congress on Evolutionary Computation. 5Adversarial search • Max & Min – Max wants to win – Min wants Max to loose Initial Board Situation New Board Situations 1 0 Win Loss Draw Loss MAX MIN MAX : : : Two-person games: Players = Final Board Situations - End Games -1 -1 6• Basic Assumption • • Minimax search Strategy: – MAX wants to maximise its payoff – MIN is trying to prevent this. MiniMax procedure maximises MAX’s moves and minimises MIN’s moves. 7An example 1 1 0 a b d c e f g MAX MIN Terminal States 1 1 Best value for MAX is 1 -1 -1 8• If terminal state then return payoff • then use MINIMAX on the children and return the maximum of the results. • Otherwise (MIN node), use MINIMAX on the children and return the minimum of the results. Function MINIMAX (called at each node): Minimax recursive procedure Else if MAX node 9Problems • m) b branching factor and m depth of the terminal states (Chess, b=35, m=100 � 35100»10154 nodes to visit) • Not possible to search the full game tree Cutoff the tree at a certain depth • But payoffs defined only at terminal states Time complexity: O(b10Cognitive Game Theory • Alpha/Beta Search • Adversary Modeling • Evolutionary Algorithms – Minimax search – Evaluation function – Alpha-Beta cutoffs – Other improvements – Demo We return to the outline to note that the next section of this talk will now focus on a still small, but more detailed and less abstract example of how evolutionary algorithms may be applied to create chess players. This example can be found in the paper: Kendall and Whitwell. An Evolutionary Approach for the Tuning of a Chess Evaluation Function using Population Dynamics, Proc. 2001 IEEE Congress on Evolutionary Computation. 11Heuristic evaluation function • Estimate the chance of winning from board configuration. • Important qualities: – Must agree with terminal states – Must be fast to compute – Should be accurate enough • Value of all black pieces Chess or checkers: Value of all white pieces – 12Heuristic evaluation function Val ???Val = (4*1) – (4*1+1*2) = -2 13Our evaluation function • Normal checker = 100000 • 4 parameters (long): – King value – Bonus central square for kings – Bonus move forward for checkers – Bonus for order of the moves (*depth/2) 14Our evaluation function • Normal checker = 100000 • 4 parameters (long): – King value – Bonus central square for kings – Bonus move forward for checkers – Bonus for order of the moves (*depth/2) No Bonus + 1*Bonus + 2*Bonus + 3*Bonus 15Cognitive Game Theory • Alpha/Beta Search • Adversary Modeling • Evolutionary Algorithms – Minimax search – Evaluation function – Alpha-Beta cutoffs – Other improvements – Demo We return to the outline to note that the next section of this talk will now focus on a still small, but more detailed and less abstract example of how evolutionary algorithms may be applied to create chess players. This example can be found in the paper: Kendall and Whitwell. An Evolutionary Approach for the Tuning of a Chess Evaluation Function using Population Dynamics, Proc. 2001 IEEE Congress on Evolutionary Computation. 16• Search deeper in the same amount of time • cannot possibly influence the final decision • (two searches in parallel: MAX and MIN) Alpha-Beta pruning Basic idea: prune away branches that Similar to the Branch-and-Bound search 17General case : m n MAX MIN MAX MIN for MAX then n will never get into play will always be chosen in preference. If m is better than n because m 18B1 1 0 3 12 8 4 4 6 4 root A3A2A1 B2 B3 B1 B2 B3 Best assignment: [A1,B1], value = 3 Review of Branch-and-Bound Var A Var B = 4 19• Search game tree keeping track of: – Alpha: Highest value seen so far on maximizing level – Beta: Lowest value seen so far on minimizing level • Pruning: : prune parent if node evaluation smaller than Alpha : prune parent if node evaluation greater than Beta Alpha-Beta procedure – MAX node– MIN node20• MIN: minimize board valuation � minimize • MAX: maximize board valuation � inverse • Prune parent instead of current node (stop expanding siblings) Branch-and-Bound analogy constraints in Branch-and-Bound of Branch-and-Bound (but same
View Full Document
Unlocking...