Sowing the Seeds of Intractability: Kalah is PSPACE-complete
Ethan Dickey, Ethan Mader
Abstract
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 under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store.
We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially).
Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.
Review reports
xPeerd (AI review)
AI Review (xPeerd — DAReview)
Summary
This manuscript proves that the generalized decision problem for Kalah is PSPACE-complete when the board width is part of the input and pit counts are encoded in unary. The central claim is stated explicitly in the abstract and Section 1: “deciding whether a designated player can force a win from such a position is PSPACE-complete” and this remains true “under either common convention for capture opposite an empty pit, and with or without the bonus rule” . The paper’s main technical route is to introduce an intermediate problem, Line Kalah, reduce quantified Boolean formulas to it, and then embed Line Kalah into Kalah with empty stores . A complementary upper bound is also given: every unary Kalah play has polynomial length, yielding membership in PSPACE .
The manuscript’s strengths are clear theorem statements, robust handling of rule variants, and a carefully layered proof architecture summarized in Figure 5 and Section 9.5 . Its main weaknesses are not obvious logical gaps from the retrieved text, but rather the paper’s very high proof complexity, heavy notation, and dependence on many deferred lemmas and appendices, which may make verification and reproducibility difficult for readers and reviewers. The manuscript appears coherent and situated within a recognized complexity-theoretic paradigm, and I do not see strong paper-mill or fabrication signals in the retrieved passages. The AI-disclosure statement, however, raises a heightened need for especially careful human verification of all proofs and exposition choices .
Potential Major Revisions
- Improve proof accessibility and auditability of the central hardness construction.
The paper’s main contribution depends on a long multistage reduction pipeline: “Sections 5 to 8 reduce quantified formulas to Line Kalah, Section 9 reduces Line Kalah to Kalah, and Section 10 discusses open questions” . The organization is mathematically standard, but the proof burden appears unusually high because correctness relies on many tightly coupled invariants, policies, and appendices. For example, the manuscript states: “The two strategy theorems handle arbitrary play by the opponent, not only the intended play. Every part of the hardness proof also uses the facts about landing columns and covers in Section 3.2” . This is rigorous in intent, but the exposition as shown is difficult to audit.
I think the paper would benefit from a dedicated “proof roadmap” subsection immediately before the technical core, not only with dependency structure, but with a compact statement of the exact invariant preserved at each stage of the reduction. At present, specialized concepts such as “slack,” “cover rule,” “right-first policy,” and “left-first policy” appear in dense succession—for instance, “Alice may postpone one triple while its slack exceeds the number of saves that the other triple still needs” in Section 6.3 . This may be correct, but it is cognitively expensive to verify.
- Clarify the novelty claim relative to prior complexity results and fixed-board solution literature.
The manuscript correctly distinguishes fixed-board solving from asymptotic complexity, stating that previous computer solutions “concern fixed boards” and “do not resolve the complexity of the game on boards of growing size” . This is a sound positioning move. However, the introduction would be stronger if it more explicitly isolated what is novel in the reduction technique itself, not only in the theorem statement.
A promising novelty statement already exists: “At the center of the proof is Line Kalah, a game on a line that we introduce. It separates captures from the rest of the rules” . I recommend making this methodological novelty more explicit in the introduction: is the main conceptual contribution the Line Kalah abstraction, the robustness across capture conventions and bonus rules, the empty-store embedding, or the specific timer/target construction? Right now, all are present, but the hierarchy of contributions is somewhat diffuse.
- Strengthen reproducibility of the upper-bound and embedding arguments with more intuitive examples.
Section 4 gives a concise and elegant potential-function style argument: “Every move either increases Σ, or leaves Σ unchanged and lowers Ψ” . This appears to be one of the cleanest parts of the paper. By contrast, the later embedding arguments rely on many parameters: “Π = M0 + 1, Z = (p − 1)Π ... Φ = qZ + Σ(h + x)Bx, N = h + D + (Φ + 1)M + 1” . Even if formally correct, this level of parameterization can make the construction feel opaque.
I recommend adding one fully worked small example tracing a toy quantified formula through:
- formula encoding,
- Line Kalah construction,
- empty-store Kalah embedding,
- and the win/loss correspondence.
Without such an example, reviewers must trust the machinery without enough intuitive anchoring.
- Add a more explicit integrity and verification note around AI-assisted drafting.
The AI disclosure is unusually specific: “The authors used large language models ... to explore candidate reductions and intermediate game variants (including Line Kalah), assist with drafting and restructuring the exposition and terminology, and generate figures. All mathematical constructions, reductions, and proofs were rigorously verified, refined, and validated by the authors” . This disclosure is commendably transparent. Still, because the paper’s claims are proof-heavy and subtle, I think the manuscript should include a short appendix or statement describing the verification workflow more concretely—e.g., whether proofs were independently rechecked by both authors, whether mechanized checks were attempted for any lemmas, or whether figure-generation by LLMs was manually audited against formal definitions.
This is not an accusation of unreliability. Rather, the disclosure itself creates a reasonable expectation for extra precision in documenting how correctness was ensured.
- Discuss the remaining gap for binary encodings more sharply.
The manuscript states that with binary counts, the problem is “in EXPTIME and PSPACE-hard” and that “whether the winner can still be decided in polynomial space is open” . This is a useful result, but the practical and conceptual meaning of the gap should be discussed more explicitly. Since the unary result is complete while the binary result remains open, the paper should help the reader understand whether the obstacle is merely the play-length argument, or whether there are deeper structural barriers to adapting the hardness/containment framework.
- Add a concise anti-confusion subsection on rule variants.
A major strength is the robustness claim that the “same positions are hard under both capture conventions, with and without the bonus rule” . But because these variants affect move semantics, the paper would benefit from a boxed summary showing exactly which lemmas are convention-sensitive and which are not. The manuscript partly addresses this in Proposition 8.7, which explains why “the convention does not affect the arguments for these positions” . Still, a consolidated map would reduce reviewer effort and prevent accidental misunderstanding.
Potential Minor Revisions
- Improve local readability in dense definitional passages.
The core problem definition is precise, but several sentences are long and nested. For example: “If the last stone lands in a pit on the mover’s side that was empty immediately before it arrived, it captures the opposite pile...” . I would not call this incorrect, but some rule explanations could be broken into shorter sentences or displayed bullet points for easier scanning.
- Reduce notation overload where possible.
The manuscript introduces many symbols in short spans, especially in the embedding section. In Definition 9.1, the block assigning MB, M0, Π, Z, M, q, h, Φ, and N is mathematically legitimate but visually dense . A notation table near the start of Section 9 would help.
- Make appendix dependence more reader-friendly.
The paper often defers proofs to appendices, e.g., “The proofs of the three lemmas of this subsection and the next are in Appendix E” . This is acceptable for a theory paper, but readers would benefit if each deferred result were accompanied by a one-sentence proof idea in the main text.
- Typographic and formatting issues visible in extracted text.
In the retrieved snippets, there are several extraction-visible formatting problems, such as page-number collisions and line-merge artifacts like “299 From Line Kalah to Kalah” and “329.5 Proof of the main theorem” . These may partly be PDF extraction artifacts rather than source errors, but the final manuscript should be checked carefully for pagination, heading spacing, and line wrapping.
- Clarify one phrase that may sound informal.
The phrase “only one is needed adversarially” in the abstract’s clause-testing description may be clear to specialists, but a brief clarification would improve accessibility .
- AI content analysis for this post-2021 work.
Estimated percentage of AI-generated content: low to moderate in prose assistance, indeterminate in mathematical substance. The explicit disclosure indicates LLM use “to explore candidate reductions and intermediate game variants ... assist with drafting and restructuring the exposition and terminology, and generate figures” . Based on the retrieved text alone, I do not see obvious generic-AI hallmarks such as shallow repetition, fabricated references, or semantically empty abstraction. The prose is technical, specific, and tightly aligned with formal claims. The main AI-relevant concern is not stylistic artificiality but verification burden: a proof-heavy manuscript that acknowledges AI assistance should be checked especially carefully for subtle overclaims, omitted cases, or polished but fragile exposition.
Highlighted AI-detected sections:
- The formal AI disclosure section itself on page 33 is the clearest direct evidence of AI use .
- I do not identify any additional passage from the retrieved snippets as obviously AI-generated solely on linguistic grounds.
- Assessed epistemic impact: moderate. Because the manuscript’s contribution is theorem-driven, any weakness would arise from proof correctness rather than prose style. The disclosure reduces hidden-risk concerns, but it does not by itself validate the proofs.
Recommendations
- Preserve the theorem-level contribution, but revise the manuscript to make the proof architecture substantially easier to verify.
- Add one end-to-end worked example from quantified formula to Kalah instance.
- Insert a compact “invariants and dependencies” guide summarizing what each section proves and exactly what later sections rely on.
- Strengthen the introduction’s novelty framing around Line Kalah as a conceptual abstraction, not only as an intermediate gadget.
- Add a short verification note explaining the authors’ human checking process in light of the disclosed LLM assistance.
- Add a notation table and a rule-variant map for the capture conventions and bonus rule.
- Perform a careful final formatting audit, especially for appendix transitions, pagination, and heading presentation.
Overall, I view the manuscript as potentially strong and publishable in a theoretical computer science venue if the exposition is revised to improve auditability and reviewer confidence. I do not currently see strong signs of fraud, fabrication, or incoherent paradigm mismatch in the retrieved material; the paper fits a recognizable computational complexity framework and articulates a concrete theorem, proof strategy, and open problems clearly .
Author response
Several of the suggested major revisions concern material already in the paper. Section 2 gives a detailed proof overview, Figure 5 shows the dependencies between the main results, Section 6 states the local assumptions and policies, and Section 8 explains the global strategy and induction. The introduction and Section 10 also explain why the unary play-length argument does not establish PSPACE membership for binary counts. The capture conventions and bonus rule are addressed in the definitions, Proposition 8.7, and Section 9.
The reported heading collisions appear to be text-extraction artifacts. The page numbers and section headings are separated correctly in the PDF.
A smaller example connecting a writer's choice to its records and the reader's test could still help make the construction easier to follow. The abstract's phrase "only one is needed adversarially" could also be clearer: the intended point is that Bob only needs to find one false clause.
The report's discussion of AI-generated-content percentages does not identify a mathematical issue. Our disclosure describes how AI tools were used and makes clear that the authors are responsible for the paper. We welcome specific questions about the proofs, but the report does not identify an incorrect inference, missing case, or counterexample.
Reviewer3 (AI review)
AI Review (reviewer3.com)
Overview
PSPACE-Completeness of Kalah
Contribution
This study proves that deciding whether a designated player can force a win in generalized Kalah with unary stone counts is PSPACE-complete.
Line Kalah Framework
Contribution
The authors introduce Line Kalah as an intermediate PSPACE-complete game model that isolates capture interactions to simplify computational complexity reductions.
Comments (2)
1. Gap between consecutive band tops is 2W, not W — Editorial
. Consecutive band tops differ by W , except a n − 1 − b ⋆ = W +16
In Section 5.3, Table 5, and Appendix A.3, the paper states that is the gap between consecutive bands and that consecutive band tops differ by . However, in Section A.1, the band coordinates are defined as and . Under this definition, for consecutive writers and , the difference between consecutive band tops is (and ), while the gap between the top of band and the bottom/top of band is . Thus, consecutive band tops differ by , contradicting the prose in Section A.3 that "Consecutive band tops differ by , except ."
2. Off-by-one discrepancy in selector Bob move numbers — Editorial
Otherwise, if this is Bob’s move number
Because Alice moves first and the players alternate, at the start of writer (after moves by each player), Bob has already made moves, so his moves during writer are his moves number . However, several places in the text refer to Bob's selector move during writer as his "move number " (or "move "), while simultaneously stating that it occurs during writer (e.g., as "his eighth move of the writer" or after moves have already been made). Specifically:
- Section 7.1 (Definition 7.1, rule 2): "if this is Bob's move number for a universal writer ..."
- Section 7.2 (Lemma 7.2(1)): "At the start of writer ... Bob has made moves, of which one at each universal writer was a selector... captured by the selector on his move $8i'$". If writer is universal and has not started yet, Bob cannot have already made his move at writer ; moreover, for (if universal) move does not exist, and for move occurred during writer .
- Appendix C (Proof of Lemma 7.2): "So each of Bob's first moves crosses both selectors of writer , and before his move $8i''$ each of them lands exactly at its weapon." Since the selector initial count in Section A.1 is , the selector lands at after receiving stones, which happens before Bob's -th move (the last move of writer ), not on "his eighth move of the writer" as stated in the proof of Lemma 7.3 ("Rule 2 applies at most on his eighth move of the writer").
- Section 8.3 (Lemma 8.4(2)) and Appendix D (Proof of Lemma 8.5(1)): "A captured weapon of writer was captured on Bob's move (Lemma 8.4(2)), just before the writer started", which directly contradicts Lemma 7.3's proof that the selector of writer is fired on Bob's eighth move of writer .
XSci (AI review)
Summary
The manuscript determines the computational complexity of Kalah, a two-player sowing game of the mancala family, in the generalization where the number of pits per side is part of the input, the starting position is arbitrary, and stone counts are written in unary. A potential argument (Lemma 4.1) bounds every play by moves, giving membership in PSPACE and a polynomial-time algorithm at each constant width. For hardness the authors introduce Line Kalah, a game on a line in which stones leaving the line disappear and the only interaction between the players is capture, reduce quantified Boolean formulas to it by a construction of timers, writers and a reader (Theorem 5.1), and embed the resulting line positions into Kalah boards with both stores empty (Theorem 9.7). The conclusion is that deciding the winner is PSPACE-complete under either capture convention, with or without the bonus rule.
Contribution and Significance
The core contribution is Theorem 1.2: generalized unary Kalah is PSPACE-complete, with hardness holding for a single family of positions in all four rule variants, with both stores empty and Alice to move. This settles a question listed as open in Guy's problem collection (Problem 39, Games of No Chance, 1996) and restated as Problem D3(39) by Nowakowski in Games of No Chance 6 (2025), for a game with an unusually long history in computer science, from Silver's 1961 PDP-1 program [19] and Slagle and Dixon [20] to the solving work of Irving, Donkers and Uiterwijk [8]. It matters because no hardness result was known for any mancala variant with a variable number of pits, not even NP-hardness.
Relative to the closest prior work the advance is real. Irving et al. [8], Carstensen [2] and Romein and Bal [17] solve fixed boards and report game-tree and state-space sizes, which say nothing about asymptotic complexity. Maei et al. [10] give sufficient winning conditions for capture-free Simple-Kalah and a count of reachable configurations; as the authors correctly observe, such a count does not exclude a polynomial-time algorithm. Broline and Loeb [1], Erickson [3] and Musesti et al. [11] study sowing combinatorially rather than complexity-theoretically. The reduction is also not an application of an existing framework: sowing offers no natural wiring, so the authors must manufacture deadlines out of the one quantity the rules provide, a pile's landing column, and make the argument survive the fact that either player may select any nonempty pit at any time.
Two qualifications. The theorem concerns arbitrary positions, not the uniform openings that most readers associate with the name; the authors say so in Section 1.2 and leave it open in Section 10. And the hard boards are extremely sparse: the active line segment of width sits inside a board of width . Both are normal for this genre (Chess [4], Checkers [16], Othello [9]) but should be kept in view.
Strengths
- The membership proof is short, complete and convention-independent: the pair (store mass , negated distance sum ) increases lexicographically on every move, which bounds the play length and, at constant width, also orders the positions for a polynomial-time evaluation (Lemma 4.1 and the remark after Theorem 4.2).
- Robustness is handled properly rather than asserted. Lemma 3.3(5) isolates the single situation in which the two capture conventions can differ and shows it cannot arise opposite a pending target, and Proposition 8.7 and Theorem 9.7 then carry one family of positions through all four rule choices.
- Section 6 abstracts the right thing. Slack, frontier and the cover rule are defined for a general band setting, so Lemmas 6.3 to 6.5 and Theorems 6.7 and 6.9 serve writers, the reader and off-script play alike, which is what makes unrestricted moves manageable.
- The forcing arguments for false formulas are genuinely tight, not waved at. Lemma 7.3 rules out a timer capture on Alice's moves 1, 3, 4, 5 and 6 or later by separate counts, and the case turns on the observation that saving adds a stone to every pile above it, so that afterwards no pile below lands at , which uses Lemma 5.5(3) to rule out any Alice pile landing at .
- Lemma 8.5(4) is the elegant core of the other direction: because , every Bob move that feeds also feeds , so , and forces the entire preceding play to have been intended branches whose bits form a play of the assignment game.
Recommendation
Minor Revision for the International Colloquium on Automata, Languages and Programming. The paper settles a named open problem about a classical game with a complete proof, a matching upper bound, and robustness across all four rule variants, and the load-bearing steps (Lemmas 4.1, 5.3, 5.5(4), 7.2(2), 7.3, 7.4, 8.2(2), 8.5(2)-(4) and Section 9) check out. What remains is presentation and assurance: several internal slips listed below occur in load-bearing statements, and a construction calibrated this finely deserves a sanity check that a referee can run.
Minor Revision for the International Conference on Mathematical Foundations of Computer Science. Nothing changes in the assessment; the main adjustment is that the page limit will force even more of Sections 6 to 9 into an appendix, so the body should carry a self-contained proof sketch of Theorem 5.1.
Minor Revision for the International Symposium on Algorithms and Computation. Also a good fit; for that audience the algorithmic side (Lemma 4.1, the polynomial-time algorithm at constant width, and the EXPTIME bound of Proposition 10.1) deserves more prominence than it currently receives.
The concerns below are written against the benchmark venue.
Major Concerns
None.
Minor Comments
- In the proof of Theorem 6.7, case "Bob fires " (Appendix B), the conclusion reads "the hypotheses of Lemma 6.5 hold with and ", but has just fired and both the statement of Theorem 6.7 and the preceding computation (; "By (W1), lies below and ") concern .
- In Section A.1 the dummy record count is written , but is defined nowhere; Section A.3 and Lemma 5.5(4) both use .
- The weapon count and the genuine-guard count differ only in letter case and appear in adjacent formulas throughout Appendix A; renaming one would remove a real obstacle to checking Section A.5.
- Table 1 appears to be shifted by one row: from "band, triple" onward each term carries the next term's meaning, and the last two rows both read "Alice's strategy for true formulas before and after Bob first leaves the intended play".
- Table 5 lists the four writer timers as "" and calls the selectors "sectors", and the jump entry of Definition 8.1 reads "If the firing timer is , or ... If it is or ", where and are evidently meant; please check whether these survived typesetting.
- A computational check would raise confidence considerably: implement the map of Section A.1, or a scaled-down variant with the slack constants reduced, and verify by exhaustive game-tree search on small formulas that Alice wins the line position exactly when the formula is true.
- There is no worked miniature example anywhere; one existential variable and one clause, with the actual columns and counts of Section A.1 laid out, would make Sections 5 and 6 far easier to follow.
- The constants , , and the repeated "" are chosen with slack; stating up front the handful of inequalities the proofs actually use, as Lemma A.1(2) nearly does, and only then verifying that these values satisfy them would separate the design from the arithmetic.
- The output board has width with , so is of order with ; a remark on whether the long empty stretch can be shortened, and what polynomial degree is achievable, would be welcome.
- Section 1 expresses the hope that separating captures out as Line Kalah "helps to classify other sowing games", but Section 10 lists Oware as open without indicating what an embedding of line positions into it would require, given its different sowing, capture and feeding rules; even a sketch would support the claim.
- The bounded two-player constraint-logic framework of Hearn and Demaine is cited only as a general pointer [7]; one or two sentences on why a direct reduction from quantified formulas is needed for Kalah would help place the construction.
- In the "Upper bounds" bullet of Section 1.1, "a polynomial-time algorithm for each constant width" should carry the unary qualifier explicitly, since the configuration count in the remark after Theorem 4.2 is exponential for a binary input.
Author response
This review makes a few useful suggestions, but several of its specific comments appear to come from errors in reading the PDF.
In Comment 1, the proof of Theorem 6.7 already uses T_right = {R'}, the surviving backup timer. In Comment 2, the dummy-record count is R_star - d_eta - 6n - eta; K_star does not appear there. The issues described in Comments 4 and 5 are also not present in the PDF: Table 1 is aligned correctly, and Table 5 and Definition 8.1 use the correct timer names, selectors, and subscripts.
The suggestion to repeat the unary-encoding assumption in the constant-width algorithm claim is helpful. Distinguishing k_0 and K_0 more clearly and adding a small example connecting a writer's choice to the reader's test could also improve readability. The paper does already include a numerical move example and an eight-move writer trace, though, so it is not quite accurate to say that there are no miniature examples.
Computational checks could provide additional confidence in the construction. Checking the coordinate inequalities and local move sequences would be more practical than exhaustively searching the actual constructed positions, even for small formulas. Using smaller constants would require separately checking that the modified construction still satisfies the necessary inequalities.
Finally, the review broadens one of our claims. The paper says that no hardness result was known for generalized Kalah, not for every mancala variant. An Oware embedding or a smaller polynomial construction would be interesting directions for future work.