CMPUT 455 MIDTERM QUESTIONS & ANSWERS
What is cognitorial search? - Answers -A search method with many options but few
solutions, often involving guessing and checking.
Give an example of a real-life application of cognitorial search. - Answers -Pathfinding
in vehicle routing for video games and map applications.
What is combinatorial search? - Answers -A search method dealing with a finite
number of discrete states, requiring a goal to satisfy.
What is the purpose of depth-first search (DFS)? - Answers -To find any path from a
start state to an end state, using a stack data structure.
What is the main drawback of DFS? - Answers -It can get stuck in infinite loops or lead
to suboptimal solutions.
How does breadth-first search (BFS) differ from DFS? - Answers -BFS uses a queue
and guarantees finding the shortest path by exploring closest states first.
What is the significance of heuristics in search algorithms? - Answers -Heuristics
provide additional information to improve search efficiency, especially in pathfinding.
What is the A* (A star) search algorithm? - Answers -A search algorithm that utilizes
heuristics and a priority queue to find the shortest path efficiently.
What does the function f(s) represent in A* search? - Answers -f(s) = d(s) + h(s), where
d(s) is the distance from the start and h(s) is the heuristic estimate to the end.
What is the difference between deterministic and stochastic games? - Answers -
Deterministic games have predictable outcomes, while stochastic games involve
randomness.
What is a zero-sum game? - Answers -A situation where one player's gain is exactly
balanced by the losses of other players.
Define a directed acyclic graph (DAG). - Answers -A graph with no loops or cycles,
where edges have a direction.
What is the role of parent and child states in search algorithms? - Answers -Parent
states have actions leading to child states, forming a tree structure in the search space.
What is the purpose of a search space? - Answers -To define all reachable states
relevant to a specific goal in a search algorithm.
, What is the concept of a power set in combinatorial search? - Answers -The set of all
different subsets of a given set, denoted as |P(S)| = 2^|S|.
What is the significance of the Manhattan distance in heuristics? - Answers -It
measures the absolute distance from the target using the formula |x1 - x2| + |y1 - y2|.
What is a tree in the context of search algorithms? - Answers -A graph where every
node has at least one parent, representing a hierarchical structure.
What are reachable states? - Answers -States that can be accessed from the root state
through a series of actions.
What is the main goal of search algorithms? - Answers -To discover states and the
actions connecting them to find a goal.
What is the difference between perfect and imperfect information in games? - Answers
-Perfect information means all relevant info is known, while imperfect information means
some is hidden.
What is the significance of backtracking in DFS? - Answers -Backtracking allows the
algorithm to return to previous states when no actions are available.
What is the purpose of using a priority queue in A* search? - Answers -To explore
states based on their estimated distance to the end, optimizing the search process.
What is a multi-agent game? - Answers -A game involving multiple players or agents,
often competing against each other.
What is a classical game theory example? - Answers -The prisoner's dilemma, where
two players choose actions simultaneously.
What is the new game introduced this year about? - Answers -Powers of Exponent 2,
where players create lines for points based on their length.
What is the purpose of a nested loop in game state checking? - Answers -To check all
the lines on the board that could be scoring.
Why is creating all game states in memory inefficient? - Answers -It is highly inefficient
for games like tic-tac-toe; states should only be created as needed.
Which search algorithm is better for game state exploration, DFS or BFS? - Answers -
BFS is better for exploring game states.
What are admissible heuristics? - Answers -Heuristics that never overestimate the
distance between the start and end states.
What is cognitorial search? - Answers -A search method with many options but few
solutions, often involving guessing and checking.
Give an example of a real-life application of cognitorial search. - Answers -Pathfinding
in vehicle routing for video games and map applications.
What is combinatorial search? - Answers -A search method dealing with a finite
number of discrete states, requiring a goal to satisfy.
What is the purpose of depth-first search (DFS)? - Answers -To find any path from a
start state to an end state, using a stack data structure.
What is the main drawback of DFS? - Answers -It can get stuck in infinite loops or lead
to suboptimal solutions.
How does breadth-first search (BFS) differ from DFS? - Answers -BFS uses a queue
and guarantees finding the shortest path by exploring closest states first.
What is the significance of heuristics in search algorithms? - Answers -Heuristics
provide additional information to improve search efficiency, especially in pathfinding.
What is the A* (A star) search algorithm? - Answers -A search algorithm that utilizes
heuristics and a priority queue to find the shortest path efficiently.
What does the function f(s) represent in A* search? - Answers -f(s) = d(s) + h(s), where
d(s) is the distance from the start and h(s) is the heuristic estimate to the end.
What is the difference between deterministic and stochastic games? - Answers -
Deterministic games have predictable outcomes, while stochastic games involve
randomness.
What is a zero-sum game? - Answers -A situation where one player's gain is exactly
balanced by the losses of other players.
Define a directed acyclic graph (DAG). - Answers -A graph with no loops or cycles,
where edges have a direction.
What is the role of parent and child states in search algorithms? - Answers -Parent
states have actions leading to child states, forming a tree structure in the search space.
What is the purpose of a search space? - Answers -To define all reachable states
relevant to a specific goal in a search algorithm.
, What is the concept of a power set in combinatorial search? - Answers -The set of all
different subsets of a given set, denoted as |P(S)| = 2^|S|.
What is the significance of the Manhattan distance in heuristics? - Answers -It
measures the absolute distance from the target using the formula |x1 - x2| + |y1 - y2|.
What is a tree in the context of search algorithms? - Answers -A graph where every
node has at least one parent, representing a hierarchical structure.
What are reachable states? - Answers -States that can be accessed from the root state
through a series of actions.
What is the main goal of search algorithms? - Answers -To discover states and the
actions connecting them to find a goal.
What is the difference between perfect and imperfect information in games? - Answers
-Perfect information means all relevant info is known, while imperfect information means
some is hidden.
What is the significance of backtracking in DFS? - Answers -Backtracking allows the
algorithm to return to previous states when no actions are available.
What is the purpose of using a priority queue in A* search? - Answers -To explore
states based on their estimated distance to the end, optimizing the search process.
What is a multi-agent game? - Answers -A game involving multiple players or agents,
often competing against each other.
What is a classical game theory example? - Answers -The prisoner's dilemma, where
two players choose actions simultaneously.
What is the new game introduced this year about? - Answers -Powers of Exponent 2,
where players create lines for points based on their length.
What is the purpose of a nested loop in game state checking? - Answers -To check all
the lines on the board that could be scoring.
Why is creating all game states in memory inefficient? - Answers -It is highly inefficient
for games like tic-tac-toe; states should only be created as needed.
Which search algorithm is better for game state exploration, DFS or BFS? - Answers -
BFS is better for exploring game states.
What are admissible heuristics? - Answers -Heuristics that never overestimate the
distance between the start and end states.
