Overview
Research has demonstrated that the problem of determining if a given player possesses a winning strategy in a specific Quoridor position is PSPACE-complete. This classification applies to the game played on an $n \times n$ board.
Research Context
Quoridor is an abstract strategy game, published in 1997 and designed by Mirko Marchesi. It is characterized as a turn-based, deterministic, perfect-information game played on a square grid. The game shares characteristics with other combinatorial games such as chess, checkers, and Go. Similar games mentioned include Maze Attack, Blockade (also known as Cul-de-sac), and Pinko Pallino.
Approach
The PSPACE-completeness classification for Quoridor was established via a reduction from Gpos(POS CNF). Gpos(POS CNF) is a Boolean formula game initially defined by T. Schaefer in 1978. The reduction specifically addresses the problem of determining a winning strategy for a player in a given Quoridor position on an $n \times n$ board.
Findings
The primary finding is that the decision problem of determining whether a specific player has a winning strategy in a given Quoridor position on an $n \times n$ board is PSPACE-complete. This characterization places Quoridor within a complexity class that includes problems for which the amount of memory (space) required to solve them grows polynomially with the size of the input, while the time required may be exponential. The proof technique involved a reduction from Gpos(POS CNF).