Python TicTacToe with Tk and minimax AI

tictactoe

Whenever I’m learning a new language I always implement some little games. My favorite 3 games to are:

  • TicTacToe
  • Connect4
  • Minesweeper

These are easy to implement since they are easy point-and-click games that do not require complex graphics or animation. They will require some multi-dimensional arrays fiddling and basic logic to implement. The GUI needed is pretty straight-forward and can be build using a window and a grid of buttons. Any window toolkit will provide these. If you like the idea of programming a game to learn a language, but you don’t like these specific games, check out “49 ideas for game clones to code“. Note that learning Python by programming small computer games is also suggested on “inventwithpython.com” (free e-book).

If you are not attracted to game programming you might want to check out “Python koans“.

Koan: a paradoxical anecdote or riddle without a solution, used in Zen Buddhism to demonstrate the inadequacy of logical reasoning and provoke enlightenment.

The Python Koans is a set of exercises that will make you learn Python. It is inspired by the “Ruby Koans“, which are also very good. You will run the tests and see them fail (red) and by changing the code you can make the tests pass (green). This is just as the Test Driven Development (TDD) method prescribes. So the Koans make you learn programming and TDD at the same time. Awesome!

TicTacToe in Python with “minimax” AI

This is my code for TicTacToe. It uses Tk since this is included in the Windows and MacOSX distributions of Python. In Linux “python-tk” is easy to install using the package manager. The game implements the “minimax” algorithm for Artificial Intelligence (AI). It has no heuristic (depth parameter and horizon effect) so it plays at infinite strength. With this game that is possible, because of it limited set of possible states.

          # coding=UTF8
          from Tkinter import Tk, Button
          from tkFont import Font
          from copy import deepcopy

          class Board:

            def __init__(self,other=None):
              self.player = 'X'
              self.opponent = 'O'
              self.empty = '.'
              self.size = 3
              self.fields = {}
              for y in range(self.size):
                for x in range(self.size):
                  self.fields[x,y] = self.empty
              # copy constructor
              if other:
                self.__dict__ = deepcopy(other.__dict__)

            def move(self,x,y):
              board = Board(self)
              board.fields[x,y] = board.player
              (board.player,board.opponent) = (board.opponent,board.player)
              return board

            def __minimax(self, player):
              if self.won():
                if player:
                  return (-1,None)
                else:
                  return (+1,None)
              elif self.tied():
                return (0,None)
              elif player:
                best = (-2,None)
                for x,y in self.fields:
                  if self.fields[x,y]==self.empty:
                    value = self.move(x,y).__minimax(not player)[0]
                    if value>best[0]:
                      best = (value,(x,y))
                return best
              else:
                best = (+2,None)
                for x,y in self.fields:
                  if self.fields[x,y]==self.empty:
                    value = self.move(x,y).__minimax(not player)[0]
                    if value<best[0]:
                      best = (value,(x,y))
                return best

            def best(self):
              return self.__minimax(True)[1]

            def tied(self):
              for (x,y) in self.fields:
                if self.fields[x,y]==self.empty:
                  return False
              return True

            def won(self):
              # horizontal
              for y in range(self.size):
                winning = []
                for x in range(self.size):
                  if self.fields[x,y] == self.opponent:
                    winning.append((x,y))
                if len(winning) == self.size:
                  return winning
              # vertical
              for x in range(self.size):
                winning = []
                for y in range(self.size):
                  if self.fields[x,y] == self.opponent:
                    winning.append((x,y))
                if len(winning) == self.size:
                  return winning
              # diagonal
              winning = []
              for y in range(self.size):
                x = y
                if self.fields[x,y] == self.opponent:
                  winning.append((x,y))
              if len(winning) == self.size:
                return winning
              # other diagonal
              winning = []
              for y in range(self.size):
                x = self.size-1-y
                if self.fields[x,y] == self.opponent:
                  winning.append((x,y))
              if len(winning) == self.size:
                return winning
              # default
              return None

            def __str__(self):
              string = ''
              for y in range(self.size):
                for x in range(self.size):
                  string+=self.fields[x,y]
                string+="\n"
              return string

          class GUI:

            def __init__(self):
              self.app = Tk()
              self.app.title('TicTacToe')
              self.app.resizable(width=False, height=False)
              self.board = Board()
              self.font = Font(family="Helvetica", size=32)
              self.buttons = {}
              for x,y in self.board.fields:
                handler = lambda x=x,y=y: self.move(x,y)
                button = Button(self.app, command=handler, font=self.font, width=2, height=1)
                button.grid(row=y, column=x)
                self.buttons[x,y] = button
              handler = lambda: self.reset()
              button = Button(self.app, text='reset', command=handler)
              button.grid(row=self.board.size+1, column=0, columnspan=self.board.size, sticky="WE")
              self.update()

            def reset(self):
              self.board = Board()
              self.update()

            def move(self,x,y):
              self.app.config(cursor="watch")
              self.app.update()
              self.board = self.board.move(x,y)
              self.update()
              move = self.board.best()
              if move:
                self.board = self.board.move(*move)
                self.update()
              self.app.config(cursor="")

            def update(self):
              for (x,y) in self.board.fields:
                text = self.board.fields[x,y]
                self.buttons[x,y]['text'] = text
                self.buttons[x,y]['disabledforeground'] = 'black'
                if text==self.board.empty:
                  self.buttons[x,y]['state'] = 'normal'
                else:
                  self.buttons[x,y]['state'] = 'disabled'
              winning = self.board.won()
              if winning:
                for x,y in winning:
                  self.buttons[x,y]['disabledforeground'] = 'red'
                for x,y in self.buttons:
                  self.buttons[x,y]['state'] = 'disabled'
              for (x,y) in self.board.fields:
                self.buttons[x,y].update()

            def mainloop(self):
              self.app.mainloop()

          if __name__ == '__main__':
            GUI().mainloop()

Copy the above code into a file and save that as “tictactoe.py”. Then execute it using “python tictactoe.py”. Enjoy!

Python3 compatibility and dependencies

The code is fully Python3 compatible, you only need to change the names of the external modules, so that:

from Tkinter import Tk, Button
from tkFont import Font

Becomes:

from tkinter import Tk, Button
from tkinter.font import Font

The packages you need to install on Ubuntu Linux for Python3 may be called “python3” and “python3-tk”. In order to run the code in Python3 you need to use the “python3” command instead of the normal “python” one.

Share

Python performance optimization techniques

If you want to optimize the performance of your Python script you need to be able to analyze it. The best source of information I found on the web is the PerformanceTips page on the Python wiki. We are going to describe two types of performance analysis in Python. The first type uses a stopwatch to time the repeated execution of a specific piece of code. This allows you to change or replace the code and see whether or not this improved the performance. The other is by enabling a profiler that will track every function call the code makes. These calls can then be related, aggregated and visually represented. This type of profiling allows you to identify what part of your code is taking most time. We will show how to do both, starting with the stopwatch type.

Simple stopwatch profiling

You can apply basic stopwatch style profiling using the “timeit” module. It outputs the time that snippet of code takes to execute the specified number of times (in milliseconds), default number of times is one million. You can specify a startup statement that will be executed once and not counted in the execution time. And you can specify the actual statement and the number of times it needs to be executed. You can also specify the timer object if you do not want wall clock time but for example want to measure CPU time.


def lazyMethod(stringParts):
  fullString = ''
  for part in stringParts:
    fullString += part
  return fullString

def formatMethod(stringParts):
  fullString = "%s%s%s%s%s%s%s%s%s%s%s" % (stringParts[0], stringParts[1],
  stringParts[2], stringParts[3],
  stringParts[4], stringParts[5],
  stringParts[6], stringParts[7],
  stringParts[8], stringParts[9],
  stringParts[10])
  return fullString

def joinMethod(stringParts):
  return ''.join(stringParts)

print 'Join Time: ' + str(timeit.timeit('joinMethod()', 'from __main__ import joinMethod'))
print 'Format Time: '+ str(timeit.timeit('formatMethod()', 'from __main__ import formatMethod'))
print 'Lazy Time: ' + str(timeit.timeit('lazyMethod()', 'from __main__ import lazyMethod'))

The output should be something like this:

Join Time: 0.358200073242
Format Time: 0.646985054016
Lazy Time: 0.792141914368

This shows us that the join method is more efficient in this specific case.

Advanced profiling using cProfile

To identify what takes how much time within an application we first need an application. Let us profile a very simple Flask web application. Below is the code of a very simple “Hello World” application in Flask. We replaced “app.run()” with “app.test_client().get(‘/’);” to make the application run only the one request.

from flask import Flask

app = Flask(__name__)

@app.route("/")
def hello():
  return "Hello World!"

if __name__ == "__main__":
  #app.run()
  app.test_client().get('/');

Running the application with the profiler enabled can be done from the command line, so there is no need to change the code. The command is:

python -m cProfile -o flask.profile flaskapp.py

Visualizing cProfile results

RunSnakeRun is a GUI tool by Mike Fletcher which visualizes profile dumps from cProfile using square maps. Function/method calls may be sorted according to various criteria, and source code may be displayed alongside the visualization and call statistics.” – source: Python PerformanceTips

We are now analyzing the generated “flask.profile” file by running the “runsnake” tool using with following command:

runsnake flask.profile

It gave us some real nice insights:

profile_results_miliseconds_small

Picture 1: The visual output of RunSnakeRun

profile_results_miliseconds_expensive_calls

Picture 2: The list of function calls shows 77 calls to the regex library (re.py) acounting for only 0.5 of the 79 ms.

profile_results_miliseconds_call_map

Picture 3: A map showing all calls, the rectangle in the upper right (testing.py) is the test client running.

We showed you how to profile your Python application, now go practice and optimize your code. One advice though: go for low hanging fruit only, because over-optimized code is not Pythonic.

Share