How To Make The AI Faster

EasyAI has been written with clarity/simplicity and in mind, rather than speed. In this section we will see how to make the AI run faster with a few refinements in the way the game is defined.

• Profile your code !
• Optimize (avoid recomputing things that have already been computed).
• For the most computer-intensive parts use fast libraries or code in C/Cython.

Let’s play Connect 4

So let’s start. We want to play Connect 4 (rules) against the computer.

I chose this game because the implementation given in easyAI (see section Connect 4) is really not optimized: we will show that it can be sped up 25 times.

We load the game and start a match, with the following code:

from easyAI.games import ConnectFour
from easyAI import Human_Player, AI_Player, Negamax

ai = Negamax(7) # AI thinks 7 moves in advance
game = ConnectFour( [ AI_Player(ai), Human_Player() ])
game.play()

We launch the script, and the computer plays after nine seconds... nine seconds !!! I mean, even in the 1990s it was considered slow ! So let’s see what we can do about that.

First we profile the AI with:

import cProfile
cProfile.run("game.play(1)") # play one move, stop the game, profile

This will print every function used to play the first move, and the time taken by each function.

Cythonize what you can

The results of cProfile are clear: 6.7 of the 9 seconds are spent computing the function find_four, which checks whether there are 4 connected pieces in the board. This is not the kind of function that python likes (many for and while loops) so we will rewrite this function in a faster language. You can write it in C and link it to python, but for this example I prefer to write it in Cython, because it integrates well with Python and the iPython Notebook (Cython code). After the function is rewritten, we run again

import cProfile
cProfile.run("game.play(1)") # play one move and profile

Now it takes 2.7 seconds !

Use unmake_move

So what is the next bottleneck ? Apparently the function deepcopy is called a lot and takes a total of 1.4 seconds.

This problem is very much linked with the way easyAI works: when the AI thinks a few moves in advances, it creates whole copies of the entire game, on which it can experiment. In our case the AI has created 35000 copies of the game, no wonder it was slow.

A better solution is to perform a move directly on the original game, and once the move is evaluated, undo the move and continue with the same game. This is very easy to do with easyAI, all we have to do is to add a method called unmake_move to the class ConnectFour, which explains how to cancel a given move:

def unmake_move(game, column):
    """ Unmake a move by removing the last piece of the column """
    line = (6 if (game.board[:, column].min()>0) else
        np.argmin( game.board[:, column] != 0) )
    game.board[line-1, column] = 0

Now as expected cProfile tells us that our program runs in 1.2 seconds. Note that for some games undoing a move knowing just the move is not easy (sometimes it is even impossible).

Don’t look twice if you have lost

Now the function Connect4.lose() is responsible for half of the duration. This is the method which calls find_four, to see if the opponent has won. Connect4.lose() is really not called efficiently: first the AI checks if the player has lost with Connect4.lose(), in order to know if the game is over (method is_over), then it computes a score, and for this it calls the function scoring, which will also call Connect4.lose().

It would be better if is_over could directly tell to scoring something like we have lost, I already checked. So let’s rewrite these two functions:

def lose(self):
    """ You lose if your opponent has four 'connected' pieces """
    self.haslost = find_four(self.board,self.nopponent) # store result
    return self.haslost

def scoring(game):
    if game.haslost !=None:
        haslost = game.haslost # use the stored result of ``lose``.
        game.haslost = None
        return -100 if haslost else 0
    else:
        return -100 if game.lose() else 0

Now that Connect4.lose() is called less our program runs in 0.74 seconds.

Use transposition tables

Transposition tables store the values of already-computed moves and positions so that if the AI meets them again it will win time. To use such tables is very easy. First you need to tell easyAI how to represent a game in a simple form (a string or a tuple) to use as a key when you store the game in the table. In our example, the game will be represented by a string of 42 caracters indicating whether the different positions on the board are occupied by player 1, by player 2, or just empty.

def ttentry(self):
    return "".join([".0X"[i] for i in self.board.flatten()])

Then you simply tell the AI that you want to use transposition tables:

from easyAI import TT
ai = Negamax(7, scoring, tt = TT())

The AI now runs in 0.4 seconds !

Transposition tables become more advantageous when you are thinking many moves in advance: Negamax(10) takes 2.4 seconds with transposition tables, and 9.4 second without (for Connect 4 it is known that the tables help the AI a lot. In some other games they might be useless).

Solve the game first

Not all games are solvable. But if it is possible to fully solve a game, you could solve it first, then store the results for use in your program. Using the GameOfBones example

tt = TT()
GameOfBones.ttentry = lambda game : game.pile  # key for the table
r,d,m = id_solve(GameOfBones, range(2,20), win_score=100, tt=tt)

After these lines are run the variable tt contains a transposition table storing the possible situations (here, the possible sizes of the pile) and the optimal moves to perform. With tt you can play perfectly without thinking:

game = GameOfBones( [  AI_Player( tt ), Human_Player() ] )
game.play()  # you will always lose this game :)

One could save the solved transposition table to a file using a python library such as pickle. Then, your program need not recalculate the solution every time it starts. Instead it simply reads the saved tranposition table.

Conclusion

Now there are no obvious ways to gain significant speed. Maybe speeding up Python in general by using an optimized compiler like PyPy could help win a few more percents. But if you really want a fast and smart AI you may also consider other strategies like mixing algortihms, using opening books, etc.