Q$.2$ This single player puzzle has two types of tiles "Horse" $($H$)$ and "Kangaroo" $($G$).$ The player starts with a Horse tile and tries to move it to the empty space$/$tile and alternates between two types of tiles resulting in the position swapping with the empty tile. ie$.,$ In the second move the player should move different tile, here any one Kangaroo tile & the empty tile are swapped and in third move any of the Horse tile is swapped position with the empty tile and so on$.$ Below defines the valid moves$/$swaps allowed and corresponding action cost. The objective is to reach the goal state from the given initial state as shown.

Goal State

G G G

H H H

Initial State

H $,$ G $,G,H,G,H$

The two legal moves with respective costs are detailed below:

Way$1$: A tile may swap with an adjacent empty location. This has a cost of $1.$

Way$2$: A tile may only hop over one tile ahead or hop over two other tiles into the empty position to swap. This has a cost equal to the number of tiles jumped over. An additional step cost of $1$ is added in this move.

The two heuristic functions recommended for this problem from any arbitrary state $\text{'}n\text{'}$ are: $H1(n)=$ Total number of misplaced Horses and Kangaroos tiles in the current state $\text{'}n\text{'}$ compared to the goal state.

H$2(n)=$ Manhattan distance of the empty tile in the current state $\text{'}n\text{'}$ compared to goal position.

View full document

a$)$ Expand & depict the search tree for up to exactly three levels. $($Given initial state can be assumed to be on level$-0.).$

b$)$ Among the above two defined heuristics $($ H $1$ and H $2),$ if you are restricted to choose only one of them, which one would you choose and why? Justify your choice with brief answer with appropriate numerical illustration w$.$r$.$t to the given problem.

c$)$ Apply Depth First Best First Search algorithm for the search results obtained from part a$,$ only till first $5$ closed list updates or till the goal is reached whichever is achieved the earliest. Show the status of OPEN and CLOSE list at each level and shown the step by step procedure as discussed in the class.

$[2+3+5=10$ Marks$]$