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.