# Unbeatable Tic-Tac-Toe program seems difficult to read

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?

• @Barry, remember that the interval on random() is [0, 1), meaning that in theory, 1 is never actually reached. I simply had .99/2 which is .495. I moved it down to .494 since that side will include 0, which makes it like a .001 difference? :P – Gavin Feriancek Oct 28 '13 at 5:26
• One small comment. Instead of using and in some of your if statements, you can say if a == b == c – jcfollower Oct 28 '13 at 13:38
• Why for diagonal in range(1, 10, 2):? There are only two diagonals, right? Maybe just deal with them individually, since they use different code. – jcfollower Oct 28 '13 at 13:44
• In check_winner(), just call draw_board() once after the elif block, rather than inside every if block. – jcfollower Oct 28 '13 at 13:46
• Not sure if anyone mentioned this, but this is procedurally written code, see this . Functional programming is a bit different, see here – Scüter May 7 '14 at 21:02

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.

• Thanks for all of the input! I'll look into the string formatting interface, and it's nice to know about that Tail Recursion limit (I thought about changing it to a while loop, but it worked, so I left it. Nice to know that it isn't good to do). The chained comparisons will also help out a lot! As far as 'strategy' goes, was used in the old code to tell the computer if it starts first, but thinking back it does seem unnecessary. Using parameters does seem to be cleaner. Do you think it'd be better off as is or more Object oriented with the objects 'board' and 'player'? Thanks again! – Gavin Feriancek Oct 30 '13 at 0:19
• Why not try both and see which is better? – Gareth Rees Oct 30 '13 at 10:51
• Hmm, good point. :P I'm still a little hazy with OOP, but I'm working on learning! I do feel that it would help clean up those globals though, since most of them would then become an argument in some part of the class. – Gavin Feriancek Oct 30 '13 at 13:34

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()