I am doing an AI in CLISP for a game that is basically Gomoku. (It has one more additional rule.) I have implemented a basic alpha-beta minimax tree, but it is WAY too slow. I was wondering if anyone had some advice or knew of a way to speed this up. I think the key is in culling the number of branches at each step, but I can''t think of a good way to do this. Anyone have any ideas or advice? >^,,^<

This is the second (or third) question this week about this.

You can speed your program up by:

1. Keeping a principal variation, and searching it first.
Use information about the line of play from the previous search to determine what the most likely best move is, and search it first.

2. Using Hash Tables
Often there are many ways to get to the same board state. This means that the same state will appear a number of times in your search. If you remember details about the boards you''ve looked at, you wont have to bother re-analyzing them. This is called move transposition.

You can also use this information to improve move ordering (so best moves are searched first). This makes AlphaBeta much faster.

3. Do some form of forward pruning. That is, find some static way to determine if a move is worth exploring.

4. Use MTD(f) or NegaScout to enhance your AlphaBeta.

There is a really good article about this here on GameDev.net, but it applies to chess.

Will

Well, I am in the process of reading that very article! I am just worried because my current setup (in CLISP) takes about 40 seconds for a single ply. Since I only get 2 seconds for a turn, I fear this design is severly flawed.

Sorry about the repeat subject, but the forum search thingy doesn''t work. I figured this has probably been covered before.

Thanks for the help though!

Go-moku is all about the evaluation function. With good evaluation you can consider a limited number of moves decreasing the branch factor, you can find early wins giving an extra ply or two, alpha-beta works best, etc.