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

### Search Homework 1

#### Problem 1

Question:

• 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:

• Depth-First Search
• Solution found: Start - A - Goal
• Nodes expanded: Start - A - Goal
• 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)

### Search Homework 2

Solution see fifteen-puzzle.

### Games Homework 1

Question:

1. The game tree:

Where,

• Edges: are the actions.
• Nodes: are the states (or the remaining amount).
• Leaf: the winning state.
1. Yes, from the game tree above we see that she can force a win by picking up 2 coins when she starts the game.

2. 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:

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.