## Coding challenge: Tic-tac-toe

This is a coding challenge to build a “computer player” which is able to play tic-tac-toe on a board varying from 3×3 to 10×10 in size. In order to win, the player has to put either “X” or “O” on any horizontal, vertical or diagonal line across the entire board.
I drew reference from this website for the basic structure of the code. On top of that, I designed a strategy for the computer player that can be implemented regardless of the board size.

Here is a simple explanation of the computer player’s strategy:

Click here to watch a short video of the game in action! (In this game, the player is “X” and the computer is “O”.)

Overall, I’m quite happy with the results considering this is the first game I have ever programmed. The computer player is at least able to end the game with a tie (which in fact is almost always the case for boards larger than a 3×3).

When I first received this challenge, it sounded like a mission impossible given I have only been learning Python for a few months. However, with the help of online resources and some creativity and persistence, I tackled one small problem after another and eventually completed the whole game. I learnt a lot from this challenge and it further confirmed my belief that nothing is impossible as long as you’re persistent.

Here is the code written in Python, please feel free to leave your comments on how to improve it.

##### 1. Setting up the basic structure of the game
Generate a board which size could vary from 3 x 3 to 10 x 10.
```import random

def boardsize():
global size

size = random.randint(3, 10)
print "You will play on a %d by %d board" % (size, size)

```
Visualizing the board.
X and Y coordinates are displayed so it’s easier for players to input their intended moves.
```def drawBoard(board):
xcoord = []
for ii in range(size):
xcoord.append(str(ii))

print " ", xcoord
for i in range(size):
print i, theBoard[i]
print "-------------------------------------------------"
```
The player is asked to choose which letter he/she wants to be.
```def inputPlayerLetter():
letter = ''
while not (letter == 'X' or letter == 'O'):
print "Do you want to be X or O?"
letter = raw_input().upper()

# Returns the player's letter as the 1st element and the computer's letter as the 2nd element
if letter == 'X':
return ['X', 'O']
else:
return ['O', 'X']
```
Randomly chooses which player goes first.
```def whoGoesFirst():
if random.randint(0, 1) == 0:
return 'computer'
else:
return 'player'
```
At the end of a game, the player is asked whether he / she wants to play another round.
```def playAgain():
print "Do you want to play again? (yes or no)"
return raw_input().lower().startswith('y')
```
##### 2. Defining the game strategy
This function obtains the X and Y coordinates of the intended move and then inputs the player/computer’s letter there
```def makeMove(board, letter, move_x, move_y):
board[move_y][move_x] = letter
```
This function checks whether either player has won to determine if the game should end or continue.
```def isWinner(board, letter):
isWinner.win = 0

# Check if either player has won by having all his/her letters across a row horizontally
for i in range(size):
if board[i].count(letter) == size:
isWinner.win = 1

else:
None

# Check if either player has won by having all his/her letters across a column vertically
if isWinner.win != 1:
for ii in range(size):
cols = []

for i in range(size):
if board[i][ii] == letter:
cols.append(1)
else:
None
if sum(cols) == size:
isWinner.win = 1
break
else:
None
else:
None

'''Check if either player has won by having all his/her letters across the diagonal lines
First, check the diagonal line from upper left corner to bottom right corner'''
if isWinner.win !=1:
diag1 = []
for i in range(size):
if board[i][i] == letter:
diag1.append(1)
else:
None
if sum(diag1) == size:
isWinner.win = 1
else:
None
else:
None

# Then, check the diagonal line from upper right corner to bottom left corner
if isWinner.win !=1:
diag2 = []
for i in range(size):
if board[i][size-1-i] == letter:
diag2.append(1)
else:
None
if sum(diag2) == size:
isWinner.win = 1
else:
None
else:
None

if isWinner.win == 1:
return True
```
This function checks if the game is a tie, if so, the game is terminated.
A tie is declared if all rows, columns and diagonal lines contain at least one “X” and “O” so that there are no possible moves for either player to win.
```def isTie(board, playerLetter, computerLetter):

# First, check if each row contains at least one "X" and "O"
row_tiecheck = []
for i in board:
if playerLetter in i and computerLetter in i:
row_tiecheck.append(1)
else:
None

# Secondly, check if each column contains at least one "X" and "O"
col_tiecheck = []
for i in range(size):
col_letters = []
for ii in range(size):
col_letters.append(board[ii][i])
if playerLetter in col_letters and computerLetter in col_letters:
col_tiecheck.append(1)

# Then, check if each diagonal line contains at least one "X" and "O"
diag_tiecheck = []
diag1_letters = []
diag2_letters = []
for i in range(size):
diag1_letters.append(board[i][i])
diag2_letters.append(board[i][size-1-i])
if playerLetter in diag1_letters and computerLetter in diag1_letters:
diag_tiecheck.append(1)

if playerLetter in diag2_letters and computerLetter in diag2_letters:
diag_tiecheck.append(1)

# The game is a tie if all rows, columns and diagnal lines contain "X" and "O"
if sum(row_tiecheck) == size and sum(col_tiecheck) == size and len(diag_tiecheck) == 2:
return True
```
A duplicate of the board is made in order to test if a move causes a player to win.
```def getBoardCopy(board):
dupeBoard = []
for i in board:
dupeBoard.append(i)
return dupeBoard
```
Before any move is implemented, it is checked whether the cell to be taken up is free.
```def isSpaceFree(board, move_x, move_y):
return board[move_y][move_x] == ' '
```
This function lets the human player input his/her move according to the coordinates he/she chose.
```def getPlayerMove(board):
move_x = ' '
move_y = ' '
# The while-statement ensures player inputs valid coordinates within the board AND the coordinates are not already taken up
while move_x not in range(0, size) or move_y not in range(0, size) or not isSpaceFree(board, move_x, move_y):
move_x = int(raw_input("Enter x-coordinate of your next move: "))
move_y = int(raw_input("Enter y-coordinate of your next move: "))

return move_x, move_y
```
Now, the most exciting part.
This function helps the computer to determine its move.
```def getComputerMove(board, computerLetter):
if computerLetter == 'X':
playerLetter = 'O'
else:
playerLetter = 'X'

move_x = ' '
move_y = ' '

# First, the computer checks if it can win in the next move, if so, the computer will implement that move
for i in range(size):
for ii in range(size):
# Get a copy of the current board
copy = getBoardCopy(board)
# If a cell is free, try to put the computer's letter there
if isSpaceFree(copy, ii, i):
makeMove(copy, computerLetter, ii, i)
# If the move makes the computer win, return the X and Y coordinates in order to implement that move
if isWinner(copy, computerLetter):
move_x = ii
move_y = i
return move_x, move_y
copy[i][ii] = " "
break

else:

copy[i][ii] = " "
else:
None

'''Then, the computer checks if the human player can win in his/her next move
If so, the computer will take up that place to block the human player immediately'''
for i in range(size):
for ii in range(size):
# Similarly, a copy of the board is obtained and empty cells are checked if they can cause the human player to win
copy = getBoardCopy(board)
if isSpaceFree(copy, ii, i):
makeMove(copy, playerLetter, ii, i)
# If the cell will cause a human player to win in its next move, the computer will take the cell to block the human player
if isWinner(copy, playerLetter):
move_x = ii
move_y = i
return move_x, move_y
copy[i][ii] = " "
break

else:

copy[i][ii] = " "
else:
None

# The while-statement ensures the computer inputs valid coordinates within the board AND the cell has not been taken up
while move_x not in range(0, size) or move_y not in range(0, size):

'''If none of the cells will cause the computer or human player to win in the next move, the computer will try to make its best possible move
The strategy will be to calculate a score for each cell and take the cell that has the highest score

First, the computer will look at each row in the board and calculate 2 scores, offensive and defensive score.
Offensive score represents how likely certain coordinates will help to extend the computer's current line, if any.
A row with more of the computer's letter is regarded as more valuable in helping the computer to win
On the other hand, defensive score aims at blocking the human player's line, if any.
A row with more of the human player's line is regarded as a more imminent threat therefore a higher defensive score is assigned.'''

offensive_row = []
defensive_row = []
offensive_col = []
defensive_col = []
offensive = []
defensive = []
score = []

'''Score calculation by row
Offensive score of each cell = number of computer letters in that row
Likewise, defensive score of each cell = number of human player letters in that row
However, if that row has both computer and player letters, that row is a tie. Score of cells in that row = 0'''
for i in range(size):
for ii in range(size):
if computerLetter in board[i] and playerLetter in board[i]:
offensive_row.append(0)
defensive_row.append(0)
else:
offensive_row.append(board[i].count(computerLetter))
defensive_row.append(board[i].count(playerLetter))

#Similar scores are calculated for each columns in the board.

for ii in range(size):
temp_off_col = []
temp_def_col = []
for iii in range(size):
if board[iii][ii] == computerLetter:
temp_off_col.append(1)
elif board[iii][ii] == playerLetter:
temp_def_col.append(1)

'''If there is no player letter in that column, offensive score of that column  = no. of computer letters
Otherwise, offensive score = 0'''
if sum(temp_def_col) == 0:
offensive_col.append(sum(temp_off_col))
else:
offensive_col.append(0)
'''Likewise, if there is no computer letter in that column, defensive score of that column = no. of player letters
Otherwise, defensive score = 0'''
if sum(temp_off_col) == 0:
defensive_col.append(sum(temp_def_col))
else:
defensive_col.append(0)

# Multiply the column scores to assign the same column scores for each row
offensive_col = offensive_col*size
defensive_col = defensive_col*size

'''Score calculation by diagonal lines
First, calculate the offensive score for diagonal1 (top left to bottom right) and diagonal 2 (top right to bottom left)
If there is no player letter in that diagonal line, score of that line = no. of computer letters
Otherwise, that diagonal line is a tie hence score = 0'''
temp_off_diag1 = []
temp_off_diag2 = []

for i in range(size):
if board[i][i] == computerLetter:
temp_off_diag1.append(1)
elif board[i][i] == playerLetter:
temp_off_diag1.append(0)
for i in range(size):
if board[i][size-1-i] == computerLetter:
temp_off_diag2.append(1)
elif board[i][size-1-i] == playerLetter:
temp_off_diag2.append(0)

if not 0 in temp_off_diag1:
diag_offscore1 = sum(temp_off_diag1)
else:
diag_offscore1 = 0

if not 0 in temp_off_diag2:
diag_offscore2 = sum(temp_off_diag2)
else:
diag_offscore2 = 0

off_diag1 = *size**2
off_diag2 = *size**2
for i in range(size):
off_diag1[i*(size+1)] = diag_offscore1
off_diag2[(i+1)*(size-1)] = diag_offscore2

off_diag = [x + y for x, y in zip(off_diag1, off_diag2)]

# Calculate defensive score for each diagonal lines using the same principles above
temp_def_diag1 = []
temp_def_diag2 = []

for i in range(size):
if board[i][i] == playerLetter:
temp_def_diag1.append(1)
elif board[i][i] == computerLetter:
temp_def_diag1.append(0)

for i in range(size):
if board[i][size-1-i] == playerLetter:
temp_def_diag2.append(1)
elif board[i][size-1-i] == computerLetter:
temp_def_diag2.append(0)

if not 0 in temp_def_diag1:
diag_defscore1 = sum(temp_def_diag1)
else:
diag_defscore1 = 0

if not 0 in temp_def_diag2:
diag_defscore2 = sum(temp_def_diag2)
else:
diag_defscore2 = 0

def_diag1 = *size**2
def_diag2 = *size**2
for i in range(size):
def_diag1[i*(size+1)] = diag_defscore1
def_diag2[(i+1)*(size-1)] = diag_defscore2
def_diag = [x + y for x, y in zip(def_diag1, def_diag2)]

'''The scores for rows and columns are summed together to calculate aggregate offensive and defensive scores for each cell.
Cells which were taken are assigned score "-1" since they cannot be chosen'''
offensive = [x + y + z for x, y, z in zip(offensive_row, offensive_col, off_diag)]
defensive = [x + y + z for x, y, z in zip(defensive_row, defensive_col, def_diag)]
for i in range(size):
for ii in range(size):
if board[ii][i] == "X" or board[ii][i] == "O":
offensive[(ii*size+i)] = -1
defensive[(ii*size+i)] = -1

# A total score (offensive+defensive) is calculated for each cell.

score = [x + y for x, y in zip(offensive, defensive)]

'''The computer will try to take the cell with the highest total score. If there are more than one cells
that share the same highest total score, the one with higher offensive score is chosen.
If the offensive scores are the same, choose any one. '''

maxval_score = max(score)
indices_score = [index for index, val in enumerate(score) if val == maxval_score]

if len(indices_score) == 1:
index = indices_score

else:
indices_offensive = {}
for i in range(len(indices_score)):
indices_offensive[indices_score[i]] = offensive[indices_score[i]]
sort_offensive = sorted(indices_offensive, key=indices_offensive.get, reverse = True)
index = sort_offensive

# Obtain the X and Y coordinates of that cell
move_y = int(index / size)
move_x = index - size * move_y

return move_x, move_y

```
Return True if every cell on the board has been taken to declare the game a tie. Otherwise return False.
This function helps to terminate the game whenever its a tie instead of having to fill up the entire board for the game to end.
```def isBoardFull(board):
for ii in range(size):
for i in range(size):
if isSpaceFree(board, ii, i):
return False

return True
```

#### Let’s start playing!

```print "Welcome to Tic Tac Toe!"

# Determining the size of the board
boardsize()

while True:
# Setting up the board
theBoard = [[] for i in range(size)]
for i in range(size):
for ii in range(size):
theBoard[i].append(" ")

# Player to choose letter
playerLetter, computerLetter = inputPlayerLetter()

# Randomly decide who goes first
turn = whoGoesFirst()
print "The " + turn + " will go first."
gameIsPlaying = True

while gameIsPlaying:
if turn == 'player':
# Player’s turn.
drawBoard(theBoard)
# Ask for player's input of coordinates
move_x, move_y = getPlayerMove(theBoard)
# With player's input, place his/her letter on the relevant cell
makeMove(theBoard, playerLetter, move_x, move_y)

#check if player has won, if so, end the game
if isWinner(theBoard, playerLetter):
drawBoard(theBoard)
print "The player has won."
gameIsPlaying = False
# check if all rows, columns and diagonal lines contain both player and computer letter and declare the game a tie
elif isTie(theBoard, playerLetter, computerLetter):
drawBoard(theBoard)
print "There are no possible winning moves, the game is a tie!"
gameIsPlaying = False
else:
# check if all cells in the board are taken hence the game is a tie, end the game
if isBoardFull(theBoard):
drawBoard(theBoard)
print "The board is full, the game is a tie!"
gameIsPlaying = False
else:
# if player hasn't won and it's not a tie, it will be the computer's turn to play
turn = 'computer'

else:
# Computer’s turn.
# using the scoring mechanism to decide what move the computer will make
move_x, move_y = getComputerMove(theBoard, computerLetter)
makeMove(theBoard, computerLetter, move_x, move_y)
#similarly, check if the computer has won or if the game is a tie
if isWinner(theBoard, computerLetter):
drawBoard(theBoard)
print "The computer has won."
gameIsPlaying = False
elif isTie(theBoard, playerLetter, computerLetter):
drawBoard(theBoard)
print "There are no possible winning moves, the game is a tie!"
gameIsPlaying = False
else:
if isBoardFull(theBoard):
drawBoard(theBoard)
print "The game is a tie!"
break
else:
turn = 'player'

# after the game has ended, ask if the player wants to play again
if not playAgain():
break
```