What structure should I use to express a turn in a board game?

Question

I've got a working implementation of a Kalah solver, an application that calculates the optimal succession of moves on the first turn of the game.

I'm in the process of reimplementing this application, although this time with a test suite and (hopefully) prettier code that makes use of the more interesting structures like monoids or monads.

As you can see in the original code (or not, it's very convoluted and that's why I'm rewriting it) I've defined one "move" as follows:

1. I'm passing in a list of Pot as my board, along with a starting position on my side of the board.
2. I pick up and drop marbles until I get to the end of the list of Pot.
3. At the end of a "lap" I return the altered board ([Pot]), how many marbles I might be holding in my hand and an ADT expressing whether I should go for another lap or not (LapResult).

The thing is that I suspect that I wouldn't need to separate a move into laps if I expressed the board state with some clever data structure that I could both pass in as an input argument to a function and have that same data structure come out as a return value. At least that's my guess, my thought was that board state reminds me of what I've read about monoids.

So if I define one "move" as all the pick-up-and-drop-marbles until you land in an empty pot or in the store, is there some obvious way of rewriting the code for how a "move" works?

Current state of reimplementation can be found here.

Answer 1

Note: I have not tested any of this. Its probably buggy.

I think your problem is that you need to consider the board from two points of view, call them "White" and "Black".

data Player = White | Black

otherPlayer :: Player -> Player
otherPlayer White = Black
otherPlayer Black = White

The Mancala board is a circular structure, which suggests modular arithmentic. I'd suggest something like:

import Data.Vector -- More efficient version of Array

type PotNum = Int  -- Use Int for simple index of pot position.

type Pot = Int   -- Just record number of marbles in the pot.

You might get a more compact data structure by using Data.Word8 instead of Int, but I'm not sure. Keep it simple for the moment.

type Board = Vector Pot

Then have isStore be a simple function of PotNum and the player

isStore :: Player -> PotNum -> Bool
isStore White 0 = True
isStore Black 7 = True
isStore _ _ = False

You also want to move forwards around the board, skipping the other player's stores..

nextPot :: Player -> PotNum -> PotNum
nextPot White 6 = 8  -- Skip Black's store
nextPot White 13 = 0
nextPot Black 12 = 0 -- Skip White's store
nextPot _ n = n + 1

A list of the controlled pots for each player

playerPots :: Player -> [PotNum]  -- Implementation omitted.

The number of marbles in a given pot

marblesIn :: PotNum -> Board -> Int  -- Implementation omitted.

Now you can write a move function. We'll have it return Nothing for an illegal move.

move :: Player -> PotNum -> Board -> Maybe Board   -- Implementation omitted.

Using the List monad you can make this produce all the potential moves and resulting board states

allMoves :: Player -> Board -> [(PotNum, Board)]
allMoves p b1 = do
    n <- playerPots p
    case move p n b1 of
       Nothing -> fail ""   -- List monad has this as []
       Just b2 -> return (n, b2)

So now you can get the complete game tree from any starting position using Data.Tree.unfold, which takes a variant of the move function. This is slightly inelegant; we want to know the move that resulted in the position, but the initial position has no move leading to it. Hence the Maybe.

The unfoldTree function takes a function (f in the code below) which takes the current state and returns the current node and the list of child node values. The current state and the current node are both a triple of the player who just moved, the move they made, and the resulting board. Hence the first bit of "f". The second bit of "f" calls the "opponentMoves" function, which transforms the value returned by "allMoves" to add the right data.

unfoldGame :: Player -> Board -> Tree (Player, Maybe PotNum, Board)
unfoldGame p b = unfoldTree f (p, Nothing, b)
   where 
      f (p1, n1, b1) = ((p1, n1, b1), opponentMoves (otherPlayer p1), b1
      opponentMoves p2 b2 = map (\(n3, b3) -> (p2, Just n3, b3)) $ allMoves p2 b2  

Now you just need to walk the tree. Each leaf is an end of the game because there are no legal moves left. The unfoldGame function is lazy so you only need the memory to hold the game states you are currently considering.