MinMax

Last three days I have been struggling and fighting with MinMax, I conquered it finally and made a demo game using it but still there are lot of things to learn in a simple MinMax Algorithm. I will try to explain what it is :

In a normal two-player board games the general scenario involves each of the opponents trying to minimize the others gain and look to maximize their gain. There is no "both win situation"/"co-operative mode", so when making the computer AI for such games, one has to look ahead and choose suitable move that will pay-off in favor of computer. The computer is programmed to look ahead and see all possible moves that can possibly take place from the current scenario and weigh each of the moves, finally choosing the one that will benefit in the long run. What exactly happens is that we make a tree, starting node is the current position of the game and its children basically show the possible next moves that can happen, we weigh each of the node from their children. These algorithms are called MinMax or MiniMax, generally applied to board games like chess, tic-tac-toe, go, zerosum etc.

Apart from normal MinMax there are other algorithms too that help dispense of the moves which will not happen at all. Like take example of chess, there are always so many moves from current position and then if we try to make the tree for all possible next moves and then possible moves from the player, the figure can become too large in matter of depths(levels of children). Alpha-beta pruning is one such method in which those possibly never happening moves or bad choices are discarded early on, so that the computer can spend time working out only the best moves from given position. There is also an algorithm called NegaMax which does exactly the same thing but is a lot faster. I will explain more of this later, possibly with some code and graphs/images to assist. Till then chow!! and keep checking this space. :)