HEXAGONbeta

Generalized Bawo: A Finite-State Model and an EXPTIME Upper Bound

A mix of human-written and AI-generated textHuman understanding: all partscs.CC — Computational Complexitycs.DS — Data Structures and Algorithms

Contributed by Isaac kaimfa ↗

SubmitterIsaac kaimfa

Version 1 / Sep 28, 2026 / CC BY 4.0

Abstract

Four-row mancala games, including Malawian Bawo and the related East African Bao, have received limited attention in computational complexity theory despite their combinatorial richness. This paper introduces GENERALIZED-BAWO-WIN, a finite-state two-player game model inspired by Malawian Bawo. The model is parameterized by a half-board width n and a binary-encoded lap cap L, and incorporates relay sowing, marker-pit capture, a formalized capture-relay rule (abstracting kichwa), mandatory capture, a singleton-start prohibition, and an explicit lap-cap truncation rule that guarantees move termination. We prove that GENERALIZED-BAWO-WIN belongs to EXPTIME under these semantics. The proof proceeds by establishing that the game's state space has size at most 2poly(|I|), that legal successors can be generated in 2poly(|I|) time, and that a WIN/LOSS/DRAW retrograde attractor can be computed over the resulting finite game graph. We emphasize that this is an upper bound: no hardness result is established. We further emphasize that the theorem applies only to the formally defined generalized model and does not classify Bao as played in East Africa, whose rules differ materially.

References

  1. A. de Voogt. A Survey of Mancala in Africa. Board Game Studies , 1999.
  2. A. de Voogt. Distribution of mancala board games: a methodological inquiry. Board Game Studies , 2(1):104--114, 1999.
  3. A. de Voogt. A Limiting Factor in the Distribution of Mancala. In New Approaches to Board Games Research , 1995.
  4. A. de Voogt. Reproduction of Bao positions using a learning algorithm. Board Game Studies , 5:63--72, 2002.
  5. I. Kaimfa. The state-space complexity of Malawian Bawo. Working paper, 2026.
  6. J. Donkers and J. Uiterwijk. Programming Bao. In Proceedings of the Computer and Games Conference , 2000.
  7. J. Donkers, J. van den Herik, and J. Uiterwijk. Selecting evaluation functions in Bao. In Advances in Computer Games , 2003.
  8. J. Donkers. Searching with Bao. PhD thesis, Universiteit Maastricht, 2002.
  9. A. de Voogt. The never-ending move in Bao. In Board Game Studies Colloquium , 1998.
  10. D. Lichtenstein and M. Sipser. GO is polynomial-space hard. Journal of the ACM , 27(2):393--401, 1980.
  11. E. Demaine and R. Hearn. Playing games with algorithms: algorithmic combinatorial game theory. In Games of No Chance 3 , 2009.
  12. A. Fraenkel and D. Lichtenstein. Computing a perfect strategy for $n n$ chess requires time exponential in $n$. Journal of Combinatorial Theory, Series A , 31(2):199--214, 1981.
  13. J. Robson. The complexity of checkers on an $N N$ board. In Proceedings of FOCS , 1984.
  14. S. Reisch. Hex ist PSPACE -vollst\"andig. Acta Informatica , 15:167--191, 1981.
  15. E. Emerson and C. Jutla. Tree automata, mu-calculus, and determinacy. In Proceedings of FOCS , 1991.

Version history

  1. v1Initial depositCurrentSep 28, 2026