3 ms·

>>1) There are currently no algorithms that can compute deterministic equilibrium strategies [0]. Therefore, mixed (randomized) strategies must be used for prof

>>1) There are currently no algorithms that can compute deterministic equilibrium strategies [0]. Therefore, mixed (randomized) strategies must be used for professional-level play or stronger. It's not that the algorithm is currently not known but it's the nature of the game that deterministic equilibrium strategies don't exist for anything but most trivial games. It's very easy to prove as well (think Rock-Paper-Scissors). >>2) In practice, strong play has been achieved with: i) online search and ii) a mechanism to ensure strategy consistency. Without ii) an adaptive opponent can learn to exploit inconsistency weaknesses in a repeated play. In practice strong play was achieved by computing approximate equilibria using various algorithms. I have no idea what you mean by "online search" or "mechanism to ensure strategy consistency". Those are not terms used by people who solve/approximate poker games. >>3) LLMs do not have a mechanism for sampling from given probability distributions. E.g. if you ask LLM to sample a random number from 1 to 10, it will likely give you 3 or 7, as those are overrepresented in the training data. This is not a big limitation imo. LLM can give an answer like "it's likely mixed between call and a fold" and then you can do the last step yourself. Adding some form of RNG to LLM is trivial as well and already often done (temperature etc.) >>Based on these points, it’s not technically feasible for current LLMs to play poker strongly Strong disagree on this one. >>This is in contrast with Chess, where there is lots more of training data, there exists a deterministic optimal strategy and you do not need to ensure strategy consistency. You can have as much training data for poker as you have for chess. Just use a very strong program that approximates the equilibrium and generate it. In fact it's even easier to generate the data. Generating chess games is very expensive computationally while generating poker hands from an already calculated semi-optimal solution is trivial and very fast. The reason both games are hard for LLMs is that they require precision and LLMs are very bad at precision. I am not sure which game is easier to teach an LLM to play well. I would guess poker. They will get better at chess quicker though as it's more prestigious target, there is way longer tradition of chess programming and people understand it way better (things like game representation, move representation etc.). Imo poker is easier because it's easier to avoid huge blunders. In chess a miniscule difference in state can turn a good move into a losing blunder. Poker is much more stable so general not-so-precise pattern recognition should do better. I am really puzzled by "strategy consistency" term. You are a PhD but you use a term that is not really used in either poker nor chess programming. There really isn't anything special about poker in comparison to chess. Both games come down to: "here is the current state of the game - tell me what the best move is". It's just in poker the best/optimal move can be "split it to 70% call and 30% fold" or similar. LLMs in theory should be able to learn those patterns pretty well once they are exposed to a lot of data. It's true that multiway poker doesn't have "optimal" solution. It has equilibrium one but that's not guaranteed to do well. I don't think your point is about that though.

Cool_Caribou 1y ago
Is limit poker a trivial game? I believe it's been solved for a long time already.
- bluecalm 1y ago
  >>Is limit poker a trivial game? I believe it's been solved for a long time already. It's definitely not trivial. Solving it (or rather approximating the solution close enough to 0) was a big achievement. It also doesn't have a deterministic solution. A lot of actions in the solution are mixed.
- eclark 1y ago
  No it's far from trivial for three reasons. First being the hidden information, you don't know your opponents hand holdings; that is to say everyone in the game has a different information set. The second is that there's a variable number of players in the game at any time. Heads up games are closer to solved. Mid ring games have had some decent attempts made. Full ring with 9 players is hard, and academic papers on it are sparse. The third is the potential number of actions. For no limit games there's a lot of potential actions, as you can bet in small decimal increments of a big blind. Betting 4.4 big blinds could be correct and profitable, while betting 4.9 big blinds could be losing, so there's a lot to explore.
hadeson 1y ago
I don't think it's easier, a bad poker bot will lose a lot over a large enough sample size. But maybe it's easier to incorporate exploitation into your strategy - exploits that rely more on human psychology than pure statistics?
michalsustr 1y ago
> It's not that the algorithm is currently not known but it's the nature of the game that deterministic equilibrium strategies don't exist for anything but most trivial games. Thanks for making this more precise. Generally for imperfect-information games, I agree it's unlikely to have deterministic equilibrium, and I tend to agree in the case of poker -- but I recall there was some paper that showed you can get something like 98% of equilibrium utility in poker subgames, which could make deterministic strategy practical. (Can't find the paper now.) > I have no idea what you mean by "online search" Continual resolving done in DeepStack [1] > or "mechanism to ensure strategy consistency" Gadget game introduced in [3], used in continual resolving. > "it's likely mixed between call and a fold" Being imprecise like this would arguably not result in a super-human play. > Adding some form of RNG to LLM is trivial as well and already often done (temperature etc.) But this is in token space. I'd be curious to see a demonstration of sampling of a distribution (i.e. some uniform) in the "token space", not via external tool calling. Can you make an LLM sample an integer from 1 to 10, or from any other interval, e.g. 223 to 566, without an external tool? > You can have as much training data for poker as you have for chess. Just use a very strong program that approximates the equilibrium and generate it. You don't need an LLM under such scheme -- you can do a k-NN or some other simple approximation. But any strategy/value approximation would encounter the very same problem DeepStack had to solve with gadget games about strategy inconsistency [5]. During play, you will enter a subgame which is not covered by your training data very quickly, as poker has ~10^160 states. > The reason both games are hard for LLMs is that they require precision and LLMs are very bad at precision. How you define "precision" ? > I am not sure which game is easier to teach an LLM to play well. I would guess poker. My guess is Chess, because there is more training data and you do not need to construct gadget games or do ReBeL-style randomizations [4] to ensure strategy consistency [5]. [3] https://arxiv.org/pdf/1303.4441 https://arxiv.org/pdf/1303.4441 [4] https://dl.acm.org/doi/pdf/10.5555/3495724.3497155 https://dl.acm.org/doi/pdf/10.5555/3495724.3497155 [5] https://arxiv.org/pdf/2006.08740 https://arxiv.org/pdf/2006.08740

Cool_Caribou 1y ago

Is limit poker a trivial game? I believe it's been solved for a long time already.

bluecalm 1y ago
>>Is limit poker a trivial game? I believe it's been solved for a long time already. It's definitely not trivial. Solving it (or rather approximating the solution close enough to 0) was a big achievement. It also doesn't have a deterministic solution. A lot of actions in the solution are mixed.
eclark 1y ago
No it's far from trivial for three reasons. First being the hidden information, you don't know your opponents hand holdings; that is to say everyone in the game has a different information set. The second is that there's a variable number of players in the game at any time. Heads up games are closer to solved. Mid ring games have had some decent attempts made. Full ring with 9 players is hard, and academic papers on it are sparse. The third is the potential number of actions. For no limit games there's a lot of potential actions, as you can bet in small decimal increments of a big blind. Betting 4.4 big blinds could be correct and profitable, while betting 4.9 big blinds could be losing, so there's a lot to explore.

hadeson 1y ago

I don't think it's easier, a bad poker bot will lose a lot over a large enough sample size. But maybe it's easier to incorporate exploitation into your strategy - exploits that rely more on human psychology than pure statistics?

michalsustr 1y ago

> It's not that the algorithm is currently not known but it's the nature of the game that deterministic equilibrium strategies don't exist for anything but most trivial games. Thanks for making this more precise. Generally for imperfect-information games, I agree it's unlikely to have deterministic equilibrium, and I tend to agree in the case of poker -- but I recall there was some paper that showed you can get something like 98% of equilibrium utility in poker subgames, which could make deterministic strategy practical. (Can't find the paper now.) > I have no idea what you mean by "online search" Continual resolving done in DeepStack [1] > or "mechanism to ensure strategy consistency" Gadget game introduced in [3], used in continual resolving. > "it's likely mixed between call and a fold" Being imprecise like this would arguably not result in a super-human play. > Adding some form of RNG to LLM is trivial as well and already often done (temperature etc.) But this is in token space. I'd be curious to see a demonstration of sampling of a distribution (i.e. some uniform) in the "token space", not via external tool calling. Can you make an LLM sample an integer from 1 to 10, or from any other interval, e.g. 223 to 566, without an external tool? > You can have as much training data for poker as you have for chess. Just use a very strong program that approximates the equilibrium and generate it. You don't need an LLM under such scheme -- you can do a k-NN or some other simple approximation. But any strategy/value approximation would encounter the very same problem DeepStack had to solve with gadget games about strategy inconsistency [5]. During play, you will enter a subgame which is not covered by your training data very quickly, as poker has ~10^160 states. > The reason both games are hard for LLMs is that they require precision and LLMs are very bad at precision. How you define "precision" ? > I am not sure which game is easier to teach an LLM to play well. I would guess poker. My guess is Chess, because there is more training data and you do not need to construct gadget games or do ReBeL-style randomizations [4] to ensure strategy consistency [5]. [3] https://arxiv.org/pdf/1303.4441 https://arxiv.org/pdf/1303.4441 [4] https://dl.acm.org/doi/pdf/10.5555/3495724.3497155 https://dl.acm.org/doi/pdf/10.5555/3495724.3497155 [5] https://arxiv.org/pdf/2006.08740 https://arxiv.org/pdf/2006.08740