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?
\$\begingroup\$
\$\endgroup\$
Add a comment
|
3 Answers
\$\begingroup\$
\$\endgroup\$
2
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.
-
\$\begingroup\$ I think you're talking about en.wikipedia.org/wiki/Killer_heuristic \$\endgroup\$– AdamCommented 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\$– brandonCommented Apr 25, 2011 at 19:47
\$\begingroup\$
\$\endgroup\$
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.
\$\begingroup\$
\$\endgroup\$
Look into move ordering and principle variation search
