Game Theory – Minimax / Negamax Algorithm Visualization
by Kristian Kraljic, January 13, 2012
Have you ever tried of solving any two-player game (such as Tic-tac-toe, Chess, Go, etc.), using a computer? I bet you ever wanted to invent the next version of IBMs Deep Blue, the chess computer which was once able to beat one of the greatest chess grandmaster of human history Garry Kasparov!? But as a picture is worth a thousand words (Wikipedia is so great!):
One approach would be to use a simple evolutionary algorithm or a neural network to solve the problem, or simply try guessing.
Using a more strategic approach, you will soon come accross the theory of artificial intelligence and the mathematical methods in the game theory. One simple algorithm used commonly on two-player games is the so called Minimax algorithm for minimizing the possible loss for a worst case (maximum loss) scenario. I will not start explaining the theory much in detail here, there are enough of great books (Artificial Intelligence: A Modern Approach) out there, explaining it a lot better than I would possibly be able to do.
Soon you will start thinking of how to optimize the algorithm and come accross the Negamax method and α/β pruning. This is where things start to get difficult but interesting.
Because I thought implementing the algorithm and explaining it at the same time would be kind of fun, here are my results:
Game Theory – Minimax / Negamax Algorithm Visualization Applet
I think game theory is one realy interesting area, both in mathematics and informatics. Hopefully this small applet implementation will help you to understand this quite simple methods more easily, so you can use it in future to create the next version of Deep Blue beating the first Go grandmasters in some years.