Minimax Algorithm Tic Tac Toe Intermediate State
I have been trying to understand the working of the minimax algorithm at the intermediate states of a game of tic tac toe. But I am unable to do so. I understand that the min max algorithm returns the best possible state for the player at every step. If the states were like this
At the final stages of the game, it is easier to understand that the state that leads to an advantage or maximum points for a player is the best configuration. In this example, we can see that the state which has the score '1', at the leaf is the best state. But what happens at the intermediate stages or when the game begins.
Suppose we had 3 positions to begin with or the player could go to these states by playing a certain position. And these positions further lead to further board configurations down the tree. Each of the three branches from the initial/start node will eventually lead to victory denoted by '1' at the leaf nodes or a defeat denoted by '-1' in the leaf nodes or in some cases a draw denoted by '0'.
What does the minimax algorithm do here? Which position or branch will the minimax return after the initial node?
The minimax algorithm, as mentioned here examines the extremal outcome of the move. For the player which aims at maximizing the score (in the case of Tic-Tac-Toe, the maximum score is 1), the value of a move is the maximum of all possible outcomes and the algorithm aims at maximizing the value of the move.
Likewise, for the player which aims at minimizing the score, the algorithm aims at chosing a move with minimaxl value (which is -1 for Tic-Tac-Toe).
More formally, the value of a move is the value of the resulting end game state if the move would result in a terminal game state (ie the move reaches a leaf of the game tree). If the move results in an inner node of the game tree, it depends on whether the level of the game tree is even or odd (because the moves would be done by the alternating players) and is defined recursively; for an even level, the value of a move is the minimum value attainable of successive moves and for an odd level, the value of a move is the maximum value attainble of succesive moves (or vice versa, depending on the exact definition of level and which player aims at what value).
Less formally, the minimax algorithm evaluates the entire game tree based on the following reasoning. To evaluate a move, just make the move, and take the position of the opponent and do the very same evaluation, namely evaluate a move and take the position of the opponent again. In total, this results in determining a move which is optimal under the assumption that the opponent also play optimally - which is implemented by emulation of his or her choice of moves by also using the minimax algorithm to evaluate his or her moves.
链接地址: http://www.djcxy.com/p/56376.html上一篇: MinMax算法不能正常工作
下一篇: Minimax算法井字中间状态