8
\$\begingroup\$

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?

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think you're talking about en.wikipedia.org/wiki/Killer_heuristic \$\endgroup\$ – Adam Apr 25 '11 at 19:40
  • \$\begingroup\$ 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. \$\endgroup\$ – brandon Apr 25 '11 at 19:47
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Look into move ordering and principle variation search

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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