Id: arxiv/2611.17252 Url: https://arxiv.org/abs/2611.17252 Tags: cs.CC, cs.GT, math.CO Score: 0 Title: Sowing the Seeds of Intractability: Kalah is PSPACE-complete Domain: cs.CC Source: arxiv Authors: Ethan Dickey, Ethan Mader Reviews: 0 Subject: cs.CC Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.17252 Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard…