HackerPapers

arXiv:2007.15895cs.GT

Quixo Is Solved

Satoshi Tanaka, François Bonnet, Sébastien Tixeuil, Yasumasa Tamura

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Quixo is a two-player game played on a 5$\times$5 grid where the players try to align five identical symbols. Specifics of the game require the usage of novel techniques. Using a combination of value iteration and backward induction, we propose the first complete analysis of the game. We describe memory-efficient data structures and algorithmic optimizations that make the game solvable within reasonable time and space constraints. Our main conclusion is that Quixo is a Draw game. The paper also contains the analysis of smaller boards and presents some interesting states extracted from our computations.

arXiv comments
19 pages
Journal reference
DOI
Subjects
cs.GTComputer Science and Game Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jun 2022 to Jun 2022.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Show HN: I made a deceptively simple but hard sliding puzzle 1 comment

    • Quixo (the game this seems to be based on) is also deceptively simple but Exptime complete (https://www.sciencedirect.com/science/article/pii/S002001902...) and was solved after 2 decades (draw at optimal play on a 5x5 board, win for first player on smaller boards)…

      captn3m0View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.