# Day 9: Tic tac toe

Who didn't play Tic tac toe with his friends? :)

## What to expect

Today we will implement tic tac toe game in Nim, with 2 modes

• Human vs Human
• Human vs AI

## Implementation

So, let's get it. The winner in the game is the first one who manages to get 3 cells on the board to be the same in the same column or row or diagonally first.

### imports

``````import sequtils, tables, strutils, strformat, random, os, parseopt2

randomize()
``````

### Constraints and objects

As the game allow turns we should have a way to keep track of the next player

``````let NEXT_PLAYER = {"X":"O", "O":"X"}.toTable
``````

Here we use a table to tell us the next player

#### Board

``````type
Board = ref object of RootObj
list: seq[string]
``````

Here we define a simple class representing the board

• list is a sequence representing the cells `maybe cells is a better name`
• please note list is just a sequenece of elements `0 1 2 3 4 5 6 7 8` but we visualize it as
``````0 1 2
3 4 5
6 7 9
``````

instead of using a 2d array for the sake of simplicity

``````let WINS = @[ @[0,1,2], @[3,4,5], @[6,7,8], @[0, 3, 6], @[1,4,7], @[2,5,8], @[0,4,8], @[2,4,6] ]
``````

We talked `WIN` patterns cells in the same row or the same column or in same diagonal

``````proc newBoard(): Board =
var b = Board()
b.list = @["0", "1", "2", "3", "4", "5", "6", "7", "8"]
return b
``````

this is the initializer of the board and sets the cell value to the string represention of its index

##### Winning
``````proc done(this: Board): (bool, string) =
for w in WINS:
if this.list[w] == this.list[w] and this.list[w]  == this.list[w]:
if this.list[w] == "X":
return (true, "X")
elif this.list[w] == "O":
return (true, "O")
if all(this.list, proc(x:string):bool = x in @["O", "X"]) == true:
return (true, "tie")
else:
return (false, "going")
``````

Here we check for the state of the game and the winner if all of the item in `WIN` patterns are the same

``````proc `\$`(this:Board): string =
let rows: seq[seq[string]] = @[this.list[0..2], this.list[3..5], this.list[6..8]]
for row  in rows:
for cell in row:
stdout.write(cell & " | ")
echo("\n--------------")
``````

Here we have the string representation of the board so we can show it as 3x3 grid in a lovely way

``````proc emptySpots(this:Board):seq[int] =
var emptyindices = newSeq[int]()
for i in this.list:
if i.isDigit():
return emptyindices
``````

Here we have a simple helper function that returns the empty spots indices `the spots that doesn't have X or O in it`, remember all the cells are initialized to the string representation of their indices.

#### Game

``````type
Game = ref object of RootObj
currentPlayer*: string
board*: Board
aiPlayer*: string
difficulty*: int

proc newGame(aiPlayer:string="", difficulty:int=9): Game =
var
game = new Game

game.board = newBoard()
game.currentPlayer = "X"
game.aiPlayer = aiPlayer
game.difficulty = difficulty

return game
# 0 1 2
# 3 4 5
# 6 7 8
``````

Here we have another object representing the game and the players and the difficulty and wether it has an AI player or not and who is the current player

• difficulty is only logical in case of AI, it means when does the AI start calculating moves and considering scenarios, 9 is the hardest, 0 is the easiest.
``````proc changePlayer(this:Game) : void =
this.currentPlayer = NEXT_PLAYER[this.currentPlayer]
``````

Simple procedure to switch turns between players

#### Start the game

``````
proc startGame*(this:Game): void=
while true:
echo this.board
if this.aiPlayer != this.currentPlayer:
stdout.write("Enter move: ")
this.board.list[parseInt(\$move)] = this.currentPlayer
this.change_player()
let (done, winner) = this.board.done()

if done == true:
echo this.board
if winner == "tie":
echo("TIE")
else:
echo("WINNER IS :", winner )
break

``````

Here if we don't have `aiPlayer` if not set it's just a game with 2 humans switching turns and checking for the winner after each move

### Minmax and AI support

Minmax is an algorithm mainly used to predict the possible moves in the future and how to minimize the losses and maximize the chances of winning

``````
type
Move = tuple[score:int, idx:int]
``````

We need a type Move on a certain idx to represent if it's a good/bad move `depending on the score`

• good means minimizing chances of the human to win or making AI win => high score +10
• bad means maximizing chances of the human to win or making AI lose => low score -10

So let's say we are in this situation

``````O X X
X 4 5
X O O
``````

And it's `AI turn` we have two possible moves (4 or 5)

``````O X X
X 4 O
X O O
``````

this move (to 5) is clearly wrong because the next move to human will allow him to complete the diagonal (2, 4, 6) So this is a bad move we give it score -10 or

``````O X X
X O 5
X O O
``````

this move (to 4) minimizes the losses (leads to a TIE instead of making human wins) so we give it a higher score

``````proc getBestMove(this: Game, board: Board, player:string): Move =
let (done, winner) = board.done()
# determine the score of the move by checking where does it lead to a win or loss.
if done == true:
if winner ==  this.aiPlayer:
return (score:10, idx:0)
elif winner != "tie": #human
return (score:(-10), idx:0)
else:
return (score:0, idx:0)

let empty_spots = board.empty_spots()
var moves = newSeq[Move]()
for idx in empty_spots:
# we calculate more new trees depending on the current situation and see where the upcoming moves lead
var newboard = newBoard()

newboard.list = map(board.list, proc(x:string):string=x)
newboard.list[idx] = player
let score = this.getBestMove(newboard, NEXT_PLAYER[player]).score
let idx = idx
let move = (score:score, idx:idx)

if player == this.aiPlayer:
return max(moves)
# var bestScore = -1000
# var bestMove: Move
# for m in moves:
#   if m.score > bestScore:
#     bestMove = m
#     bestScore = m.score
# return bestMove
else:
return min(moves)
# var bestScore = 1000
# var bestMove: Move
# for m in moves:
#   if m.score < bestScore:
#     bestMove = m
#     bestScore = m.score
# return bestMove

``````

Here we have a highly annotated `getBestMove` procedure to calculate recursively the best move for us

Now our startGame should look like this

``````proc startGame*(this:Game): void=
while true:
##old code

## AI check
else:
if this.currentPlayer == this.aiPlayer:
let emptyspots = this.board.emptySpots()
if len(emptyspots) <= this.difficulty:
echo("AI MOVE..")
let move = this.getbestmove(this.board, this.aiPlayer)
this.board.list[move.idx] = this.aiPlayer
else:
echo("RANDOM GUESS")
this.board.list[emptyspots.rand()] = this.aiPlayer

## oldcode

``````

Here we allow the game to use difficulty which means when does the AI starts calculating the moves and making the tree? from the beginning 9 cells left or when there're 4 cells left? you can set it the way you want it, and until u reach the starting difficulty situation AI will use random guesses (from the available `emptyspots`) instead of calculating

### CLI entry

``````proc writeHelp() =
echo """
TicTacToe 0.1.0 (MinMax version)
Allowed arguments:
-h | --help         : show help
-a | --ai           : AI player [X or O]
-l | --difficulty   : destination to stow to
"""

proc cli*() =
var
aiplayer = ""
difficulty = 9

for kind, key, val in getopt():
case kind
of cmdLongOption, cmdShortOption:
case key
of "help", "h":
writeHelp()
# quit()
of "aiplayer", "a":
echo "AIPLAYER: " & val
aiplayer = val
of "level", "l": difficulty = parseInt(val)
else: