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

What makes a heuristic admissible for a heuristic algorithm?

Heuristic function must never overestimate the cost to reach the goal (i.e. not larger than the lowest possible cost from current state to the goal)

When does the A* algorithm become greedy and lose optimality?

When the heuristic cost, h, is so large it dominates g.

What is a greedy algorithm?

An algorithm that picks the locally-optimal/best choice at the moment in the hope it will lead to a globally-optimal solution.

When does the A* algorithm become Uniform Cost Search?

When the heuristic cost, h, is 0

What is the A* Search Algorithm?

A Heuristic search which combines the cost so far and the estimated cost to goal.
f(n) = g(n) + h(n) where g is path cost from initial state to current, h is heuristic cost from current state to goal and f is the overall estimated cost.

How does a heuristic function differ from a blind function?

Heuristics use domain knowledge to explore the next best node which is most likely to lead to a goal state.
Makes educated guesses.
Directed search.

What is a Heuristic function?

A function to inform the search about the direction to a goal

What is a Blind Search?

A search which has no information about its domain.
All it can do is distinguish a non-goal state from a goal state.