6 - games and adversarial search

Question 1

Games vs. single-agent search

Answer 1

We don’t know how the opponent will act
Solution: strategy or policy + efficnecy

Question 2

Minimax value of a node

Answer 2

the utility (for MAX) of being in the corresponding state, assuming perfect play on both sides

indicates how good it would be for a player to reach that position

Question 3

Minimax strategy

Answer 3

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

Question 4

Alpha-Beta Pruning

Answer 4

Alpha-beta pruning enhances the Min-Max algorithm by eliminating branches that do not affect the final decision. The key formulas for alpha-beta pruning are:
Alpha (α): The best value that the maximizing player can guarantee so far.
Beta (β): The best value that the minimizing player can guarantee so far.

Question 5

ALPHA-BETA cutoff

Answer 5

ALPHA-BETA cutoff is a method for reducing the number of nodes explored in the Minimax strategy. For the nodes it explores it computes, in addition to the score, an alpha value and a beta value.

Question 6

Expectiminimax

Answer 6

for chance nodes, average values weighted by the probability of each outcome

Question 7

Monte Carlo simulation

Answer 7

when you get to a chance node, simulate a large number of games with random dice rolls and use win percentage as evaluation function