Games & AI

Question 1

What are the 04 components of games as search?

Answer 1

1. Initial state
2. Successor function - list of moves
3. Terminal state - is the game over?
4. Utility function - numerical value of state

Question 2

What are the 02 major differences between game trees and search trees?

Answer 2

In game trees,
1. you have an opponent
2. you have to generate the whole tree

Question 3

What are the main components of a search problem? (06)

Answer 3

1. start state
2. goal state
3. operators/ actions
4. step cost –> path cost
5. heuristic
6. constraints

Question 4

What are the components of a search solution?

Answer 4

1. a problem graph
2. a tree
3. a strategy
4. a fringe
5. a solution path
6. cost of the solution

Question 5

Name 4 uninformed search algorithms and their queue type

Answer 5

1. BFS -
2. DFS -
3. IDS -
4. UCS -

Question 6

Name 2 informed search algorithms and their queue type

Answer 6

1. GBFS -
2. A* -

Question 7

What do
1) Visiting a node
2) Exploring a node
mean?

Answer 7

1) Visiting/Expanding - going to node
2) Exploring - exploring child nodes

Question 8

What is the heuristic?

Answer 8

It is a function h(n), that gives the distance from the node (n) to the goal.

Question 9

What is an admissible heuristic?

Answer 9

A heuristic function that always underestimates the distance to the goal. (eg. straight line, manhattan dist).
* if admissible –> A* gives least cost