Recently, I made a chess program in Python and published the source on github here. The code is just under 1000 lines, about 20% of which is dedicated to the AI. In this post I’ll cover how the AI works, what each part does. and why it works like that. You can just read through, or download the code and mess around with it as you read. The AI is all in the AI.py file, although it might help to look at the other files to see what the classes that the AI depend on do.

An overview of the AI

The AI goes through three distinct steps when it’s deciding on what move to make. First, it finds all the legal moves that it can make (usually 20-30 moves early on in the game down to just a few later on). Second, it generates a tree of moves which it will use later to decide on the best move. The tree of moves can be any depth, although it grows exponentially every time the depth is incremented. Assuming there are an average of 20 moves each turn, a depth of 1 would be 20 moves, a depth of 2 would be 400, a depth of 3 would be 8000, etc. Finally, it traverses the tree and determines what move will result in the best point advantage after x moves, x being the chosen depth. For the rest of the article I’ll assume the chosen depth is 2 for simplicity’s sake.

Generating the move tree

The move tree is the core of the AI. The class which the tree of composed of is the MoveNode class, in the MoveNode.py file. The init method looks like this :

def __init__(self, move, children, parent) :
   self.move = move
   self.children = children
   self.parent = parent
   pointAdvantage = None
   depth = 1

There are five attributes in this class. The first is move, the move it contains (this is an instance of a class in Move.py). The Move class isn’t very important here, just know that it is a move that tells a piece where to go, what to capture, etc. The second is children, which are also of type MoveNode. The third attribute of this class is parent, so it can know what MoveNodes are above it. The attribute pointAdvantage is what the AI uses to determine if a move is ‘good’ or not. The attribute depth is how deep the node is, i.e. how many nodes are above it, plus one. The code to generate the move tree is as follows:

def generateMoveTree(self) :
    moveTree = []
    for move in self.board.getAllMovesLegal(self.side) :
        moveTree.append(MoveNode(move, [], None))

    for node in moveTree :
        self.board.makeMove(node.move)
        self.populateNodeChildren(node)
        self.board.undoLastMove()
    return moveTree

The moveTree variable starts out as an empty list, then it is populated with objects which are instances of the MoveNode class. After the first loop it’s just an array of MoveNodes which have no children or parents, as they are the ‘root’ nodes. The second loop iterates over the moveTree, and populates each node with it’s children, with the populateNodeChildren function :

def populateNodeChildren(self, node) :
    node.pointAdvantage = self.board.getPointAdvantageOfSide(self.side)
    node.depth = node.getDepth()
    if node.depth == self.depth :
        return

    side = self.board.currentSide

    legalMoves = self.board.getAllMovesLegal(side)
    if not legalMoves :
        if self.board.isCheckmate() :
            node.move.checkmate = True
            return
        elif self.board.isStalemate() :
            node.move.stalemate = True
            node.pointAdvantage = 0
            return

    for move in legalMoves :
        node.children.append(MoveNode(move, [], node))
        self.board.makeMove(move)
        self.populateNodeChildren(node.children[-1])
        self.board.undoLastMove()

This function is recursive, and so it’s a bit harder to visualize. It’s initially passed a MoveNode object. That MoveNode object will have a depth of 1, since it has no parent. We’re still assuming the AI has been assigned a depth of 2. The node that gets passed to this function first will therefore skip the first if statement.

Then, all legal moves are determined, which is outside of the scope of this post, but the code is all on Github if you want to check it out. The next if statement checks if there are any legal moves. If there are not any, then it’s either checkmate or stalemate. If it’s checkmate, set the node.move.checkmate attribute to True and return, since there can’t be any further moves made. Stalemate is similar, although node.pointAdvantage is also set to 0 since neither side has any advantage.

If it was not checkmate or stalemate, then the moves in the variable legalMoves are all added to the node’s children as MoveNodes, and the function is called to populate those children with their own MoveNodes.

When the depth of the node is equal to self.depth (2 in this example), nothing is done, and the node’s children are left as an empty array.

Traversing the tree

Now that we have a tree with MoveNodes, we need to traverse it and find the best move. The logic for this is kind of tricky, and it took a while for me to come up with it (before realizing it’s a well established algorithm and I should really use Google more often), so I’ll try to explain it as fully as I can. Let’s say this is our move tree :

If the AI was really dumb and only had a depth of 1, it would go for bishop takes rook, resulting in a gain of 5 points and a total advantage of +7. Then on the next move a pawn would take it’s queen and now it’s gone from +7 to -2 because it didn’t look ahead to the next move.

Now let’s say it has a depth of 2. It would see that choosing queen takes knight results in a score of -4, and moving the queen results in a score of +1. Therefore, it chooses to move its queen.

So we have to choose the best move when it’s the AI’s turn, and assume the opponent will choose the worst move (from the AI’s perspective) during his turns. Here’s how that’s implemented :

def getOptimalPointAdvantageForNode(self, node) :
    if node.children:
        for child in node.children :
            child.pointAdvantage = self.getOptimalPointAdvantageForNode(child)

        #If the depth is divisible by 2, it's a move for the AI's side, so return max
        if node.children[0].depth % 2 == 1 :
            return(max(node.children).pointAdvantage)
        else :
            return(min(node.children).pointAdvantage)
    else :
        return node.pointAdvantage

This is also a recursive function, so it’s not obvious what it does at first glance. There are two cases, either the node has children or it doesn’t. Assume the move tree is exactly how it is in the picture earlier (in a real game there would be many more nodes per branch).

In the first case, the node has children. Take the first move for example, Q takes N. The depth of its child is 2, so 2 % 2 will not be equal to 1. This means that child contains a move for the opponent, so return the minimum move (assume the opponent makes the worst move for the AI, aka the best move for the opponent).

The node’s children will not have children themselves, since we’re assuming a depth of 2. Therefore, they return their actual point value (-4 and +5 for the children of the first move). The minimum of these is -4, so the first move, Q takes N, is given a value of -4.

These steps are repeated for the other two moves, moving the queen is given a score of +1, and bishop takes rook is given a score of -2.

Choosing the best move

The hard work is out of the way now, and all the AI has to do is choose from the moves that have been given the highest values, like so :

def bestMovesWithMoveTree(self, moveTree) :
    bestMoveNodes = []
    for moveNode in moveTree :
        moveNode.pointAdvantage = self.getOptimalPointAdvantageForNode(moveNode)
        if not bestMoveNodes :
            bestMoveNodes.append(moveNode)
        elif moveNode > bestMoveNodes[0] :
            bestMoveNodes = []
            bestMoveNodes.append(moveNode)
        elif moveNode == bestMoveNodes[0] :
            bestMoveNodes.append(moveNode)

    return [node.move for node in bestMoveNodes]

There are three cases here. If the bestMoveNodes variable is empty, then append the moveNode regardless of its value. If the value of moveNode is higher than the value of the first element of bestMoveNodes, clear the list and append moveNode to it. If the value of moveNode is the same, then append it to the list.

Now all that’s left to do is choose a random move from the best moves (this is mostly for the beginning of the game, when most moves will have the same value, so we don’t want the AI doing the same thing every time).

bestMoves = self.bestMovesWithMoveTree(moveTree)
randomBestMove = random.choice(bestMoves)

That’s all there is to it. The AI generates a tree, populates it with children to an arbitrary depth, traverses the tree to find the value of each move, then randomly selects one of the best. There’s various optimizations to make from here; pruning, razoring, quiescence search, etc., but hopefully this post gave a good idea of how a basic, brute-force chess AI can work.