Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

AI > Exam 3 > Flashcards

Exam 3 Flashcards

Chapters 4 and 5

1
Q

What is the point of a local search algorithm?

A

To find the final state and not the path itself to get there (such as the 8-queens problem). Only the final configuration matters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a state-space landscape?

A

It’s the state-space shown as a landscape function, with each point (state) having it’s elevation which is defined by the value of the objective function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is hill-climbing search?

A

It’s a local search algorithm that continuously moves on to neighboring states with the highest value until it reaches a peak (no neighbor has a higher value)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a complete-state formulation?

A

Every state has all the components of a solution but they might not all be in the right place

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a greedy local search?

A

A local search algorithm that grabs a good neighbor state without thinking ahead about where to go next (sometimes hill climbing is greedy)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is stochastic hill climbing?

A

Hill climbing that chooses at random from among the uphill moves, depending on the probably of selection which varies with the steepness of the uphill move

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is first-choice hill climbing?

A

Stochastic hill climbing that generates successors randomly until one is generated that is better than the current state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

When would you use first-choice hill climbing?

A

When a state has many (thousands) of successors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is random-restart hill climbing?

A

It conducts a series of hill-climbing searches from randomly generated initial states until a goal is found

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Does the success of hill climbing depend on the shape of the state-space landscape?

A

Yes, a good solution is found quickly depending on the landscape and the algorithm used

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is simulated annealing?

A

It uses the concept of gradient descend (minimizing cost), starting at a high temperature then goes to the lowest temperature possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is local beam search?

A

It keeps track of k states rather than just one, and allows all parallel search threads to communicate information

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is stochastic beam search?

A

Local beam search that instead of choosing the top k successors, it chooses successors with a probability proportional to the successor’s value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are evolutionary algorithms?

A

Can be seen as variants of stochastic beam search, inspired by biological natural selection; There is a population of individuals (states) in which the fittest (highest value) individuals produce offspring (successor states) that populate the next generation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the process that evolutionary algorithms take called?

A

Recombination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a genetic algorithm?

A

Each individual is a string over a finite alphabet, in which all individuals are also recombined

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What makes up evolutionary algorithms?

A

Population size, individual representation, mixing number (p), selection process, recombination, and mutation rate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is constrained optimization?

A

Solutions having to satisfy some hard constraints on the values of variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What do we assume when we use search algorithms?

A

A fully observable, deterministic, known environment

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a belief state?

A

A set of physical states that the agent believes are possible, usually used in not fully observable and/or nondeterministic environments

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does a conditional plan do?

A

Specifies what to do depending on what percepts the agent receives while executing the plan

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does an AND-OR search tree consist of?

A

OR nodes (agent does this or that action), and AND nodes (agent needs to find plan for 2 or more states at the same time)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a cyclic solution?

A

It keeps trying a certain action until it works when that action isn’t guaranteed to execute

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a sensorless problem?

A

The agent percept’s provide no information at all

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is localization?

A

An agent working out where it is, given a map of it’s environment and a sequence of percepts and actions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is an offline search algorithm?

A

Agents that compute a complete solution before taking their first action

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is an online search algorithm?

A

Agents that interleave computation and action; first it takes an action, then observes the environment, then computes the next action

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What are online search algorithms best for?

A

In dynamic/semi-dynamic environments where an agent should not compute for too long, as well as nondeterministic domains

29
Q

What is the mapping problem?

A

A robot is placed in an unknown building and must explore to build a map that can later be used for getting from A to B, usually an example of online search

30
Q

What is the competitive ratio?

A

The comparison between the estimated cost of the total path and the optimal path

31
Q

What is the adversary argument?

A

The adversary constructing the state space while the agent explores it, with the adversary placed goals and dead ends wherever it chooses

32
Q

What makes a state space safely explorable?

A

Some goal state is reachable from every reachable state

33
Q

What is a random walk?

A

The agent simply selects at random one of the available actions from the current state, with preference to unexplored actions being possible

34
Q

What is optimism under uncertainty?

A

The assumption that an unexplored state will lead immediately to the goal with the least possible cost

35
Q

What is a competitive environment?

A

Two or more agents having conflicting goals, which creates adversarial problems

36
Q

How does an economy stance work in multi-agent environments?

A

The aggregate of a very large number of agents; increasing demand will cause prices to rise in general, don’t have to predict the action of individuals

37
Q

How does pruning work?

A

It “cuts off” (ignores) portions of the search tree that make no difference to the optimal move, saves time

38
Q

What is an evaluation function?

A

It estimates who is winning based on features of the state

39
Q

What is considered a game with imperfect information?

A

Games where not all possible information is known, such as card hands as in UNO or Poker

40
Q

What does zero-sum mean?

A

What is good for one player is just as bad for the other; no win-win outcome

41
Q

What does a game consist of?

A

Initial state (s0), To-Move(s), Actions(s), Result(s,a) (the transition model), Is-Terminal(s) (the terminal test), and Utility(s,p)

42
Q

What is a complete game tree?

A

A search tree that follows every sequence of moves all the way to a terminal state

43
Q

What is minimax search?

A

An algorithm used on a two-ply (two players) game tree, alternates between moves taken by each player, with each state having a minimax value (usually depending on the max player); can be thought of as working backwards from the terminal states to the root

44
Q

What is the minimax decision?

A

The optimal choice for max that leads to the state with the highest minimax value

45
Q

Describe the minimax search properties

A

Time complexity: O(b^M); space complexity O(bm)

46
Q

What is alpha-beta pruning?

A

Similar to minimax, but implements pruning of decisions that wouldn’t affect the optimal route; saves time and memory

47
Q

What do the alpha and beta values mean in minimax?

A

alpha is the value for the best choice for the MAX player and beta is the best choice for the MIN player

48
Q

What does the effectiveness of alpha-beta pruning depend on?

A

The order in which the states are examined

49
Q

What are transpositions?

A

Different permutations of the move sequence that end up in the same position

50
Q

What is the Type A strategy?

A

Considering all possible moves to a certain depth in the search tree, and then using a heuristic evaluation function to estimate the utility of states at that depth (explores wide but shallow portion)

51
Q

What is the Type B strategy?

A

Ignores moves that look bad and follows promising lines “as far as possible” (explores deep but narrow portion)

52
Q

What is the cutoff test?

A

A test that returns true for terminal tests, otherwise it is free to decide when to cut off the search

53
Q

How does the evaluation function vary?

A

For terminal states, Eval(s,p) = Utility(s,p); For nonterminal states, Utility(loss,p) <= Eval(s,p) <= Utility(win,p)

54
Q

What do most evaluation functions work with?

A

Features of the states, which are the characteristics of the game

55
Q

How does a weighted linear function work?

A

Eval(s) = w1f1(s) + … + wnfn(s); each feature is multiplied by their weight (how important a feature is)

56
Q

What is a quiescent position?

A

Positions in which there is no pending move that would wildly swing the evaluation

57
Q

What is the horizon effect?

A

When an opponent’s move will cause serious damage and is ultimately unavoidable but can be temporarily avoided by using delaying tactics

58
Q

What are singular extensions?

A

Moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point

59
Q

What is forward pruning?

A

Pruning that prunes moves that appear to be poor moves but could be possibly be good ones (is a Type B strategy)

60
Q

What is the late move reduction?

A

It reduces the depth to which we search for good moves, which can save time; based off the alpha value and decides if it re-runs the search with full depth

61
Q

What is the Monte Carlo tree search?

A

It works by using the value of a state that is estimated as the average utility over a number of simulations of complete games starting from the state

62
Q

What is the playout policy?

A

A bias for the good moves

63
Q

What is the pure Monte Carlo search?

A

Do N simulations starting from the current state of the game, and track which of the possible moves from the current position has the highest win percentage

64
Q

What is a selection policy?

A

It focuses on selecting the computational resources on the important parts of the game tree, balanced on explorations of states with few playouts and exploitation of states that have had well past playouts

65
Q

What is early playout termination?

A

Stopping a playout that is taking too many moves; evaluate it with a heuristic evaluation function or just declare it a draw

66
Q

What are stochastic games?

A

Games with a bit of unpredictability caused by a random element (such as throwing dice)

67
Q

What are chance nodes?

A

Often shown as circles as trees, denote all possible outcomes of an action that’s based off chance (all possible dice rolls)

68
Q

What is the expected value of a position?

A

The average over all possible outcomes of the chance nodes

69
Q

What is the expectiminimax value?

A

A generalization of the minimax value for deterministic games

AI (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions