Sage Journals: Discover world-class research

Abstract

This study presents a strong solution for the two-player, perfect-information, zero-sum board game PYLOS under three different rule sets: the rule set for children, the standard rule set, and the rule set for mature players. Using a zero-suppressed binary decision diagram, we systematically index all pseudo-reachable positions, that is, those that satisfy necessary structural constraints but may not be reachable during actual gameplay. Retrograde analysis is then executed on each rule set to assign game-theoretic values to all positions. A total of over 12 billion pseudo-reachable positions are considered. We also develop a method to extract truly reachable positions from this superset and verify the consistency of both indexing and value assignments. Experiments show that in all three rule sets, the first player is forced to lose, from the initial position, within 36, 40, and 46 moves, respectively. Furthermore, our analysis reveals that PYLOS has a higher proportion of zugzwang positions compared to previously solved games, emphasizing the strategic importance of conserving spheres. The mature players’ rule set generated the greatest number of legal moves. This study demonstrates the feasibility of computing strong solutions to PYLOS, and highlights structural differences among the three rule sets in terms of reachability and strategy.

Keywords

PYLOS strongly solving zero-sum game retrograde analysis ZDD zugzwang board game

Get full access to this article

View all access options for this article.

References

Aichholzer

Detassis

Hackl

Steinbauer

Thonhauser

(2010). Playing Pylos with an autonomous robot. In 2010 IEEE/RSJ International conference on intelligent robots and systems. (pp. 2507–2508).

Allis

van der Meulen

van den Herik

(1991). Databases in Awari. In D. Levy & D. Beal (Eds.), Heuristic programming in artificial intelligence: The second computer olympiad (London, August 15–21, 1990), Ellis Horwood Series in Artificial Intelligence, (Vol. 2, pp. 73–86). Ellis Horwood.

Allis

L. V.

(1994). Searching for Solutions in Games and Artificial Intelligence. PhD Thesis, University of Limburg.

Gasser

(1996). Solving nine men’s morris. Computational Intelligence, 12(1), 24–41.

Kishimoto

Winands

M. H.

Müller

Saito

J. T.

(2012). Game-tree search using proof numbers: The first twenty years. ICGA Journal, 35(3), 131–156.

Knuth

D. E.

(1997). The art of computer programming: Volume 4A. Addison-Wesley Professional.

Minato

(2011). Overview of ERATO Minato project: The art of discrete structure manipulation between science and engineering. New Generation Computing, 29(2), 223–238.

Minato

(2013). Techniques of BDD/ZDD: Brief history and recent activity. IEICE Transactions on Information, E96-D(7), 1419–1429.

Romein

J. W.

Bal

H. E.

(2002). Awari is solved. ICGA Journal, 25(3), 162–165.

10.

Romein

J. W.

Bal

H. E.

(2003). Solving Awari with parallel retrograde analysis. Computer, 36(10), 26–33.

11.

Sanno

Yamamoto

Hoki

(2024). [Strongly solving the two-player perfect-information zero-sum game “pylos” of three rule sets: Rule set for children, standard rule set, and rule set for mature players] Futari kanzen joho zerowa gemu “PYLOS” no kodomoyo, tsujo, jokyu ruru de no kyo kaiketsu (in Japanese). IPSJ SIG Technical Report: Game Informatics (GI), 2024-GI-51(24), 1–9.

12.

Schaeffer

Burch

Bjornsson

Kishimoto

Muller

Lake

Sutphen

(2007). Checkers is solved. Science (New York, N.Y.), 317(5844), 1518–1522.

13.

Takeda

Hoki

(2020). [Analysis of the number of piece placements in N men’s morris] n menzu morisu no koma no haichi no kazu no bunseki (in Japanese). IPSJ SIG Technical Report: Game Informatics (GI), 2020-GI-43(8), 1–8.

14.

Takizawa

(2023). Othello is solved. preprint arXiv:2310.19387.

15.

Tanaka

Bonnet

Tixeuil

Tamura

(2022). Quixo is solved. In C. Browne, A. Kishimoto & J. Schaeffer (Eds.), Advances in Computer Games: 17th International conference, ACG 2021, Virtual Event, November 23–25, 2021, Revised Selected Papers, Lecture Notes in Computer Science (LNCS), (Vol. 13262, pp. 85–95). Springer.

16.

Tanaka

(2007). Complete analysis of a board game “SIMPEI”. IPSJ Journal, 48(11), 3470–3476.

17.

Tanaka

(2009). An analysis of a borad game “doubutsu shogi”. IPSJ SIG Technical Report, 22(3), 1–8.

18.

Tanaka

(2020). Sixteen musashi is strongly solved. In Proceedings of the game programming workshop. (pp. 194–201).

19.

van den Herik

H. J.

Uiterwijk

J. W.

van Rijswijck

(2002). Games solved: Now and in the future. Artificial Intelligence, 134(1–2), 277–311.

20.

van der Goot

(2001). Awari retrograde analysis. In T. Marsland & I. Frank (Eds.), Computers and Games: Second international conference, CG 2000, Hamamatsu, Japan, October 26–28, 2000 Revised Papers, Lecture Notes in Computer Science (LNCS), (Vol. 2063, pp. 87–95). Springer.

21.

Yamamoto

(2024). [A Study on the Number of Positions and Winning Strategies in Board Games] Bodo gemu no koma no haichi su to hissho senryaku ni kansuru kenkyu (in Japanese). Master’s thesis, The University of Electro-Communications.

22.

Yamamoto

Hoki

(2023). [NOCCA

\times

NOCCA is solved] NOCCA

\times

NOCCA no kyo kaiketsu (in Japanese). IPSJ Journal, 64(12), 1678–1688.

A Strongly Solving PYLOS Under Three Rule Sets: Rule Set for Children,Standard Rule Set,and Rule Set for Mature Players

Abstract

Keywords

Get full access to this article

References