Week 3: Informed Search Algorithms

Question 1

Informed
(heuristic) search

Answer 1

A heuristic is:
* A function that estimates how close a state is
to a goal
* Designed for a particular search problem
* Examples: Manhattan distance, Euclidean
distance for pathing

Question 2

Best First Search Algorithm

Answer 2

Idea: use an evaluation function for each node
* estimate of “desirability”
⇒ Expand most desirable unexpanded node

Implementation: fringe is a queue sorted in decreasing order
of desirability

Special cases:
* greedy search
* A* search

Question 3

Greedy search

Answer 3

Evaluation function h(n) is a heuristic
* It estimates the cost from n to the closest goal

Greedy search expands the node that appears to be closest to goal

Question 4

Completeness of greedy search?

Answer 4

Time: O(b^m)
Space: O(b^m)
Not complete! - unless you use repeated-state checking
Not Optimal

All nodes are kept in memory

Question 5

A* search

Answer 5

Idea: avoid expanding paths that are already expensive
* Evaluation function f(n) = g(n) + h(n)
* g(n) = cost so far to reach n
* h(n) = estimated cost to goal from n
* f(n) = estimated total cost of path through n to goal

A* search uses an admissible heuristic

Theorem: A* search is optimal

Question 6

Admissible Heuristics

Answer 6

A heuristic is admissible (optimistic) if:

0 <= h(n) <= h*(n)

Question 7

Properties of A*

Answer 7

• Complete: Yes, unless there are infinitely many nodes with f <= f(G)
• Time: Exponential in [relative error in h × length of solution].
• Space: Keeps all nodes in memory
• Optimal: Yes

Question 8

Adversarial Search

Answer 8

Adversarial search is a search, where we examine the problem which arises when we try to plan ahead of the world and other agents are planning against us

Question 9

Types of Games in AI

Answer 9

Perfect information: agents can look into the complete board. Agents have all the information about the game, and they can see each other moves also. Examples are Chess, Checkers

Imperfect information: agents do not have all information about the game and not aware with what’s going on, such type of games are called the game with imperfect information, such as tic-tac-toe, Battleship

Deterministic games: Deterministic games are those games which follow a strict pattern and set of rules for the games, and there is no randomness associated with them

Non-deterministic games: Non-deterministic are those games which have various unpredictable events and has a factor of chance or luck. This factor of chance or luck is introduced by either dice or cards. These are random, and each action response is not fixed

Question 10

Zero-Sum Game

Answer 10

In Zero-sum game each agent’s gain or loss of utility is exactly balanced by the losses or gains of utility of another agent.

One player of the game try to maximize one single value, while other player tries to minimize it.

Question 11

Minimax

Answer 11

Perfect play for deterministic, perfect-
information games

Idea: choose move to position with
highest minimax value