Hello everyone, I have been working on a checkers variant for some time and am running into some speed issues. My game has a branching factor around 15-20 at the beginning of the game, close to 60 by mid game, then down to 10 or less by end game... so it develops quickly. I am having trouble getting it to run quickly... I am doing a 6ply minimax search, with alpha-beta, some killer-moves and a transposition table but with all of this.. 6ply search is taking me close to 3 minutes. In one common mid-game move. when I look at how many nodes the evaluation function is touching it reads 2.9million, total search time: 165,000ms, total move generation time: 29,000ms, total evaluation function time: 78000ms. I've tried to optimize my move generation by placing the better strategy moves toward the top of the list. Perhaps I could be doing a better job at this. One point I am seeing that might be problematic is that I am starting with an empty transposition table after each turn (the game is being run through a webserver, so I've made it as stateless as possible)... Any questions,comments,suggestions are very very appreciated! (PS I am writing this to run in a java servlet) Thanks everyone!

Depth 6 is entirely too shallow for checkers, and it should take less than a second, even when the number of moves available gets to around 60. Are you using iterative deepening? How good is your move ordering? (Are you storing the best move in the hash table so you can try it first? Killer moves? History heuristic?)

Also, you seem to only search about 17K nodes per second. You should be able to get a lot more than that. Perhaps you are using dynamic memory allocation during the search? But concentrate on the algorithmic changes first.

EDIT: Oh, I didn't realize you were using Java. It will be hard to get decent speeds in that language.

I am dynamically allocating memory to generate the move positions. I had switched to allocating a large block when the turn starts and then indexing off of that, but had problems when to many users (more then 1) would make turns simultaniously and give me memory-full errors. Remember, this is running on a web server where multiple concurrent games will be running.

I think much of my time is being spent evaluating the nodes. I've worked hard to get the evaluation function to produce good results which takes some carefull analysis of the gameboard. There are several recursive loops that get run through each node, used to determine positional awareness... most loops only go three or four levels deep however (and by end-game they don't loop at all).

I think Iterative deepening is my next step. I've spent some time working on ordering the moves that are coming from my generateMoveList() function based on good strategy for my game. I'm wondering if that logic will be unneeded when I switch to IDDFS because I will be reordering my movelist after each iteration... my question: when using IDDFS, should the move ordering happen in the generateMoveList() function, or after each iteration of the minimax through the depth-0 moves...... or both? Is move-ordering really the meat and potatos of AI performance?

As far as plys go, what is an acceptable level for skilled checkers players? Playing my game at 6ply kicks my butt.... but I'm not a great strategy game player.

You can always use the University of Alberta Checkers Database

Runs in O(1).

Quote: Original post by gfrommer
I think Iterative deepening is my next step. I've spent some time working on ordering the moves that are coming from my generateMoveList() function based on good strategy for my game. I'm wondering if that logic will be unneeded when I switch to IDDFS because I will be reordering my movelist after each iteration... my question: when using IDDFS, should the move ordering happen in the generateMoveList() function, or after each iteration of the minimax through the depth-0 moves...... or both? Is move-ordering really the meat and potatos of AI performance?

When you use iterative deepening, you can keep very good ordering of the moves at the root: Simply promote a move to the top of the list when you find it's the best move you've seen. You still need to sort the moves in inner nodes somehow. Transposition tables help here (usually you store the best move you found here, so even if you can't use the score, you can try it first). There are those other techniques I mentioned (killer heuristic, history heuristic), which will help with sorting the rest of the moves.

Iterative deepening will also give you an opportunity to control how much time you use.

Quote: As far as plys go, what is an acceptable level for skilled checkers players? Playing my game at 6ply kicks my butt.... but I'm not a great strategy game player.

There is no simple answer to this question. I have a friend who is a Spanish checkers master and the first move he thought off was typically what my program saw at depth 7. :)