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.
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
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.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 : bestMoveNodes =  bestMoveNodes.append(moveNode) elif moveNode == bestMoveNodes : bestMoveNodes.append(moveNode) return [node.move for node in bestMoveNodes]
There are three cases here. If the
bestMoveNodes variable is empty, then append
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
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.
2015-05-10 04:38 +0000