Kalah is a finite two-player sowing game in which counters are moved around two rows of pits and accumulated in stores (Irving et al. 2000). On a turn, a player empties a nonempty pit on that player's side and distributes its counters successively around the board, placing a counter in the player's store and skipping the opponent's store. If the last counter lands in the player's store, the usual rule grants another turn. If it lands in an empty pit on the player's side, the capture rule transfers it and the counters in the opposite pit to that player's store. A play ends when one side is empty, and the remaining counters are collected in their owner's store. The player with more stored counters wins. Variants differ on whether capture requires a nonempty opposite pit and on whether bonus turns are allowed.
Dickey and Mader (2026) proved that deciding whether a designated player can force a strict win is PSPACE-complete for variable-width boards and arbitrary supplied positions whose counter counts are encoded in unary. Hardness already holds when the designated player moves first and both stores start empty. The same hard positions work for both capture conventions, independently with and without bonus turns. The theorem does not restrict the input to the usual uniform opening positions.
If there are 
pits per player and 
counters, play length is at most 
. Fixed-width unary
instances can therefore be solved in polynomial time.
For binary-encoded counts, the general problem is PSPACE-hard
and lies in EXPTIME, but its exact complexity remains
open. Dickey and Mader (2026) report AI assistance in exploring candidate reductions
and intermediate game variants, which they checked and refined.
