Statistical Learning and Inference Methods for Reasoning in Games March 30, 2005 Brian Mihok Michael Terry Draper Laboratory CSAIL, MIT 1Outline • Intro to Games • • • Trees • • Summary Texas Hold ‘em Demo Hidden Markov Models – Structure Learning Bayesian Nets – Interpolating Conditional Density Project Preview – Level 1 Reasoning in Poker using HMMs and Bayesian Nets In this lecture, we present two key techniques for reasoning in games. To motivate our talk, we begin with a demonstration from the game of Texas Hold’Em. We use this demonstration to provoke some key questions in reasoning, and follow that up with lectures on two key techniques: Bayesian Nets and Hidden Markov Models. For these topics, we will begin with a review some of the fundamentals in each of these areas, then move into describing some more recent developments in research for the advanced portions of the talk. We then wrap up the information presented, and describe how we will use these methods in our final project. 2Why Games? • Economic Models • Combat Scenario Models • AI Benchmarks • Fun • $$$ I’d like to point out that lessons learned from modeling and learning games and game theory have been extended to a number of domains: For example, Adam Smith’s classic, “Wealth of Nations”, can be modeled as a zero sum game. Also, simulation of warfare typically involves adversary modeling. Finally, games have a set of clearly defined rules, providing good AI benchmarks with a good way of evaluating algorithms on specific problem domains. These are a few of the many domains where principles of games and game theory can be applied. 3• • Goal: make best 5 card poker hand out of 7 • Betting proceeds after every round • Round 1: Each player dealt 2 cards face down • Round 2: Flop – 3 cards face up for all players to use • Round 3 and 4: Turn, River – Turn and River adds a card each to community cards • Showdown Texas Hold ‘em Poker 2-10 players To demonstrate the techniques we will cover in this lecture in action, we will now have a demonstration of how Texas Hold ‘em. We will do this by having four volunteers from the crowd come and play a hand. Before we ask for volunteers, I’ll give you a basic overview of the game. Texas Hold ‘em is typically played with 2-10 players all sitting around a common table. The goal of the game is to make the best poker hand, consisting of 5 cards, from a total of 7 cards. The game starts by each player receiving two cards face down. These cards are only for the individual player to see. Then, each players bets upon the strength of these cards. Next, the flop comes. In the flop, 3 cards are dealt face up in the middle of the table. These are the start of 5 community cards that all the players can use. Based upon the strength of these cards and the two face down cards, the players bet again. This round of betting is followed by the “Turn,” which deals another card face up in the middle of the table. This is again followed by a round of betting. The final card is dealt face up in what is called the “River.” This is followed by a final round of betting. After the betting concludes, each player shows their hand in “the showdown.” The winner is determined by who has the best hand using their own two individual cards and the 5 community cards. Now that you know how the game is played, can we get 4 volunteers to play a round of Hold ‘em? (Demo a round of Hold ‘em. Talk through the game at each and every point to minimize pressure and stress. Try to make new players comfortable.) 4• Hand Strength • Hand Potential • Odds • Bluffing • Psychology • Keys to Hold’em Multi-Level Reasoning As we saw in the demo, there are a number of factors that go into deciding one’s actions in Hold’Em. At the most basic level, we are reasoning about our own hand and it’s potential. As we start to reason beyond these concepts, we realize that the odds, bluffing, and psychology are a few of the many factors tha t determine how us and our opponents act. I would like to break Hold’Em strategy down into what I call a multi-level reasoning problem: Level 0: Reasoning about your hand Level 1: Reasoning about your opponents hand Level 2: Reasoning about what your opponent thinks about his and your hand Level 3: What to do about what your opponent thinks … Professional players are often thinking on level 4 or 5, which would be incredibly difficult for a machine to accomplish without the lower level reasoning. 5Reasoning Techniques for Games Games Search Statistical Inference Bayesian Nets Hidden Markov Models Minimax/ Evolutionary Algorithms Kalmann Filters… …Alpha-Beta In this lecture we will focus on two techniques for reasoning about games to address the Level 1 reasoning problems just introduced. These techniques fall under the category of statistical inference. We chose these two techniques because they are very powerful for reasoning about situations with hidden information. In general, these techniques use statistics in the form of large mined datasets to learn the structures and parameters for graphical methods. We describe the representation for these methods, along with a number of recent advances in research used to more efficiently learn this representation. 6Outline for HMM Section • Background • Info extraction using HMM structures learned by stochastic optimization • Summary – HMM intro and formalization – HMM example related to Hold’em – Problems to solve and general solutions Here is an outline of the HMM section of the lecture. First, I will discuss some background about HMMs. I will start off with a graphical explanation of HMMs and then proceed into a more formal definition. I will follow up this formalization with an example of how a Hold ‘em hand can be represented with HMMs. Specifically, this will be used to show how the model changes as more information becomes available and the essence of the problem related to inferring your opponent’s hole cards given only his/her observations. Then, this example will be generalized to problems related to all HMMs and a mention of how to solve these problems will be mentioned. Then, I will go into the advanced portion of the lecture. This section deals with how a HMM structure can be learned through stochastic processes to best extract information from human readable
View Full Document
Unlocking...