SEARCH

Question 1

An entity that perceives its environment and acts upon that environment.

Answer 1

Agent

Question 2

A configuration of an agent in its environment

Answer 2

State

Question 3

The state from which the search algorithm starts

Answer 3

Initial State

Question 4

Choices that can be made in a state.

Answer 4

Actions

Question 5

A description of what state results from performing any applicable action in any state

Answer 5

Transition Model

Question 6

The set of all states reachable from the initial state by any sequence of actions.

Answer 6

State Space

Question 7

The condition that determines whether a given state is a goal state

Answer 7

Goal Test

Question 8

A numerical cost associated with a given path

Answer 8

Path Cost

Question 9

A sequence of actions that leads from the initial state to the goal state.

Answer 9

Solution

Question 10

A solution that has the lowest path cost among all solutions.

Answer 10

Optimal Solution

Question 11

Node - a data structure that contains the following:

Answer 11

• A state
• Its parent node
• Action
• Path cost

Question 12

The mechanism that “manages” the nodes

Answer 12

Frontier

Question 13

Exhausts each one direction before trying another direction

Answer 13

Depth-First Search Algorithm

Question 14

In depth-first search, the frontier is managed as a ____

Answer 14

stack data structure

Question 15

Pros and Cons of depth-first search

Answer 15

Pros:
1. At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then depth-first search takes the least possible time to get to a solution.
Cons:
1. It is possible that the found solution is not optimal.
2. At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

Question 16

Opposite of depth-first search

Answer 16

breadth-first search

Question 17

This algorithm follows multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction

Answer 17

breadth-first search algorithm

Question 18

In breadth-first search, the frontier is managed as a ____

Answer 18

queue data structure

Question 19

Pros and Cons of breadth-first search

Answer 19

Pros:
1. This algorithm is guaranteed to find the optimal solution.
Cons:
1. This algorithm is almost guaranteed to take longer than the minimal time to run.
2. At worst, this algorithm takes the longest possible time to run.

Question 20

A type of algorithm that considers additional knowledge to try to improve its performance

Answer 20

informed search algorithm

Question 21

This algorithm do not utilize any knowledge about the problem that they did not acquire through their own exploration

Answer 21

uninformed search algorithm

Question 22

Expands the node that is the closest to the goal, as determined by a heuristic function h(n).

Answer 22

Greedy best-first search

Question 23

the function that estimates how close to the goal the next node is

Answer 23

heuristic function

Question 24

ignores walls and counts how many steps up, down, or to the sides it would take to get from one location to the goal location

Answer 24

Manhattan distance

Question 25

Examples of uninformed search algorithm

Answer 25

Breadth-first and depth-first

Question 26

A development of the greedy best-first algorithm

Answer 26

A* Search

Question 27

Considers not only h(n), the estimated cost from the current location to the goal, but also g(n), the cost that was accrued until the current location

Answer 27

A* Search

Question 28

For A* search to be optimal, the heuristic function, h(n), should be:

Answer 28

1. Admissible, or never overestimating the true cost, and 2. Consistent, To put it in an equation form, h(n) is consistent if for every node n and successor node n’ with step cost c, h(n) ≤ h(n’) + c.

Question 29

the algorithm faces an opponent that tries to achieve the opposite goal.

Answer 29

adversarial search

Question 30

A type of algorithm in adversarial search

Answer 30

Minimax

Question 31

represents winning conditions as (-1) for one side and (+1) for the other side.

Answer 31

Minimax

Question 32

Max-value pseudocode

Answer 32

Function Max-Value(state) v = -∞ if Terminal(state): ​ return Utility(state) for action in Actions(state): ​ v = Max(v, Min-Value(Result(state, action))) return v

Question 33

Min-value pseudocode

Answer 33

Function Min-Value(state) v = ∞ if Terminal(state): ​ return Utility(state) for action in Actions(state): ​ v = Min(v, Max-Value(Result(state, action))) return v

Question 34

A way to optimize Minimax

Answer 34

Alpha-beta pruning

Question 35

skips some of the recursive computations that are decidedly unfavorable

Answer 35

Alpha-beta pruning

Question 36

considers only a pre-defined number of moves before it stops, without ever getting to a terminal state.

Answer 36

Depth-limited Minimax

Question 37

Depth-limited minimax relies on

Answer 37

evaluation function

Question 38

estimates the expected utility of the game from a given state, or, in other words, assigns values to states

Answer 38

evaluation function

Question 39

Of the four search algorithms discussed in lecture — depth-first search, breadth-first search, greedy best-first search with Manhattan distance heuristic, and A* search with Manhattan distance heuristic — which one (or multiple, if multiple are possible) could be the algorithm used?

Answer 39

Could only be DFS

Question 40

Between depth first search (DFS) and breadth first search (BFS), which will find a shorter path through a maze?

Answer 40

BFS will sometimes, but not always, find a shorter path than DFS

Question 41

Why is depth-limited minimax sometimes preferable to minimax without a depth limit?

Answer 41

Depth-limited minimax can arrive at a decision more quickly because it explores fewer states

Question 42

Consider the Minimax tree below, where the green up arrows indicate the MAX player and red down arrows indicate the MIN player. The leaf nodes are each labelled with their value. What is the value of the root node?

Answer 42

5