2
\$\begingroup\$

I have written a tic-tac-toe game in Haskell and was wondering if anyone could provide any hints on how it could be improved

import Data.Bits
import System.IO
import Data.List

type Board = (Int, Int) -- the first Int is X's board, the second Int is O's board
data Player = X | O deriving (Eq, Show)

emptyBoard :: Board
emptyBoard = (0, 0)

place :: Board -> Player -> Int -> Maybe Board
place (xb, ob) player pos
  | testBit xb pos || testBit ob pos = Nothing -- position is already occupied
  | player == X = Just (setBit xb pos, ob)
  | player == O = Just (xb, setBit ob pos)

winningMasks :: [Int]
winningMasks = [0o7, 0o70, 0o700, 0o111, 0o222, 0o444, 0o421, 0o124]

winner :: Board -> Maybe Player
winner (xb, ob)
  | any (\mask -> (mask .&. xb) == mask) winningMasks = Just X -- X wins
  | any (\mask -> (mask .&. ob) == mask) winningMasks = Just O -- O wins
  | otherwise = Nothing -- the game is not over yet

data Score = OWins | Tie | XWins deriving (Eq, Ord, Show)

minimax :: Board -> Player -> (Score, Maybe Board)
minimax board player
  | winner board == Just X = (XWins, Nothing)
  | winner board == Just O = (OWins, Nothing)
  | popCount (fst board .|. snd board) == 9 = (Tie, Nothing)
  | player == X = maximum [(fst (minimax newBoard O), Just newBoard) | i <- [0..8], Just newBoard <- [place board X i]]
  | player == O = minimum [(fst (minimax newBoard X), Just newBoard) | i <- [0..8], Just newBoard <- [place board O i]]


-- Utility functions

readInt :: String -> Maybe Int
readInt s = case reads s of
              [(x,"")] -> Just x
              _ -> Nothing

readMove :: IO Int
readMove = do
  putStr "Enter move (0-8): "
  hFlush stdout
  input <- getLine
  case readInt input of
    Just move | move `elem` [0..8] -> return move
    _ -> readMove

printBoard :: Board -> IO ()
printBoard (xb, ob) = putStrLn $ unlines (intersperse divider [intersperse '|' [symbol (mask .&. (xb .|. ob)) | mask <- masks j] | j <- [0, 3, 6]])
  where
    symbol 0 = ' '
    symbol m = if m .&. xb /= 0 then 'X'  else 'O'
    masks j = [1 `shiftL` (j + i) | i <- [0..2]]
    divider = replicate 6 '-'

-- Main game loop

main :: IO ()
main = do
  putStrLn "Welcome to tic-tac-toe!"
  putStrLn "You are X, and the computer is O."
  putStrLn "Enter a number between 0 and 8 to make your move."
  playGame emptyBoard X

playGame :: Board -> Player -> IO ()
playGame board player = do
  printBoard board
  case winner board of
    Just X -> putStrLn "You win!"
    Just O -> putStrLn "Computer wins!"
    Nothing -> case player of
      X -> do
        move <- readMove
        case place board X move of
          Just newBoard -> playGame newBoard O
          Nothing -> do
            putStrLn "That square is already occupied."
            playGame board X
      O -> do
        case minimax board O of
          (score, Just newBoard) -> playGame newBoard X
          (score, Nothing) -> putStrLn "Game ends in a tie."
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Your code is good and concise, my suggestions are:

In the winner function:

winner :: Board -> Maybe Player
winner (xb, ob)
  | any (\mask -> (mask .&. xb) == mask) winningMasks = Just X -- X wins
  | any (\mask -> (mask .&. ob) == mask) winningMasks = Just O -- O wins
  | otherwise = Nothing -- the game is not over yet

You have repetition, you can write a small helper function playerWins board player -> bool and use it twice.


In the minimax function:

minimax :: Board -> Player -> (Score, Maybe Board)
minimax board player
  | winner board == Just X = (XWins, Nothing)
  | winner board == Just O = (OWins, Nothing)
  | popCount (fst board .|. snd board) == 9 = (Tie, Nothing)
  | player == X = maximum [(fst (minimax newBoard O), Just newBoard) | i <- [0..8], Just newBoard <- [place board X i]]
  | player == O = minimum [(fst (minimax newBoard X), Just newBoard) | i <- [0..8], Just newBoard <- [place board O i]]

You also have some repetition, but most importantly the concept that all possible moves must be explored is not evident, so I suggest the helper function allPossibleMoves board = [newBoard | i <- [0..8], Just newBoard <- [place board O i] ] to reduce duplication, lower cognitive load and make this fact about the minimax algorithm self-apparent.


Regarding minimax, I think that the score should be a number rather than a custom type to allow expanding to games where you cannot see until the end and as such must use heuristics. I think that your current system of a type for the score is incompatible with this extension.


I would replace printBoard :: Board -> IO () with showBoard :: Board -> String to make it easier to test, you can call print in the main function with the result of showBoard, remember to try to interact with the outside world in as few places as possible to improve testability. On the topic of that function, it looks overcomplicated to be a single function, so try to divide it into two parts (I did not understand it enough to refactor it myself).

I would have done converting to string like this:

  • boardToArray: to go from bits to an array
  • showBoardArray: to go from an array to a string

Given that you use a bitmask for the board rather than a more high-level representation, you should add comments explaning how to read to and from the data structure, especially when binary masks like these are present: winningMasks = [0o7, 0o70, 0o700, 0o111, 0o222, 0o444, 0o421, 0o124], also if you used binary masks for fun and learning it is ok, but the performance boost from them is not really needed and a normal data-structure would be ok.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.