# Ceasar's Mind

## Chess & Artificial Intelligence

with one comment

So I’ve been developing artificial intelligence for a computer chess game recently, and I thought the subject was interesting as it related to design and decision making. For now I’ll just explain the basics and then go on with my thoughts in future posts.

The Basics

The actual AI works rather simply. For a depth of one ply, or a turn for a single player, the AI moves a piece, scores the position based on mobility and piece count, moves the piece back, and repeats with all the possible moves in a given position. It then sorts all of the scores, takes the best score, and makes what it has determined to be the best move.

A deeper search is slightly more intense. For two ply, it makes a move, makes another move, scores the position, undoes the last move, and then searches the rest of the alternatives until it finds the best. From there, the AI assigns the best score to the initial move. (It’s worth noting that since it would be the opponent’s turn at that point, the best move is the worst for the AI.) The AI repeats the whole process with each of its alternatives, that is, finding the opponent’s best response, and then determines what its best move is. The basic idea is the same for a depth for any amount of ply.

Now theoretically, you could solve chess by just setting the depth to infinity and playing all games through to their end. However, on average, in any given position their are on average about 40 moves available. Every extension of the depth therefore increases the amount of positions searched by 40-fold for a total of 40^n. In other words, the amount of positions to be searched gets very big, very fast. (Too big for computers to compute anywhere near reasonably, a statement I’ve come to understand through experience.) In fact, the amount of time spent searching is often so unreasonable that the program must be either executed on impressive hardware or be set to play at a very dumb level- Otherwise, it’ll end up taking hours or even days per move.

Obviously though, that’s not exactly the case- Quite a few chess programs exist that play at a reasonable pace and superb strength. The solution, at least in terms of making something that can beat the grandmasters, is to not look at all the moves. Or rather, only look at the moves worth looking at. (The process is known as “pruning”.) Basically, the idea is that certain moves would be a waste of time to search, so we can ignore them. And less positions to score means that the AI will work faster, allowing it to search deeper. More on that in the next post though.

Written by Ceasar Bautista

2010/06/28 at 19:03