4 ms·
My favourite example of this is how no limit Texas holdem was solved. This game is of course an imperfect information game (you don’t know your opponents hole
by hmate9 5y ago
My favourite example of this is how no limit Texas holdem was solved.
This game is of course an imperfect information game (you don’t know your opponents hole cards). We have lots of great algos for perfect information games but not imperfect.
So what the researches did is they mapped hold em to a perfect information game by tweaking it: now nobody knows their hole cards and all players must publicly announce their strategy to a “referee”. Then the referee looks at the players cards and places bets on behalf of the players. A player’s strategy looks something like: if I have a pair of aces then I want to raise 94% of the time and call 6% of the time and fold 0% of the time etc etc.
You know your opponent’s strategy too (as they have announced it like you did to the referee) so you can now iterate and optimise your strategies which will approach a Nash equilibrium.
- monkeyjoe 5y agoGot a reference for this? My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information. The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iteration.
- hmate9 5y agoEverything you said about Nash equilibrium is true, I didn't mean to imply that it can only be found in perfect information games via iteration. What I wanted to say is that methods for finding it via iteration and self-play exist and are well defined but only for perfect information games. The research itself is here: https://ai.facebook.com/blog/rebel-a-general-game-playing-ai-bot-that-excels-at-poker-and-more/ https://ai.facebook.com/blog/rebel-a-general-game-playing-ai...
- monkeyjoe 5y agoHey just wanted to say thanks for sharing this.
- telxosser 5y agoI believe you could say the minimax strategy to the 2 player game of heads up no limit is solved but beyond that is stretching it. I am way out of it though. I suspect anything more than 2 players is unsolvable when you factor in the stochastic nature of the drunk guy at the table with more than 2 players. Then based on his play he subtracts or adds EV to us randomly. I won't even let myself think past this though with poker because IMO it is a waste of time.