Game TreesTrees – A ReviewPowerPoint PresentationCommon Traversal AlgorithmComputer GamesSlide 6Slide 7Slide 8Slide 9Slide 10Minimax - ComputerMinimax - HumanDemonstrationConclusionsWhat can we do?Alpha-Beta PruningSlide 17Slide 18Slide 19Slide 20Transposition TablesSlide 22Slide 23Slide 24Slide 25Slide 26ReferencesGame TreesRyan WilsonChapter 6Trees – A ReviewTrees are a collection of nodesA Tree has a root node and zero or more sub-treesEBAGC D F H IRoot NodeAn Example TreeCommonTraversalAlgorithmFunction TraverseTree( node )visit( node )for each child of nodeTraverseTree( child )end forEnd FunctionTraverseTree( root )Computer GamesProblem: How do we make an intelligent opponent for a human player to compete against?One Possibility:Game TreesGame TreesTreat each state of the game as a node in a treeSearch the tree to find the best moveXX XX XXOO OO OXXGame Trees3 Components to Implementing a Game Tree:Tree GeneratorPosition EvaluatorMinimax MethodXXX XXOOO OX X…XXOOOXO O OXXOOXXOX01-11 = Computer Wins0 = Draw-1 = Human Wins…PositionEvaluator4060 203040 2040MAXComputer’s TurnMINHuman’s TurnREMEMBER!Higher Scoreis better forthe computer!Minimax - ComputerFunction FindComputerMove(GameStateNode) var bestValueif( terminal )return evaluate(GameStateNode)for each child of GameStateNodevalue = FindHumanMove(child)if( value > bestValue )bestValue = valueend forEnd functionMinimax - HumanFunction FindHumanMove(GameStateNode) var bestValueif( terminal )return evaluate(GameStateNode)for each child of GameStateNodevalue = FindHumanMove(child)if( value < bestValue )bestValue = valueend forEnd functionDemonstrationTic-Tac-Toe!ConclusionsIn Tic-Tac-Toe, there’s only about 27 legal moves for the computer to considerThat’s about 30,000 movesBut it’s still kind of slow…Almost 45 seconds to make the first move!Experts estimate 10100 legal moves in Chess!That’s approx. 2333 legal positions!What can we do?Apply the position evaluator to non-terminal nodesLimit the depth of your search through the treeHave to estimate the value of a positionAlpha-Beta Pruning“Trim” un-needed portions of the treeTransposition TablesAlpha-Beta Pruning Don’t need to look at all subtrees of a given node if you can already know which one is best4060 203040 <20>40MAXComputer’s TurnMINHuman’s TurnREMEMBER!Higher Scoreis better forthe computer!Alpha-Pruning100 40 120 30100 >120<100MAXComputer’s TurnMINHuman’s TurnREMEMBER!Higher Scoreis better forthe computer!Beta-PruningDemonstrationTic-Tac-Toe!With Alpha-Beta PruningConclusionsA definite improvement!First move only takes about 4 seconds (about 2000 moves)Transposition TablesIn many games, there are multiple ways to arrive at the same board position…X XOXO XX XOXO XTransposition TablesOnce we’ve calculated the value of a given position, we save it in a table so it’s easy to look up.For each position in the tree, look that position up in the table, if it exists, return the value stored in the table.DemonstrationTic-Tac-Toe!With Alpha-Beta PruningWith Transposition TablesConclusionsAnother improvement!First move only takes about 3 seconds (918 nodes)Almost ½ as many nodes!Game TreesHow-To of Game TreesAlpha-Beta PruningTransposition TablesReferencesDewdneyThe New Turing OmnibusWeissAlgorithms, Data Structures, and Problem Solving with C++WeissData Structures & Algorithm Analysis in
View Full Document
Unlocking...