Wednesday, January 30, 2013

Classic AI: Mancala

Thing practiced: logic programming

Tools used: Sublime Text 3 beta, SWI-Prolog, J.R. Fisher’s Prolog tutorial

Mancala is a traditional African two-player board game with many different variations. One variant of mancala, called Kalah, has a long history in AI research – see e.g. Silver 1961 (pdf), Bell 1968, Slagle and Dixon 1969 (pdf), and Irving et al 2000 (pdf).

Prolog is a logic programming language devised by Alain Colmerauer and his colleagues in the early 1970s. The idea behind the language is that you feed the computer a set of facts and rules, then ask the computer to use those constraints to answer questions about things you want to know.

For today’s practice, I tried to implement a program to play mancala in Prolog – specifically the version of mancala I learned as a kid, which has three seeds per hole (game rules are here). To solve the game, we can generate a tree of possible moves for each state and use minimax with alpha-beta pruning to find the optimal one. The code is here.