Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm studying AI. My teacher gave us source code of a chess-like game and asked us to enhance it. My exercise is to improve the alpha/beta algorithm implementing in that game. The programmer already uses transposition tables, MTD(f) with alpha/beta+memory (MTD(f) is the best algorithm I know by far). So is there any better algorithm to enhance alpha-beta search or a good way to implement MTD(f) in coding a game?

share|improve this question
add comment

3 Answers

I'll answer generally then more specifically. First, in my experience when a professor asks is there a better way.. I immediately go to the book and look for things the author noted as shortfalls of the algorithm in question. Second, I look at optimizations that have helped me in the past.

For a tree searching algorithm like alpha-beta I would look at adding a heuristic that reduces the number of searches or causes it to look in more likely locations first.

I would assign weights to paths that can be taken in the tree based on past results. If a path has resulting in a higher score in the past, the it's probably a good path to take again. So long story short, add heuristics to the paths and choose to go with those so the algorithm can terminate earlier.

Note that I don't really remember much about the specific algorithm, just that it is a tree and the naive approach to it does not involve this heuristic.

share|improve this answer
    
I think you're talking about en.wikipedia.org/wiki/Killer_heuristic –  Adam Apr 25 '11 at 19:40
    
Looks like it. I tried to give a less specific answer to help with future problems since the approach is all the same. The real problem wasn't that risa doesn't know alpha-beta optimization, it's that they need to see the common approach of optimizations, especially in AI as this is a very search related field. –  brandon Apr 25 '11 at 19:47
add comment

Look into move ordering and principle variation search

share|improve this answer
add comment

You didn't mention null move pruning or late move reductions. They're fairly easy to implement and are even more effective at reducing the search size than alpha-beta pruning. Search extensions are also important to mitigate the horizon effect; quiescence search in particular is a very important component for a chess AI.

share|improve this answer
add comment

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.