Minimax Explained

By ai-depot | July 28, 2002

Alpha-Beta Cutoff

Adding Alpha-Beta Cutoffs

With 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 implementation

An 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.

Minimax Board

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:

  • Java version - http://www.progtools.org/games/projects/checkers/checkers.html
  • C# version - http://www.progtools.org/games/projects/sharp_checkers/sharp_checkers.html

Conclusion

The 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.
[2] - Bratko Ivan. “PROLOG. Programming for artificial intelligence” Addison-Wesley, 1990. ISBN 0-201-41606-9
[3] - Rich Elaine, Knight Kevin. “Artificial Intelligence”. McGraw-Hill Inc., 1991. ISBN 0-07-100894-2
[4] - Analytical Reasoning FAQ. Available at http://www.west.net/~stewart/lwfaq.htm

Written by Paulo Pinto.

Pages: 1 2 3

Tags: none
Category: tutorial |

13 Responses to “Minimax Explained”

  1. Jim Igor Says:
    August 18th, 2007 at 6:33 pm

    I just want to say thank you for writing this article and that it has helped me alot in my studies at time of writing.

  2. dobau Says:
    September 16th, 2007 at 7:53 am

    For me too, thanks Paulo.

  3. Sri Says:
    October 25th, 2007 at 11:20 pm

    Thank you for such simple yet elegant explanation.

  4. mohamamed Says:
    January 9th, 2008 at 4:27 pm

    neeeeeeeed your help

  5. Armin Says:
    January 29th, 2008 at 12:04 pm

    I want a chess source code using minimax alghoritm. you explaind checkers game.please help me.thank you

  6. Fming Says:
    February 13th, 2008 at 9:13 am

    Thank you
    it is very useful

  7. Does This Mistake Make Your AI Look Smarter? — AiGameDev.com Says:
    March 25th, 2008 at 5:08 pm

    […] game theory and, in a broader sense, decision theory. Most AI programmers who are familiar with his minimax model also know that one of the requisite premises of applying it is perfect knowledge of the game […]

  8. rupali Says:
    April 19th, 2008 at 5:51 am

    is it possible for 4 players

  9. Julio Granados Says:
    May 9th, 2008 at 4:04 am

    Thanks a lot. You really helped me out. I’ve had spent hours reading an incorrect translation of Russell and Norvig’s AI book without success. Your site helped me.

  10. Azade Says:
    June 11th, 2008 at 3:31 pm

    I want to impelement Othello with c#,but I can’t
    write c# code for minimax and alpha-beta.
    please help me.
    thanks

  11. toer Says:
    July 2nd, 2008 at 10:04 am

    Thanks for the good explaination

  12. toer Says:
    July 2nd, 2008 at 10:11 am

    sorry for two messages. One thing which would have been good to add, is the scoring on your tic tac toe game. showing which decision would have been made given the search depth of 2.

    Otherwise, a really great explanation

  13. thx Says:
    July 2nd, 2008 at 2:01 pm

    Very informative. Aside from the not-so-uncommon typo or grammatical error, a good read. This helped me with my AI project :)

Comments