Counterfactual Regret Minimization with Kuhn Poker
blog.varunajayasiri.com
blog.varunajayasiri.com
Anyhow, I came up with another question while considering this problem. Player 1 should only bluff at the optimal rate if player 2 punishes them for deviating from this rate by changing the frequency that they call when holding the king. Otherwise, Player 1 gains more on average by bluffing with the queen more frequently. So, how should Player 2 figure out if Player 1 is actually bluffing at the optimal rate (and not higher)? It could happen, with exponentially small probability, that Player 1 decides whether to bluff randomly, and bluffs with the first 10,000 queens before ever folding with a queen. How does Player 2 distinguish this from Player 1 only ever bluffing with the queen?
But perhaps this is something that the Nash Theorem deals with? I don't know. Any comments from people who know more than me on this are welcome!
You're describing exploitative strategies - that's the kind of circular thinking of "if he knows that I know what he knows...". In a Nash equilibrium neither side has an incentive to change their strategy even if they know what their opponent is doing. If you're betting at the optimal frequency, there is nothing that your opponent can do to counterexploit your strategy. If you're deviating from the optimal frequency, your opponent can adjust, you can adjust in return and so on.
"If first player has a K, because of 1. and 2., he would only lose if he bets. So first player should pass if he has a K."
It actually means that the first player always loses on average if he bets (expected utility -1/2 if not mistaken). If he folds however the expected utility is clearly zero since half of the time wins and half of the time loses.
I have not reached yet the description of the algorithm.
I actually find somewhat paradoxical that the first player should fold with a K and bluff with a Q! I remember that I loved little results like this when years ago I first followed the game theory course in Coursera. It was a little dry but I completed it nevertheless since I found it quite fascinating. I do wonder what possible applications are for my working field, machine learning, to apply these kind of algorithms. I would love to have an excuse to devote some time to it.
Bluffing is a strategy that wins against the middling hands you can convince to fold, and loses against the strongest hands which just call you anyways. The game is special in that when you have a middling hand, your opponent never has one, so they always either correctly call with the best hand or correctly fold with the worst.
"If he folds however" - this should be "if he checks". It doesn't make sense for him to fold when he isn't facing a bet. The original article uses "pass" to mean both fold and check depending on the context and that can get really confusing.