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\$

3 Answers 3

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\$
2
  • \$\begingroup\$ I think you're talking about en.wikipedia.org/wiki/Killer_heuristic \$\endgroup\$
    – Adam
    Apr 25, 2011 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, 2011 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\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .