Ceasar's Mind

Follow me: @Ceasar_Bautista

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.

Advertisements

Written by Ceasar Bautista

2010/06/28 at 19:03

One Response

Subscribe to comments with RSS.

  1. I have been investigating chess, machine learning, and artificial intelligence for quite some time. The areas of investigation have been knowledge based approaches such as Wilkins and Bratko, inductive logic programming by Morales, and reinforcement learning. A recent paper from NIPS 2009 called Bootstrapping from Game Tree Search will be interest to you.

    Best wishes with your research.

    aiguy

    2010/07/04 at 20:54


Comment

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s