Question

In: Computer Science

Explain, how the Mini-Max algorithm is used in decision-making and game theory. Make sure to explain...

Explain, how the Mini-Max algorithm is used in decision-making and game theory. Make sure to explain how this algorithm applies the utility function to get the utility values for the terminal states. Feel free to add any diagram/tree structure to represent all the possible moves that allow a game to move from one state to the next state. Also, discuss how the alpha-beta pruning approach is used for optimization.

Solutions

Expert Solution

Minimax is a kind of backtracking algorithm that is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally. It is widely used in two player turn-based games such as Tic-Tac-Toe, Backgammon, Mancala, Chess, etc.

In Minimax the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.

Every board state has a value associated with it. In a given state if the maximizer has upper hand then, the score of the board will tend to be some positive value. If the minimizer has the upper hand in that board state then it will tend to be some negative value. The values of the board are calculated by some heuristics which are unique for every type of game.

Example:
Consider a game which has 4 final states and paths to reach final state are from root to 4 leaves of a perfect binary tree as shown below. Assume you are the maximizing player and you get the first chance to move, i.e., you are at the root and your opponent at next level. Which move you would make as a maximizing player considering that your opponent also plays optimally?

Since this is a backtracking based algorithm, it tries all possible moves, then backtracks and makes a decision.

  • Maximizer goes LEFT: It is now the minimizers turn. The minimizer now has a choice between 3 and 5. Being the minimizer it will definitely choose the least among both, that is 3
  • Maximizer goes RIGHT: It is now the minimizers turn. The minimizer now has a choice between 2 and 9. He will choose 2 as it is the least among the two values.

Being the maximizer you would choose the larger value that is 3. Hence the optimal move for the maximizer is to go LEFT and the optimal value is 3.

Now the game tree looks like below :

The above tree shows two possible scores when maximizer makes left and right moves.

Note: Even though there is a value of 9 on the right subtree, the minimizer will never pick that. We must always assume that our opponent plays optimally.

Alpha-Beta pruning is not actually a new algorithm, rather an optimization technique for minimax algorithm. It reduces the computation time by a huge factor. This allows us to search much faster and even go into deeper levels in the game tree. It cuts off branches in the game tree which need not be searched because there already exists a better move available. It is called Alpha-Beta pruning because it passes 2 extra parameters in the minimax function, namely alpha and beta.

Let’s define the parameters alpha and beta.
Alpha is the best value that the maximizer currently can guarantee at that level or above.
Beta is the best value that the minimizer currently can guarantee at that level or above.


Related Solutions

In the game given below, use the mini-max algorithm to find the prudent strategies for both...
In the game given below, use the mini-max algorithm to find the prudent strategies for both players and to find all the saddle points. Draw the flow diagram. Find any dominated strategies and completely reduce the game. 2 0 0 1 0 -1 0 -1 -2
How can we use game theory to improve strategic decision-making? How can we use game theory...
How can we use game theory to improve strategic decision-making? How can we use game theory in the construction and/or design of a strategy?
How have you used the rational decision-making model to make a decision? What was the context?...
How have you used the rational decision-making model to make a decision? What was the context? How well did the model work? Please explain in at least 120 words.
how is technology used for decision making?
how is technology used for decision making?
Describe expectancy theory. Make sure you address how and when it is best used in the...
Describe expectancy theory. Make sure you address how and when it is best used in the workplace.
explain how linear regression could be used in business decision making?
explain how linear regression could be used in business decision making?
Question 02: Game theory is the study of multi- player decision making in situation where the...
Question 02: Game theory is the study of multi- player decision making in situation where the choices of each player may affect the pay-offs received by other players. Arrange how many types you can categorized Game Theory. ( 10 Marks) . Note: Plagiarism is strictly prohibited please do not copy paste from internet
If the goal of your decision making is to make the optimum decision or make the...
If the goal of your decision making is to make the optimum decision or make the best choice, you should utilize the bounded rationality model of decision making. the intuitive decision-making model. the creative decision-making model. the rational decision making model.
Decision Making: Discuss how relevant information is used to make short-term decisions and how pricing affects...
Decision Making: Discuss how relevant information is used to make short-term decisions and how pricing affects short-term decisions. Explain the concept of capital budgeting and detail the capital budgeting techniques used to make decisions. This includes, the payback method, the accounting rate of return method, and the discounted cash flow method.
Q1. Have you used the rational decision-making model to make a decision? What was the context?...
Q1. Have you used the rational decision-making model to make a decision? What was the context? How well did the model work? Give example of your work place. (You need to provide a convincing and relevant justification for the points, and it would be better if you can provide real life workplace examples to support the justification of the points)
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT