in Japanese

 

The Nash Equilibrium Strategies in Kuhn Poker
Jan-2023 written by N.Tsuda
mail to: ntsuda@master.email.ne.jp

Abstract

This document discusses the Nash equilibrium strategy of the simplified two-person poker game known as "Kurn Poker".

As shown in reference [1] and Wikipedia [2], optimal strategies have been presented, but no explanation of the reasons why they are optimal strategies is provided. Additionally, it delves into small (perceived) errors and will touch on these points in more detail.

Kuhn Poker

Nash Equilibrium

A brief explanation of Nash Equilibrium.

Nash Equilibrium is defined as "a combination of strategies such that no player can improve their outcome by changing only their own strategy while the other player's strategies remain fixed" (quoted from wikipedia).

In a typical rock-paper-scissors game, choosing rock, paper, and scissors with equal probability of 1/3 is the Nash Equilibrium strategy. This is because, regardless of what the opponent chooses and the probability with which they choose it, the expected gain is ±0 and changing strategy will not result in a higher expected gain.

If the opponent always chooses rock, playing scissors 100% of the time will result in an expected gain of +1, which is higher than the expected gain from the Nash Equilibrium strategy. However, if the opponent then switches to paper, their expected gain becomes +1, and the player who used to play scissors will no longer have a higher expected gain. As the opponent can improve their outcome by changing their strategy, this is not the Nash Equilibrium strategy.
In other words, the Nash Equilibrium strategy is not the one that results in the highest expected gain, but rather one that eliminates the opponent's options for strategy selection.

Game Tree

The following is a representation of the complete game tree for Kuhn Poker.

    PlayerⅠ    PlayerⅡ   PlayerⅠ      ※ Gain seen from PI
    ---------   ---------  --------      ---------------
    ○┬Check ─□┬Check─◆            ±1
      │          └Raise─○┬Fold─◆  -1
      │                     └Call─◆  ±2
      └Raise ─□┬Fold─◆             +1
                  └Call─◆             ±2

The states are represented by nodes denoted by ○, □, and ◆, each indicating the turn of player 1, player 2, and the terminal state (the state where the outcome has been determined).

Parent-child nodes are connected by lines (branches) and actions are described between them. In case multiple actions are possible, branches split into multiple child nodes. Nodes with the same parent are called sibling nodes.

It is assumed that folding in a state where Raise has not been performed has no meaning, so it is not performed.

Hand

The first and second player's hands consist of only six combinations of cards: "JQ, JK, QJ, QK, KJ, KQ."

The player can only see their own hand and do not know the opponent's hand, so the actual state is represented as "K?" (in this case, KJ or KQ) for the first player, and as "?Q" for the second player.

Representation of State and Utility

The state is represented by the combination of hand and action history, as follows:

    Q?:○─Check─□─Raise─○

State representation and gain

A state is represented by the player's hand and the action history, as follows:

The above represents a state in which player 1's hand is Q, both the first and second players have performed a Check, and it is now player 1's turn.

When the showdown or either player folds and the game is decided, the gain is described to the right of the end node, leaving a blank space (always viewed from player 1). If the victory or defeat is determined by the hand, a ± sign is described.

    Q?:○─Check─□─Raise─○┬─Fold─◆  -1
                                └─Call─◆  ±2

Action Probabilities

In cases where multiple actions are available, the probability of their selection is denoted before the action name. Probabilities can be expressed as a fraction or as a percentage. Additionally, Greek letters such as α, β, γ, etc. can be used to represent arbitrary probabilities (with certain constraints such as being in the range [0, 1]).

    Q?:○─Check─□─Raise─○┬ 2/3 Fold─◆  -1
                                └ 1/3 Call─◆  ±2
    J?:○┬─  α Raise─□
          └─1-α Call ─□

Heuristic Optimal Action

Below is an illustration of the best action that is not based on Nash Equilibrium, but rather a heuristic approach.

    ?J:○─Raise─□─100% Fold─◆
    J?:○─Check─□─Raise─100% Fold─◆

If the hand is J, losing by -2 by calling Raise is inevitable, so it is best to 100% Fold and keep the loss at -1.

    ?K:○─Raise─□─100% Call─◆
    K?:○─Check─□─ Raise─100% Call─◆

In the case where the player has a hand of K, calling will result in a guaranteed win of +2 (one of the ideal scenarios is to let the opponent Raise and then Call). Therefore, in the case of a Raise, 100% Call is made.

    ?Q:○─Check─□─100% Check─◆

When a hand of Q is raised, if the opponent has K, the expected gain will be -2 as seen from the Q side due to the call, and if the opponent has J, the expected gain will be +1 due to the fold, yielding an expected value of -0.5. When the hand of Q checks, if the opponent has K, the expected gain will be -1, and if the opponent has J, the expected gain will be +1, yielding an expected value of ±0.

    Q?:○─100% Check─□

If a raise is made with Q, and the opponent has K, the opponent will call, resulting in a loss of -2. If the opponent has J, it will fold, resulting in a gain of +1. The expected value is -0.5 (same as the case of ?Q).
In the case of a check, there is a possibility that the opponent may raise, so it is slightly more complex, but the expected value is approximately ±0 (the specific value will be discussed later).

    ?K:○─Check─□─100% Raise─○

In the case where Player 1 checks and Player 2 has a hand of K, it is guaranteed to win by checking, but it will only result in a +1 gain. However, if Player 2 raises, the expected gain will increase as Player 1 might call.

Nash Equilibrium Strategy

In this chapter, we will discuss Nash Equilibrium strategy in cases where the best move cannot be determined heuristically.
When the hand is Q, it is best to Check instead of Raise, so it is necessary to consider what probability to Raise with J and K.
Conversely, in the case of Raise, it is best to Fold or Call when the hand is J or K, so it is necessary to consider only the probability of Call or Fold when the hand is Q.

Player 1 Raises, Player 2's Hand is Q

The following is the Nash Equilibrium strategy for Player 2 if Player 1's hand is J.

    JQ:○─Check─□─Check─◆         -1
    JK:○─Check─□─Raise─○─Fold─◆   -1
                             ※ Expected value:-1
    JQ:○─Raise─□┬2/3 Fold─◆  +1
                     └1/3 Call─◆  -2
    JK:○─Raise─□─Call─◆          -2
                             ※ Expected value:-1

This is to ensure that the expected value of gain is the same regardless of whether player 1 checks or raises.
If player 1 checks, the opponent has Q or J, so if the opponent checks and shows down, player 1 will always lose (gain: -1). Even if the opponent raises, player 1 still loses -1 by not folding.
If player 1 raises, if the opponent's hand is K, the opponent will always call and the gain will be -2.
Therefore, if the expected value of gain in the case of the opponent having a Q becomes ±0, the expected value of gain in the case of player 1 checking becomes -1. In other words, player 1 will have a Nash equilibrium strategy in which the gain does not change regardless of the probability of raise.

To make the expected value of gain in the case of Q ±0, it is good to make the call probability of Q 1/3 and the fold probability 2/3. The gain from the perspective of player 1 becomes -2 * 1/3 + 1 * 2/3 = 0.

Next, consider the case where player 1's hand is K.

    KJ:○─Check─□┬2/3 Check─◆        +1
                     └1/3 Raise─Call─◆  +2
    KQ:○─Check─□─Check─◆                +1               
                               ※ Expected value:(4/3 + 1)/2 = 7/6
    KJ:○─Raise─□─Fold─◆            +1
    KQ:○─Raise─□┬2/3 Fold─◆    +1
                     └1/3 Call─◆    +2
                               ※ Expected value:(4/3 + 1)/2 = 7/6

In the case where the hand of Player 1 is a King, even if the hand of Player 2 is a Queen, the Nash equilibrium strategy is to fold with a 2/3 probability and call with a 1/3 probability (the reason for the 1/3 probability of the rear-hand Jack raising will be explained later).

Therefore, regardless of whether the hand of Player 1 is a Jack or a King, if Player 1 raises and the hand of Player 2 is a Queen, the Nash equilibrium strategy is to fold with a 2/3 probability and call with a 1/3 probability.

When Player 1's Hand is Q and Player 2 Raises

When Player 1's hand is Q, the initial best move is to Check. And if Player 2 raises, it is in the same situation as the previous section, so for a hand of Q, the Nash equilibrium strategy is to Fold with a 2/3 probability and Call with a 1/3 probability.

    QJ:○─Check─□─Raise─○┬2/3 Fold─◆  -1
                                └1/3 Call─◆  +2
    QK:○─Check─□─Raise─○┬2/3 Fold─◆  -1
                                └1/3 Call─◆  -2

When Player 1's Hand is J or K

While Player 2's hand may not necessarily be Q, there exists a heuristic best action in cases where it is not Q, so only the case where it is Q will be considered here.

If Player 2 folds, Player 1's gain is +1, so Player 1's action will be determined in such a way that the same gain is achieved even if Player 2 calls.

    JQ:○─α Raise─□┬Fold─◆  +1
                        └Call─◆  -2
    KQ:○─γ Raise─□┬Fold─◆  +1
                        └Call─◆  +2

In the case where player Ⅱ folds, player Ⅰ's gain is +1. The expected value of player Ⅰ's gain when player Ⅱ calls is -2α + 2γ. Therefore, in order to make this expected value the same as when player Ⅱ folds, we have:
-2α/(α+γ) + 2γ/(α+γ)= 1
-2α + 2γ = α + γ
γ = 3α
So, when player Ⅰ has a hand of J or K, they raise with the following probability (assuming 0≦α≦1/3).

    J?;○─α Raise
    K?:○─3α Raise

When Player 1 Checks with a Q and Player 2 Has a J or K

If Player 2 has a K, they will Raise with a 100% probability. If we set the Raise probability for J to 1/3, the ratio of K to J will be 3:1, making it a Nash Equilibrium strategy, similar to the previous section.

Expected Gain

The expected gain for player 1, when both players adopt the Nash equilibrium strategy, is as follows.

    JQ:○┬1-α Check─□─Check─◆    -1 * (1-α) = -(1-α)
          └  α Raise─□┬1/3 Call─◆ -2 * α * 1/3 = -2/3α
                          └2/3 Fold─◆ +1 * α * 2/3 = 2/3α
    JK:○┬1-α Check─□─Raise─○─Fold─◆ -1 * (1-α) = -(1-α)
          └  α Raise─□─Call ─◆     -2 * α = -2α

Expected gain for player 1 when player 1 has a hand of J:
(-(1-α) -2/3α + 2/3α -(1-α) -2α) / 2
= -1

    QJ:○─Check─□┬2/3 Check─◆                +1 * 2/3 = 2/3
                     └1/3 Raise─○┬2/3 Fold─◆  -1 * 1/3 * 2/3 = -2/9
                                    └1/3 Call─◆  +2 * 1/3 * 1/3 = +2/9
    QK:○─Check─□─Raise─○┬2/3 Fold─◆  -1 * 2/3 = -2/3
                                └1/3 Call─◆  -2 * 1/3 = -2/3

Expected gain for player 1 when player 1 has a hand of Q:
(2/3 - 2/9 + 2/9 - 2/3 - 2/3) / 2
= -1/3

    KJ:○┬1-γ Check─□┬2/3 Check─◆  +1 * (1-γ) * 2/3 = 2/3*(1-γ)
          │              └1/3 Raise─○─Call─◆ +2 * (1-γ) * 1/3 = 2/3*(1-γ)
          └  γ Raise─□─Fold─◆       +1 * γ = γ
    KQ:○┬1-γ Check─□─Check─◆      +1 * (1-γ) = (1-γ)
          └  γ Raise─□┬1/3 Call─◆   +2 * γ * 1/3 = 2/3*γ
                          └2/3 Fold─◆   +1 * γ * 2/3 = 2/3*γ

Expected gain for player 1 when player 1 has a hand of K:
(2/3 - 2/3*γ + 2/3 - 2/3*γ + γ + (1-γ) + 2/3*γ + 2/3*γ) / 2
(2/3 + 2/3 + 1 - 2/3*γ - 2/3*γ + γ - γ + 2/3*γ + 2/3*γ) / 2
=7/6

Therefore, the expected gain of player 1 is (-1 + -1/3 + 7/6) / 3 = -1/18 (as it is a two-player zero-sum game, the expected gain of player 2 is +1/18).

Differences between the paper and Wikipedia version

The paper and Wikipedia have a description of the optimal strategy, but do not explain why it is the optimal strategy.

The difference between them and this article is in the section where Player 1 has a hand of Q and after the initial Check, Player 2 raises. In the paper and Wikipedia, it is written that "Call with a probability of 1/3 + α". In this article, we simply consider "Call with a probability of 1/3".

    QJ:○─Check─□┬2/3 Check─◆                   +1 * 2/3 = 2/3
                     └1/3 Raise─○┬2/3-α Fold─◆  -1 * 1/3 * (2/3-α) = -2/9 + 1/3α
                                    └1/3+α Call─◆  +2 * 1/3 * (1/3+α) = +2/9 + 2/3α
    QK:○─Check─□─Raise─○┬2/3-α Fold─◆  -1 * (2/3-α) = -2/3 + α
                                └1/3+α Call─◆  -2 * (1/3+α) = -2/3 - 2α

The above figure shows the game tree for when Player 1 has a hand of Q and calls with a probability of 1/3+α. The expected gain is calculated as follows:
(2/3 - 2/9 + 2/9 - 2/3 - 2/3 + 1/3α + 2/3α + α - 2α) / 2 = -1/3
The expected gain remains constant regardless of α, as Player 2 adopts a Nash equilibrium strategy.
If Player 2's raise probability for a hand of J is set to 0, the expected gain is as follows:

    QJ:○─Check─□─Check─◆                   +1
    QK:○─Check─□─Raise─○┬2/3-α Fold─◆  -1 * (2/3-α) = -2/3 + α
                                └1/3+α Call─◆  -2 * (1/3+α) = -2/3 - 2α

-1/6 - 1/2α, which results in a decrease (increase) in player 1's (player 2's) expected gain, contradicting the definition of Nash equilibrium, where players cannot gain a higher return by changing their strategy.

Therefore, it is considered that "Call with a probability of 1/3 + α" is incorrect, and it is correctly "Call with a probability of 1/3".

Conclusion

This paper has presented a concrete explanation of the derivation of the Nash Equilibrium strategy in Kuhn Poker. The derived strategy is almost the same as the one previously shown, but only the last move is different. The previous strategy showed that player II can gain a better gain by changing their strategy, which indicates that it is not a Nash Equilibrium strategy.

Acknowledgments

The author would like to express gratitude to I-san, Y-san, and Kentaro Kobayashi-san for their careful listening and support during the writing of this paper. The author believes that it was thanks to their support that he was able to clarify his thoughts.
Furthermore, I would like to express my gratitude to the Motooka Open Salon for making a connection with Kobayashi-san.

References

[1] Kuhn, H. W. (1950). "Simplified Two-Person Poker". In Kuhn, H. W.; Tucker, A. W. (eds.). Contributions to the Theory of Games. Vol. 1. Princeton University Press. pp. 97–103.

[2] "Kuhn Poker", wikipedia( https://en.wikipedia.org/wiki/Kuhn_poker