Playing Geister by Estimating Hidden Information
with Deep Reinforcement Learning
Keisuke Tomoda

Koji Hasebe

s2120620@s.tsukuba.ac.jp

hasebe@cs.tsukuba.ac.jp

Department of Computer Science
University of Tsukuba
1-1-1, Tennodai, Tsukuba 305-8573, Japan

Abstract—A number of attempts have been made to solve
imperfect information games using reinforcement learning. Since
it is not easy to apply reinforcement learning directly to imperfect
information games, methods, such as Neural Fictitious SelfPlay (NFSP), have been proposed. In this study, we investigate
an alternative method to solve imperfect information games
using reinforcement learning. The basic idea is to learn fromself-playing the perfect information games where the hidden
information in the original game is revealed. Based on the policy
obtained from this learning, the current state of the game isestimated from the opponent’s moves and the own best move.
We applied the proposed method to an imperfect information
game called Geister and evaluated its effectiveness throughexperiments. As a result, we obtained that the winning rate washigher than that of the direct learning of imperfect information
games using reinforcement learning.
Index Terms—Imperfect information game, Reinforcement
learning, Geister.

I. I NTRODUCTION
A number of computer programs (agents) have been proposed for playing various games. These studies range fromperfect information games, such as Go and chess, to imperfect
information games, such as poker [8] [3]. Some of them haveeven outperformed professional human players.
Reinforcement learning is often used in developing suchprograms. It is known that the method of reinforcement
learning is effective for solving perfect information games.
However, the optimal solution diverges for imperfect information games (cf. [6]). To address this problem, the study [6]proposed a method called Neural Fictitious Self-Play (NFPS)
and applied it to poker. This method integrated a well-known
learning model for Nash equilibrium with a technique oflearning from self-play. This method directly learns fromplaying imperfect information games. However, to solve imperfect information games, an alternative approach, not yet
thoroughly studied, is to use the results learned from theperfect information game obtained by revealing the hidden
information.
In this study, we propose a method for solving imperfect
information games by estimating hidden information using
reinforcement learning. The basic idea behind the proposed
method is to learn from self-playing the perfect information
games where the hidden information in the original game isrevealed. When playing a game, the policy (i.e., function that

determines the probability distribution over actions that yield
the highest value in a given state) obtained from this learning
is used to estimate the current state and the own best move byassuming that the current state is where the opponent’s move isrational. To evaluate the effectiveness of the proposed method,
we choose Geister as a target game, a chess-like imperfect
information game consisting of red and blue pieces whosecolors are undisclosed to the opponent.
We evaluated the proposed method through the following
experiments. First, to develop an agent (named PM) basedon the proposed method, we employed a deep reinforcement
learning framework called HandyRL [1] to learn the policy
for a fully informed Geister where the colors of all pieces
are exposed. We implemented an algorithm based on thisfunction for estimating the current board state (with hidden
piece colors) of the original Geister from the opponent’s move.
We also implemented an algorithm for determining the mosthighly evaluated move on the estimated board state. As acomparison, we obtained a policy by learning directly theoriginal Geister with imperfect information and developed anagent (named II) deciding the moves based on this function.
These two agents played against an agent (named RDM) that
randomly chooses moves and an agent (named MCTS) basedon the Monte Carlo tree search [5]. As a result, the agent PM
won 93% and 62% against RDM and MCTS, respectively.
Additionally, as a result of playing PM and II directly against
each other, the winning percentage of PM was 64%.
These results suggest that the proposed method is effective
for solving imperfect information games using reinforcement
learning. However, the advantage of the proposed method over
NFSP, the dependency on a specific learning framework, andits applicability to other games have not been investigated,which are subjects for future work.
The rest of this paper is organized as follows. Section 2
presents related work. Section 3 overviews the rules of Geister.
Section 4 describes the proposed method. Section 5 presents
the experimental results. Finally, Section 6 concludes the paper
and presents future work.
II. R ERATED W ORK
A number of attempts have been made at developing agentsto play games. In perfect information games, such as chess [4]and Go [10], agents have been developed that outperformed
human professional players.
One of the best known such studies on perfect information
games is that of Silver et al. [11]. They proposed a program
called AlphaZero based on the deep reinforcement learningthat makes it possible to learn from self-play in various perfect
information games. They demonstrated that the agents played
games sophisticatedly without any training data or gamespecific approaches.
The results of the study [11] suggest that reinforcement
learning is useful for solving games. However, in general,
applying reinforcement learning directly to imperfect information games can lead to the problem that the solution diverges
during the learning process. A study that addressed this issue
is the work of Heinrich et al. [6]. As mentioned in theprevious section, they proposed NFSP that enables learning
an approximate Nash equilibrium from self-play in imperfect
information games. Other studies include the work by Brown
et al. [3]. Their method is based on the counterfactual regret
minimization (CFR) [12], an algorithm for computing Nashequilibrium in an extensive-form game. Generally, CFR isdifficult to adapt directly to games with a large number ofstates. To address this issue, they introduced a state reduction
technique. The main difference between these studies and ours
is that our approach is to solve a game through learning fromperfect information games, while their methods directly learn
from imperfect information games.
Osawa [9] proposed an algorithm for estimating hidden
information from other players’ game actions in a card gamecalled Hanabi. The experimental results showed that estimating hidden information increases the game scores. Theirestimation algorithm assumes that other players act according
to a known strategy. However, our proposed method does
not limit the strategy of the opponent. It chooses a move by
estimating the opponent’s private information.
III. OVERVIEW OF G EISTER
A. Initial Setup
Geister is a two-player chess-like game where players taketurns moving their pieces on a 6×6 board, as shown in Figure
1. In the board, the left and right squares (indicated by an iconin Figure 1) at the far end of the board, as seen by each player,
are special squares called “exits.” Each player has initiallyeight pieces, four of which are blue and the other four are red.
The colors are visible only to the owner of the pieces. Before
starting the game, each player is free to place the eight pieces
she owns in the 2 × 4 area of the center of the front of theboard (marked gray in Figure 1 for the player on the bottom).
An example of the initial board setting from the viewpoint of
the player on the bottom is shown in Figure 2.
B. RulesIn the game, the first and second players take turns moving
one of their pieces. At each turn, the move is to an adjacentsquare in either the vertical or horizontal direction, unless it
is outside the board or in a square that is already occupied by

Fig. 1. Board of GeisterFig. 2. An example of the initial board
setting from the viewpoint of the playeron the bottom.

her own piece. If a piece is moved to a square that belongs toan opponent, the opponent’s piece is removed from the gameand may not be reused. Furthermore, each player can make aspecial move called “escape” on her next turn if she has herpieces in one of her exits.
C. GoalThe first player who achieves any of the following wins.
1) Escape one of her pieces.
2) Take all the opponent’s blue pieces.
3) The opponent takes all her red pieces.
IV. P ROPOSED M ETHOD
A. Outline
The agent playing Geister developed by the proposed
method consists of the following three components.
1) Policy for the fully informed Geister (i.e., the Geister
where the colors of all pieces are revealed).
2) Algorithm for estimating hidden information in thecurrent board.
3) Algorithm for deciding the next move.
The policy was obtained by applying deep reinforcement
learning to the fully informed Geister. Based on this function,an algorithm for estimating the current board state from the
opponent’s moves in a play in the original (i.e., including
hidden information) Geister is developed. The idea behind ourestimation method is to assume the rationality of the opponent.
It means that the higher the evaluation of the opponent’s
move in a board state, the higher the likelihood of thatstate. In the previously estimated board state, the most highly
evaluated move is chosen using the policy. The details of thesecomponents will be explained in the following subsections.
B. Learning Geister with Perfect Information
Our method learns a policy from fully informed Geister toestimate the value of a move in a board state. We employ
deep reinforcement learning to learn the policy of the Geisterwith perfect information. Here, the policy is a probability
distribution of the moves to be chosen for a given board
state. With sufficient learning, the resulting policy will be a
distribution so that the values of the moves that lead to winningare larger and vice versa. Thus, the policy can be regarded as
the value of the moves on a given board state. Since the total
value and variance of the policy may vary depending on thegiven board, which may affect the decision of moves, we use
the normalized distribution of the policy for each board.
C. Estimation of Hidden Information
We present the formal description of our estimation method
for hidden information as follows. Here, the symbol R denotes
the set of real numbers.
First, let Pi (for i = 1, 2) be the set of pieces owned by
player i, and let P = P1 ∪ P2 . Assume that each piece isassigned a unique ID. The set of coordinates of the board isdenoted by C = {(1, 1), . . . , (6, 6)}. Let posi : Pi → C andcoli : Pi → {blue, red} be the functions that determine thepositions and colors of each piece of player i on the board,
respectively. A state of the board in the game is represented
as quadruple ⟨pos1 , pos2 , col1 , col2 ⟩. Let S be the set of all
possible states of the board. The subjective state of the board
from the viewpoint of player i can also be represented as a
triple ⟨pos1 , pos2 , coli ⟩. This is because the color of playerj(̸= i)’s piece is unknown. We denote the set of subjective
boards for player i by Si . According to the game rules, theset of possible moves (actions) for a given state s ∈ S is
uniquely determined. Let us denote this set as As .
As mentioned earlier, the value of a move a ∈ As at a states ∈ S is determined by the normalized value of the policy
function. Let us denote this function by pol : A × S → [0, 1].
With the above setting, assume that in the n-th turn, thesubjective state for player i is si ∈ Si and the opponent makesa move a ∈ As . The function Ei : Si × As × Colj → Rdetermining the certainty that the colors of the opponent’s
pieces is colj is defined as follows.
E(si , a, col) := γ ·n−1∑

E(ski , ak , col) + pol(a, si ).

k=0

In the past moves up to the state si , the k-th state transitionis assumed to be ⟨ski , ak ⟩. Additionally, γ is a constant that
represents the weight for past estimates.
D. Decision of the Next Move
The method for player i to determine the move in state s is
as follows. First, find the value of each a ∈ As in each si ∈ Si
using the policy pol. Additionally, likelihood of each possible
state si ∈ Si from the viewpoint of player i (denoted by esi )is evaluated using the function E. In practice, the likelihood
is calculated for all possible combinations of colors of the
opponent’s pieces. Finally, based on these results, the action
is obtained by calculating the following value:argmax pol(a, si ) · esi .
a∈As

V. E XPERIMENTAL E VALUATION
A. Basic Settings
To evaluate the effectiveness of the proposed method forsolving imperfect information games, we conducted the following experiments. First, we implemented an agent named
PM based on the proposed method described in Section IV. For
comparison, we implemented an agent named II that directly

Fig. 3. Change in the winning rate in the plays against RDM

learns a policy for the imperfect information game using deep
reinforcement learning, and chooses a move with the highest
evaluation by the policy for the state of the board in eachturn. As a common opponent for comparing the performanceof PM and II, we also implemented an agent named RDM
that randomly selects a move at each turn and an agent named
MCTS that decides a move using Monte Carlo tree search.
We evaluated the performance of agents PM and II bycomparing their winning rates against RDM and MCTS,
respectively. Here, we evaluated the winning rate for each caseby measuring the average of 100 plays. To evaluate the impactof learning duration on the winning rate, we measured every
9 hours during the learning progress. Here, at the beginning(i.e., when the learning period is 0), the agent has not learned
anything and chooses a random action.
As a reinforcement learning framework, we used HandyRL,
an implementation of the distributed reinforcement learningalgorithm based on IMPALA [7]. For training, we used amachine equipped with a XeonE5-1620 CPU, 192 GB ofmemory, and two RTX2080Ti GPUs. In the implementation of
MCTS, the root node is evaluated 300 times where nodes are
selected according to UCB1 [2]. In this case, the color of thehidden opponent’s piece is randomly assumed from possiblecombinations and evaluates a node.
B. Results
Figure 3 shows the change in the results of PM and II
playing against RDM, as a function of the length of thelearning time. Similarly, Figure 4 shows the change in the
results of PM and II playing against MCTS. Furthermore,
Figure 5 shows the change in the winning rate of PM when
PM and II directly play against each other, as a function of
the length of the learning time.
As shown in Figure 3, both PM and II maintain a constanthigh winning rate regardless of the learning duration whenplaying against RDM. This result indicates that both PM and II
could maintain choosing “good” moves over random choices.
Even though PM’s board estimation assumes the rationality

Fig. 4. Change in the winning rate in the plays against MCTSof the opponent, it has a high winning rate against irrational
opponents, such as RDM. This may be because good moves
that lead to winning are common to some extent in all board
states.
As shown in Figure 4, in the play against MCTS, the winning percentage of II was highest after 36 hours of learning,
and then gradually decreased as the learning period increased.
On the other hand, it was confirmed that the winning rateof PM increased with the increase in the learning duration.
Furthermore, the final winning rate of PM against MCTS
was about 33% higher than that of II. This result indicatesthat PM’s board estimation worked effectively against MCTS
because MCTS rationally choose their moves. When learning
directly from an imperfect information game, such as II,
the problem of policy convergence is known, and a similar
phenomenon is observed.
As shown in Figure 5, when PM and II directly play against
each other, the winning rate of PM is eventually 64%. Thissuggests that PM’s board estimation is effective against II thatchooses the moves rationally, similar to the case of playing
against MCTS. In our experiment, PM performs better than IIwith sufficient learning time.
VI. C ONCLUSIONS AND F UTURE W ORKThis study presents a method for solving imperfect information games using deep reinforcement learning. The idea behind
our method is to learn the optimal policy by self-play in theperfect information game, where the hidden information in theoriginal game is revealed. Based on this policy, the proposed
method estimates a state with imperfect information so thatthe opponent’s move is most reasonable as the real state, andchooses the most effective move on the estimated state. We
implemented an agent playing Geister, a kind of imperfect
information game, and compared its performance with that ofan agent developed by applying direct reinforcement learning
to imperfect information games. The experimental results
showed that the proposed method performs better than theFig. 5. Change in PM’s winning rate when PM and II directly play against
each otheragent based on the Monte Carlo tree search that chooses arational pointing move.
The performance of the proposed method was verified for
one type of game and learning model. In future studies, we will
evaluate the effectiveness of the proposed method for various
games and learning models.
R EFERENCES[1] Website of HandyRL:https://github.com/DeNA/HandyRL.
[2] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite time analysis of themultiarmed bandit problem. Machine Learning. vol.47, pp.235-256,
2002.
[3] N. Brown and T.Sandholm. Superhuman AI for multiplayer poker.
Science, vol.365, pp.885-890, 2019.
[4] M. Campbell, A. J. Hoane and F. Hsu. Deep Blue. Artificial Intelligencevol.134, pp.57-83, 2002.
[5] R. Coulom, Efficient selectivity and backup operators in monte-carlo tree
search. In International conference on computers and games, pp.72-83,
2006.
[6] J. Heinrich and D. Silver. Deep Reinforcement Learning from Self-Playin Imperfect Information Games. arXiv:1603.01121, 2016.
[7] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y.
Doron, V. Firoiu, T. Harley, I. Dunning, S. Legg, and K. Kavukcuoglu.
IMPALA: Scalable distributed Deep-RL with importance weighted
actor-learner architectures. arXiv:1802.01561, 2018.
[8] M. Moravčı́k, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T.
Davis, K. Waugh, M. Johanson and M. Bowling. Deepstack: Expertlevel artificial intelligence in heads-up no-limit poker. Science, vol.356,
pp.508-513, 2017.
[9] H. Osawa. Solving hanabi: Estimating hands by opponent s actions
in cooperative game with incomplete information. Workshops at theTwenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
[10] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van
Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M.
Lanctot, et al. Mastering the game of Go with deep neural networks andtree search. Nature, vol.529, pp.484-489, 2016.
[11] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M.
Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan and
D. Hassabis. A general reinforcement learning algorithm that masters
chess, shogi, and Go through self-play. Science, vol.362, pp.1140-1144,
2018.
[12] M. Zinkevich, M. Johanson, M. Bowling and C. Piccione. Regret Minimization in Games with Incomplete Information, neural information
processing systems, pp.1729-1736, 2008.