Battle Sheep is PSPACE-complete

Battle Sheep is a board game published by Blue Orange Games. With two players, it is a combinatorial game that uses normal play rules. We show that it is PSPACE-complete, even when each stack has only up to 3 tokens.

Artificial Intelligence in Games Advanced Combinatorial Mathematics Advanced Graph Theory Research

Paper

Similar papers

One Hex reduction to rule them all: Quoridor, Maze Attack, Pinko Pallino and Blockade are PSPACE-completeFrancesco Carboni, Daniele Muscillo2026 · arXiv (Cornell University) In Library

The Game of Tumbleweed is PSPACE-completeLear Bahack2022 · arXiv (Cornell University) In Library

Dots & Boxes is PSPACE-completeKevin Buchin, Mart Hagedoorn, Irina Kostitsyna et al.2021 · arXiv (Cornell University) In Library

Turning Tiles is PSPACE-completeKanae Yoshiwatari, Hironori Kiya, Koki Suetsugu et al.2023 · arXiv (Cornell University) In Library

Dots & Boxes Is PSPACE-CompleteKevin Buchin, Mart Hagedoorn, Irina Kostitsyna et al.2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

Hive Is PSPACE-HardDaniël Andel, Benjamin Rin2025 · ArXiv.org In Library

6-Uniform Maker-Breaker Game Is PSPACE-CompleteLutfar Rahman, Thomas Watson2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

Celeste is PSPACE-hardLily Chung, Erik D. Demaine2022 · arXiv (Cornell University) In Library

Quoridor is PSPACE-CompleteMarius Drop, Benjamin Rin, Finn van der Velde2026 · arXiv (Cornell University) In Library

A Solution to the Subset Sum Game Complexityhoussem drablia2026 · Zenodo (CERN European Organization for Nuclear Research) In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal