MI-AI MCQ: Heuristic Searches

Problems with MiniMax algorithm efficiency?

Combinatorial Explosion leads to search trees being too large
Evaluation of positions is time consuming

What are the values in MiniMax algorithm called?

Utility Values

Why is the MiniMax algorithm difficult for larger problems?

May not be able to represent it through a search tree

What is the Minimax Algorithm?

An algorithm used in game playing where one opponent tries to maximise their chance of winning and minimise their opponent's chance at every move

Talk through how the MiniMax algorithm works (different for different problems of course)
Set of values at terminal positions (triangles) at the bottom.
Level above is the last player who played a move
If + value is PC winning and they played the last move, we move every positive value up to their parents
If - value is ME winning, on the level above that, move the smaller values up to their parents
Keep going until you reach the root

What does it mean to use the Manhattan Distancing as a heuristic?

Means that the heuristic cost, h, is the sum of the x and y distances from the current state to goal state

Why is a straight line distance an admissible heuristic?

Never over-estimates the cost from current state to goal