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 = [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
    
        
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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s