Hi all, I am currently writing a chess program with AI. The AI uses minimax with alpha-beta pruning going to a depth of 4 plies. Using this, it takes the computer about 5 minutes to make a move, which I think is extremely slow. Does this seem like a reasonable amount of time for the computer to search through 4 plies, or is it more likely that there must be something wrong/inefficient with my current alpha-beta algorithm?

In any case, I would also like to further optimize my AI via iterative deepening which will sort the moves in way to reduce the number of nodes searched, but I am not sure how to go about implementing this. For instance, how will I store the sorted moves in each of the nodes for later use?

Any input would be greatly appreciated!

Quote: Original post by Artichoker
Hi all, I am currently writing a chess program with AI. The AI uses minimax with alpha-beta pruning going to a depth of 4 plies. Using this, it takes the computer about 5 minutes to make a move, which I think is extremely slow. Does this seem like a reasonable amount of time for the computer to search through 4 plies, or is it more likely that there must be something wrong/inefficient with my current alpha-beta algorithm?

Five minutes does sound a bit slow for only 4 plies. I would suspect something wrong with the pruning portion of your algorithm.

I'm not all that familiar with chess AI, but what other optimizations have you been looking into?

A depth-4 search in chess should take less than one second.

Assuming a branching factor of 40 (it's probably a bit less most of the time for chess), a depth-4 search would have around 2.6Mnodes. If it's taking you 5 minutes, it means you are visiting less than 10Knodes per second, which is very slow.

There are two important things I left out of that computation:
(1) Alpha-beta, which should dramatically reduce the number of nodes you need to visit (to something like 10Knodes), but this is highly dependent on the order in which you visit the moves.
(2) Quiescence search, which requires you to make a little search at each leaf of the tree. This might require you to search some multiple of the nodes (I don't know, five times more perhaps?). I don't know if you have implemented quiescence search yet, but you should.

You can count how many nodes you are visiting. Do this for depths 1, 2, 3 and 4. That should give us an idea of how broken your program might be.

Hi, thanks for your responses.

Omega, I have not really looked at too many observations because (as you and alvaro seem to have confirmed) I suspected there must be something wrong with my initial algorithm.

Quote: Original post by alvaro
A depth-4 search in chess should take less than one second.

Assuming a branching factor of 40 (it's probably a bit less most of the time for chess), a depth-4 search would have around 2.6Mnodes. If it's taking you 5 minutes, it means you are visiting less than 10Knodes per second, which is very slow.

There are two important things I left out of that computation:
(1) Alpha-beta, which should dramatically reduce the number of nodes you need to visit (to something like 10Knodes), but this is highly dependent on the order in which you visit the moves.
(2) Quiescence search, which requires you to make a little search at each leaf of the tree. This might require you to search some multiple of the nodes (I don't know, five times more perhaps?). I don't know if you have implemented quiescence search yet, but you should.

You can count how many nodes you are visiting. Do this for depths 1, 2, 3 and 4. That should give us an idea of how broken your program might be.

Thanks for your insight alvaro. With my current algorithm (which involves alpha-beta but does not have a quiescence search):
- the first depth visited 20 nodes and that took less than a second.
- the second depth visited 640 nodes and took around 2 seconds.
- the third depth visited 3344 nodes and took around 4 seconds.
- the fourth depth visited 76401 nodes and took around 2 minutes (I guess I was exaggerating, but 2 minutes is still a lot, according to you, and I agree).

Do the number of nodes visited look correct? They seem roughly correct to me, as the average branching factor for chess is 30 (although closer to 20 for the first couple of moves) and it has alpha beta pruning, so less nodes will be visited... which is why the enormous amount of time it is taking is disturbing...

Also, I will take a look at trying to implement a quiescence. I have heard of it but am not sure what it does. Is it an optimization?

Make sure you're testing the speed with the debugging information turned off. My engine went way faster (like 50-100 times) when I turned that off.

Quote: Original post by beneficii
Make sure you're testing the speed with the debugging information turned off. My engine went way faster (like 50-100 times) when I turned that off.

Would running the .exe file of it go the same speed? Although I saw a small improvement, it still seems awful slow. I think my problem may be inefficient move generation. How did you implement move generation in your engine?

Quote: Original post by Artichoker

Quote: Original post by beneficii
Make sure you're testing the speed with the debugging information turned off. My engine went way faster (like 50-100 times) when I turned that off.

Would running the .exe file of it go the same speed? Although I saw a small improvement, it still seems awful slow. I think my problem may be inefficient move generation. How did you implement move generation in your engine?

I retain redundant information about the pieces and the board. I retain the physical board representation and lists of pieces. I go through the list, look at the pseudo-legal moves, check to see if they don't leave the king in check, and add them to a list, which I then sort according to various factors. I can get about 2 or 300,000 nodes per second with this, with the debugging information turned off. It's way slower without it. (This is for a chess variant which has a bigger board and more pieces and about twice the branching factor, though that's largely irrelevant to the speed per node, it seems.)

EDIT: About the debugging information, your compiler/GUI should have an option to turn off the debugging information when you compile. What do you use?

Quote: Original post by Artichoker
[...] With my current algorithm (which involves alpha-beta but does not have a quiescence search):
- the first depth visited 20 nodes and that took less than a second.
- the second depth visited 640 nodes and took around 2 seconds.
- the third depth visited 3344 nodes and took around 4 seconds.
- the fourth depth visited 76401 nodes and took around 2 minutes (I guess I was exaggerating, but 2 minutes is still a lot, according to you, and I agree).

Do the number of nodes visited look correct? They seem roughly correct to me, as the average branching factor for chess is 30 (although closer to 20 for the first couple of moves) and it has alpha beta pruning, so less nodes will be visited... which is why the enormous amount of time it is taking is disturbing...

The amount of nodes is on the high side. The good news is that there are many things you can do to help the situation: Hash tables and move ordering are probably the most important.

Your raw speed is really low. Perhaps you are copying boards left and right: You should only have one copy of the board, on which you perform moves and then you take them back. Or you might be generating the whole tree in memory before you explore it, or something crazy like that.

Quote: Also, I will take a look at trying to implement a quiescence. I have heard of it but am not sure what it does. Is it an optimization?

No, it's an absolute must for any chess program. Imagine you are searching depth 5. In the fifth move, your program will see that it can capture a knight with its queen and this seems to result in a gain of material. The problem is that the knight is protected, so the queen will be lost immediately. What quiescence search does is give the opponent an opportunity to capture the queen.

Decent descriptions of how this is achieved are easy to find online.

Quote: Original post by beneficii
I retain redundant information about the pieces and the board. I retain the physical board representation and lists of pieces. I go through the list, look at the pseudo-legal moves, check to see if they don't leave the king in check, and add them to a list, which I then sort according to various factors. I can get about 2 or 300,000 nodes per second with this, with the debugging information turned off. It's way slower without it. (This is for a chess variant which has a bigger board and more pieces and about twice the branching factor, though that's largely irrelevant to the speed per node, it seems.)

EDIT: About the debugging information, your compiler/GUI should have an option to turn off the debugging information when you compile. What do you use?

Thanks for the info, I will try some of those suggestions. Also, I am using C# on Microsoft Visual Studio 2010.

@Alvaro. Thanks for your response. I will look into hash tables and a quiescence search once I can at least get my engine to a decent speed. I am not copying boards or generating the entire tree or anything like that. Rather, I think my problem may be in inefficient move generation.

Quote: Original post by Artichoker

Quote: Original post by beneficii
I retain redundant information about the pieces and the board. I retain the physical board representation and lists of pieces. I go through the list, look at the pseudo-legal moves, check to see if they don't leave the king in check, and add them to a list, which I then sort according to various factors. I can get about 2 or 300,000 nodes per second with this, with the debugging information turned off. It's way slower without it. (This is for a chess variant which has a bigger board and more pieces and about twice the branching factor, though that's largely irrelevant to the speed per node, it seems.)

EDIT: About the debugging information, your compiler/GUI should have an option to turn off the debugging information when you compile. What do you use?

Thanks for the info, I will try some of those suggestions. Also, I am using C# on Microsoft Visual Studio 2010.

@Alvaro. Thanks for your response. I will look into hash tables and a quiescence search once I can at least get my engine to a decent speed. I am not copying boards or generating the entire tree or anything like that. Rather, I think my problem may be in inefficient move generation.

I'm using C++ on Microsoft Visual C++ 2010, which is notorious for having slow memory deallocation when programs compiled with it are run in debug mode. Really do try turning it off. Go to Solution in the Solution Explorer, go to Properties, go to Compiling Properties, and make sure the Solution is built as Release, not Debug, when you test the speed (and then make sure you test the EXE in the Release folder). If you're testing other aspects, you would probably just want to search to a shallow depth, like 3 ply, when you do the testing in debug mode.