Game Playing
Let's make the computer play with you. Let's have some fun with artificial intelligence.
Minimax Algorithm in AI
In game playing, first, let's look at minimax algorithm which will help us to find an optimum move to win the game. In the next lesson, we will look at tic-tac-toe game where we will use minimax algorithm to make an unbeatable tic-tac-toe game.
Consider an 2 player game like tic-tac-toe, chess, checker, etc. Now, our goal or aim is to predict a move which will lead us to the winning state. If we are playing then obviously we want to increase our score and decrease the opponent's score as much as we can, this principle or logic we will apply and predict the move. On the other hand when the opponent is playing then he would decrease our score and increase his. So this type of playing we would stimulate in our code and generate all the plausible move and from those select the one which will lead us to the win state. Ok, let's think and compare with a human thought process. When human plays he will think like :
1) ok, this is my state or situation
2) If I play this move then the opponent can play those set of moves and from those moves, if he plays that move then I could play this move in turn and I could win.
3) Human repeats steps 2, till he can find a move which will help in winning
Basically, this kind of thought process we want to stimulate with the computer.
Minimax search procedure to find an optimum move is a depth-first and depth-limited search procedure. The idea behind minimax is that we will start from the current position and use the plausible-move generator to generate the set of possible successor positions.
MiniMax example
Let's understand with an example
let's say
a winning state=+10
a losing state is -10
a draw is 0
The left move will be selected and rest will be discarded.
Example of minimax algorithm with a general tree:-