Hari's Corner
Humour, comics, tech, law, software, reviews, essays, articles and HOWTOs intermingled with random philosophy now and thenTic Tac Toe (a.k.a Noughts and Crosses) in Haskell
Filed under:
Tutorials and HOWTOs by
Hari
Posted on Fri, Aug 30, 2013 at 10:21 IST (last updated: Mon, Sep 16, 2013 @ 14:33 IST)
| In this series | < Previous | Next > |
A couple of years ago, I had written a C++ version of an AI playable Tic Tac Toe program. I have now written a similar version in Haskell, which uses the same kind of logic as the C++ one. I thought it would be kind of challenging to try a program like this in Haskell, but it turned out to be quite easy, as a matter of fact. I wrote this as a way to revisit Haskell while trying a non-trivial exercise.
I am sure there are better Tic Tac Toe programs/algorithms implemented in Haskell that illustrate more advanced techniques than the ones I have used, but still, I think mine would be a bit easier to understand for a newbie and is perfectly adequate for a simple game like this.
Simply the algorithm I used for the AI is this:
- Check for any winning move and make it.
- Check for opponent winning move and block it.
- Check if the center of the board is free and occupy it.
- Check if any one of the corners are free and occupy it.
- Occupy any other free cell.
That's about it. This makes the game unwinnable from a human player point of view (which is what most TicTacToe AIs implement). The best result that can be achieved is a draw. Pretty boring game, but still... In fact, the game can be won by the human player as pointed out in the comment by Jonathan below.
Without further ado, here's the code:
-- Tic tac toe in Haskell -- By V.Harishankar (C) 2013 -- board is a list containing the elements -- e0, e1, e2 -- e3, e4, e5 -- e6, e7, e8 -- and each can store either 0 (blank) 1 (cross) or 2 (nought) -- the computer move - return the new board after -- playing the move computermove :: Int -> [ Int ] -> [ Int ] -- the player move - return the new board after -- playing the move playermove :: Int -> Int -> [ Int ] -> [ Int ] -- format the board for terminal display printboard :: [ Int ] -> String -- representation of the nought or cross for -- terminal display rep :: Int -> String -- statement to display on winning/draw winstatement :: Int -> String -- check if the player (nought or cross) has won -- and return a boolean checkifwon :: Int -> [ Int ] -> Bool -- check if the game is over (i.e. all the moves) -- are completed checkgameover :: [ Int ] -> Bool -- function for the gameplay gameplay :: Int -> [ Int ] -> IO () -- representation of nought and cross in the list rep 1 = " X " rep (-1) = " O " rep n = " " -- winning/game draw statements winstatement 1 = "Cross has won!" winstatement (-1) = "Noughts has won!" winstatement n = "Game drawn..." -- draw the board in its state printboard board = rep (head board) ++ "|" ++ rep (board !! 1) ++ "|" ++ rep (board !! 2) ++ "\n" ++ "---+---+---" ++ "\n" ++ rep (board !! 3) ++ "|" ++ rep (board !! 4) ++ "|" ++ rep (board !! 5) ++ "\n" ++ "---+---+---" ++ "\n" ++ rep (board !! 6) ++ "|" ++ rep (board !! 7) ++ "|" ++ rep (board !! 8) ++ "\n" -- check if the game is over checkgameover board -- if zero is present in any position, then board is not fully played yet | 0 `elem` board = False | otherwise = True -- check if the game is won checkifwon ch board -- check the rows | head board == ch && board !! 1 == ch && board !! 2 == ch = True | board !! 3 == ch && board !! 4 == ch && board !! 5 == ch = True | board !! 6 == ch && board !! 7 == ch && board !! 8 == ch = True -- check the cols | head board == ch && board !! 3 == ch && board !! 6 == ch = True | board !! 1 == ch && board !! 4 == ch && board !! 7 == ch = True | board !! 2 == ch && board !! 5 == ch && board !! 8 == ch = True -- check cross \ | head board == ch && board !! 4 == ch && board !! 8 == ch = True -- check cross / | board !! 2 == ch && board !! 4 == ch && board !! 6 == ch = True -- not won | otherwise = False -- player move playermove 0 ch board -- if the position is free then play | head board == 0 = ch:tail board -- else allow the computer to play on behalf of the player | otherwise = computermove ch board playermove 8 ch board -- if the position is free then play | board !! 8 == 0 = take 8 board ++ [ ch ] -- else allow the computer to play on behalf of the player | otherwise = computermove ch board playermove n ch board -- if the move is invalid then allow the computer to play | n < 0 || n > 8 = computermove ch board -- if the position is free then play | board !! n == 0 = take n board ++ [ ch ] ++ drop (n+1) board -- else allow the computer to play on behalf of the player | otherwise = computermove ch board -- computer moves computermove ch board -- if in a winning position then win -- examine first row | head board == ch && board !! 1 == ch && board !! 2 == 0 = take 2 board ++ [ ch ] ++ drop 3 board | head board == ch && board !! 1 == 0 && board !! 2 == ch = [head board] ++ [ ch ] ++ drop 2 board | head board == 0 && board !! 1 == ch && board !! 2 == ch = ch:tail board -- examine second row | board !! 3 == ch && board !! 4 == ch && board !! 5 == 0 = take 5 board ++ [ ch ] ++ drop 6 board | board !! 3 == ch && board !! 4 == 0 && board !! 5 == ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 3 == 0 && board !! 4 == ch && board !! 5 == ch = take 3 board ++ [ ch ] ++ drop 4 board -- examine third row | board !! 6 == ch && board !! 7 == ch && board !! 8 == 0 = take 8 board ++ [ ch ] | board !! 6 == ch && board !! 7 == 0 && board !! 8 == ch = take 7 board ++ [ ch ] ++ drop 8 board | board !! 6 == 0 && board !! 7 == ch && board !! 8 == ch = take 6 board ++ [ ch ] ++ drop 7 board -- examine first col | head board == ch && board !! 3 == ch && board !! 6 == 0 = take 6 board ++ [ ch ] ++ drop 7 board | head board == ch && board !! 3 == 0 && board !! 6 == ch = take 3 board ++ [ ch ] ++ drop 4 board | head board == 0 && board !! 3 == ch && board !! 6 == ch = ch:tail board -- examine second col | board !! 1 == ch && board !! 4 == ch && board !! 7 == 0 = take 7 board ++ [ ch ] ++ drop 8 board | board !! 1 == ch && board !! 4 == 0 && board !! 7 == ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 1 == 0 && board !! 4 == ch && board !! 7 == ch = [head board] ++ [ ch ] ++ drop 2 board -- examine third col | board !! 2 == ch && board !! 5 == ch && board !! 8 == 0 = take 8 board ++ [ ch ] | board !! 2 == ch && board !! 5 == 0 && board !! 8 == ch = take 5 board ++ [ ch ] ++ drop 6 board | board !! 2 == 0 && board !! 5 == ch && board !! 8 == ch = take 2 board ++ [ ch ] ++ drop 3 board -- examine the cross \ | head board == ch && board !! 4 == ch && board !! 8 == 0 = take 8 board ++ [ ch ] | head board == ch && board !! 4 == 0 && board !! 8 == ch = take 4 board ++ [ ch ] ++ drop 5 board | head board == 0 && board !! 4 == ch && board !! 8 == ch = ch:tail board -- examine the cross / | board !! 2 == ch && board !! 4 == ch && board !! 6 == 0 = take 6 board ++ [ ch ] ++ drop 7 board | board !! 2 == ch && board !! 4 == 0 && board !! 6 == ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 2 == 0 && board !! 4 == ch && board !! 6 == ch = take 2 board ++ [ ch ] ++ drop 3 board -- block opponent winning positions -- examine first row | head board == -ch && board !! 1 == -ch && board !! 2 == 0 = take 2 board ++ [ ch ] ++ drop 3 board | head board == -ch && board !! 1 == 0 && board !! 2 == -ch = [head board] ++ [ ch ] ++ drop 2 board | head board == 0 && board !! 1 == -ch && board !! 2 == -ch = ch:tail board -- examine second row | board !! 3 == -ch && board !! 4 == -ch && board !! 5 == 0 = take 5 board ++ [ ch ] ++ drop 6 board | board !! 3 == -ch && board !! 4 == 0 && board !! 5 == -ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 3 == 0 && board !! 4 == -ch && board !! 5 == -ch = take 3 board ++ [ ch ] ++ drop 4 board -- examine third row | board !! 6 == -ch && board !! 7 == -ch && board !! 8 == 0 = take 8 board ++ [ ch ] | board !! 6 == -ch && board !! 7 == 0 && board !! 8 == -ch = take 7 board ++ [ ch ] ++ drop 8 board | board !! 6 == 0 && board !! 7 == -ch && board !! 8 == -ch = take 6 board ++ [ ch ] ++ drop 7 board -- examine first col | head board == -ch && board !! 3 == -ch && board !! 6 == 0 = take 6 board ++ [ ch ] ++ drop 7 board | head board == -ch && board !! 3 == 0 && board !! 6 == -ch = take 3 board ++ [ ch ] ++ drop 4 board | head board == 0 && board !! 3 == -ch && board !! 6 == -ch = ch:tail board -- examine second col | board !! 1 == -ch && board !! 4 == -ch && board !! 7 == 0 = take 7 board ++ [ ch ] ++ drop 8 board | board !! 1 == -ch && board !! 4 == 0 && board !! 7 == -ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 1 == 0 && board !! 4 == -ch && board !! 7 == -ch = [head board] ++ [ ch ] ++ drop 2 board -- examine third col | board !! 2 == -ch && board !! 5 == -ch && board !! 8 == 0 = take 8 board ++ [ ch ] | board !! 2 == -ch && board !! 5 == 0 && board !! 8 == -ch = take 5 board ++ [ ch ] ++ drop 6 board | board !! 2 == 0 && board !! 5 == -ch && board !! 8 == -ch = take 2 board ++ [ ch ] ++ drop 3 board -- examine the cross \ | head board == -ch && board !! 4 == -ch && board !! 8 == 0 = take 8 board ++ [ ch ] | head board == -ch && board !! 4 == 0 && board !! 8 == -ch = take 4 board ++ [ ch ] ++ drop 5 board | head board == 0 && board !! 4 == -ch && board !! 8 == -ch = ch:tail board -- examine the cross / | board !! 2 == -ch && board !! 4 == -ch && board !! 6 == 0 = take 6 board ++ [ ch ] ++ drop 7 board | board !! 2 == -ch && board !! 4 == 0 && board !! 6 == -ch = take 4 board ++ [ ch ] ++ drop 5 board | board !! 2 == 0 && board !! 4 == -ch && board !! 6 == -ch = take 2 board ++ [ ch ] ++ drop 3 board -- if center is blank - choose center of the board | board !! 4 == 0 = take 4 board ++ [ ch ] ++ drop 5 board -- otherwise choose one of the corners of the board | head board == 0 = ch:tail board | board !! 2 == 0 = take 2 board ++ [ ch ] ++ drop 3 board | board !! 6 == 0 = take 6 board ++ [ ch ] ++ drop 7 board | board !! 8 == 0 = take 8 board ++ [ ch ] -- otherwise choose one of the sides of the board | board !! 1 == 0 = [head board] ++ [ ch ] ++ drop 2 board | board !! 3 == 0 = take 3 board ++ [ ch ] ++ drop 4 board | board !! 5 == 0 = take 5 board ++ [ ch ] ++ drop 6 board | board !! 7 == 0 = take 7 board ++ [ ch ] ++ drop 8 board -- if nothing is possible return the board as is | otherwise = board -- main gameplay function gameplay ch board = -- if it is the cross player then the human player should -- make a move if ch == 1 then do putStrLn "Your move. Make an invalid move to allow the computer to choose a cell." putStrLn "Enter the cell# to play (1..9)" cellno <- getLine -- make the player move let newboard = playermove (read cellno - 1) ch board -- display the board putStrLn $ printboard newboard -- if game is over if checkgameover newboard then -- if the player has won display the win statement or -- the drawn statement putStrLn $ winstatement (if checkifwon ch newboard then ch else 0) -- game is not over else -- if the player has won display the win statement -- else continue gameplay if checkifwon ch newboard then putStrLn $ winstatement ch else gameplay (-ch) newboard -- if it is the noughts player let the computer make the move else do let newboard = computermove ch board putStrLn "Computer Move: " putStrLn $ printboard newboard -- check if game is over if checkgameover newboard then -- if the player has won display the won statement -- else display the draw statement putStrLn $ winstatement (if checkifwon ch newboard then ch else 0) -- game is not over else -- if the player has won display the won statement -- else continue gameplay if checkifwon ch newboard then putStrLn $ winstatement ch else gameplay (-ch) newboard main = do -- initialize the board let board = [0, 0, 0, 0, 0, 0, 0, 0, 0] putStrLn "Welcome to Noughts and Crosses" putStrLn "" putStrLn $ printboard board putStrLn "Do you wish to start first (cross) [Y/N]? " choice <- getLine if choice == "Y" || choice == "y" then gameplay 1 board else gameplay (-1) board
In this series
- Musings on Functional Programming and Haskell
- Tic Tac Toe (a.k.a Noughts and Crosses) in Haskell
- Five tips about Functional Programming for a Haskell newbie from a Haskell newbie
- My Haskell article was linked at reddit
- Why learning Functional Programming and Haskell in particular can be hard
- Something about Haskell I wanted to share
- So on to learning Haskell
Comments closed
The blog owner has closed further commenting on this entry.
2 comment(s)
Comment by Jonathan S (visitor) on Sun, Sep 8, 2013 @ 21:12 IST #
Comment by Hari (blog owner) on Sun, Sep 8, 2013 @ 22:21 IST #