Artificial Intelligence - The minimax method.

ARTIFICIAL INTELLIGENCE PROJECT

INTRODUCTION

Game Playing

Playing games have always been an attraction of computers, and will probably always be so. Action games where you charge around blowing everything up are one type of game, but we are more interested in this project in examining a more thoughtful game. How do you get a computer to make sensible moves when for our game there are 97 possible positions and a horribly big number of board configurations? Surely we can use the search techniques that we have covered. The problems we have thus far considered have been of the type where the problem is well defined at the beginning and nothing changes during the search. Except for one player games that have no chance involved, such as the game of solitaire, (a game where you have to remove pegs from a board), games involve either chance, or another player's moves or both. In this case we cannot simply search for a solution as the other player will try to block you and games of chance simply will no cooperate!
However, we do not throw away all that we have just looked at in Search. We do need to modify the techniques to allow for opponents.

Generate and Test

One approach to take is to look at the problem as one of generating then testing possible sets of moves. One extreme would be to generate a number of complete sets of moves and then test each of them, taking the best one. The alternate extreme is to generate one move at a time, evaluate each move, take the best, and then generate the next move. Obviously, these do not make particularly ideal solutions. The first method might take months or years to run; the other technique is incapable of sacrificing at early stages to gain later in the game. We obviously need a bit of both, but the two extremes do show us where we need to concentrate.

We need to produce a move generator that only produces good moves; suicidal moves and plain silly moves will get us nowhere.
We need to develop a technique for searching through the resulting possible moves that picks out the most likely helpful moves first and tests these before going onto less beneficial moves - it needs to be able to recognize a good move when it sees one!

If we can develop a good move generator then that will help us generate a better evaluation function. So we want first of all to create a very good plausible move generator that will not bother to forward unlikely solutions to the main evaluator. By doing this we then allow ourselves to apply a far more powerful evaluator as it would have, in this case, ten times as long to evaluate each possibility. We would be able to whittle down the sensible solutions much more effectively.

Game State Evaluation

Now that we have our efficient generator and evaluation function, all we need to do now, surely, is find the ideal path to a winning state and we've won the game. Firstly, we have to remember that our opponent will seek to slow us down and even beat us, , with an average branching factor of about 7, there are still more plausible paths than we could ever generate, let alone evaluate. The way that we get round this problem is to generate a value for each state considered that gives an estimate of how good this particular position is, i.e. how near to or far from a win this position is likely to be. Our evaluation function will be one of the most important parts of the game since this is how the player interacts with the world.

THE MINIMAX SEARCH METHOD

Description

The minimax method allows us to tackle the problem of opponents in a relatively simple manner.

The game that we will be considering is a two player games, so each move will consist of two plies.
Let us assume that our opponent is playing to win, a fair assumption, and that they will always take the move that will give them the best advantage. Given this, we need to develop a technique that will take into account the opponent's best moves yet still give us the winning strategy. This is what Minimax attempts ...