SUGISAKAMASANORI

Journal of Robotics, Networking and Artificial Life
Vol. 10(3); December (2023), pp. 231–234
ISSN (Online): 2352-6386; ISSN (Print): 2405-9021
https://alife-robotics.org/jrnal.html

Research Article

An analysis of Quoridor by reusing results from the reduced
version
Satoshi Ikeda1, Takuro Iwanaga2,Makoto Sakamoto1, Takao Ito3

Faculty of Engineering, University of Miyazaki, Miyazaki-City, Miyazaki, Japan
Graduate School of Engineering, Miyazaki University, Miyazaki-City, Miyazaki, Japan
Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima, Japan123ARTICLE INFO
Article History
Received 06 December 2022
Accepted 06 March 2024
Keywords
Perfect play
Retrograde analysis
Quoridor
Combinatorial theory

ABSTRACT

Retrograde analysis is a representative game analysis method that initially lists all legal positions
and searches for the best move by analyzing from the final positions to the initial position. Thismethod is effective for analyzing the games where the same position appears multiple times
during sequential analysis from the initial position. However, it also has the drawback of requiring
a huge amount of memory to enumerate the legal solutions. In this paper, we focus on the board
game "Quoridor" released by Gigamic.
© 2022 The Author. Published by Sugisaka Masanori at ALife Robotics Corporation Ltd.
This is an open access article distributed under the CC BY-NC 4.0 license(http://creativecommons.org/licenses/by-nc/4.0/).

1. Introduction
A game tree is a graph structure that represents a game asa directed graph with game positions as nodes andplayers' moves as edges [1]. The standard method forgame analysis is to expand this game tree. Fig. 1
illustrates a game tree for tic-tac-toe, displaying all
moves up to the second move. A complete game tree
enables the identification of the best move. However,there are some problems with this method. One of theproblems is the possibility of repeating the same
positions. In Tic-Tac-Toe, the number of squares
available for placement decreases with each move to anarbitrary position, and positions that have appeared
before the current position will never appear again.

Fig. 1 The game tree of Tic-tac-toe

However, in chess and shogi, once a move is made, it canbe reverted to the previous position, allowing the sameposition to appear multiple times at different nodes of thegame tree.
Retrograde analysis was developed to address thecomplexities of game analysis. This method involves
examining all regal positions and tracking win/loss
outcomes from the final position back to the initial one.
Once the win-loss outcomes stabilize, the initial positionis categorized as a must-win game, a must-lose game, ora tie for the first player. Retrograde analysis effectively
prevents loops in the game tree that may occur during

Corresponding author E-mail: bisu@cs.miyazaki-u.ac.jp, hm17008@student.miyazaki-u.ac.jp

231

2.3. Pawn moves

gameplay. However, it necessitates examining andanalyzing all legal positions, leading to memory-related
issues. Consequently, efforts are made to minimize thenumber of examined positions as much as possible.
This study aims to reduce the number of positions inretrograde analysis by reusing the results from a reducedversion.

As shown in Fig. 3, the pawns are moved one square ata time, either horizontally or vertically, forwards orbackwards, but never diagonally. The pawns mustnavigate around the fences. If, while you move, you
encounter your opponent's pawn, you can jump over it.

Fig. 2 Before and after reusing.

Fig. 3 How to move pawn

The white squares indicate where the white pawn canmove, while the black squares indicate where the blackpawn can move.

In this study, the phase set is organized according toFig. 2. When the phases follow the sequence Sk(k=0,1,...)
such that S0⊂S1⊂S2..., with phase transitions occurring
only between adjacent phases in Sk, the results analyzed
in Sk(k=0,1,...,n-1) can be reused. This decreases thenumber of phases needed to be enumerated in Sn. It's
important to note that Sk-1 represents a simplified versionof Sk, where the number of items is reduced by one step.
Here, the reduced version of the original game refers to ascenario where the number of items or board size has
been reduced.

2.4. Positioning of the fences
The fences must be placed between two sets of twosquares. By strategically placing fences, you can compel
your opponent to navigate around them, thereby
increasing the number of moves they must make.
However, it is not permissible to block your opponent'spawn completely; it must always have a clear path to its
goal, with at least one square available for movement.
2.5. Jumping over opponent's pawn

2. Quoridor

As shown in Fig. 4, if two pawns are adjacent and there's
no fence between them, the current player can jump over
the opponent's pawn, moving ahead an extra square.
However, if there's a fence behind the opponent's pawn,
the player can move their pawn to the left or right of theopponent's pawn instead.

In this paper, we discuss the miniature version of theboard game Quoridor [2]. This section outlines the rules
for a 5x5 board designed for two players, each with onefence.
2.1. Object of the GameThe objective of the game is the same as the standard
version [3] : to be the first to reach the line opposite one'sbaseline.
2.2. Game Play (2 players)
Each player takes turns choosing to move their pawn orto place a fence. A player who has run out of fences mustmove their pawn. At the start of the game, the board isempty. Place your pawn in the center of the first row on
your side of the board. Your opponent takes anotherpawn and places it in the center of the first row on theirside of the board. Then, each player takes one fence.

Fig. 4 Encounters Between Pawns and Fences2322.6. End of the game

This method allows for the analysis of newly added
game states and the propagation of information to the
reduced version, making it sufficient to enumerate only
S'n when analyzing Sn.

The winner is the first player to reach one of the fivesquares opposite their baseline.
3. Retrograde Analysis

5. Results

In this study, we conducted an experiment using
retrograde analysis [4], [5]. This method involves
retracing steps from the final stage, where victory or
defeat is determined, back to the initial board, one step ata time. During this process, if the preceding move leads
to a victory, that information is recorded; likewise, if all
moves lead to defeat, that information is recorded, andthe process repeats until the outcome of the initial phaseis determined. The update of win/loss information isdepicted in Fig. 5. Blue represents an undecided game,white represents a game won by the white player, andblack represents a game won by the black player.

Initially, in the case where both players have one fence
each on a 5x5 board (S2), we enumerated 498,764
positions including S0 and conducted retrograde analysis
directly. As a result, it was confirmed that being thesecond player ensures victory [6].
Table 1 Number of Game States and Changes in Win/LossInformation
Number ofNumber
Number of phases infencesof allwhich win/loss
installedphasesinformation changed
0 fence960
1 fence
61440
764
2 fence
43636449273

Table 1 shows the number of enumerated positions andthe number of positions where win/loss information
changed when applying the proposed method to split theset of positions into subsets based on the number offences on the board (0 fences for S0, 1 fence for S'1, and2 fences for S'2) during retrograde analysis of S2. For
example, enumerating 436,364 positions in S'2 andpropagating them to S'1 through retrograde analysis
resulted in changes in win/loss information for 49,273
positions. This means that the number of positions
enumerated at once has decreased by approximately 14%.
Thus, an improvement in space complexity was observed.
However, concerning the Quoridor game addressed inthis study, the impact of changes in win/loss information
was about 80%, which was significant, and did not leadto a reduction in computational complexity.

Fig. 5 The updating of win/loss information

One advantage of this method is its ability to consider tie
scenarios, wherein players repeat the same moves,referred to as "Sennichite."
4. Research Methods

6. Conclusion

This study proposes a method to determine the outcomeof a game by reusing results obtained from a reduced
version of the game board. The term "reduced version"refers to adjustments made to the game board's size or thenumber of items. For example, in a fixed-size Quoridor
game, reuse occurs in situations where irreversible moves
are made, typically related to placing fences. In a set ofgame states Sn where the number of fences on the board
is n or less, a containment relationship S0 ⊂S1 ⊂S2…
holds. Thus, defining S'k = Sk \ Sk-1 (k=1,2,3, …), we have
Sk = Sk-1∪S'k, Sk-1 ∩ S'k = φ.
Consequently, during the analysis of game state Sk, it
suffices to examine whether S'k introduces updates to thevalues of S'k-1, given that the analysis of state Sk-1 hasalready been completed. If updates occur, they arepropagated sequentially to S'k-2, S'k-3, and so on.

Retrograde analysis is an effective method for analyzing
the outcomes of games that allow for draws, but it
presents challenges in terms of space complexity rather
than time complexity. Therefore, retrograde analysis isdifficult to apply to problems other than those with asmall number of legal positions.
In this study, we aimed to reduce the number ofenumerated legal positions in game analysis using
retrograde analysis, and proposed a method to partition
the set of legal positions by irreversible moves. As aresult, the effectiveness of the proposed method wasconfirmed.
However, when dividing the set of legal positions, it isnecessary to minimize the impact of newly added
positions on the previously analyzed ones. This can lead233

to significant savings in terms of time complexity. Itshould be possible to reduce the computational
complexity requiring reanalysis by devising partitioning
methods, even in the Quoridor game studied in thisresearch.

Prof. Makoto Sakamoto
He received the Ph.D. degree incomputer science and systems
engineeringfromYamaguchi
University. He is presently anassociate professor in the Faculty ofEngineering, University of Miyazaki.
He is a theoretical computer scientist,and his current main research interests
are automata theory, languages, andcomputation, etc.

References
1.
2.
3.
4.
5.
6.

Hu, Te Chiang; Shing, Man-tak, Combinatorial
Algorithms. Courier Dover Publications. 2002.
https://quoridor.jp/#“Quoridor
GameRules”
https://www.ultraboardgames.com/quoridor/gamerules.php
Teturo Tanaka An Analysis of a Board Game“Doubutsu Shogi” Journal of Information Processing,Vol. 48, No. 11, pp. 3470–3476(2007).
J. Romein and H. Bal: Solving the Game of Awari
using Parallel Retrograde Analysis, IEEE Computer,Vol. 36, No. 10, pp. 26 – 33(2003).
Takuro IWANAGA, Makoto SAKAMOTO, Takeo
ITO, Satoshi IKEDA, Analysis of Quoridor, 2022
Information Processing Society of Japan.

Prof. Takao Ito

He is Professor of Management ofTechnology (MOT) in Graduate
School of Engineering at Hiroshima
University.
Heisserving
concurrently as Professor of Harbin
Institute of Technology (Weihai)
China. He has published numerous
papers in refereed journals andproceedings, particularly in the area of management
science, and computer science. He has published morethan eight academic books including a book on Network
Organizations and Information (Japanese Edition). His
current research interests include automata theory,
artificial intelligence, systems control, quantitative
analysis of inter-firm relationships using graph theory,etc.

Authors Introduction
Dr. Satoshi Ikeda

He received PhD degree fromHiroshima University. He is anassociate professor in the Faculty ofEngineering, University of Miyazaki.
His research interest includes graphtheory, probabilistic algorithm, fractalgeometry and measure theory.

Mr. Takuro Iwanaga

He received his B.S. degree inInformation Systems Engineeringfrom the University of Miyazaki in
2021. He is currently enrolled in themaster's program at the University ofMiyazaki.

234