Unbeatable Tic-Tac-Toe program seems difficult to read

Question

I've made an unbeatable Tic-Tac-Toe in Python 3.3. While it truly was unbeatable, it was an eyesore to look at and nigh impossible to read. That code is here.

I have since then optimized it for Python 2.7.5 as follows:

from random import randrange, random
from time import sleep
#First, setup the board!!

def draw_board():
    print '', board[1], '|', board[2], '|', board[3], \
          '\n-----------\n', \
          '', board[4], '|', board[5], '|', board[6], \
          '\n-----------\n', \
          '', board[7], '|', board[8], '|', board[9], \
          '\n'
#Next, Choose what team you're on!

def player_team():
    team = raw_input('Do you want to be X or O? \n').upper()
    print
    if team == 'X':
        return ['X', 'O']
    elif team == 'O':
        return ['O', 'X']
    else:
        print ('That is not a valid choice. Please try again \n')
        return player_team()
#Next, Find out what player goes first!

def first_turn():
    turn = random()
    if turn <= .494:
        print 'You will go first \n'
        return ('user', True)
    else:
        print 'The Computer will go first \n'
        return ('computer', False)
#Next, be able to determine which spaces are available!

def available(space):
    if board[space] == ' ':
        return True
#Next, allow a player to pick their move!

def user_turn():
    try:
        move = int(raw_input('Where would you like to move? (Enter a number from 1-9) \n'))
        if 0 < move < 10:
            if not available(move):
                print ('That space is already taken by a player. '
                       'Please select an open space \n')
                return user_turn()
            else:
                board[move] = user_team
                print
    except:
        print 'That is not a valid move. Please try again. \n'
        return user_turn()   
#Now define the A.I!

def computer_turn():
    move = randrange(1, 10)
    if available(move):
        board[move] = computer_team
        return move
    else:
        return computer_turn()
#Next, we must check if the game has ended or not, and see who won!

def end_game():
    for row in range(1, 10, 3):
        if not available(row):
            if board[row] == board[row + 1] and board[row] == board[row + 2]:
                return True
    for column in range(1, 4):
        if not available(column):
            if board[column]== board[column + 3] and board[column] == board[column + 6]:
                return True
    for diagonal in range(1, 10, 2):
        if not available(diagonal):
            if (diagonal == 1 and board[diagonal] == board[diagonal + 4]
                and board[diagonal] == board[diagonal + 8]):
                return True
            elif (diagonal == 3 and board[diagonal] == board[diagonal + 2]
                and board[diagonal] == board[diagonal + 4]):
                return True
    if board.count('X') + board.count('O') == 9:
        return 'Tie'

def check_winner():
    global user_win, computer_win, ties
    if end_game() == 'Tie':
        ties += 1
        draw_board()
        print ("The game is a tie. You're going to have to try harder"
               "\nif you wish to beat the computer! \n")
    elif end_game():
        if turn == 'user':
            user_win += 1
            draw_board()
            print ('You won! \n')
        else:
            computer_win += 1
            draw_board()
            print ('The computer has won! But... We already knew'
                   'that would happen. (: \n')    
#Finally, give the option of a New Game+!

def play_again():
    print 'Your wins:', user_win, '\n' \
          'Computer wins:', computer_win, '\n' \
          'Ties:', ties, '\n'
    restart = raw_input('Do you wish to play another game? Yes or no? \n').upper()
    print
    if restart == 'YES':
        return True
    elif restart == 'NO':
        return False
    else:
        print ('That is not a valid choice. Please try again. \n')
        return play_again()
#Main Program:    

print ('Welcome to my Impossible Tic-Tac-Toe game! You are of the bravest'
       'of souls \nto take on my challenge, but only failure awaits you. \n')
count = 1
user_win, computer_win, ties = 0, 0, 0
new_game = True
while new_game:
    board = [' '] * 10
    user_team, computer_team = player_team()
    turn, strategy = first_turn()
    print 'Game', count, '\n'
    while not end_game():
        if turn == 'user':
            draw_board()
            user_turn()
            check_winner()
            turn = 'computer'
        else:
            draw_board()
            print 'The computer is thinking... \n'
            sleep(1)
            space_taken = computer_turn()
            print 'The computer moved on space', space_taken, '\n'
            check_winner()
            turn = 'user'
    if not play_again():
        new_game = False
    count += 1

(The AI in the new code is just a placeholder until I fix up the old one.)

I definitely feel like it's improved a lot, but I am still unfamiliar about a few things.

My program is mainly functional-based, but would switching to OOP have any benefits in this scenario?

Answer 1

1. Some of the comments are wrong, for example:

   #First, setup the board!!
   

   appears just before the draw_board function, which does not set up the board.

   The best practice here is to write a docstring for each function explaining what it does, how to call it, and what kind of values it returns.

2. You use global variables board, user_win, computer_win, ties, user_team, computer_team, turn. Global variables make code hard to read, because you have to remember which variables are globals, and this might not be at all obvious. For example, the function first_turn starts with the line:

   turn = random()
   

   but this is not the global turn, it's a local variable with the same name!

   Global variables also make it hard to test from the interactive interpreter, because you have to fiddle about getting the globals into the right state for whatever it is you want to test.

   It is generally better if you pass your state as parameters to functions (for example, the draw_board function could take board as a parameter), or maintain it as properties of objects (for example, user_win could be a property of an object).

3. Your draw_board function could benefit from using Python's string formatting interface. I would also rename it print_board (because I prefer to reserve the word draw for rendering graphics).

   def print_board(board):
       """Print 'board' to standard output."""
       print(" {1} | {2} | {3}\n"
             "---+---+---\n"
             " {4} | {5} | {6}\n"
             "---+---+---\n"
             " {7} | {8} | {9}\n".format(*board))
   

   Now it's straightforward to test it from the interactive interpreter:

   >>> print_board('.XOXXOOOXX')
    X | O | X
   ---+---+---
    X | O | O
   ---+---+---
    O | X | X
   

4. Your function player_team uses tail recursion to implement a potentially infinite loop. But Python does not support tail call elimination, so a player who insists on repeatedly entering a wrong choice will eventually overflow the Python stack and cause it to fail:

   >>> import sys
   >>> sys.setrecursionlimit(3)
   >>> player_team()
   Do you want to be X or O? 
   No!
   
   That is not a valid choice. Please try again 
   
   Do you want to be X or O? 
   No, thank you.
   
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr33359.py", line 23, in player_team
       return player_team()
     File "cr33359.py", line 17, in player_team
       if team == 'X':
   RuntimeError: maximum recursion depth exceeded in cmp
   

   (In real life, sys.setrecursionlimit is larger than 3, so it would take somewhat longer to reach the maximum recursion depth, but a determined player could get there in the end.)

   Instead, you should use iteration, for example like this:

   def player_teams():
       """Prompt user for their preferred symbol (X or O), repeatedly if
       necessary, and return a string consisting of the player's symbol
       and the computer's symbol.
   
       """
       while True:
           team = raw_input('Do you want to be X or O? ').upper()
           if team == 'X': return 'XO'
           elif team == 'O': return 'OX'
           else: print("Please enter X or O.")
   

   There are similar problems in user_turn, computer_turn, and play_again.

5. The first_turn function returns a pair whose second value (called strategy in the main loop) is unused. So why bother returning it?

6. In the available function:

   def available(space):
       if board[space] == ' ':
           return True
   

   what happens if board[space] is not a space? There's no else: clause, so the function just ends without explicitly returning anything. Luckily for you, "Falling off the end of a function returns None"

   >>> def noreturn(): pass
   ... 
   >>> print(noreturn())
   None
   

   and None becomes False when converted to a Boolean:

   >>> bool(None)
   False
   

   so available works. But this seems needlessly tricky. It's simpler and clearer to write:

   def available(board, position):
       """Return True if 'position' is available to play on 'board'."""
       return board[position] == ' '
   

7. Your function end_game returns the Boolean True if the game is over and there's a winner, the string 'Tie' if the game is over and there's no winner, and it falls off the end (thus returning None) if the game is not over. This is a confusing interface. If you had tried to write a docstring for the function, as recommended in point 1 above, that explained what it was supposed to return then the confusion would have become apparent.

   It would be better to redesign the interface so that it's easier to understand, for example like this:

   def game_status(board):
       """Return the status of 'board' as one of the following strings:
       'X' or 'O' if that player has three in a row;
       'tie' if the board is full but neither player has won; or
       'unfinished' otherwise.
       """
   

8. The function end_game seems rather complex. In tic-tac-toe there are just eight winning lines, so why not just list them? I would write:

   # The legal board positions.
   BOARD_POSITIONS = list(range(1, 10))
   
   # Triples of board positions giving the eight winning lines.
   WINNING_LINES = [(1, 2, 3), (4, 5, 6), (7, 8, 9)
                    (1, 4, 7), (2, 5, 8), (3, 6, 9),
                    (1, 5, 9), (3, 5, 7)]
   
   def game_status(board):
       """Return the status of 'board' as one of the following strings:
       'X' or 'O' if that player has three in a row;
       'tie' if the board is full but neither player has won; or
       'unfinished' otherwise.
       """
       for i, j, k in WINNING_LINES:
           if not available(board, i) and board[i] == board[j] == board[k]:
               return board[i]
       if any(available(board, i) for i in BOARD_POSITIONS):
           return 'unfinished'
       return 'tie'
   

   Note the use of Python's chained comparisons here. In some other languages you would have to write:

   board[i] == board[j] and board[j] == board[k]
   

9. In check_winner you call end_game twice, and you call it again in the main loop. But nothing changes between the first call and the subsequent calls, so why not remember the value and avoid the unnecessary computation?

That's probably enough comments to be going on with.

Answer 2

Since you are interested in an OOP approach, I take the opportunity to show you a toy program I did during a programming course. The comments in the code are in italian (sorry) but I hope it is clear anyway.

The code comprises:

• a Board class which represents the state of the game (with all the rules and check for valid moves and winner);
• a Player class which is a dummy base class to implement players:
• the Human player ask the moves to the user,
• the Random player makes a random valid move,
• the Smart player finds the better move through an exaustive search in the tree of moves (this actually requires memoization otherwise it would take a long time also for a game as simple as this);
• a Game object takes two Players and let them play one against the other.
• the __main__ function let the Human player play against the Smart player.

Just a funny note: I asked my students to write their own implementation of Player... but I was disappointed to see that most of them were beaten by my Random player!

---

import random

'''
Gioco del tris (filetto). Mette a disposizione le seguenti classi:

Board: schema di gioco

Player: giocatore stupido (esegue prima mossa possibile)
Human: giocatore umano (chiede la mossa da eseguire)
Random: giocatore casuale (esegue una mossa a caso)

Game: partita tra due giocatori
'''

class Board(object):
    '''
    rappresentazione del gioco Tris
    scacchiera 3x3: ogni cella contiene X, O oppure .
    inoltre mantiene informazione sul turno di gioco
    Le caselle sono identificate da una cifra da 1-9 come nello schema:

    123
    456
    789

    ''' 
    def __init__(self,board=None):
        'nuovo schema di gioco vuoto oppure copia di @board'
        if board is None:
            self.s = '.........' # '.'*9
            self.turn = 'O'
        else:
            self.s = board.s
            self.turn = board.turn
        self._state = 'not ended'

    def rows(self):
       'restituisce le tre righe di tre caratteri'
       return [self.s[n*3:(n+1)*3] for n in range(3)]

    def cols(self):
       'restituisce le tre colonne di tre caratteri'
       return [self.s[n] + self.s[n+3] + self.s[n+6] for n in range(3)]

    def diags(self):
       'restituisce le due diagonali di tre caratteri'
       return [self.s[0]+self.s[4]+self.s[8], self.s[2]+self.s[4]+self.s[6]]

    def __str__(self):
        'rappresentazione dello schema in una stringa multi-linea'
        r = '\n'.join(self.rows())+'\n'+'turn: '+self.turn+'\n'
        s = self.state()
        if s != 'not ended':
            if s == 'draw':
                r += 'DRAW!\n'
            else:
                r += s + ' WINS!'
        return r

    def is_valid(self,move):
        '''la mossa @move e' valida?'''
        return move in range(1,10) and self.s[move-1] == '.'

    def valid_moves(self):
        'lista di tutte le mosse valide'
        return [x for x in range(1,10) if self.is_valid(x)]

    def state(self):
        '''stato corrente: 'O', 'X', 'draw', 'not ended' '''
        return self._state

    def compute_state(self):
        for r in self.rows() + self.cols() + self.diags():
            if r == 'OOO':
                self._state = 'O'
                return
            if r == 'XXX':
                self._state = 'X'
                return
        if self.s.find('.') == -1:
            self._state = 'draw'
            return
        return 'not ended'

    def play(self, move):
        'effettua una mossa nella posizione @move: 1,2,3, 4,5,6, 7,8,9'
        if self.is_valid(move):
            self.s = self.s[0:move-1] + self.turn + self.s[move:9] 
            if self.turn == 'O':
                self.turn = 'X'
            else:
                self.turn = 'O'
            self.compute_state()
        else:
            # print 'mossa non valida!'
            if move in range(1,10):
                self.s = self.s[0:move-1] + (self.turn.lower()) + self.s[move:9]
            else:
                self.s = self.turn.lower()*9
            if self.turn == 'O':
                self._state = 'X'
            else:
                self._state = 'O'

class Player(object):
    ''' Giocatore. Puo' essere inizializzato con un nome. 
        Gioca la prima mossa valida
    '''

    def __init__(self,name='no-name'):
        self.name = name

    def move(self,board):
        return board.valid_moves()[0]

    def __str__(self):
        return '{0}: {1}'.format(type(self).__name__, self.name)

class Human(Player):
    def move(self,board):
        while True:
            move = raw_input('%s: che mossa vuoi fare? ' % self.name)
            try: 
                move = int(move)
                if board.is_valid(move):
                    return move
                else:
                    print 'mossa non valida: %s' % move
                    print board
            except ValueError:
                print 'la mossa deve essere un numero tra 1 e 9'

class Random(Player):
    def move(self,board):
        return random.choice(board.valid_moves())

class Smart(Player):
    def think(self,board):
        ''' restituisce una coppia (esito,move) con la mossa migliore e relativo esito '''

        # controlla se abbiamo gia' esaminato questa posizione
        if not hasattr(self,'cache'):
            self.cache = {}
        hash = board.turn + board.s
        if hash in self.cache:
            return self.cache[hash]

        me = board.turn
        draw_move = None
        for m in board.valid_moves():
            b = Board(board)
            b.play(m)
            s = b.state()
            if s == me:
                self.cache[hash] = (me,m)
                return (me,m) # mossa vincente!
            if s == 'draw': # unica mossa possibile!
                self.cache[hash] = ('draw',m)
                return ('draw',m)
            assert s == 'not ended'
            (s,mm) = self.think(b)
            if s == me:
                self.cache[hash] = (me,m)
                return (me,m) # mossa vincente!
            if s == 'draw':
                draw_move = m # mossa pattante... c'e' di meglio?
        # nessuna mossa vincente trovata. puntiamo alla patta
        if draw_move:
            self.cache[hash] = ('draw',draw_move)
            return ('draw',draw_move)
        # vince avversario :( scegliamo una mossa a caso
        self.cache[hash] = (b.turn,random.choice(board.valid_moves()))
        return self.cache[hash]

    def move(self,board):
        return self.think(board)[1]

class Game(object):
    def __init__(self,player_O,player_X,verbose=2):
        self.players = {'O': player_O,
                        'X': player_X}
        self.board = Board()
        self.verbose = verbose
        if self.verbose > 0:
            print 'O={0}, X={1}'.format(player_O.name, player_X.name)

    def play(self):
        while self.board.state() == 'not ended':
            # visualizza schema di gioco:
            if self.verbose>1:
                print self.board

            # chiede al giocatore di turno la mossa da fare:
            current_player = self.players[self.board.turn]
            move = current_player.move(Board(self.board))
            if self.verbose>1:
                print "{0} sceglie la mossa: {1}".format(current_player, move)

            # esegue mossa sullo schema:
            self.board.play(move)

        # visualizza posizione finale 
        state = self.board.state()
        if self.verbose > 1:
            print self.board
            if state in self.players:
                print 'Ha vinto: {0}'.format(self.players[state])
        return self.board

if __name__ == '__main__':
    # esecuzione diretta del codice
    name = raw_input('Come ti chiami? ')
    game = Game(Human(name),Smart('computer'))
    game.play()