Games

What is the significance of adversarial games?

They involve interaction with another agent, often with competing goals.

What is the Minimax algorithm?

An algorithm used in zero-sum games to minimize the possible loss for a worst-case scenario.

What is α-β pruning?

An optimization technique for the Minimax algorithm that reduces the number of nodes evaluated in the search tree.

What is the value of a state in game theory?

The best achievable outcome (utility) from that state.

What is a terminal state in game theory?

A state where the game ends and a utility value is assigned.

What is a zero-sum game?

A game where one player's gain is exactly balanced by the losses of other players.

What is a general-sum game?

A game where players have independent utilities and can cooperate or compete.

What is the role of a policy in game theory?

A strategy that recommends a move from every possible state.

What is the computational complexity of the Minimax algorithm?

Time complexity is O(b^m) and space complexity is O(b^m), where b is the branching factor and m is the maximum depth.

What is the purpose of adversarial search?

To find optimal strategies in games with competing agents.

What is the difference between deterministic and stochastic games?

Deterministic games have predictable outcomes, while stochastic games involve randomness.

What does the term 'utility' refer to in game theory?

A measure of satisfaction or value that a player derives from a particular outcome.

What is a multi-agent utility in game theory?

A scenario where multiple players have their own utility functions and may cooperate or compete.

What is a terminal utility in game theory?

The utility value assigned to a terminal state based on the outcome of the game.

What are the components of a deterministic game?

States (S), Players (P), Actions (A), Transition function, Terminal test, and Terminal utilities.

What is a policy in the context of game theory?

A mapping from states to actions (S → A) for a player.

What is the goal of minimax algorithms?

To maximize a player's minimum gain while minimizing the opponent's maximum gain.

What is the value of a non-terminal state?

The best achievable outcome (utility) from that state.

What does the minimax search algorithm compute?

Each node's minimax value, representing the best achievable utility against an optimal adversary.

What is the time complexity of the minimax algorithm?

O(b^m), where b is the branching factor and m is the maximum depth.

What happens to the values of intermediate nodes in alpha-beta pruning?

They might be incorrect, but the root's minimax value remains unaffected.

What is the effect of good child ordering in alpha-beta pruning?

It improves the effectiveness of pruning, potentially dropping time complexity to O(b^(m/2)).

What is a depth-limited search in game trees?

A search that only explores to a limited depth and uses an evaluation function for non-terminal positions.

What is an evaluation function in game theory?

A function that scores non-terminal positions in depth-limited search, ideally returning the actual minimax value.

What is the main challenge of realistic games in minimax algorithms?

The inability to search to the leaves of the game tree due to resource limits.

What are terminal utilities in game theory?

Values assigned to terminal states that represent the outcome for players.

What is the transition function in game theory?

A function that describes how actions lead to new states (S x A → S).

What is the difference between zero-sum and general-sum games?

In zero-sum games, one player's gain is another's loss; in general-sum games, players have independent utilities.

What is the minimax implementation's recursive structure?

It involves functions for max-value and min-value, alternating between maximizing and minimizing utilities.

What does the minimax example illustrate?

The calculation of values for game states based on the minimax algorithm.

What is the role of the utility tuples in multi-agent utilities?

Each player maximizes its own utility component from the terminal states.

What is the impact of resource limits on game tree searches?

They restrict the depth of search and require the use of evaluation functions for non-terminal positions.

What is the expected outcome of a minimax algorithm against a perfect player?

It is optimal, but against non-optimal players, the outcome may vary.

What is the significance of emergent coordination in multi-agent games?

It allows for dynamic cooperation and competition among players.

What is the significance of depth in evaluation functions?

The deeper in the tree the evaluation function is buried, the less the quality of the evaluation function matters.

What are games considered in the context of decision problems?

Games are decision problems with two or more agents.

What defines optimal decisions in zero-sum games?

Optimal decisions are defined by the minimax strategy.

What is the purpose of Expectimax search?

Expectimax search computes the average score under optimal play, considering chance nodes.

How does Expectimax differ from Minimax?

Expectimax accounts for uncertainty and computes expected utilities, while Minimax focuses on worst-case outcomes.

What is Expectiminimax?

Expectiminimax is used in games like Backgammon, where there is an extra random agent that moves after each min/max agent.

What happens to the probability of reaching a search node as depth increases?

The probability of reaching a given search node shrinks, diminishing the usefulness of the search.

What is the challenge with pruning in Expectiminimax?

Pruning is trickier due to the additional randomness introduced by the extra agent.

What does the term 'mixed layer types' refer to in game theory?

It refers to scenarios where different types of agents interact, such as deterministic and probabilistic agents.

What is the expected utility in Expectimax?

It is calculated as the weighted average of the utilities of the child nodes.

What is the significance of the term 'chance node' in Expectimax?

A chance node represents an outcome that is not under the control of the player, such as randomness in the environment.

What is the impact of evidence on probabilities?

As more evidence is gathered, probabilities may change based on updated information.

What is the role of simulations in determining probabilities for chance nodes?

Simulations help estimate the probabilities of outcomes for chance nodes based on the behavior of opponents.

What is the expected outcome of a chance node with multiple possible outcomes?

The expected outcome is the sum of the probabilities of each outcome multiplied by their respective utilities.

What is the significance of the term 'adversarial games'?

Adversarial games assume the presence of an opponent, influencing the strategies used by players.

What is the challenge of finding exact solutions in games like chess?

Exact solutions are impossible even for small games due to the vast number of possible game states.

What is the relationship between depth of search and computational complexity?

As depth increases, the computational complexity grows exponentially, making it harder to evaluate all possible outcomes.

What is a utility in the context of game theory?

Utility represents the satisfaction or value that a player derives from a particular outcome.

How does the concept of 'non-negative probabilities' apply in probability theory?

Probabilities must always be non-negative and sum to one across all possible outcomes.

What is the primary method used in MCTS for evaluating positions?

Evaluation by rollouts, where multiple games are played to termination from a state.

What does MCTS stand for?

Monte Carlo Tree Search

Why is alpha-beta search ineffective for games like Go?

Because Go has a branching factor (b) greater than 300, making fixed horizon assumptions impractical.

What are the two main ideas combined in MCTS?

Evaluation by rollouts and selective search.

What is the goal of a rollout in MCTS?

To play a move according to a fixed, fast rollout policy and record the result.

What does the fraction of wins in rollouts correlate with?

The true value of the position.

What is the purpose of allocating rollouts to more promising nodes in MCTS?

To improve the decision-making process by focusing on nodes that are likely to yield better outcomes.

What does the UCB1 formula in MCTS combine?

Exploitation and exploration.

What is the UCT in MCTS?

Upper Confidence Bound for Trees, a method that applies UCB to choose paths in the search tree.

What happens in MCTS when a new child node is added?

A rollout is run from the new child node, and win counts are updated back to the root.

What is the relationship between the number of rollouts (N) and the minimax move in MCTS?

As N approaches infinity, MCTS approximates the minimax move.

What is a key difference between minimax and MCTS?

Minimax uses exact evaluations, while MCTS uses simulations to approximate values.

What are some applications of MCTS mentioned in the notes?

Chess, Go, and partial-information games in economics like poker.

What challenges do video games present for MCTS?

High branching factors, large state spaces, partial observability, and multiple players.

What is the significance of the theorem regarding UCT and minimax?

It states that as N approaches infinity, UCT selects the minimax move.

What is the utility of the number of rollouts from a node (N(n)) in MCTS?

It helps determine the exploration versus exploitation balance in the search process.

What does U(n) represent in the UCB1 formula?

The total utility of rollouts (e.g., number of wins) for the player at the parent node.

What is the outcome of MCTS Version 0?

It records the fraction of wins from rollouts at each child of the root and picks the best move.

How does MCTS Version 1.0 improve upon earlier versions?

By allocating rollouts to both promising and uncertain nodes.

What is a limitation of alpha-beta pruning in large state spaces?

It becomes ineffective due to the vast number of possible moves and outcomes.