课程: AI Algorithms for Game Design with Python

Minimax overview - Python教程

课程: AI Algorithms for Game Design with Python

开始一个月试用 购买团队方案

Minimax overview

“

- [Instructor] The main algorithm our intelligent agent will use to produce its next move is called minimax. And that's because it minimizes the opponent's maximum payoff, which is to say it minimizes your own maximum loss. This trade-off is due to the fact that we will simulate an opponent who wants to beat our intelligent agent, maximizing his or her payoff, and an intelligent agent who wants to beat the opponent, minimizing the opponent's payoff. Minimax is a tree-based search algorithm that performs a depth-first traversal for search. And you'll see that this is almost a completely brute force approach. Let me show you an example for you to get a good idea of minimax. Let's suppose we have a game with an initial state represented by a triangle pointing up. Let's say that this is our intelligent agent's turn and that it always has three possible moves. In this case, I've named them a, b, and c. These moves will produce the ensuing states of the game, now shown as triangles pointing down. At this level, it's the opponent's turn. Now the opponent also has three possible moves, which will produce the third-level states, now shown again as upward triangles. These represent our agent's turn, each with three possible moves once more. Now these options will produce states where the game ends. The values shown represent the final score. Now, this is a zero-sum game, which means that our loss is our opponent's gain. So when these numbers are positive, it means our agent won. When they are negative, it means our opponent won. Zero represents a tie or draw, meaning that neither has won. Naturally, we want the largest positive score we can get. And our opponent wants the largest negative score possible. That's what the triangles mean. I have labeled the levels of the tree at the left, starting at level zero, and at the right, I've labeled the role of each of these levels. The top level, level zero, has only one node in which we are trying to maximize our score. This is known as a max node. And it's represented by an upward triangle. In level one, our opponent is supposed to make a decision, so we assume that the opponent wants to minimize the score towards a negative value. That's why the nodes at this level are minimizing nodes, or min nodes, which are represented by downward triangles. At level two, we have max nodes again. And so we have max nodes for our agent's turn and min nodes for our opponent's turn. This goes on until we have terminal nodes. Be aware that not all game trees have a constant branching factor, nor do they always end at one specific level. This example was designed for convenience. So as you'll see shortly, each min node copies the most negative score obtained from its possible moves. And each max node copies the most positive score from its moves. This has to happen from the bottom up, because only the terminal states have scores. Finally, at the top, the algorithm picks move a, b, or c, whichever yields the most positive value.

内容