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

```
import random
def boardsize():
global size
size = random.randint(3, 10)
print "You will play on a %d by %d board" % (size, size)
```

```
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 "-------------------------------------------------"
```

```
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']

```
def whoGoesFirst():
if random.randint(0, 1) == 0:
return 'computer'
else:
return 'player'
```

```
def playAgain():
print "Do you want to play again? (yes or no)"
return raw_input().lower().startswith('y')
```

##### 2. Defining the game strategy

```
def makeMove(board, letter, move_x, move_y):
board[move_y][move_x] = letter
```

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

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

```
def getBoardCopy(board):
dupeBoard = []
for i in board:
dupeBoard.append(i)
return dupeBoard
```

```
def isSpaceFree(board, move_x, move_y):
return board[move_y][move_x] == ' '
```

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

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 = [0]*size**2
off_diag2 = [0]*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 = [0]*size**2
def_diag2 = [0]*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[0]
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[0]
*# 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

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