Ceasar's Mind

Follow me: @Ceasar_Bautista

Posts Tagged ‘chess

Alpha Beta Pruning

with 3 comments

The most significant improvement that can be made to the AI is the implementation of alpha beta pruning. Alpha beta pruning basically evaluates the board the same way that human minds do and allows both us and computers to save drastic amounts of time when figuring out the best move.

How it Works

If I analyze a move and my opponent’s best response leads to a position that is equal and then I start analyzing another position and see at one point that my opponent has a response that is worse than equal for me, then I immediately stop looking at that move since I know that I could always just play my original move and end up with a better game. Analyzing my opponent’s alternatives would be a waste since I knew I’d wouldn’t be playing the move when I found that first response that was bad for me. Alpha beta works exactly the same way.

Let me put that in concrete terms- If for example, I analyze a Knight move and see that at best my opponent can’t do better than equalize, and then I start analyzing an alternative, say,  my Queen capturing a guarded enemy Pawn, I don’t have to analyze all the moves that my opponent has in response to my Queen capturing his Pawn if I see that he can simply capture my Queen. (Remember, I could always just play my Knight move.) For three ply though, it gets a little bit more tricky. For example, if I make a pawn move, my opponent makes a pawn move, and I capture a Knight, my opponent probably won’t make that pawn move if a different move would save the Knight (or maybe even capture one of mine). Of course, I can always reject my initial pawn move though, so it can get a little tricky.

Back to the pruning idea though: Alpha and beta both represent numbers. Alpha I assign to my best move (and let’s say I am playing black). So every time it’s white’s turn, I go through all the responses, score them, and assign the best score to alpha. Then I start checking white’s next alternative and all of my responses. If I find one that scores higher than alpha, I stop looking at that move. White won’t play it. If however, I find no response better than alpha, if they’re all worse for example, then I find the best of them and set that as the new alpha. In this way, I find my worst best move.

Beta on the other hand, keeps the tab for white. I do the same thing, except I look for scores worse than beta.

Here is basically the code I use, all written in Java.  (My actual code has some ugly stuff to make it work in the context I’m using it.) And here is an excellent link that also explains the idea, but more importantly, it has an interactive application on the bottom that shows how the algorithm works if I haven’t explained it fully.

Alpha Beta pruning reduces the amount of searching drastically. However, to get the full effect, one last improvement has to be made. Since the order of the moves to be searched affects when a search will be terminated, it’s best to sort the moves (I believe at each level) from strongest to weakest. This indeed involves scoring every possible position (minus those at the last ply to be searched), but I found that it is still far more efficient. The only level not worth sorting is the final level, at depth 0, since that’s where the alpha beta pruning kicks in (reducing the need to score everything).

Anyhow, I hope this all makes sense.

Advertisements

Written by Ceasar Bautista

2010/06/28 at 21:31

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