![]()
Visiting guest. Why not sign in?
|
|
|
Alpha-Beta CutoffAdding Alpha-Beta CutoffsWith all this talk about search speed many of you might be wondering what this is all about. Well, the search speed is very important in AI because if an algorithm takes too long to give a good answer the algorithm may not be suitable. For example, a good MinMax algorithm implementation with an evaluation function capable to give very good estimatives might be able to search 1000 positions a second. In tourament chess each player has around 150 seconds to make a move. So it would probably be able to analyze 150 000 positions during that period. But in chess each move has around 35 possible branchs! In the end the program would only be able to analyze around 3, to 4 moves ahead in the game[1]. Even humans with very few pratice in chess can do better than this. But if we use MinMax with alpha-beta cutoffs, again a decent implementation with a good evaluation function, the result behaviour might be much better. In this case, the program might be able to double the number of analyzed positions and thus becoming a much toughter adversary. An example implementationAn example is always a good way to show how an algorithm might be implemented. Back in 1999, I and a friend of mine have implemented a checkers game as a Java application for the AI class in the university. I have recently ported the game to C#. The MinMax algortihm isn't a great implementation. In fact I should mention that the best thing about it is that it works. However I think that it presents a way that the algorithm might be implemented and as an example it is good enough. ![]() Figure 3: Example of a board with the values estimated for each position The game uses MinMax with alpha-beta cutoffs for the computer moves. The evaluation function is an weighted average of the positions occupied by the checker pieces. The figure 3 shows the values for each board position. The value of each board position is multiplied by the type of the piece that rests on that position, described in Table 1. The Listing 4 shows the Java implementation of the evaluation function. It has been slightly modified for the article. Please note that the code uses a vector, 0-31 based, for the board game positions. The game code is available at:
ConclusionThe MinMax might not be the best answer for all kind of computer games that need to have AI that resembles human behaviour. But given a good implementation it can create a tought adversary. I hope that this article has gave you some insight on the MinMax algorithm and how you might use it on your games. References
[1] - Russell Stuart J., Norvig Peter. "Artificial Intelligence. A modern approach.". Prentice Hall, 1995. ISBN 0-13-103805-2. Remember you can visit the Message Store to discuss this tutorial. There are already 4 replies in the thread, why not join in? Back to the Artificial Intelligence Depot.
|