The board
For flexibility, we define constants for the row and column size of the board, length of a winning sequence, and search depth for the game tree:
rows :: Int rows = 6
cols :: Int cols = 7
win :: Int win = 4
depth :: Int depth = 6
The board itself is represented as a list of rows, where each row is a list of player values, subject to the above row and column sizes:
type Board = [Row]
type Row = [Player]
In turn, a player value is either a nought, a blank, or a cross, with a blank representing a position on the board that is not yet occupied:
data Player = O | B | X
deriving (Ord, Eq, Show)
For example, here is a typical board:
test :: Board test = [[B,B,B,B,B,B,B],
[B,B,B,B,B,B,B],
[B,B,B,B,B,B,B],
[B,B,B,X,X,B,B],
[B,B,O,O,X,B,B],
[B,O,O,X,X,X,O]]
The user interface
The following code displays a board on the screen:
2
showBoard :: Board -> IO () showBoard b =
putStrLn (unlines (map showRow b ++ [line] ++ [nums]))
where
showRow = map showPlayer
line = replicate cols ’-’
nums = take cols [’0’..]
showPlayer :: Player -> Char showPlayer O = ’O’ showPlayer B = ’.’ showPlayer X = ’X’
For example, showBoard test gives the following output:
....... ....... ....... ...XX.. ..OOX.. .OOXXXO ------- 0123456
Exercise
Write a Haskell program
main :: IO ()
that allows a human player to play connect four against the computer, using game trees and the minimax algorithm (as explained in the lectures) to im- plement the computer player. Your solution should aim to be independent of the precise values of the constants row, cols, win and depth.
Hint: construct your program from the bottom-up, starting by defining a number of utility functions on rows and boards, and only then proceeding to think about game trees, minimax, and the user-interface.
3