Let's build an Othello AI - part 2A - Data Structures and Basic Functions (16.4.2017)

In the series:

Within the previous post, we left at the point where we had a functioning scaffold. I also hope you took a peek at the further reading section, particularly at the e-books teaching Haskell.

This post will be split into two separate pages due to the breadth of stuff required. To today's topic:

Part 2A - Data Structures

Where we are at?

Right now, if you look at the main source file (src/Main.hs in the project folder), you should find something like this

module Main where main :: IO () main = do putStrLn "hello world"

This is the program we ran in the previous part. It doesn't do much of interest: it declares a Main module, where there is a main function returning an IO monad consisting of an output to the console. IO monads are Haskell's way of allowing interaction and side effects to the world outside; we need not to be concerned about them in our project though.

Adding our structures

Let's start by ripping whole that out, and adding this instead. All following segments can be pasted in the file in the order given.

{-#LANGUAGE InstanceSigs#-} -- Permit type declarations in instance definitions module Main where -- Fixed-size arrays indexed by an Ix instance import Data.Array -- Haskell doesn't have a NULL type per se, so Maybe can be used to describe a result that may not have a definite value import Data.Maybe -- Folds/recursive combining of some foldable entities (e.g lists, sets) to one import Data.Foldable -- Our graphics library import Graphics.Gloss -- We need access to events, so we use the game mode. import Graphics.Gloss.Interface.Pure.Game

That's a whole bunch of things! Do not despair though; that bunch of lines simply declares the start of our module, and the prerequisite dependencies. It also switches on a certain special language feature available in GHC, which will also be used further down this post.

Under that, let's next declare a few unit types. We shall use type statements for that, as to declare some type identifier to be equivalent to some other type. As so:

-- In what type board scores are (described later) type UnitScore = Int -- How are coordinates defined? type Coordinate = (Int, Int)

Right under that, let's define our board and players. We will use a few more complex datatypes; data statements create a wholly new datatype, which in this case consists of the values enumerated. BoardPosition in addition can contain a Player when placed - an empty spot doesn't have such a value. We also utilize a Haskell array library to have a fixed-size board that can be accessed directly using an index; in this case, a tuple containing coordinates. Not all datatypes can be used as an index; they must be instances of a special Ix class, which requires that there is a suitable mapping between a range of objects and integers.

-- A player is either a Red or a Blue. Derive default comparison and show data Player = Red | Blue deriving (Eq, Show) -- Define the state of each spot on a board; either it is empty, or it may have a player's button placed on it. data BoardPosition = Empty | Placed Player deriving (Eq, Show) -- Define a simple model for a board; an array indexed by 2-dimensional coordinates and containing board positions. data Board = Board { -- Implicitly create a function called 'boardGrid', which extracts the grid array itself from a Board value boardGrid :: Array Coordinate (BoardPosition) }


Next, let's define a few functions and their prerequisite constants.

First, constants:

-- Grid size gameGridSize :: Int gameGridSize = 8 -- Starting pieces, where appropriate. First coordinate is X, second Y - both indexes start from zero, so (0,0) would be the upmost left corner, while (7,7) would be the lowest on the right startPieces :: (Int, Int) -> BoardPosition startPieces (3,3) = Placed Red startPieces (4,4) = Placed Red startPieces (3,4) = Placed Blue startPieces (4,3) = Placed Blue -- If no other coordinate matches, it is an empty square. startPieces _ = Empty

and then, basic board handling functions:

-- Returns a count of pieces on a board - red first, blue second pieceCount :: Board -> (Int, Int) pieceCount board = foldr (counter) (0,0) (elems (boardGrid board)) -- Recursively add the score together position by position where -- A function to define how the total score changes per position found counter :: BoardPosition -> (Int, Int) -> (Int, Int) counter pos (red, blue) = case (pos) of Empty -> (red, blue) -- No change Placed Red -> (red+1, blue) -- One more for red Placed Blue -> (red, blue+1) -- One more for blue -- Calculate the winner using the traditional rules - who has most pieces, wins. If we can not determine one, return Nothing winningPlayer :: Board -> Maybe Player winningPlayer board | draw = Nothing | otherwise = if redCount > blueCount then Just Red else Just Blue where draw = (blueCount == redCount) (redCount, blueCount) = pieceCount board -- Function that gets a piece from a coordinate pieceAtCoordinate :: Board -> Coordinate -> BoardPosition pieceAtCoordinate board coordinate = (boardGrid board) ! coordinate -- Function that checks if a given coordinate is within the given board coordinateInBounds :: Board -> Coordinate -> Bool coordinateInBounds board coord = inRange (bounds (boardGrid board)) coord -- Define an initial board initialBoard = Board (array ((0,0), (gameGridSize-1, gameGridSize-1)) (gridComprehension (\point -> (point, startPieces point)))) -- A helper function for grid comprehension - map some function over the game grid gridComprehension :: (Coordinate -> x) -> [x] gridComprehension func = [(func (a,b)) | a <- [0..gameGridSize-1], b <- [0..gameGridSize-1]] -- Definition of the opposing player for a given player opposingPlayer :: Player -> Player opposingPlayer Red = Blue opposingPlayer Blue = Red

Still following? We've now defined some basic board functions; in the next post, we'll complete part 2 by adding UI rendering, dependencies, and testing that what we've added builds so far.

Thanks for your time! Be sure to comment if there's anything you'd like to say or ask, as I can't possibly know what to cover at the first try :D

The full source is available also on GitHub