Games and search Flashcards
What kind of games are zero-sum games?
Games where a good move for one player is bad for the other player.
What assumption does the computer have of the opponent?
That the opponent plays optimally.
What does ply mean?
The number of moves ahead.
What is a minimax-tree?
A tree for representing zero-sum games. It is called minimax because it wants to max its own utility and minimize the utility when it is out of turn (Since it assumes opponent plays optimally)
How does alpha-beta pruning work?
Works by using a variable alpha holding the best possible value for MAX-player, and a variable beta holding the best possible value for MIN-player.
If at any point beta is less than alpha, we can prune.
Will still find optimal solution.
What is the difference between type-A and type-B search?
Type-A: Considers all possible moves to a certain depth, and estimates utility of states at that depth based on heuristic function. (Wide but shallow)
Type-B: Ignores moves that look bad, and follows promising lines as deep as possible. (Deep but narrow)
What is the difference between alpha-beta pruning and heuristic alpha-beta pruning?
Heuristic alpha-beta pruning search cuts early and applies a heuristic function to states due to computation time.
What is the horizon effect?
The horizon effect is when an opponent move that causes serious damage and is unavoidable happens.
Makes the program make bad moves to delay the inevitable.
What is the characteristics of forward pruning?
Prunes moves that appear to be bad moves, at the risk of making an error. (Used by humans)
What characterizes beam search in the context of games and search?
A variant of forward-pruning, where only the n best moves according to the evaluation function are checked.
What characterizes Monte Carlo Tree Search (MCTS)?
The value of a state is estimated as the average utility of a number of simulations of complete games starting from the state.
Disadvantage: Might fail to consider certain moves.
In what cases are Monte Carlo Tree Search preferable?
It is preferable for games with a very high branching factor, because other search algorithms just can’t search deep enough in a reasonable time.
Also useful for cases where it is difficult to determine a good evaluation function.
