Now, getting back to the minimax algorithm. The minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. Pseudo-code of Minimax is as follows:. Suppose the game being played only has a maximum of two possible moves per player each turn.
The algorithm generates the tree below, where the circles represent the moves of the player running the algorithm maximizing player , and squares represent the moves of the opponent minimizing player. Because of the limitation of computation resources, the tree is limited to a look-ahead of 4 moves. The minimax algorithm is a way of finding an optimal move in a two player game.
Nodes representing your moves are generally drawn as squares or possibly upward pointing triangles :. These are also called MAX nodes. The goal at a MAX node is to maximize the value of the subtree rooted at that node.
These are also called MIN nodes. The goal at a MIN node is to minimize the value of the subtree rooted at that node. Alpha-beta pruning gets its name from two bounds that are passed along during the calculation, which restrict the set of possible solutions based on the portion of the search tree that has already been seen. Thus, when any new node is being considered as a possible path to the solution, it can only work if:.
To visualize this, we can use a number line. At any point in time, alpha and beta are lower and upper bounds on the set of possible solution values, like so:. As the problem progresses, we can assume restrictions about the range of possible solutions based on min nodes which may place an upper bound and max nodes which may place a lower bound. As we move through the search tree, these bounds typically get closer and closer together:.
This convergence is not a problem as long as there is some overlap in the ranges of alpha and beta. At some point in evaluating a node, we may find that it has moved one of the bounds such that there is no longer any overlap between the ranges of alpha and beta:.
At this point, we know that this node could never result in a solution path that we will consider, so we may stop processing this node. In other words, we stop generating its children and move back to its parent node. For the value of this node, we should pass to the parent the value we changed which exceeded the other bound. To demonstrate minimax with alpha-beta pruning, we use the following minimax tree as an example:. For the purposes of this minimax tutorial, this tree is equivalent to the list representation:.
The alpha-beta pruning is meant to avoid having to generate all the states and calculate all the evaluation functions.
Check this page out if you want some notes on how a real world version of minimax with alpha-beta pruning would vary from your version. Thus we will go to a depth of 4 in the tree, then evaluate the state. At the start of the problem, you see only the current state i. Since the bounds still contain a valid range, we start the problem by generating the first child state, and passing along the current set of bounds. At this point our search looks like this:.
And one more time:. When we get to the first node at depth 4, we run our evaluation function on the state, and get the value 3. Thus we have this:. We pass this node back to the min node above. Since this is a min node, we now know that the minimax value of this node must be less than or equal to 3.
The minimax criterion is the choice from a set of options that minimizes the risk of a worse-case scenario. Also, by focusing on the worse-case, less severe risks may be neglected even if they are far more likely to occur. A maximin strategy is a strategy in game theory where a player makes a decision that yields the 'best of the worst' outcome.
All decisions will have costs and benefits, and a maximin strategy is one that seeks out the decision that yields the smallest loss. According to the maximin rule we should compare alternatives by the worst possible outcome under each alternative, and we should choose one which maximize the utility of the worst outcome. Thus we use the maximin rule. Rawls thinks that original position satisfies these conditions.
The minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. What does Maximin mean? Definition of maximin. What is the Minimax strategy? In game theory, minimax is a decision rule used to minimize the worst-case potential loss; in other words, a player considers all of the best opponent responses to his strategies, and selects the strategy such that the opponent's best strategy gives a payoff as large as possible.
What is the minimax regret decision? The Minimax Regret Criterion is a technique used to make decisions under uncertainty.
Under this Minimax Regret Criterion, the decision maker calculates the maximum opportunity loss values or also known as regret for each alternative, and then she chooses the decision that has the lowest maximum regret.
The highest minimum payoff arises from supplying 40 salads. The minimax regret strategy is the one that minimises the maximum regret.
It is useful for a risk-neutral decision maker. Essentially, this is the technique for a 'sore loser' who does not wish to make the wrong decision. To solve this a table showing the size of the regret needs to be constructed. This means we need to find the biggest pay-off for each demand row, then subtract all other numbers in this row from the largest number. If we had decided to supply 50 salads, we would achieve a nil profit.
Daily supply Daily Demand 40 salads. A manager employing the minimax regret criterion would want to minimise that maximum regret, and therefore supply 40 salads only. Note that the above techniques can be used even if we do not have probabilities. To calculate expected values , for example, we will need probabilities.
0コメント