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

In the series:

- Introduction
- Structures and Basic Functionality
- Advanced functions, and UI Scaffolding
- AI
- Wrapping up and adding interactivity

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)
}
```

## Functionality

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**

**NEXT POST: Part 2B**

Show comments on this page