Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

AndyTang

Alpha beta speed

This topic is 5761 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I''m creating a Chinese Chess program using an alpha beta search for the AI. Unfortuantely, even at depth 3, the speed of the algorithm is still too slow and Im using a relatively powerful computer. Any ideas on how to speed things up such as how structure should be, size of algorithm, ways to do things? I want to try to speed things up with alpha beta as much as possible before I try adding things such as Transposition table, iterative deeping etc. Thanks for your help.

Share this post


Link to post
Share on other sites
Advertisement
how slow is too slow?

have you tried profiling it?

i don''t know about the specific algorithm but is it big? could you show some code? at least some data structures and main loops...

pete

Share this post


Link to post
Share on other sites
I don't know how well would this work in general or for your particular application, but here's the idea: you only store one board structure (a matrix holding all the pieces). The min/max recursive function will make a move (change this board structure), call itself recursively, and then undo the move after the recursive call has completed. If you copy your board once for each min/max call, this could improve speed a lot.

[edited by - Diodor on September 13, 2002 3:55:38 PM]

Share this post


Link to post
Share on other sites
When you say "an alpha beta search", I assume you are referring to minimax search with alpha beta pruning.

First off, make sure you are doing alpha beta pruning and not just a simple minimax. This is about the best thing you can do to improve search speed, as it keeps you from searching branches of the tree that have no chance at profit.

Make sure your evaluation function is fast. Since it gets called about a skillion times during a search, it''s important that it be as fast as possible.

Finally, you might try a simple function that, before the search, will sort moves with the most likely profitable moves first. That will allow the alpha-beta pruner to work more efficiently at killing off branches that have no chance at profit.

---
John Hattan
The Code Zone
Sweet software for a saturnine world

Share this post


Link to post
Share on other sites
hmmm, how slow is too slow. At the moment with a depth of 3 it takes about 3-5 seconds. Maybe it doesnt seem to slow, is this too slow for this depth? Think of normal chess.

Yes, I am using mini-max alpha beta pruning It does cut off at the correct places. As for the evaluation function, it is relatively simple, it loops through the board and add or subtract the value of the pieces (simple at the moment) so I''m not sure how to make it faster.

As for sorting the moves, its doing this based on captured pieces - Im not sure how else to sort it. Any suggestions appreciated.

One area is that I am using linked list for move generation, maybe the link list is too slow for the application?

Share this post


Link to post
Share on other sites
As for the evaluation function, you can (and perhaps should) resolve to assembly. And, make sure you don''t have it as a separate function; put it inside the recursive function or have it inline. Trim the recursive function''s parameters, so they are as few as possibly, and perhaps make "contstant" values (like depth) globals instead of pushing and poping them around all the time.

Share this post


Link to post
Share on other sites
Grandmaster Chess Ultra, on the grand master setting, with a recursion depth of a mere 20, takes 5 to 10 minutes to make a move. 2 to 5 seconds is not slow; unless your ai really sucks. I can sit and wait 5 minutes for a move, because I am spending the time thinking of my own move, and the program is good enough to completly whomp on me every time.

Share this post


Link to post
Share on other sites
Thanks guys I appreciate all this.

I forgot about inlining and I will try to used as few arguments and parameters as possible. I forgot that poping them in and out take time. As for assembly, I dont think I know that well enough to use.

I think most people would not wait for the computer as well as some advance players. Some people would just make a move and then expect the computer to make a move. That is why I am trying to make it as fast as possible.

Share this post


Link to post
Share on other sites
Yeah, you should first of all make sure you''re using the best algorithm (I have no idea about this stuff though), then implement it in C code the best you can. If you still need to squeeze performance, you could look at the assembly; I''m sure there are people willing to help here if you post your code. Sometimes you can really improve performance by utilizing the processor registers and thereby avoiding memory access, which compilers seem to be very fond of.

Share this post


Link to post
Share on other sites
Since usually AI functions uses recursive calling. It is best to preallocate all the memory it needs, instead of for each call to the function, you new variables in the start, and delete variables in the end.

btw, is your Chiness Chess game freely available for downloads??

[edited by - DerekSaw on September 13, 2002 9:19:32 PM]

Which kind of sort algorithm are you using? eg. For small number of items, simple sorting like ShellSort or BubbleSort have less overhead than QuickSort.

[edited by - DerekSaw on September 13, 2002 9:23:41 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!