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

Question

I have a working implementation of the Kalah solution, an application that calculates the optimal sequence of moves on the first turn of the game.

I am redefining this application, although this time with a set of tests and (hopefully) more beautiful code that uses more interesting structures such as monoids or monads.

As you can see in the source code (or not, this is very confusing and why I rewrite it). I defined one “move” as follows:

• I am passing the Pot list as my board along with the starting position on my side of the board.
• I pick up and drop the marble until I reach the end of the Pot list.
• At the end of the “circle” I return the modified board ( [Pot] ), how many balls I can hold in my hand and ADT, expressing whether I should go to another circle or not ( LapResult ).

The fact is, I suspect that I would not need to separate the movement in circles if I expressed the state of the board with some smart data structure, which I could pass as an input argument to the function and have the same data; the structure is given as a return value . At least my hunch, I thought that this state of government reminds me of what I read about monoids.

So, if I define one “move” as all the balls for grabbing and falling until you land in an empty bank or in a store, is there any obvious way to rewrite the code for how to “move”, work?

The current state of re-implementation can be found here .

Answer 1

Note. I have not tested this. This is probably a mistake.

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 

Mancala's board is a circular structure that offers modular arithmetic. I would 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 can get a more compact data structure using Data.Word8 instead of Int, but I'm not sure. Keep it simple for now.

 type Board = Vector Pot 

Then we have a simple PotNum and player function

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

You also want to move forward on board, skipping another store.

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

A list of controlled pots for each player

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

The number of marbles in this pot

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

Now you can write a move function. We will return him nothing for an illegal move.

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

Using the List monad, you can do this by making all possible movements and emerging board states.

 allMoves :: Player -> Board -> [(PotNum, Board)] allMoves p b1 = do n <- playerPots p case move pn 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 accepts a variant of the move function. It is a little inelegant; we want to know the move that led to the position, but in the starting position there is no movement leading to it. Therefore, it is possible.

The unfoldTree function takes a function (f in the code below) that takes the current state and returns the current node and a list of child node values. The current state and the current node are the three of the player who has just moved, the movement he made and the final board. Therefore, the first bit is "f". The second bit of "f" calls the function "enemyMoves", which converts the value returned by "allMoves" to add the desired data.

 unfoldGame :: Player -> Board -> Tree (Player, Maybe PotNum, Board) unfoldGame pb = 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 on the tree. Each sheet is the end of the game because there are no left movements left. The unfoldGame function is lazy, so you only need memory to store the game states you are currently considering.