A couple of blog posts ago, I interviewed my friend Stuart about his new job as an app developer. As part of his interview, he was given a week to program a simple 2-player tic-tac-toe game using a programming language of his choice. This seems to be a common homework problem for computer programming students and I thought it would be good practice to see if I could write my own version in Python. Here is an example of a tic-tac-toe programming assignment I found from a google search:
You are to implement the two player game of Tic Tac Toe. The program should display the board and prompt each user a move. The program should validate each move and handle any incorrect input. The entire user interaction should be command line based. Upon winning or a draw of the game, an appropriate message should be displayed acknowledging such condition.
 |
| Not a valid win. |
Through the Computer Science 101 course I did with Udacity.com, there was a very good segment on "How to solve problems" that I've found useful as a framework to tackle programming projects. At the risk of stating the obvious, the heart of the framework is just pure good old-fashioned common sense, but it's often sooooo tempting to just jump straight into the problem. By breaking down the solution into steps, you can (hopefully) get to a more efficient and elegant solution, which should save time and frustration later on.
So the most important thing is to start off by heeding the zero-th rule! (this is computer programming after all, and everything begins from 0 rather than 1). The all important zero-th rule is....
0. DON'T PANIC! Take a deep breath and keep calm...
 |
| It's actually really funny how many times the instructor reminds us to not panic during the Udacity video lesson on Problem Solving. Computer Science students must be an anxious bunch. |
So after our chill pill, the next thing to do is to make sure we understand the problem - what are the possible inputs and what are the desired outputs. The solution is getting to a procedure that takes those inputs and maps these to the outputs defined by the job spec.
1. What are the inputs?
- Which player (X or O) is playing
- The position that the player wants to play
We need to consider how the inputs are represented -I chose to go with inputs passed in as numerical coordinates (e.g. the user enters the number of the row and column they wish to place their move). Whenever a program uses user input, we also need to program "defensively", i.e. take into account invalid inputs by the user such as inputting letters instead of numbers or coordinates on the board that don't exist or are already occupied.
2. What are the outputs?
- Print out the board after each move
- Return when a game is complete; who won or if there was a stalemate.
3. Solve the problem!
Working out the relationship between the inputs and outputs is clearly the hardest part (at various points, you may need to remind yourself of step 0). Some good advice is to start off by working out some examples and test cases by hand, consider what could a win looks like? What does a stalemate look like?Everyone has played tic tac toe so I won't bother going through the mechanics of the game here. Once you think systematically about how a human would play the game, we can come up with some "pseudocode" for our solution (i.e. an algorithm that describes the processes you want your code to run). The aim of this is to get down a draft of an idea for the solution and see if it makes sense.
- Decide which player is going first
- Ask for that player's first move and check if it's legal (e.g. that it's on a 3x3 board, and in an empty space)
- Has a win or a stalemate occurred?
- If not, it's the next player's go
- Keep going til we get to a win or stalemate
Once you get to a process of a sensible-looking solution that you're happy with, the next part is to decide which part of the code to write first. In general, the advice is to write the simple cases first and worry about special cases at a later date - don't optimise too early. Write small bits of code, test them and understand fully what they do before adding to it. Obviously it depends on the problem in hand, but it's good to make a start and make your code flexible to incorporate potential changes. I like writing a little welcome message to really get me in the mood!
print "Welcome to Tic Tac Toe, in order to play please enter your row and column numbers between 1 and 3"
print "Welcome to Tic Tac Toe, in order to play please enter your row and column numbers between 1 and 3"
Here is my full code on Github (it is written for a 2player as well as a 1player game where the computer chooses its moves randomly among the available spaces): https://github.com/ttz21/TicTacToe/blob/master/TicTacToe.py
I probably should have commented it a bit better, but below is a little bit more of a step-by-step walkthrough of how I went about solving it (Disclaimer: it's clearly not the only solution and hopefully in future, with a bit more experience I'll have time to revisit this problem and improve it).
So I started out by deciding that I would have the tic tac toe
board as an array in the program, and wrote the code that would go through each
entry in the array and “print” out the board on the screen:
board = [[" "," "," "],[" "," "," "],[" "," "," "]]
def print_board(board):
for i in range(0,3):
print " "+board[i][0]+" : "+board[i][1]+" : "+board[i][2]
if i<=1:
print
"..........."
Next, I thought about how moves would be recorded to the board
array using the raw_input() function, and how to account for invalid inputs
from the user (i.e. if something other than a 1,2 or 3 was entered as a
co-ordinate value). The function
get_player_input() below asks for either the row or the column coordinate and
returns the player’s entry –e.g. get_player_input( “X”, “row”) will ask player
X for the row coordinate on their move.
During gameplay, this “helper” function is then used to alternately
between player X and O to get their moves and store them in the board array.
def get_player_input(player_name,
coordinate):
correct_input=False
while(not correct_input):
value = raw_input("Player "+player_name+",
it is your go, enter your desired "+coordinate+":
")
try:
value=int(value)
except ValueError:
print
"That is not a valid input!"
if value>3 or value<1:
print
"Co-ordinate must be a number between 1
and 3"
else:
correct_input=True
return value
Besides inputting invalid numbers as co-ordinates, a player
could also enter a co-ordinate that is already filled, so we also need another
helper function that checks whether a particular cell is empty and returns
either True or False (otherwise known as a boolean).
def valid_cell(board,
row_value, col_value):
if(board[row_value-1][col_value-1]==" "):
return True
else:
return False
This can then be combined with the get_player_input() function
in order to write the user’s input to the board and then display the board on
the screen:
def check_player_input(player_name):
valid=False
while(not valid):
row_value =
get_player_input(player_name,"row")
col_value =
get_player_input(player_name,"col")
if(valid_cell(board,
row_value, col_value)):
board[row_value-1][col_value-1]=player_name
print_board(board)
valid=True
else:
print
"That cell is already taken!"
After these steps, it was time to write what a win looks like in
tic tac toe. The function below returns
a Boolean (True/False) by first checking whether a player has filled the cells
diagonally and then loops through the rows and columns to check for horizontal
and vertical wins.
def check_for_win(board,
player_name):
if (board[0][0]==board[1][1]==board[2][2]==player_name):
return True
if (board[0][2]==board[1][1]==board[2][0]==player_name):
return True
for i in range(0,3):
if(board[i][0]==board[i][1]==board[i][2]==player_name):
return
True
if(board[0][i]==board[1][i]==board[2][i]==player_name):
return
True
return False
In addition to a win, the game can also be stopped by a
stalemate if the board is full – the function below loops through the entries
in the board searching for empty cells.
def board_full(board):
for i in range(0,3):
for j in
range(0,3):
if
board[i][j]==" ":
return
False
return True
Finally, we just need to alternate between the players until
there is a win or the board is full. I
also added some extra functions to allow players to choose whether X or O would
go first, and later on, I put in a computer player that would make moves at
random – you can see the code for this on the github link above, but I won’t go
into it in detail in this post.
def determine_play_mode():
mode = raw_input("Would you like a 1 or 2 player game? ")
return mode
def determine_first_go():
go= raw_input("Who would like to go first? (X, O, or flip a coin?)")
if(go.upper()=="X"):
return["X", "O"]
elif(go.upper()=="O"):
return ["O", "X"]
else:
if(random.randint(0,1)==0):
return
["O", "X"]
else:
return
["X", "O"]
gameplay = True
num_gos = 0
play_order = determine_first_go()
play_mode = determine_play_mode()
while gameplay:
if(num_gos%2==0):
check_player_input(play_order[0])
else:
if(play_mode
== 2):
check_player_input(play_order[1])
else:
print
"Computer thinking..."
get_AI_input(play_order[1])
if(check_for_win(board,"X")):
print "Congratulations Player X, you have won!"
gameplay=False
elif(check_for_win(board,"O")):
print "Congratulations Player O, you have won!"
gameplay=False
elif(board_full(board)):
print "This round was a draw..."
gameplay=False
if(not gameplay):
again = raw_input("Would you like to play again? Enter Y to play again, or
any other entry to quit: ")
if (again.upper()=="Y"):
gameplay
= True
board
= [[" "," "," "],[" "," "," "],[" "," "," "]]
play_order
= determine_first_go()
play_mode
= determine_play_mode()
num_gos=-1
num_gos=num_gos+1
