Flashcard Questions - AI

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

contains the following data:
* A state
* Its parent node, through which the current node was generated
* The action that was applied to the state of the parent to get to the current node
* The path cost from the initial state to this node

Answer 11

node

Question 12

the mechanism that “manages” the nodes

Answer 12

frontier

Question 13

search algorithm that exhausts each one direction before trying another direction

Answer 13

Depth-First Search

Question 14

search algorithm where the frontier is managed as a stack data structure

Answer 14

Depth-First Search

Question 15

search algorithm that will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction.

Answer 15

Breadth-First Search

Question 16

search algorithm where the frontier is managed as a queue data structure

Answer 16

Breadth-First Search

Question 17

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

Answer 17

Informed Search Algorithm

Question 18

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

Answer 18

Greedy Best-First Search

Question 19

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 19

Manhattan Distance

Question 20

function that estimates how close to the goal the next node is, but it can be mistaken.

Answer 20

heuristic function

Question 21

The efficiency of the greedy best-first algorithm depends on

Answer 21

how good a heuristic function is

Question 22

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 22

A* Search

Question 23

For a* search to be optimal, the heuristic function has to be:

Answer 23

Admissible & Consistent

Question 24

In the heuristic function h(n) of an A* search algorithm, it is consistent if

Answer 24

for every node n and successor node n’ with step cost c, n ≤ n’ + c

Question 25

In the heuristic function h(n) of an A* search algorithm, what does it mean to be admissible?

Answer 25

Never overestimates the actual cost to reach a goal from any node

Question 26

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

Answer 26

Adversarial Search

Question 27

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

Answer 27

Minimax

Question 28

Recursively, the algorithm simulates all possible games that can take place beginning at the current state and until a terminal state is reached. Each terminal state is valued as either (-1), 0, or (+1).

Answer 28

Minimax

Question 29

an optimization technique for minimax that skips some of the recursive computations that are decidedly unfavorable

Answer 29

Alpha-Beta Pruning

Question 30

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

Answer 30

Depth-Limited Minimax

Question 31

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

Answer 31

Evaluation function