Let's build an Othello AI - part 3A - Artificial Intelligence (16.4.2017)

In the series:

Part 3A - Artificial Intelligence

Now, the moment you may have been waiting for - the AI feature!

Before we can implement the AI itself, we need to add a few more types and definitions; the AI needs to know about the concept of a score for a board and the player. The scores also need to be comparable - and this is where we implement the Ord class for BoardScores, meaning that all scores have a definite total order. This is defined as follows (add after type definitions but before rest of the code):

-- Score type for a board score. A board is Win, if it is a certain win for a given player, and Lose if it is a certain loss. If it is neither, it is Indeterminate, with a score denoting its "goodness" data BoardScore = Win | Indeterminate UnitScore | Lose deriving (Eq, Show) -- Define a order for a board score. For least complexity, define ordering as a set of comparative properties between different scores; this will be automatically used to implement other comparative operators instance Ord BoardScore where (<=) :: BoardScore -> BoardScore -> Bool (<=) Lose _ = True -- Lose is the smallest and definitely equal (<=) (Indeterminate _) Lose = False -- Indeterminate is never less or equal to a win (<=) (Indeterminate _) Win = True -- Indeterminate is always less than a win (<=) (Indeterminate a) (Indeterminate b) = (a <= b) -- For two indeterminates, their respective ordering depends on their scores (<=) Win Win = True -- Win is equal with a win (<=) Win _ = False -- Otherwise, Win beats all

We also need to set a few constants for the properties of AI

-- Which turns the AI plays? Empty list means humans play both turns. It is also permissible to have the AI play both turns aiPlays :: [Player] aiPlays = [Blue] -- How many turns the AI is approximately allowed to analyze? -- The time taken for a search should be approximately constant; larger the amount, more turns the AI can take to determine the best option, and therefore more time is spent. aiSearchDepth = 3000

Now, let's first get to the AI. You remember the move processing functionality we added the last time, but left unused? Now's the time to use them. Add this preferably to right under the applyMove function (leaving an empty row between!)

-- Get's the AI's choice of a move getAIsMove :: Board -> Player -> [Coordinate] getAIsMove board main_player = case (moves) of [] -> [] _ -> getBestMove moves where moves = movesAvailableForPlayer board main_player getBestMove mvs = fst (maximumBy (\a b -> compare (snd a) (snd b)) $ (map (\move -> (move, (getNestedScore (applyMove board main_player move) (opposingPlayer main_player) (aiSearchDepth - (length moves)) False))) mvs)) -- Calculates a nested score. This is a classic Minimax algorithm for decisionmaking getNestedScore :: Board -> Player -> Int -> Bool -> BoardScore getNestedScore brd plr depth_allowed maximizing -- If this is a game-over scenario, or we are out of moves, the terminal score is a must | gameAtEnd || (futureNestedScore < 0) = terminalScore -- If we cannot move forward, change the turn and look from the other party's viewpoint | (null currentPlrMoves) = getNestedScore brd (opposingPlayer plr) (futureNestedScore) (not maximizing) -- If we want to maximize our score, get the maximum score available | maximizing = maximum (Lose:(map (\move -> getNestedScore (applyMove brd plr move) (opposingPlayer plr) (futureNestedScore) (not maximizing)) currentPlrMoves)) -- On the other hand, if we want the least good score for the player whose score we should minimize, calculate that here | otherwise = minimum (Win:(map (\move -> getNestedScore (applyMove brd plr move) (opposingPlayer plr) (futureNestedScore) (not maximizing)) currentPlrMoves)) where futureNestedScore = if (length currentPlrMoves == 0) then (depth_allowed-1) else (depth_allowed - (length currentPlrMoves)) `div` (length currentPlrMoves) -- Innovate - subtract the amount of further turns, and then allocate the rest for nested processing terminalScore -- Terminal score for our main player; this way, minimization and maximization always have a reasonable result -- Endgame, at this point we know the wins and the losses | gameAtEnd, redCount /= blueCount = if (main_player == Red && (redCount > blueCount)) then Win else Lose | otherwise = Indeterminate ((if (main_player == Red) then 1 else -1) * (redCount-blueCount)) (redCount,blueCount) = pieceCount brd -- Is this game at its end? Enforce that gameAtEnd = (null (currentPlrMoves)) && (null (opposingPlrMoves)) && plr == main_player -- Moves for both parties currentPlrMoves = movesAvailableForPlayer brd plr opposingPlrMoves = movesAvailableForPlayer brd (opposingPlayer plr)

That's the AI in its gist. What that code implements is a slightly optimized Minimax algorithm; it tries to maximize our score, while minimizing the opponents score. If it is not possible to advance any further from some point, a terminal score is calculated, giving a comparable value to the score. Optimization comes in by not having a simple depth criteria, but actually taking account the amount of possibilities per turn, enabling turns with just a few choices to be more thoroughly processed.

The final part comes in the next post, where we will actually bind all we've created to an user interface and a timer. 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

FINAL POST: Part 3B