### CS827: Adv. Artificial Intelligence

**Unit 2: Search and Games** (Assignment 2, answers by: A.Aziz Altowayan)

#### Problem 1

Question:

Answer:

- Depth-First Search
- Goal 8: 4 2 1 3 7 6 5 8
- Goal 5: 4 2 1 3 7 6 5

- Iterative deepening
- Goal 8: 4 4 2 7 4 2 1 3 7 6 8
- Goal 5: 4 4 2 7 4 2 1 3 7 6 8 4 2 1 3 7 6 5

#### Problem 2

Question:

Answer:

- Depth-First Search
- Solution found: Start - A - Goal
- Nodes expanded: Start - A - Goal

- Breadth-First Search
- Solution found:: Start - A - Goal
- Nodes expanded: Start - A - B - Goal - C - D

- Uniform cost search
- Solution found: Start - B - Goal
- Nodes expanded: Start - B - A - D - C - Goal
Node list (cost):

- Start(0)
- A(2) B(1)
- A(2) C(4) G(5) D(2)
- G(6) C(4) G(5) D(2)
- G(6) C(4) G(5) G(7)
- G(6) G(5) G(5) G(7)
- G(6) G(5) G(7)

- A*
- Solution found: Start - B - G
- Nodes expanded: Start - A - B - D - Goal
Node list (`f(n)`

):

- Start
- A(4) B(4)
- G(6) B(4)
- G(6) D(3) G(5) C(5)
- G(6) G(7) G(5) C(5)
- G(6) G(7) C(5)

Solution see fifteen-puzzle.

Question:

Answer:

- The game tree:

*Where,*

**Edges**: are the actions.
**Nodes**: are the states (or the remaining amount).
**Leaf**: the winning state.

Yes, from the game tree above we see that she can force a win by picking up 2 coins when she starts the game.

First to guarantee winning, she has to starts by picking 2 coins at the beginning. Then depending on what Bob picks, Alice can win either 3 or 4 coins at max.

**Exercise 5.9**

Question:

Answer:

**a )** `factorial(number of possible states)`

, so in this case it would be `9!`

= 362,880 possible games.

For **b)**, **c)**, **d)**, and **e)**
see the tree below:

For an interactive (clickable) Game Tree, try this, if that does not work. Download
this zip file and open game-tree.html locally.