Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm working on a perfect information game in my spare time. I've implemented a naive minmax algorithm for the computer player. I've further optimized it using alpha-beta pruning.

What I'm looking for is next logical steps to improve the speed of the search (currently the computer player searches 5 nodes deep with acceptable time taken).

share|improve this question

2 Answers

up vote 1 down vote accepted

The most obvious next step is to cache the tree, hang on to the calculations you already made for the branch chosen, and use the time saved by not recalculating it to extend it further.

Depending on how confident you can be that your cost function is accurate, it might be worth trying to improve it. You may be able to semi-automate this using genetic algorithms to improve it by having different versions play against each other.

share|improve this answer
There's a lot i could do with my cost function - so I'll go work on that. As for caching - there might be more then one ai opponent. In this case I think I'd have to share the calculations between them. I have to think some more on the subject :) Thanks! – Goran Feb 13 '11 at 17:38
up vote 1 down vote

You mention that there may be more than one AI opponent. Just note that alpha-beta pruning doesn't work for more than 1 opponent (although you can look into Paranoid Search). Next steps are to look at move ordering, branch and bound pruning and transposition tables (which is probably the same as caching mentioned earlier)

share|improve this answer
I've extended the algorithm a bit. Keeping track of score (and guaranteed score) for each player. Score for all players is calculated on every move. So it's not hard to prune the branch where choosing a particular move results in a lower-then-guaranteed score for a player. Are there any other reasons why this algorithm can't be extended to n players? – Goran Mar 30 '11 at 9:50
when there is a third player you can not prune grandfather nodes as the other players score (not involved in the prune) can affect the outcome. there is quite a bit of literature on this. checkout citeseerx.ist.psu.edu/… – Druzil Mar 31 '11 at 6:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.