Beating humans in a penny-matching game by leveraging cognitive hierarchy theory and Bayesian learning
Ran Tian Nan Li Ilya Kolmanovsky Anouck Girard

Improved histogram-based anomaly detector with the extended principal component features
    Sunil Aryal^1, Arbind Agrahari Baniya^1 and KC Santosh^2
    December 30, 2023
========================================================================================




It is a long-standing goal of artificial intelligence (AI) to be superior to human beings in decision making. Games are suitable for testing AI capabilities of making good decisions in non-numerical tasks. In this paper, we develop a new AI algorithm to play the penny-matching game considered in Shannon's “mind-reading machine” (1953) against human players. In particular, we exploit cognitive hierarchy theory and Bayesian learning techniques to continually evolve a model for predicting human player decisions, and let the AI player make decisions according to the model predictions to pursue the best chance of winning. Experimental results show that our AI algorithm beats 27 out of 30 volunteer human players.




§ INTRODUCTION


Developing artificial intelligence (AI) to beat humans in strategic games has been drawing attention/interest of researchers for decades <cit.>. Although AI algorithms targeted at specific games may not directly contribute to solving practical engineering problems other than those in the gambling industry, the theories developed alongside can be used to attack many problems of similar natures and of greater significance <cit.>. 

Many strategic games, for example, the games of chess, Go, and poker, require the players to do intensive calculations to identify winning strategies. AI algorithms for these games often rely on the super computing power of modern computers to beat human players <cit.>. In many other strategic games, computing power may have a less decisive effect on the game result. For instance, this holds for the cases where perfectly rational decision strategies are well-known, including the game of matching pennies (or “odds and evens”) <cit.> and the game of rock-paper-scissors <cit.>. 
For such games, recognizing the decision pattern of the opponent human player often plays a vital role in developing winning strategies for the AI player <cit.>.

In this paper, we focus on the game of matching pennies. We develop an AI to play the game repeatedly against a human player, during which the AI decision strategy is continually evolved to pursue the best chance of winning.

Such a problem has been considered by C. E. Shannon in his seminal paper <cit.>, where he named his AI a “mind-reading machine,” followed by  D. W. Hagelbarger in <cit.>, where the AI won 5,218 times out of 9,795 plays. The principle behind their AI algorithms is the hypothesis that human players are not able to generate i.i.d.[Independent and identically distributed.] random numbers but tend to follow certain patterns depending on the previous results to make their new decisions. Their AI algorithms pursue the identification of these patterns and assume that the human player will follow the same patterns the next time the same situation arises. Some later works, including <cit.> for the game of rock-paper-scissors, essentially follow the same principle to design their AI algorithms.

In this paper, we propose a new AI algorithm, which leverages cognitive hierarchy theory <cit.> and Bayesian learning. We hypothesize that human players follow certain “patterns” in making decisions, but differently from <cit.> and <cit.>, we explicitly characterize these “patterns” based on the human player's “level of reasoning,” introduced in cognitive hierarchy theory. Furthermore, we assume that humans follow these patterns probabilistically, and we use Bayesian learning techniques to identify the associated probabilities.

In summary, the contributions of this paper are:

1) We develop a new AI algorithm to play the penny-matching game, which beats 90% of volunteer human players in our experiments.

2) Our algorithm exploits the level-k framework <cit.> of cognitive hierarchy theory, which has not been considered in previously developed AI algorithms for penny-matching or rock-paper-scissors games <cit.>. 

3) Although cognitive hierarchy theory has been exploited for modeling human-agent behavior in some other application domains, such as automotive <cit.>, aerospace <cit.>, and cyber-physical security  <cit.> applications, probabilistic reasoning-level transitions in sequential decision-making scenarios, considered in this paper, have not been incorporated in these previous works. And the results of this paper suggest that such reasoning-level transitions exist in human decision making and can be modeled.

4) In the light of 3), we envision that the general approach to modeling human behavior proposed in this paper can find its utility in a broader range of application scenarios involving human-machine interactions, such as the scenarios in <cit.>.



§ MATHEMATICAL FORMULATION OF THE PENNY-MATCHING GAME


The penny-matching game under consideration, denoted by 𝒢, is a two-player zero-sum game with the normal-form representation given in Table <ref>. Formally, let u^i denote a decision of player i, i ∈𝒫 = {1,2}, taking values in the set 𝒰 = {0,1}. The payoffs of the two players, (r^1,r^2), as functions of (u^1,u^2) are defined as follows:


    r^1    = 1-2 mod(u^1 + u^2,2), 
    
    r^2    = -r^1.





We let a human player, as player 1, and an artificial intelligence (AI), as player 2, play the game 𝒢 repeatedly. For convenience, we use the subscript t ∈ℕ∪{0} to denote the round of the game. For instance, u^1_t denotes the human player's decision for game round t, and r^1_t denotes her obtained payoff in this round.

If r^i_t>0, then we say that player i wins the round t. It is easily seen from (<ref>) that there is always one and only one of the two players winning a round. Our goal is to design a strategy for the AI so that it has a higher winning rate than the human player, where the winning rate is defined as the number of wins divided by the total number of game rounds.

It is clear from (<ref>) that if the human player's decision u^1_t can be correctly predicted, the AI can win the round t by using the following decision strategy:

    u^2_t  = 1 - û^1_t,

where û^1_t denotes the predicted value of u^1_t.

Therefore, the goal to win can be achieved through developing a model of the human player that can predict u^1_t with high accuracy. 

It is well-known that the above repeated game has a unique Nash equilibrium, which involves independent repetition of the stage-game equilibrium strategy, i.e., for each player to play according to an i.i.d process where at each stage 0 or 1 is chosen with equal probability 0.5. We call this the Nash-equilibrium strategy for 𝒢. In particular, as long as one of the two players applies this Nash-equilibrium strategy, the game will end in a draw in expectation.



§ MODELING HUMAN PLAYER BASED ON COGNITIVE HIERARCHY THEORY




 §.§ Level-k models of the human player



Cognitive hierarchy theory (CHT) characterizes human decision-making processes based on assumptions of bounded rationality and iterated reasoning. In the level-k framework of CHT, a human decision-maker is assumed to make decisions based on a finite number of reasoning steps, called “level." In the setting of single-shot games, in particular, a level-k player assumes that the other player(s) are level-(k-1), predicts their decisions based on this assumption, and makes her own decision as the optimal response to the predicted decisions of the other players <cit.>. 

In order to formulate the level-k, k = 0,1,…, decision strategies of the two players in our game 𝒢, we start from defining the level-0 decision rules of the two players as follows:


    û^1,0_t     = u^2_t-1, 
    û^2,0_t     = 1 - u^1_t-1.


The above level-0 decision rules are based on the “naive” thought that the other player will make the same decision as in the previous round, which may represent a player's instinctive response to the game. 

On the basis of the level-0 decision rules (<ref>), the level-k decision rules of the two players, with k ≥ 1, are as follows:


    û^1,k_t     = û^2,k-1_t, 
    û^2,k_t     = 1 - û^1,k-1_t,


i.e., the level-k decision of player i optimally responds to the level-(k-1) decision of player (3-i) in terms of maximizing player i's own payoff.

For a given pair (u^1_t-1,u^2_t-1) ∈𝒰×𝒰, the level-k decisions of the two players for k = 0,1,2,…, are summarized in Table <ref>, where we use [κ] to denote the set of non-negative integers κ' that satisfy mod(κ',4)=κ.


We let σ_t ∈ℕ∪{0} denote the human player's level of reasoning for round t. In principle, if σ_t ∈ [κ] for some κ = 0,1,2 or 3, then u^1_t is determined as u^1_t = û^1,σ_t_t = û^1,[κ]_t, which can be read from Table <ref>. However, to account for the sub-optimality and variability in human decision making, we assume that if σ_t ∈ [κ], then the human player makes decisions according to


    ℙ(u^1_t = û^1,σ_t_t) = e^θ/e^θ+e^-θ, 
       ℙ(u^1_t = 1 - û^1,σ_t_t) = e^-θ/e^θ+e^-θ,


which is based on the “softmax” decision rule <cit.> with θ>0 being a tuning parameter. We remark that the “softmax” decision rule is a typical choice for modeling human decisions <cit.>.





 §.§ Transitions of human player's reasoning level



In a single-shot game, a player has only one chance to determine her reasoning level, relying on which to make her decision. In a repeated game, in contrast, a player can adjust her level in each round, for instance, according to whether she is winning or losing.

We assume that the human player in our repeated game 𝒢 will probabilistically adjust her reasoning level in each round according to the game result of the previous round, in particular, based on the following transition model,


    ℙ(σ_t ∈ [i]  | σ_t-1∈ [j], r^1_t-1 = 1) = p^+_(i+1),(j+1), 
       ℙ(σ_t ∈ [i]  | σ_t-1∈ [j], r^1_t-1 = -1) = p^-_(i+1),(j+1),


defined for all i,j ∈{0,1,2,3}, where ℙ(·|·) represents conditional probabilities.

However, due to the fact that different humans may have different transition models, the transition matrices p^+, p^- ∈{p ∈ [0,1]^4 × 4 | ∑_i =1^4 p_i,j = 1, j = 1,2,3,4} are not a priori known, but have to be estimated during the game. Note that there are 12 unknown parameters for each of p^+ and p^-, which poses a requirement of a large set of data for their estimation.



Therefore, we pursue a simplification of the transition model (<ref>) by leveraging the following two observations:

1) If the human player won the previous round, i.e., u^1_t-1 = u^2_t-1, then û^1,[0]_t = û^1,[3]_t and û^1,[1]_t = û^1,[2]_t.

2) If the human player lost the previous round, i.e., u^1_t-1 = 1 - u^2_t-1, then û^1,[0]_t = û^1,[1]_t and û^1,[2]_t = û^1,[3]_t.

In other words, to predict the human player's action for the next round, there is no need to distinguish her level between [0] and [3], and between [1] and [2] if she won the previous round. And similarly, there is no need to distinguish her level between [0] and [1], and between [2] and [3] if she lost the previous round. 

On the basis of the above observations, we consider a simplified transition model as follows: 


    ℙ(σ_t ∈Σ_1^+  | σ_t-1∈Σ_1^+, r^1_t-1 = 1) = q_1^+, 
       ℙ(σ_t ∈Σ_2^+  | σ_t-1∈Σ_2^+, r^1_t-1 = 1) = q_2^+, 
       ℙ(σ_t ∈Σ_1^-  | σ_t-1∈Σ_1^-, r^1_t-1 = -1) = q_1^-, 
       ℙ(σ_t ∈Σ_2^-  | σ_t-1∈Σ_2^-, r^1_t-1 = -1) = q_2^-,


where Σ_1^+ = {[0],[3]}, Σ_2^+ = {[1],[2]}, Σ_1^- = {[0],[1]}, and Σ_2^- = {[2],[3]}. Note that the probabilistic transitions from Σ_1^+ to Σ_2^+ and from Σ_2^+ to Σ_1^+ under r^1_t-1 = 1 as well as those from Σ_1^- to Σ_2^- and from Σ_2^- to Σ_1^- under r^1_t-1 = -1 can be computed based on the law of total probability. For instance, ℙ(σ_t ∈Σ_2^+  | σ_t-1∈Σ_1^+, r^1_t-1 = 1) = 1 - q_1^+. Furthermore, we assume that the probability of the event σ_t ∈Σ_i^± conditioned on σ_t-1∈Σ_j^± and r^1_t-1 = ± 1 is independent of all other events for every pair of i,j ∈{0,1}.

Suppose that σ_t-1, as well as q_1^+, q_2^+, q_1^- and q_2^-, is known. Then, depending on r^1_t-1 = 1 or -1, the probabilities of set membership σ_t ∈Σ_1^+ and σ_t ∈Σ_2^+, or the probabilities of σ_t ∈Σ_1^- and σ_t ∈Σ_2^- can be computed, based on which û^1,σ_t_t can be probabilistically predicted. Indeed, when the exact values of (σ_t-1,q_1^+,q_2^+,q_1^-,q_2^-) are not known, a distribution on {[0],[1],[2],[3]}× [0,1]^4 characterizing the probability of (σ_t-1,q_1^+,q_2^+,q_1^-,q_2^-) taking each value of {[0],[1],[2],[3]}× [0,1]^4 is sufficient for the above computation and prediction. Specifically, let π_t-1 denote such a probability distribution, then

    ℙ(σ_t ∈Σ_1^+)    = ∫_Σ_1^+ × [0,1]^4 q_1^+ dπ_t-1 + ∫_Σ_2^+ × [0,1]^4 (1-q_2^+) dπ_t-1,

if r^1_t-1 = 1, and 

    ℙ(σ_t ∈Σ_1^-)    = ∫_Σ_1^- × [0,1]^4 q_1^- dπ_t-1 + ∫_Σ_2^- × [0,1]^4 (1-q_2^-) dπ_t-1,

if r^1_t-1 = -1.

To facilitate numerical implementation, we assume that q_i^± takes values in a finite set Q ⊂ [0,1], where Q can be a grid on [0,1]. In this case, the probability distribution π_t-1 is discrete, and the formula becomes

    ℙ(σ_t ∈Σ_1^+) = ∑_q_1^+ ∈ Q q_1^+ (∑_σ∈Σ_1^+∑_q_2^+ ∈ Q∑_q_1^- ∈ Q∑_q_2^- ∈ Q
       π_t-1(σ,q_1^+,q_2^+,q_1^-,q_2^-)) + ∑_q_2^+ ∈ Q (1-q_2^+) ( 
       ∑_σ∈Σ_2^+∑_q_1^+ ∈ Q∑_q_1^- ∈ Q∑_q_2^- ∈ Qπ_t-1(σ,q_1^+,q_2^+,q_1^-,q_2^-)),

if r^1_t-1 = 1, and 

    ℙ(σ_t ∈Σ_1^-) = ∑_q_1^- ∈ Q q_1^- (∑_σ∈Σ_1^-∑_q_2^- ∈ Q∑_q_1^+ ∈ Q∑_q_2^+ ∈ Q
       π_t-1(σ,q_1^+,q_2^+,q_1^-,q_2^-)) + ∑_q_2^- ∈ Q (1-q_2^-) (
       ∑_σ∈Σ_2^-∑_q_1^- ∈ Q∑_q_1^+ ∈ Q∑_q_2^+ ∈ Qπ_t-1(σ,q_1^+,q_2^+,q_1^-,q_2^-)),

if r^1_t-1=-1.



 §.§ Bayesian learning of human player's model



On the basis of Sections <ref> and <ref>, the human player's behavior is modeled based on two parts: her reasoning level σ_t for each round t and the parameters (q_1^+,q_2^+,q_1^-,q_2^-) characterizing her reasoning level transitions. Unfortunately, these variables/parameters are neither a priori known nor directly observable. What can be observed are the human player's decision for each round, u_t^1, and the game result for each round, r_t^1. Note that given (u_t^1,r_t^1), the knowledge of u_t^2 and r_t^2 is redundant since they can be computed using (u_t^1,r_t^1) and (<ref>). 

We will use Bayesian learning techniques to learn x_t = (σ_t,q_1^+,q_2^+,q_1^-,q_2^-) from the observable data ξ_t = {u^1_0,…,u^1_t,r^1_0,…,r^1_t}. Specifically, we pursue a probability distribution on {[0],[1],[2],[3]}× Q^4, characterizing our belief  about the value of x_t, i.e., the π_t defined at the end of Section <ref>, conditioned on the available data ξ_t.

To achieve this, we rely on a hidden Markov chain formulation and its corresponding recursive Bayesian inference formula as follows:

If r^1_t = 1, then we have

    π_t(Σ_1^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) = 
       ℙ(u^1_t|σ_t ∈Σ_1^+) Π_t-1^+/∑_q̂∈ Q^4(ℙ(u^1_t|σ_t ∈Σ_1^+) Π̂_t-1,1^+ + ℙ(u^1_t|σ_t ∈Σ_2^+) Π̂_t-1,2^+)

where ∑_q̂∈ Q^4 = ∑_q̂_1^+ ∈ Q∑_q̂_2^+ ∈ Q∑_q̂_1^- ∈ Q∑_q̂_2^- ∈ Q, and


    Π_t-1^+ = q_1^+ π_t-1(Σ_1^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) 
              + (1-q_2^+) π_t-1(Σ_2^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}), 
       Π̂_t-1,1^+ = q̂_1^+ π_t-1(Σ_1^+ ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}) 
              + (1-q̂_2^+) π_t-1(Σ_2^+ ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}), 
       Π̂_t-1,2^+ = (1-q̂_1^+) π_t-1(Σ_1^+ ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}) 
                + q̂_2^+ π_t-1(Σ_2^+ ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}),


and based on (<ref>),

    ℙ(u^1_t|σ_t ∈Σ_1^+) = e^θ/e^θ+e^-θ   if   u^1_t = û^1,[0]_t (= û^1,[3]_t), 
    e^-θ/e^θ+e^-θ   if   u^1_t = û^1,[1]_t (= û^1,[2]_t), 
    
       ℙ(u^1_t|σ_t ∈Σ_2^+) = e^-θ/e^θ+e^-θ   if   u^1_t = û^1,[0]_t (= û^1,[3]_t), 
    e^θ/e^θ+e^-θ   if   u^1_t = û^1,[1]_t (= û^1,[2]_t).


Similarly, if r^1_t = -1, then we have

    π_t(Σ_1^- ×{q_1^+,q_2^+,q_1^-,q_2^-}) = 
       ℙ(u^1_t|σ_t ∈Σ_1^-) Π_t-1^-/∑_q̂∈ Q^4ℙ(u^1_t|σ_t ∈Σ_1^-) Π̂_t-1,1^- + ℙ(u^1_t|σ_t ∈Σ_2^-) Π̂_t-1,2^-

where 


    Π_t-1^- = q_1^- π_t-1(Σ_1^- ×{q_1^+,q_2^+,q_1^-,q_2^-}) 
              + (1-q_2^-) π_t-1(Σ_2^- ×{q_1^+,q_2^+,q_1^-,q_2^-}), 
       Π̂_t-1,1^- = q̂_1^- π_t-1(Σ_1^- ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}) 
              + (1-q̂_2^-) π_t-1(Σ_2^- ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}), 
       Π̂_t-1,2^- = (1-q̂_1^-) π_t-1(Σ_1^- ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}) 
                + q̂_2^- π_t-1(Σ_2^- ×{q̂_1^+,q̂_2^+,q̂_1^-,q̂_2^-}),


and based on (<ref>),

    ℙ(u^1_t|σ_t ∈Σ_1^-) = e^θ/e^θ+e^-θ   if   u^1_t = û^1,[0]_t (= û^1,[1]_t), 
    e^-θ/e^θ+e^-θ   if   u^1_t = û^1,[2]_t (= û^1,[3]_t),
    
       ℙ(u^1_t|σ_t ∈Σ_2^-) = e^-θ/e^θ+e^-θ   if   u^1_t = û^1,[0]_t (= û^1,[1]_t), 
    e^θ/e^θ+e^-θ   if   u^1_t = û^1,[2]_t (= û^1,[3]_t).


Note that in computing (<ref>) or (<ref>), we need to use π_t-1, the belief distribution of x_t-1 on {[0],[1],[2],[3]}× Q^4 conditioned on the available data ξ_t-1. However, (<ref>) or (<ref>) only provides us with partial information of π_t, that is, π_t(Σ_1^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) or π_t(Σ_1^- ×{q_1^+,q_2^+,q_1^-,q_2^-}). Note that π_t(Σ_2^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) = 1 - π_t(Σ_1^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) and π_t(Σ_2^- ×{q_1^+,q_2^+,q_1^-,q_2^-}) = 1- π_t(Σ_1^- ×{q_1^+,q_2^+,q_1^-,q_2^-}). 

To make the propagation (<ref>) or (<ref>) (which one is used depends on the game result r^1_t) recursively computable for all t, we need to reconstruct the distribution π_t from the partial information π_t(Σ_1^+ ×{q_1^+,q_2^+,q_1^-,q_2^-}) or π_t(Σ_1^- ×{q_1^+,q_2^+,q_1^-,q_2^-}). To do so, we rely on the following assumptions:

    π_t([i] ×{q_1^+,q_2^+,q_1^-,q_2^-}):π_t([j] ×{q_1^+,q_2^+,q_1^-,q_2^-}) = 
       π_t-1([i] ×{q_1^+,q_2^+,q_1^-,q_2^-}):π_t-1([j] ×{q_1^+,q_2^+,q_1^-,q_2^-})

holds for the pairs (i,j) = ([0],[3]) and (i,j) = ([1],[2]) if r^1_t = 1, and holds for the pairs (i,j) = ([0],[1]) and (i,j) = ([2],[3]) if r^1_t = -1, and for all {q_1^+,q_2^+,q_1^-,q_2^-}∈ Q^4, meaning that our relative degree of belief in any two indistinguishable[In terms of corresponding to identical û^1,σ_t_t.] levels follows its previous value.

On the basis of (<ref>), (<ref>), and (<ref>), π_t can be computed using π_t-1, u_t^1, and r_t^1 for all t.



§ DECISION STRATEGY FOR THE AI PLAYER


Using the algorithm (<ref>)-(<ref>), after each round t-1, we can obtain a belief distribution π_t-1 characterizing the human player's model. Then, we compute ℙ(σ_t ∈Σ_1^+) and ℙ(σ_t ∈Σ_2^+) = 1-ℙ(σ_t ∈Σ_1^+) using (<ref>) if r^1_t-1=1, or compute ℙ(σ_t ∈Σ_1^-) and ℙ(σ_t ∈Σ_2^-) = 1-ℙ(σ_t ∈Σ_1^-) using (<ref>) if r^1_t-1=-1.

Suppose that σ_t is known. Then, we let the AI mimic a human player's decision strategy, i.e., a “softmax” decision rule similar to (<ref>) as follows:


    ℙ(u^2_t = 1-û^1,σ_t_t|σ_t) = e^θ/e^θ+e^-θ, 
       ℙ(u^2_t = û^1,σ_t_t|σ_t) = e^-θ/e^θ+e^-θ,


with θ>0 being the same parameter as in (<ref>). We remark that although the AI does not need to mimic the sub-optimality in human decision making, the strategy (<ref>) creates some randomness in AI decisions, making it harder for the human player to identify the decision algorithm behind the AI, while guaranteeing that the probability of winning is higher than 0.5.

Since σ_t is not exactly known, we let the AI make decisions relying on the predicted distribution of σ_t as follows:

If r_t-1^1 = 1, then û^1,[0]_t = û^1,[3]_t = u^2_t-1, and we let

    ℙ(u^2_t = u^2_t-1) 
       = ∑_σ_t ∈{[0],[1],[2],[3]}ℙ(u^2_t = u^2_t-1|σ_t)ℙ(σ_t) 
       = ∑_σ_t ∈{[0],[3]}e^-θ/e^θ+e^-θℙ(σ_t) + ∑_σ_t ∈{[1],[2]}e^θ/e^θ+e^-θℙ(σ_t) 
       = e^-θ/e^θ+e^-θℙ(σ_t ∈Σ_1^+) + e^θ/e^θ+e^-θℙ(σ_t ∈Σ_2^+) 
       = e^θ/e^θ+e^-θ - e^θ - e^-θ/e^θ+e^-θ ℙ(σ_t ∈Σ_1^+).



Similarly, if r_t-1^1 = -1, then û^1,[0]_t = û^1,[1]_t = u^2_t-1, and we let 

    ℙ(u^2_t = u^2_t-1) = e^θ/e^θ+e^-θ - e^θ - e^-θ/e^θ+e^-θ ℙ(σ_t ∈Σ_1^-).



In turn, ℙ(u^2_t = 1 - u^2_t-1) = 1 - ℙ(u^2_t = u^2_t-1).



§ RESULTS




 §.§ Game GUI


We design a Graphic User Interface (GUI), shown in Fig. <ref>, to represent the game 𝒢. In each round, the human player makes a decision between left or right to dig and the AI player makes a decision between left or right to hide the treasure. The human player gains one virtual coin (r^1_t=1) if both players choose the same side, and loses one (r^1_t=-1) otherwise. The decisions of the two players for the current round are displayed once both decisions have been made and until the human player has made her decision for the next round. The accumulated payoff of the human player up to the current round t, i.e., ∑_k=1^t r^1_k, is shown in the top-middle.





 §.§ Results


We recruited human volunteers to play the game against the AI player. In particular, we let each human participant play the game twice, each time with 150 rounds. In one of the two game-runs, the AI uses our proposed strategy leveraging cognitive hierarchy theory and Bayesian learning, described in Sections <ref> and <ref>. In the algorithm (<ref>)-(<ref>), we use the parameters Q = {0.1,0.3,0.5,0.7,0.9} and θ = 1.5. In the other game-run, the AI uses a Nash-equilibrium strategy, i.e., randomly chooses between left or right with equal probability in each round. The order of these two strategies used in the two game-runs is randomly determined and the human participant knows neither the decision algorithms behind the AI, nor the fact that the AI uses different strategies in the two game-runs.

We have collected data of 30 human participants. We plot the evolution of accumulated payoff of the AI player as the game progresses, ∑_k=1^t r^2_k = - ∑_k=1^t r^1_k, in Fig. <ref>. The thick blue line represents the mean and the light blue shaded area represents the 95% confidence tube of the data for the game-run with our proposed strategy. The thick orange line represents the mean and the light orange shaded area represents the 95% confidence tube of the data for the game-runs with the Nash-equilibrium strategy. It can be observed that when the AI uses our proposed strategy, its accumulated payoff keeps increasing as the game progresses. In contrast, when the AI uses the Nash-equilibrium strategy, its accumulated payoff remains close to 0. This observation verifies the fact that as long as one of the two players applies such a Nash-equilibrium strategy, i.e., chooses between left or right with equal probability in each round, the game will end in a draw in expectation.



Fig. <ref> shows the histogram of accumulated payoffs after 150 rounds, ∑_t=1^150 r^1_t, of the 30 human participants corresponding to their game-runs where the AI uses our proposed strategy. It can be observed that the AI using our proposed strategy beats 90% of the human players.



Finally, we are interested in the results when player 1 can be perfectly modeled by our proposed human player's model incorporating level-k reasoning and probabilistic reasoning level transitions. Therefore, we create a “fake human” by letting her make decisions according to the “softmax level-k decision rules” defined by (<ref>) and Table <ref> in each round, with her reasoning level σ_t probabilistically transitioned according to the transition model defined by (<ref>) and (<ref>) between consecutive rounds, i.e., a model that perfectly satisfies all of our assumptions. In particular, we randomly generate the values for q_1^+, q_2^+, q_1^-, and q_2^- according to uniform distributions on [0,1].

We plot in Figs. <ref> and <ref> the same results as the ones of Figs. <ref> and <ref> but with the data of real human players replaced by the data generated by “fake human” players. We remark that the q_1^+, q_2^+, q_1^-, q_2^- values are regenerated for each new game-run, thus their values may be different for different 
game-runs, representing the fact that different humans may have different transition models. Furthermore, their true values are unknown by the AI, and the AI has to estimate their values during the game.





It can be observed that the results of AI against real human players in Figs. <ref> and <ref> are close to those of AI against “fake human” players in Figs. <ref> and <ref>, although the growth of accumulated payoff of the AI player against real human players is slightly slower than that against “fake human” players. Note that the latter corresponds to the ideal case where the “human” player's behavior perfectly matches the model prediction. Nevertheless, the similarity of the results implies, indirectly, that our proposed human player's model may have captured some crucial features in human decision making in the game. And in the light of this observation, it is reasonable to envision that the proposed approach to modeling human behavior in interactive and sequential decision-making scenarios can find its utility in a broader range of applications involving human-machine interactions.



§ SUMMARY


By leveraging cognitive hierarchy theory and Bayesian learning, our AI algorithm beat most human players in a repeated penny-matching game. Our approach to modeling human behavior in the game may be extended and used in other applications involving human-machine interactions.

IEEEtran




