Haskell Tic Tac Toe tuple board: How to generate possible moves?

Question

So I have a Tic Tac Toe board, in the form of nested tuples, like so:

type Row = (Field, Field, Field)
type Board = (Row, Row, Row)

data Field = X | O | B
    deriving (Eq, Ord)

Where B stands for empty. I need to take a player, a given board state, and then generate a list of all possible board states after the next move.

moves :: Player -> Board -> [Board]

However, I just can't figure it out. My initial thought is that I need to iterate through every field, to check whether or not it is empty, and then add a new Board to the list or do nothing. However, I see no way to iterate through all the fields. Even if I manually check every field with if statement or guards, how do I move onto the next field to check it, regardless of whether I end up with a possible move or not?

If I convert the board format into a list I could do it, but I feel like that defeats the purpose of this problem. There's got to be a better solution that doesn't require restructuring Board.

Answer 1

You're not going to be able to iterate through the fields of a tuple -- tuples aren't intended for that. A list of lists is probably a more natural representation for this problem.

That said, you can implement this function with the board representation you're using by following the types. A move on a Board is a move on either the first, second, or third row. A move on a row is the placement of the player on either the first, second, or third field. The difficulty with your representation is that there's no simple way to map over a tuple, since tuples are generally heterogeneous. So instead, one thing you can do is write yourself a generic way to apply a function to a location in a tuple. Here's one way to do that (if the Monad stuff confuses you, mentally substitute "list of foo" everywhere you see m foo and you'll be okay):

mReplace1 :: Monad m => (a -> m d) -> (a,b,c) -> m (d,b,c)
mReplace1 f (a,b,c) = f a >>= \d -> return (d,b,c)

mReplace2 :: Monad m => (b -> m d) -> (a,b,c) -> m (a,d,c)
mReplace2 f (a,b,c) = f b >>= \d -> return (a,d,c)

mReplace3 :: Monad m => (c -> m d) -> (a,b,c) -> m (a,b,d)
mReplace3 f (a,b,c) = f c >>= \d -> return (a,b,d)

These functions provide a way to apply a function to the first, second, and third slots in a tuple, respectively. They're wrapped in a monad so that we can have a function that returns a list of possibilities for the slot, and automatically convert that to a list of possibilities for the tuple as a whole.

With these, we can write the overall function just by stringing these calls together.

moves p board = mReplace1 rowMoves board ++
                mReplace2 rowMoves board ++
                mReplace3 rowMoves board
    where rowMoves row = mReplace1 fieldMoves row ++
                         mReplace2 fieldMoves row ++
                         mReplace3 fieldMoves row
          fieldMoves B = [p]
          fieldMoves _ = []

That is: the moves for a board are all the possibilities for a move in row 1, plus all the possibilities for row 2, plust all the possibilities for row 3. For a given row, the possible moves are all the moves for slot 1, plus all the moves for slot 2, plus all the moves for slot 3. For a given slot, if there's already an X or an O there, then there are no possible moves; otherwise there's one possible move (placing the player in that slot).

Answer 2

Here's a simple solution that I've used before

import qualified Data.Map as Map

data Piece    = O | X deriving (Eq,Ord)
type Position = (Int,Int)
type Board    = Map.Map Position Piece

positions = [(i,j) | i <- [0,1,2], j <- [0,1,2]]

spaces board = map (\pos -> Map.notMember pos board) positions

moves player board = map (\pos -> Map.insert pos player board) (spaces board)

Answer 3

As other people have stated, tuples is not a very good idea for this approach, since there is no way to traverse them.

You said you needed tuples, so there you go, I'm almost sure it works, test it.

First your code how I would've done it

import Control.Monad (msum)
import Control.Applicative ((<*>), pure)

data Player = P1 | P2 deriving (Eq, Show)

data Field = X | O | B deriving (Eq, Show)

type Board = ((Field,Field,Field)
             ,(Field,Field,Field)
             ,(Field,Field,Field))

symbolToPlayer :: Field -> Player
symbolToPlayer X = P1
symbolToPlayer O = P2

checkThree :: (Field,Field,Field) -> Maybe Player
checkThree (a,b,c)
    | a == b && a == c = Just $ symbolToPlayer a
    | otherwise        = Nothing

winHorizontal :: Board -> Maybe Player
winHorizontal (r1, r2, r3) = msum $ map checkThree [r1, r2, r3]

winVertical :: Board -> Maybe Player
winVertical ((a,b,c), (d,e,f), (g,h,i)) =
    msum $ map checkThree [(a,d,g), (b,e,h), (c,f,i)]

winDiagonal :: Board -> Maybe Player
winDiagonal ((a,_,c), (_,e,_), (g,_,i)) =
    msum $ map checkThree [(a,e,i), (c,e,g)]

hasWinner :: Board -> Maybe Player
hasWinner b = msum $ [winHorizontal, winVertical, winHorizontal] <*> pure b

---

This is the part of nextStates function

boardBlanks :: Board -> Int
boardBlanks (r1,r2,r3) = rowBlanks r1 + rowBlanks r2 + rowBlanks r3

rowBlanks :: (Field, Field, Field) -> Int
rowBlanks (a,b,c) = foldr hack 0 [a,b,c]
    where hack B c = 1 + c
          hack _ c = c

changeBoard :: Field -> Int -> Board -> Board
changeBoard f i (a,b,c)
    | hack [a] > i    = (changeRow f (i - hack []) a, b, c)
    | hack [a,b] > i  = (a, changeRow f (i - hack [a]) b, c)
    | hack [a,b,c] > i= (a, b, changeRow f (i - hack [a,b]) c)
    where
        hack ls = sum $ map rowBlanks ls

changeRow f 0 row =
    case row of
         (B,a,b)   -> (f,a,b)
         (a,B,b)   -> (a,f,b)
         (a,b,B)   -> (a,b,f)
         otherwise -> row
changeRow f 1 row =
    case row of
        (B,B,a)   -> (B,f,a)
        (a,B,B)   -> (a,B,f)
        otherwise -> row
changeRow f 2 row =
    case row of
        (B,B,B)   -> (B,B,f)
        otherwise -> row

nextStates :: Board -> [Board]
nextStates b = os ++ xs
    where
        os = foldr (hack O) [] . zip [0..] $ replicate (boardBlanks b) b
        xs = foldr (hack X) [] . zip [0..] $ replicate (boardBlanks b) b
        hack f (i,a) ls = changeBoard f i a : ls