Learning Python

Like many other people, I decided to learn Python so that I could give Google App Engine a try (and I did not want to “cheat” by getting my Java code automatically translated to Python). In order to get a feel for the language, I wrote a simple Tic-tac-toe game. I thought this example might be useful for others to get a quick overview of some of the highlights and peculiarities of Python, especially if you are more used to statically typed languages like I am. For a more detailed introduction, check out the official Python Tutorial or Dive Into Python.

Defining a class

Although Python is not specifically an object-oriented language, it does support OOP to a certain extent. So I created a couple of classes to represent the tic-tac-toe game. Let’s start with a class for the grid-shaped game board:


class Board:
    def __init__(self, size, symbol1, symbol2):
        self.size = size
        self.symbol1 = symbol1
        self.symbol2 = symbol2
        self.grid=[size * [' '] for i in range(size)]

Indentation

One thing I had to get used to with Python is the significance of code formatting. While it’s common for scripting languages to attach meaning to line breaks, I have never come across a language where even the level of indentation affects the semantics of the code. In the example above, the first line starts the definition of the Board class, and all subsequent lines with a higher indentation level are treated as part of the class definition. The second line defines the __init__ method, which becomes part of the Board class since it is indented. The subsequent lines are even more indented, which means that they form the body of the __init__ method.

Methods

Methods and functions are defined using the def keyword. The special name __init__ identifies the constructor, which is called when an instance of the class is created. There is no special keyword to refer to the current instance within a method (like the keyword this in Java, C# and C++). Instead, the instance is passed to the method as its first parameter, which by convention is called self. Function parameters and variables are untyped and can be assigned values of any type at runtime. However, the above code was written with the intention that size is an integer specifying the width and height of the grid, while symbol1 and symbol2 should be single-character strings containing the symbols used by the two players. So for the standard tic-tac-toe game, these parameters would be set to 3, ‘O’ and ‘X’.

Working with lists

The last line in the code snippet above initializes a data structure to represent the grid for the tic-tac-toe game. It makes use of several Python features for working with lists. List literals are written as comma-separated values enclosed in square brackets. The expression [' '] creates a list that contains a space character as its only element. Lists can be multiplied with integers, so if size is 3, the expression size * [' '] is equivalent to [' ',' ',' '] (a list with 3 elements, each of which is a single space character). This gives us one row for our grid. The next step is to put several such rows into another list to represent the whole grid. This is done using a Python feature called list comprehensions:

[size * [' '] for i in range(size)]

Within the outer pair of brackets, the expression before the for keyword is evaluated once for each iteration defined by the for clause, and the results from all iterations are collected in a new list. The range function returns a list containing the numbers from 0 to size – 1, and the expression for i in range(size) defines an iteration over these numbers. So the above expression creates a list with size elements, each of which is another list containing size individual space characters.

Object equality and ordering

So far our game board contains an empty grid (filled with spaces). Before we add methods to manipulate the board, let’s define a class to represent a move that a player can make in the game. A move is defined by the row index and column index of the grid cell that the player fills with his or her symbol:


class Move:
    def __init__(self, row, column):
        self.row = row
        self.column = column

    def __cmp__(self, other):
        if self.column == other.column:
            return self.row - other.row
        else:
            return self.column - other.column

In addition to a constructor identified by the special name __init__, this class contains another special method named __cmp__. This method is called whenever instances of this class need to be compared for ordering or equality. In Java terms, implementing this method is equivalent to overriding the Object.equals method and implementing the Comparable.compareTo method in a consistent way. Just like the latter, this method should return a negative integer, zero, or a positive integer depending on whether the object should be considered less than, equal to, or greater than the other object, respectively. For classes that represent value objects, it usually makes sense to implement this method, so that things like set membership work as expected.

The body of the __cmp__ method above shows how the if statement looks in Python. Again, it is important to indent the statements in the if and else clauses properly.

Working with class instances

With the Move class defined as above, we can now add the following methods to the Board class:


    def possibleMoves(self):
        moves = []
        for row in range(self.size):
            for column in range(self.size):
                if self.grid[row][column] == ' ':
                    moves.append(Move(row, column))
        return moves

    def applyMove(self, move, symbol):
        self.grid[move.row][move.column] = symbol

    def undoMove(self, move, symbol):
        self.grid[move.row][move.column] = ' '

The possibleMoves method returns a list of Move objects representing all the grid positions that are available for the next move. It iterates over all grid positions using two nested for loops, which work in a similar way to the enhanced for loop in Java and the foreach loop in C#.

A list element is accessed by writing its index in brackets. Since we represent our grid as a list of lists, the element at a specific row and column is accessed with the expression self.grid[row][column], in the same way as elements of two-dimensional arrays are accessed in Java. If the element is empty (represented by a space character), a corresponding Move instance is created and appended to the list of possible moves. An instance of a class is created by simply writing the name of the class followed by the argument list for its constructor (like in Java and C#, but without the new keyword).

Duck typing

The applyMove method simply stores the given symbol in the grid cell identified by the given Move instance. Actually, since method parameters are untyped, there is nothing that defines that the move parameter must be an instance of the Move class. In fact, it doesn’t need to be. It could be any object that has members named row and column containing integer values. This is an example for the duck typing that Python supports.

Generator expressions

Now we have a game board that accepts moves from the players, but we still need a way to determine when the game is over and who the winner is. So let’s first add a method to the Board class to determine whether the given symbol occupies a complete row, column or diagonal and therefore wins the game:


    def isWinner(self, symbol):
        # check for completely filled rows or columns
        n = self.size
        for i in range(n):
            if (n == self.grid[i].count(symbol)
            or n == sum(1 for j in range(n)
                        if self.grid[j][i]==symbol)):
                return True
        # check diagonals
        return (n == sum(1 for i in range(n)
                         if self.grid[i][i]==symbol)
        or n == sum(1 for i in range(n)
                    if self.grid[i][n-1-i]==symbol))

To determine whether row number i is filled with the given symbol, we use the expression self.grid[i] to get the list corresponding to this row and then call the count method to determine the number of elements in this list that are equal to the given symbol. Unfortunately we cannot use the same approach to check for complete columns, since each column’s elements are spread out across multiple lists. Of course we could just use a nested for loop to iterate over a column’s elements in these different lists. But I decided to make use of a nice Python feature called generator expressions instead. These are similar to the list comprehensions mentioned above, but instead of creating a complete list of values produced by an expression, they produce the values incrementally as they are processed by the surrounding expression. The following generator expression produces a sequence in which the value 1 is repeated as many times as the symbol appears in column i:

(1 for j in range(n) if self.grid[j][i]==symbol)

Applying the built-in sum function to this expression then yields the number of occurrences of the symbol in the column. Similar expressions are also used to check whether the diagonals are completely filled with the symbol.

Invoking methods

Finally, the last method in the Board class determines whether the game is over by checking if any of the two players has won or if no more move is possible because the board is filled completely:

    def isGameOver(self):
        return (self.isWinner(self.symbol1)
                or self.isWinner(self.symbol2)
                or self.possibleMoves() == [])

Note how methods are invoked using dot notation, with the instance (in this case self) before the method name, even though in the method definition it appears as the first parameter after the method name. In general, a method defined as

def method(self, param1, param2, ...)

is invoked like this:

obj.method(arg1, arg2, ...)

Inheritance

The Board class is now complete in that it encapsulates the rules of the game and the effects that individual moves have on the state of the game. What we need now is something that determines what move to make in a given state. That’s the job of the players, so let’s define a class hierarchy of players reflecting different strategies for playing the game. Here is the Player class containing common functionality and the RandomPlayer class that determines its next move by randomly choosing one of the possible moves:


import random

class Player:
    def __init__(self, symbol):
        self.symbol = symbol

    def __str__(self):
        return self.symbol

class RandomPlayer(Player):
    def nextMove(self, game):
        moves = game.board.possibleMoves()
        return moves[random.randrange(len(moves))]

The Player class keeps track of the player’s symbol (‘O’ or ‘X’). In a static language, this class would also contain an abstract declaration of the nextMove method, which must be implemented by subclasses and returns the player’s next move based on the given state of the game. But in Python with its dynamic typing, there is no need (or support) for abstract methods. We just need to remember to define such a method in every subclass, without being forced to do so by the compiler.

The Player class contains another special method named __str__. This method corresponds to the toString method in Java, or ToString in C#. It is called when a string representation of an object is needed, for example when using the print statement.

The RandomPlayer class is derived from the Player class. Unlike in Java, C# and C++, constructors in Python are inherited by derived classes. So even though the above definition of the RandomPlayer class contains no __init__ method, an instance of RandomPlayer can be created using an expression like RandomPlayer('X'), which calls the __init__ method defined in the Player class, causing the argument to the stored in the symbol member variable.

Modules

The import statement in the first line of the code snippet above loads the random module, a standard Python module providing pseudo-random number generator functions. Modules are basically Python source files. Unlike the import statement in Java (which only imports the names of classes so that they can be referred to by their simple names rather than their fully-qualified names), the import statement in Python actually loads and executes the code from the module (note: modules mostly contain class and function definitions, and executing them only creates and adds class/function objects to the symbol table, but does not execute the code inside the functions). Names from an imported module still need to be prefixed with the module name: in the last line of the code snippet above, random.randrange refers to the randrange function defined in the random module.

The nextMove method in the RandomPlayer class above expects as its parameter a game object, which should be an instance of the Game class:

class Game:
    def __init__(self, size, player1, player2):
        self.board = Board(size, player1.symbol,
                           player2.symbol)
        self.active = player1
        self.other = player2
        self.winner = None
        self.observers = []

    def run(self):
        self.notifyObservers()
        while not self.board.isGameOver():
            self.applyMove(
                self.active.nextMove(self))

    def applyMove(self, move):
        self.board.applyMove(move,
                             self.active.symbol)
        if self.board.isWinner(self.active.symbol):
            self.winner = self.active
        self.active,self.other=self.other,self.active
        self.notifyObservers()

    def notifyObservers(self):
        for observer in self.observers:
            observer(self)

    def addObserver(self, observer):
        self.observers.append(observer)

    def removeObserver(self, observer):
        self.observers.remove(observer)

The run method contains the main loop of the game, which keeps asking the active player for the next move until the game is over. For each move, it calls the applyMove method, which applies the move to the board and keeps track of the winner and the active player. It uses a multiple assignment to swap the active player with the other player.

Functions

The Game class uses the observer pattern to notify interested parties about changes to the game state. The observers list contains function objects, which are invoked by the notifyObservers method whenever the game state changes. Observer function objects can be added and removed by calling the methods addObserver and removeObserver, respectively. Let’s define an observer function that displays the current board on the console:


import string

def printBoard(game):
    n = game.board.size
    rowChars = string.digits[1:n+1]
    columnChars = string.ascii_lowercase[:n]
    print '   ' + '   '.join(columnChars)
    print ' ' + '-' * (n * 4 + 1)
    for i, row in enumerate(game.board.grid):
        print rowChars[i] + '|',
        print ' | '.join(row),
        print '|' + rowChars[i]
        print ' ' + '-' * (n * 4 + 1)
    print '   ' + '   '.join(columnChars)
    if game.board.isGameOver():
        print "Game over!"
        if game.winner is None:
            print "No winner!"
        else:
            print "The winner is", game.winner

Working with strings

The printBoard function uses string operations and the print statement to create a visual representation of the game board. Using slice notation and some predefined string constants, the expressions string.digits[1:n+1] and string.ascii_lowercase[:n] evaluate to the digits 1 to n and the first n letters in the alphabet, respectively. These characters are then used to identify the rows and columns of the board, as in algebraic chess notation. The built-in join method is used to concatenate the elements of a row with the given separator. The for loop in the printBoard function makes use of the built-in enumerate function which returns a tuple of index and value for each element in a sequence.

Here is a function that runs a game with the printBoard function as an observer, causing the current board to be printed to the console after every move:


def runGame(game):
    game.addObserver(printBoard)
    game.run()

Now we can let two instances of RandomPlayer play against each other and follow their moves on the console:


runGame(Game(3,RandomPlayer('O'),RandomPlayer('X')))

Exceptions

Watching the computer play against itself may get a bit boring, so let’s define another player class that lets the user choose the next move by typing the desired coordinates into the console:

import string

class ConsolePlayer(Player):
    class InputError(Exception):
        def __init__(self, message):
            self.message = message

    def nextMove(self, game):
        while True:
            input = raw_input("Your move please, " +
                      "player " + self.symbol + ": ")
            try:
                m = self.parseMove(input.strip(),
                                   game.board);
                if m in game.board.possibleMoves():
                    return m
                else:
                    print "Position already taken!"
            except self.InputError, e:
                print e.message

    def parseMove(self, input, board):
        if len(input) != 2:
            raise self.InputError("Please enter " +
                    "exactly two characters " +
                    "(without spaces)")
        n = board.size
        column = input[0].lower()
        columnChars = string.ascii_lowercase[:n]
        if column not in columnChars:
            raise self.InputError("First character" +
                    " must be one of these: " +
                    columnChars)
        row = input[1]
        rowChars = ''.join(string.digits[1:n+1])
        if row not in rowChars:
            raise self.InputError(
                    "Second character must be " +
                    "one of these: " + rowChars)
        return Move(rowChars.index(row),
                    columnChars.index(column))

The ConsolePlayer class is declared as a subclass of the Player class defined earlier, and it contains a nested definition of another class, InputError, which is derived from the built-in Exception class. This exception is used internally by ConsolePlayer to handle errors in the user input.

Recall that the Game class calls a player’s nextMove method whenever it is that player’s turn. The ConsolePlayer‘s implementation of the nextMove method uses the built-in function raw_input to let the user enter the desired grid position. The parseMove method is then called to interpret the input. It uses string manipulation functions to map an input string like “b3” (letter for a column, digit for a row) to the corresponding column and row indices and returns an instance of the Move class. If the input string is not in the expected format, an InputError is raised. This exception is then caught in the nextMove method by the try/except block surrounding the call to parseMove. So the exception handling in Python seems quite similar to Java, just the syntax is slightly different. And of course there is no such thing as checked exceptions in a dynamic language.

Now we can let the user play against the computer by using a ConsolePlayer instance and a RandomPlayer instance:


runGame(Game(3,ConsolePlayer('O'),RandomPlayer('X')))

OK, I think this was enough Python for today. You can get the full source code for this example from my Subversion repository or download it as a zip file. It was developed using Eclipse with the PyDev plugin. Of course there are a lot of interesting features in Python that I didn’t mention or haven’t even discovered yet. I am going to continue exploring the Python language and the available libraries, especially Google App Engine. I am planning to turn the tic-tac-toe game into a web application using Google App Engine and blog about my experience, so please stay tuned.

Bonus

In case you still want to see more Python code, here is another automated player that makes a stronger opponent than the RandomPlayer. It uses a brute force approach to find the best possible move by recursively evaluating all paths through the game. Caution: While it takes only about 1 second for this algorithm to find the best move on a 3×3 board, it would take something in the order of 1 year on a 4×4 board, because the number of possible paths grows exponentially with the number of grid elements.


class BruteForcePlayer(Player):
    def nextMove(self, game):
        bestMove = self.findBestMove(game.board,
                     self.symbol, game.other.symbol)
        return bestMove[0]

    def findBestMove(self, board, active, other):
        if (board.isGameOver()):
            if (board.isWinner(active)):
                return (None, 1)
            elif (board.isWinner(other)):
                return (None, 0)
            else:
                return (None, 0.5)
        else:
            bestMove = (None, -1)
            for move in board.possibleMoves():
                board.applyMove(move, active)
                score = 1 - self.findBestMove(board,
                                other, active)[1]
                board.undoMove(move, active)
                if score > bestMove[1]:
                    bestMove = (move, score)
                if bestMove[1] == 1:
                    break
            return bestMove
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: