RL

What is reinforcement learning?

A method where an agent learns to make decisions by receiving rewards or penalties based on its actions.

What are the two main types of reinforcement learning?

Model-based and model-free reinforcement learning.

What does model-based reinforcement learning involve?

Learning a model of the environment, solving it, and executing the solution.

What is model-free reinforcement learning?

Learning values directly from experiences to make decisions without a model.

What is temporal difference learning?

A method in reinforcement learning that updates estimates based on other learned estimates without waiting for a final outcome.

What is Q-learning?

A model-free reinforcement learning algorithm that learns the value of actions in states to inform decision-making.

What is a Markov Decision Process (MDP)?

A mathematical framework for modeling decision-making where outcomes are partly random and partly under the control of a decision maker.

What are the key components of an MDP?

States, actions, transition probabilities, and rewards.

What is the purpose of adversarial search in game playing?

To compute strategies for games with multiple agents, often involving competition.

What is the minimax algorithm?

A decision rule for minimizing the possible loss while maximizing the potential gain in zero-sum games.

What is α-β pruning?

An optimization technique for the minimax algorithm that eliminates branches in the search tree that won't affect the final decision.

What defines a zero-sum game?

A situation in which one player's gain is equivalent to another's loss, resulting in a net change of zero.

What is a deterministic game?

A game where the outcome is determined by the players' actions without any randomness.

What are terminal states in game trees?

States in a game where the game ends and a utility value is assigned based on the outcome.

What is the value of a state in adversarial games?

The best achievable outcome (utility) from that state considering optimal play by opponents.

What is the significance of the game tree in minimax?

It represents all possible moves and outcomes, allowing for the evaluation of strategies.

What is the role of the transition function in an MDP?

It defines how the state changes in response to an action taken by the agent.

What is the difference between deterministic and stochastic games?

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

What is the significance of the terminal test in game trees?

It determines whether a game state is a terminal state, signaling the end of the game.

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 a general-sum game?

A game where the total utility can vary, allowing for cooperation and competition among players.

What is the purpose of utility tuples in multi-agent games?

To represent the utility for each player, allowing for the evaluation of strategies in games with multiple players.

What is the outcome of the first computer world champion in Checkers?

In 1995, the first computer world champion in Checkers was crowned.

What breakthrough did Deep Blue achieve in Chess?

In 1997, Deep Blue defeated human champion Garry Kasparov.

What significant development occurred in Go between 2016-2017?

AlphaGo defeated human world champions in Go.

What is the main goal of algorithms in game playing?

To calculate a strategy (policy) that recommends the best move from every possible state.

What is the importance of search algorithm properties?

To determine if a search algorithm is complete (guarantees a solution) and optimal (guarantees the least cost path).

What is the purpose of algorithms in game strategies?

To calculate a policy that recommends a move from every possible state.

What are the main components of a game formalization?

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

What is a policy in the context of game strategies?

A mapping from states to actions (S → A).

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

In zero-sum games, agents have opposite utilities; in general-sum games, agents have independent utilities.

What is the value of a non-terminal state?

The best achievable outcome (utility) from that state.

What is the minimax algorithm used for?

To compute the best achievable utility against a rational adversary in deterministic, zero-sum games.

What is the role of the max and min functions in minimax?

Max function seeks to maximize the player's outcome, while min function seeks to minimize the opponent's outcome.

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 does alpha-beta pruning do?

It reduces the number of nodes evaluated in the minimax algorithm by eliminating branches that won't affect the final decision.

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

Good child ordering can improve the effectiveness of pruning, potentially reducing time complexity to O(b^(m/2)).

What happens when a game has multiple players?

The minimax algorithm generalizes to handle utility tuples for each player, allowing for cooperation and competition.

What is a depth-limited search in game trees?

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

What is an evaluation function in game strategies?

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

What is the impact of resource limits on game strategies?

In realistic games, resource limits prevent searching to the leaves of the game tree, necessitating depth-limited searches.

What is the outcome of using a depth-limited search?

Guarantee of optimal play is lost, but it allows for practical play within time constraints.

What is the role of the transition function in game strategies?

It defines how the game state changes in response to actions taken by players.

What is a terminal test in game strategies?

A function that determines whether a game state is a terminal state (end of the game).

How are terminal utilities defined?

They are defined as a mapping from terminal states and players to real numbers (S x P → R).

What is the minimax value of a terminal state?

The utility value assigned to that state, representing the outcome of the game.

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

It allows agents to adapt their strategies dynamically based on the actions of others.

What does the minimax implementation involve?

Recursive functions that compute the max and min values for states based on their successors.

What is the effect of pruning on the minimax algorithm?

Pruning can lead to faster decision-making by ignoring branches that do not affect the outcome.

What is the relationship between game tree depth and play quality?

Deeper searches generally lead to better play, but require more computational resources.

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

It guarantees optimal play, but against suboptimal players, the outcome may vary.

What is the main purpose of evaluation functions in game algorithms?

To assess the quality of game states and guide decision-making.

What happens to the quality of evaluation functions as the depth of the search tree increases?

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

What is the time complexity of a minimax algorithm?

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

What is alpha-beta pruning?

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

What is the time complexity of alpha-beta pruning with ideal node ordering?

O(b^(m/2)).

What are Markov Decision Processes (MDPs) used for?

To handle situations with randomness in decision-making, such as in games like Blackjack.

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

In zero-sum games, one player's gain is another's loss, while non-zero-sum games can have mutual benefits.

What is Expectimax search?

A search algorithm that computes expected values under optimal play, considering chance nodes.

How does Expectimax handle chance nodes?

It calculates the expected utilities by taking the weighted average of the outcomes.

What is a random variable?

An event whose outcome is uncertain.

What is a probability distribution?

An assignment of weights to all possible outcomes of a random variable.

What is the expected value of a function of a random variable?

The average value weighted by the probability distribution over outcomes.

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

It represents outcomes controlled by randomness rather than an adversary.

What is the main challenge of solving games like chess?

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

What is the role of probabilities in Expectimax search?

Probabilities model how the opponent or environment will behave in any given state.

What is the Expectiminimax algorithm?

An extension of Expectimax that incorporates an additional random agent in the decision process.

How does the depth of search affect the usefulness of search algorithms?

As depth increases, the probability of reaching a given search node shrinks, diminishing usefulness.

What is the significance of TDGammon in AI history?

It was the first AI world champion in any game, utilizing depth-2 search and reinforcement learning.

What is the expected utility in Expectimax?

The average score calculated under optimal play, considering both max and chance nodes.

What is the purpose of pruning in Expectimax?

To reduce the number of nodes evaluated while maintaining optimal choices.

What is the relationship between game depth and search node probability?

As depth increases, the probability of reaching a search node decreases.

What does the term 'multi-agent utilities' refer to?

Utilities in games that are not zero-sum or involve multiple players.

What is a depth-limited Expectimax?

An Expectimax search that limits the depth to reduce computation while estimating values.

What is the impact of randomness in game playing?

It introduces uncertainty in outcomes, requiring algorithms to adapt to unpredictable scenarios.

What are the implications of using informed probabilities in game search?

They allow for more strategic decision-making based on the opponent's likely actions.

What is the expected outcome when using Expectimax with a depth-2 minimax opponent?

The strategy should be to use Expectimax to account for the opponent's probabilistic behavior.

What does MCTS stand for?

Monte Carlo Tree Search

What type of games is MCTS particularly useful for?

Games with large state spaces, such as Go.

What are the two key ideas combined in MCTS?

Evaluation by rollouts and selective search.

What is the purpose of rollouts in MCTS?

To play multiple games to termination from a state and count wins and losses.

What does the fraction of wins from rollouts correlate with?

The true value of the position.

What is the first version of MCTS focused on?

Performing N rollouts from each child of the root and recording the fraction of wins.

How does MCTS Version 0.9 improve upon Version 0?

By allocating rollouts to more promising nodes.

What does UCB stand for in the context of MCTS?

Upper Confidence Bound.

What does the UCB1 formula combine?

Exploitation and exploration.

What is the main goal of MCTS?

To approximate the minimax value of a node using simulations.

What does the theorem state about UCT as N approaches infinity?

UCT selects the minimax move.

What is a significant limitation of alpha-beta pruning?

It does not work well for large state spaces.

What is the relationship between the number of rollouts and the concentration of rollouts in MCTS?

As N increases, rollouts concentrate in the best child(ren).

What is the utility of the node U(n) in MCTS?

It represents the total utility of rollouts (e.g., number of wins) for the parent player.

What does the term 'bounded-depth search' refer to in game decision-making?

Searching to a limited depth due to computational constraints.

How does MCTS handle uncertainty in decision-making?

By allocating rollouts to uncertain nodes.

What does MCTS aim to achieve in terms of computation efficiency?

Efficient use of computation in decision-making for games.

What is the significance of reinforcement learning in the context of MCTS?

It has been influenced by game-playing strategies like MCTS.

What challenges do video games present compared to traditional board games?

Higher branching factors, larger state spaces, and often more than two players.