Game Playing Flashcards
(25 cards)
What is the important question for a machine to decide in game playing?
What is my best next move?
What must be considered when making decisions in game playing?
The opponent’s possible moves
In the MinMax algorithm, who does MAX represent?
The player we want to be the winner
In the MinMax algorithm, who does MIN represent?
The evil opponent
What does each level of the MinMax tree represent?
Either MIN or MAX
How are leaf nodes labeled in the MinMax algorithm?
- A positive number if MAX wins
- A negative number if MIN wins
What is propagated from leaf nodes towards the root in the MinMax algorithm?
Node values based on whether the node is MAX or MIN
What is the best path in the MinMax algorithm?
The one that gives the maximum value if MAX plays
What is the n-ply look-ahead strategy?
Generate the game tree up to a depth n and evaluate leaf nodes using a heuristic function
What is the horizon effect?
The path may look promising but eventually lead to loss of the game
What is the size of the game tree in complex games described as?
Enormous due to combinatorial explosion
What does alpha-beta pruning improve?
The efficiency of the MinMax algorithm
What is the result of using alpha-beta pruning?
Can save up to √N evaluated terminal states
What are some examples of games that can be dealt with different algorithmic search approaches?
- Checkers
- Reversi (Othello)
- Backgammon
- Go
- Card games
What defines a game in game theory?
A formal representation of a situation in which individuals interact under strategic interdependence
What are the characteristics of a game?
- 2 players (agents) —- Multiple agents
- Deterministic———- Stochastic
- Turn-taking ———— Simultaneous moves
- Zero-sum ————— Non-zero sum
- Perfect Information - Imperfect Information
What is a strategy in game theory?
A complete plan or decision rule for how a player will act in each situation
What is the payoff matrix in game theory?
A table that describes the payoffs for each player based on their strategies
What is the prisoner’s dilemma?
A scenario where two individuals must decide to confess or refuse, affecting their prison time
What is a dominant strategy?
A strategy that leads to a better outcome regardless of the opponent’s choice
What is Pareto Optimal?
A situation in which all the improvements have been made
What is Nash Equilibrium?
A situation where no player can benefit by changing their strategy while others keep theirs unchanged (all of the players’ strategies would lead to an optimal choice)
What is the outcome of the prisoner’s dilemma?
It forms a Nash equilibrium but is not Pareto optimal
What factors can change the dynamics of a game?
- Repeated games
- Moral beliefs
- Limited rationality
