3 ms·
There are no fundamental algorithmic differences between chess and poker. The incomplete information aspect of it only increases the size of the nodes in a gam
by andrewprock 10y ago
There are no fundamental algorithmic differences between chess and poker. The incomplete information aspect of it only increases the size of the nodes in a game tree, as each node must now track all possible private states for each public state. Beyond that, there are no fundamental algorithmic differences. There are algorithms that have been devised to handle such large game trees to speed convergence (regret minimization for example), but beyond that it's just a bigger game.
- xapata 10y agoThe fundamental difference is the way poker is played repeatedly, tracking winnings over a long period. Winning a single hand is meaningless. Chess can be modeled with each game serving as a single observation. Poker must consider each player's entire lifetime as a single observation. Not simply a hand, but all hands that player has ever played, including what that player knew about all opponents ever faced. This quantitative increase in data creates a qualitative difference. Poker is less like chess and more like repeated rock-paper-scissors.
- andrewprock 10y agoThis does not apply to solutions which are Nash equilibriums. You are discussing exploitative strategies, something which the CMU team did not attempt to create. They created a game theory optimal strategy.
- xapata 10y agoOptimal strategy might not be a Nash equilibrium. I'm not sure why you think game theory ignores that possibility. The Alberta team wrote some good papers about it.
- andrewprock 10y agoIn a two player no-limit hold'em game, a game theory optimal solution will be at a Nash equilibrium. see: https://en.wikipedia.org/wiki/Nash_equilibrium#Nash.27s_Existence_Theorem https://en.wikipedia.org/wiki/Nash_equilibrium#Nash.27s_Exis...
- xapata 10y agoYou misunderstood "a solution" to mean the only optimal solution. Also, note that Nash equilibrium assumes the opponent does not change strategy. Once you relax that assumption, especially with the idea that you can induce change, another strategy becomes viable. Check out the "Occurrence" section in the article you linked to.
- andrewprock 10y agoA Nash equilibrium strategy does not assume that an opponents strategy never changes. A Nash equilibrium has the property that if the opponents strategy deviates from a Nash equilibrium, then the opponent will lose.
- xapata 10y agoThat's neither my memory of the phrase from school nor my reading of the Wikipedia article. Nash equilibrium may not exist if one of the players follows, say, a Markov switching process. If that process causes the opponent to stop seeking equilibrium or to settle into a false equilibrium, then the switching process may have been a better strategy than seeking equilibrium.