Friday, October 16, 2009

NegaMax with alphaBeta pruning.

In the last post, we completed the process of generating a list of all possible moves, and had the engine choose randomly from the list. Now in the alpha7 phase we add add some algorithms to enable the engine to analyse the position and calculate the best move to play. I won't attempt to explain how negamax and alpha-beta pruning works, there are plenty of websites that explain that. I will make a few general comments. My program currently has the following basic algorithms that are all design to work together.

Negamax ( which is equivalent to MiniMax ), is the standard base recursion algorithm for traversing (searching) game trees. Negamax will examine every possible variation, even obviously bad ones. It can be very slow, because we all know how the number of possible chess moves can grow exponentially.

AlphaBeta pruning is added to the picture to improve the performance of negamax, and it serves this purpose very well. It does so by eliminating from further analysis those variations that, based on best play by both sides, can't possibly change the final decision. Assuming we are searching at a fixed depth, alphaBeta will make the same move as negaMax, only it will do so faster. It follows that if we are playing under time controls, alphaBeta will search deeper than plain negaMax.

MVV/LVA (Most Valuable Victim/Least Valuable Attacker) is a method for ordering the list of possible moves at each node. The effectiveness of AlphaBeta pruning is improved if we can place those moves that are likely to be "best" at the top of the list. Naturally we can only make guesses as to which move is best, but we know that if we evaluate captures first, and furthormore we order the captures according to the MVV/LVA principle, we will significantly improve the speed of alphaBeta search.

An evaluate() function is a must. evaluate() assigns a value to those positions at the end of the search tree (leaf nodes). Negamax/alpha beta provides a means of comparison of values assigned by evaluate(). At this point, my evaluate() only calculates the material balance. This means the program has no strategy, but is very good at tactics. Strategy, in the form of a better evaluate() function, comes later once I have squeezed the most out of my algorithms.

If you wish to learn more about these topics, I can recommend the following website, which was a big help to me. It will help you to better understand my source code.

http://web.archive.org/web/20040403211728/brucemo.com/compchess/programming/index.htm

I have redesigned my GUI to help evaluate the effectiveness of the different features. There is a drop-down list which controls which algorithms will be used. It's all pretty straightforward. Output for each computer move includes the time taken and the # of leaf nodes evaluated. The Better the algorithm, the fewer leaf nodes you need to evaluate.

As always, an updated applet and source code is available on the fchess2 website. If you have any questions, you are welcome to commment in the blog.

Have a nice day.

No comments:

Post a Comment