TicTacToe in Python with MiniMax/AlphaBeta

Question

I know barely anything about Python, I just jumped into this project as I've already coded it in different languages and it's my go-to when figuring things out in a new one, any feedback will be appreciated.

I deliberately tried to avoid making things too object-oriented with private attributes and whatnot.

This runs slower than the Java / C++ versions I made, despite having already improved the performance by doing a lightweight clone instead of a deep copy.

Board.py

from enum import Enum
class Board:
 #the three states each cell can be in
 class State(Enum): 
 empty = 0
 x = 1
 o = -1
 
 def __init__(self):
 self.reset()
 
 #resets the board
 def reset(self):
 self.cells = [self.State.empty] * 9
 self.turn = self.State.x
 self.currentTurn = 0
 self.winner = self.State.empty
 self.gameOver = False
 
 #applies a move based on the current turn 
 def applyMove(self, move):
 if self.gameOver == False and self.cells[move] == self.State.empty:
 self.cells[move] = self.turn;
 self.update()
 
 #updates the turn
 def endTurn(self):
 if self.turn == self.State.x:
 self.turn = self.State.o
 else: self.turn = self.State.x
 
 self.currentTurn += 1
 
 def getTurn(self):
 return self.turn
 
 def xWon(self):
 self.winner = self.State.x
 self.gameOver = True
 
 def oWon(self):
 self.winner = self.State.o
 self.gameOver = True
 
 def draw(self):
 self.gameOver = True
 
 def getWinner(self):
 return self.winner.value
 
 # returns a list of the empty cells
 def getMoves(self):
 moves = []
 for i in range(len(self.cells)):
 if self.cells[i] == self.State.empty:
 moves.append(i)
 return moves 
 
 #checks for a winner/draw 
 def update(self): 
 
 self.endTurn()
 for i in range(3):
 
 xWin = True;
 oWin = True;
 for j in range(i*3, i*3+3):
 if self.cells[j] != self.State.x:
 xWin = False
 if self.cells[j] != self.State.o:
 oWin = False;
 
 if xWin:
 self.xWon()
 return
 if oWin:
 self.oWon()
 return
 
 xWin = True
 oWin = True
 for j in range(i, i+7, 3): 
 
 if self.cells[j] != self.State.x:
 xWin = False
 if self.cells[j] != self.State.o:
 oWin = False
 
 
 if xWin: 
 self.xWon()
 return 
 if oWin:
 self.oWon()
 return
 step = 4
 for i in range(0, 3, 2):
 
 xWin = True
 oWin = True
 for j in range(3):
 
 if self.cells[i+(j*step)] != self.State.x:
 xWin = False
 if self.cells[i+(j*step)] != self.State.o:
 oWin = False
 if xWin: 
 self.xWon()
 return
 if oWin: 
 self.oWon()
 return
 step = 2;
 if self.currentTurn == 9:
 self.draw()

Brain.py (wrapper for the minimax algorithm)

import copy
from Board import *
class Brain:
 def __init__(self, board):
 self.originalBoard = board
 self.count = 0
 
 #returns the best move according to the minimax method
 def bestMove(self):
 if self.originalBoard.gameOver:
 return
 self.count = 0
 scores = []
 moves = self.originalBoard.getMoves()
 
 for m in moves:
 scores.append(self.miniMax(self.originalBoard, m))
 print(self.count)
 
 if (self.originalBoard.getTurn() == self.originalBoard.State.x):
 return moves[self.max(scores)]
 else:
 return moves[self.min(scores)]
 
 #classic minimax with alphabeta pruning 
 def miniMax(self, board, move, alpha = -1, beta = 1):
 
 self.count += 1
 clone = copy.deepcopy(board) >now replaced as I said in the intro<
 clone.applyMove(move)
 
 if clone.gameOver:
 return clone.getWinner()
 
 availableMoves = board.getMoves() 
 if clone.getTurn() == clone.State.x:
 for m in availableMoves:
 score = self.miniMax(clone, m, alpha, beta) 
 if score > alpha:
 alpha = score 
 if alpha >= beta:
 break
 return alpha 
 
 else:
 for m in availableMoves:
 score = self.miniMax(clone, m, alpha, beta)
 if score < beta:
 beta = score
 if alpha >= beta:
 break
 return beta 
 
 #helper method that returns the index of the highest number in a list
 def max(self, list):
 max = -1
 index = 0
 if list.__len__() == 1:
 return index
 
 for i in range (len(list)):
 if (list[i] > max):
 max = list[i]
 index = i
 return index
 
 #helper method that returns the index of the lowest number in a list
 def min(self, list):
 min = 1
 index = 0
 if list.__len__() == 1:
 return index
 
 for i in range (len(list)):
 if (list[i] < min):
 min = list[i]
 index = i
 return index

TicTacToe.py (main file)

from tkinter import *
from Board import *
from Brain import *
from math import floor as floor
CELLS_ROW = 3
WIDTH = 400
HEIGHT = 400
CELLWIDTH = WIDTH / CELLS_ROW
CELLHEIGHT = HEIGHT / CELLS_ROW
tk = Tk()
tk.title("Tic Tac Toe")
board = Board()
brain = Brain(board)
# Draws the background
def drawBG(): 
 def getBGColor(i, j):
 return "#222222" if i % 2 == j % 2 else "#444444"
 for i in range(0, CELLS_ROW):
 for j in range(0, CELLS_ROW) :
 canvas.create_rectangle(i*CELLWIDTH, j*CELLHEIGHT, CELLWIDTH+i*CELLWIDTH, CELLHEIGHT+j*CELLHEIGHT, fill=getBGColor(i, j))
#Draws the naughts and crosses
def drawMarks():
 thickness = 20
 def drawMark(x, y, mark):
 if mark == board.State.x:
 canvas.create_line(x*CELLWIDTH+thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+thickness, fill="#d32f2f", width = thickness, capstyle = ROUND)
 canvas.create_line(x*CELLWIDTH+thickness, y*CELLHEIGHT+thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, fill="#d32f2f", width = thickness, capstyle = ROUND)
 else: canvas.create_oval(x*CELLWIDTH+thickness, y*CELLHEIGHT+thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, outline="#5a64c8", width = thickness)
 
 for i in range(3):
 for j in range(3):
 if board.cells[i*3+j] != board.State.empty:
 drawMark(j, i, board.cells[i*3+j])
 
#Applies a move based on the mouse position 
def click(event):
 def translateCoords(_x, _y):
 x = floor(_x / CELLWIDTH)
 y = floor(_y / CELLHEIGHT)
 return x + y * CELLS_ROW
 board.applyMove(translateCoords(event.x, event.y))
 updateCanvas()
#Resets the board
def reset(event):
 board.reset()
 updateCanvas()
#Asks the MiniMax algorithm for the best move and applies is
def requestMove(event):
 if board.gameOver == False:
 board.applyMove(brain.bestMove())
 updateCanvas()
#Calls the functions that draw the window
def updateCanvas():
 drawBG()
 drawMarks()
 tk.update()
canvas = Canvas(tk, width=WIDTH, height=HEIGHT)
canvas.bind("<Button-1>", click)
canvas.bind("<Button-2>", reset)
canvas.bind("<Button-3>", requestMove)
updateCanvas()
canvas.pack()
tk.mainloop()

Answer 1

Your program looks pretty good for a beginner. A couple of things could make the code easier to work with though, and thus reduce the risk of bugs and extra maintenance should you ever pick this up again.

State

You set a winner as follows:

def xWon(self):
 self.winner = self.State.x
 self.gameOver = True
def oWon(self):
 self.winner = self.State.o
 self.gameOver = True
def draw(self):
 self.gameOver = True

winner is a State and the gameOver is a separate variable. gameOver can't be part of State, because State is actually being abused for something it wasn't supposed to do:

#the three states each cell can be in
class State(Enum): 
 empty = 0
 x = 1
 o = -1

You're not using it just for the cell state. You're using it for the cell state, the board state (who has won) and even the turn state. Apparently it's acceptable to have a board without winner and without next-player (board state and turn state can be set to empty). If you set either of those to empty, I'd assume the game to be over as well and thus there's no need for a gameOver state. But there's an even better way.

You've tried to reduce duplication by using the same class twice. However, by doing so, you've introduced duplication elsewhere in a way that makes less sense than when you'd have allowed the duplication (making either 2 separate constructs to hold state or make 1 that's configurable).

Holding game-state in an Enum is a great idea. Holding cell-state in an Enum is too. But their possible states are not the same.

A board/game state for Tic Tac Toe can be the following:

• Incomplete (ongoing)
• Complete (finished, game over)

To keep things simple, we can replace the latter by 3 more specific states:

• X won
• Y won
• Draw

A cell state can be the following:

• X
• Y
• Empty

Do we have to check for those 3 specific states now to check whether a game is finished? No. Just check whether the board is unfinished. If it's not unfinished, it must be finished. Because those are the only states defined. This would simplify some of the checks you have later on.

For example:

if xWin:
 self.xWon()
 return
if oWin:
 self.oWon()
 return

Note: this construct is used 3 times in the same function (update(self)), which indicates the function is either poorly structured or doing too much. Or both.

If the winner is part of the game state, you can return it straight away and not bother with a double if checking temporary variables. The only question at this point is whether there should be returned at all. This could look like the following:

if gameState.xWon or gameState.yWon:
 return

This:

xWin = True
oWin = True
for j in range(3):
 if self.cells[i+(j*step)] != self.State.x:
 xWin = False
 if self.cells[i+(j*step)] != self.State.o:
 oWin = False

Completely defies the whole point of working with states in the first place. Why have states at all when at one point you set the game to assume two winners? One false step in those next lines of code and you've broken an otherwise perfectly safe program.

Comments near definitions

You like to state the purpose of what happens near a definition:

#the three states each cell can be in
class State(Enum):
#applies a move based on the current turn 
def applyMove(self, move):
#Resets the board
def reset(event):
#Asks the MiniMax algorithm for the best move and applies is
def requestMove(event):
#Calls the functions that draw the window
def updateCanvas():

This is commendable. Did you know Python has an in-built feature that makes this even better? It's called docstrings.

Consider PEP 257 – Docstring Conventions.

Docstrings provide a convenient way of putting human-readable documentation in the code itself that's easily extracted by other scripts/programs. They can be used on modules, functions, classes and methods.

A straightforward conversion would result in: class State(Enum): """The three states each cell can be in."""

def applyMove(self, move):
"""Applies a move based on the current turn."""
def reset(event):
"""Resets the board."""
def requestMove(event):
"""Asks the MiniMax algorithm for the best move and applies it."""
def updateCanvas():
"""Calls the functions that draw the window."""

Minor note: if requestMove fails to perform a move, it will not provide feedback in any way and there was a typo in the comment.

Implementing docstrings allows other programs, the Python interpreter and most IDEs to provide guidance on the functions you're using (with IntelliSense). You can then extent this even further using typing (assuming Python 3.5+) and verify whether everything that needs a docstring has one with doctest. This can be very useful when using code defined in a different file/module/library.

Readability

Most of your code is quite easy to read. Whenever it's hard to follow, that's usually due to how you play around with states. See above. Other parts of your code are easily improved.

For example:

def drawMark(x, y, mark):
 if mark == board.State.x:
 canvas.create_line(x*CELLWIDTH+thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+thickness, fill="#d32f2f", width = thickness, capstyle = ROUND)
 canvas.create_line(x*CELLWIDTH+thickness, y*CELLHEIGHT+thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, fill="#d32f2f", width = thickness, capstyle = ROUND)
 else: canvas.create_oval(x*CELLWIDTH+thickness, y*CELLHEIGHT+thickness, x*CELLWIDTH+CELLWIDTH-thickness, y*CELLHEIGHT+CELLHEIGHT-thickness, outline="#5a64c8", width = thickness)

I think you'll agree with me that the following is much easier on the eyes:

def drawMark(x, y, mark):
 if mark == board.State.x:
 canvas.create_line(
 x * CELLWIDTH + thickness,
 y * CELLHEIGHT + CELLHEIGHT - thickness,
 x * CELLWIDTH + CELLWIDTH - thickness,
 y * CELLHEIGHT + thickness,
 fill = "#d32f2f",
 width = thickness,
 capstyle = ROUND
 )
 canvas.create_line(
 x * CELLWIDTH + thickness,
 y * CELLHEIGHT + thickness,
 x * CELLWIDTH + CELLWIDTH - thickness,
 y * CELLHEIGHT + CELLHEIGHT - thickness,
 fill = "#d32f2f",
 width = thickness,
 capstyle = ROUND
 )
 else:
 canvas.create_oval(
 x * CELLWIDTH + thickness,
 y * CELLHEIGHT + thickness,
 x * CELLWIDTH + CELLWIDTH - thickness,
 y * CELLHEIGHT + CELLHEIGHT - thickness,
 outline = "#5a64c8",
 width = thickness
 )

Now the differences and similarities between the canvas calls are clear at a single glance (don't forget to update the canvas.create_rectangle call as well). You're only using canvas.create_line twice, but if you'd use it more often I'd consider writing a new function for it as a wrapper. It might be a bit overkill at this point.

Give your operators some breathing room, don't make your lines too long and be consistent with whitespace.

There are a couple of magic numbers in your code. Some of the numbers you've turned into a pseudo-constant, like CELLS_ROW = 3. But there are a lot of 3 remaining in your code and all colours are hardcoded. If you put a value into a constant, make sure it's properly named.

For example:

for i in range(0, CELLS_ROW):
 for j in range(0, CELLS_ROW):

One of those is going to be a column, not a row.

Consider PEP 8 - Style Guide for Python Code.

• Daniel: Hey, thank you for taking the time to answer to a 5 and a half year old question. I especially agree with the part about code readablility.