$COM{P}_{3}4$: Artificial Intelligence Assignment One

Due Date: $20$ September $2024$: io am

The problem

The diagram below shows a stack of $n$ numbered coins numbered, placed in ascending order on the centre circle $($labelled E$).$ Circles A and C are on the odd side of the board and circles B and D are on the even side. The problem

is to use a minimum of moves to shift the odd numbered coins from the center to the "Odd" side circles $($either A or C$)$ and even numbered coins to the "Even" side circles $($either B or D$).$ A solution would be all odd numbered coins on the odd side and all even numbered coins on the even side. The coins may be on either of the circles on the appropriate sides. The rules are: one coin may be moved at a time from the top of one pile to the top of another $($including the centre pile$)$ as long as:

you do not put a coin with a higher number on a coin with a lower one, or

you do not place an odd$-$numbered coin on an even$-$numbered coin or vice versa

Thus you can put coin I on $3,3$ on $7,$ or $2$ on $6$ ; but not not $3$ on $1$ or $1$ on $2.$ The cost of any move is $1.$

Assignment One

Due Date: $20$ September $2024$: io am

The problem

The diagram below shows a stack of $n$ numbered coins numbered, placed in ascending order on the centre circle

$($labelled E$).$ Circles A and C are on the odd side of the board and circles B and D are on the even side. The problem

Figure i: The coins problem.

is to use a minimum of moves to shift the odd numbered coins from the center to the "Odd" side circles $($either A

or C$)$ and even numbered coins to the "Even" side circles $($either B or D$).$ A solution would be all odd numbered

coins on the odd side and all even numbered coins on the even side. The coins may be on either of the circles on the

appropriate sides. The rules are: one coin may be moved at a time from the top of one pile to the top of another

$($including the centre pile$)$ as long as:

you do not put a coin with a higher number on a coin with a lower one, or

you do not place an odd$-$numbered coin on an even$-$numbered coin or vice versa

Thus you can put coin I on $3,3$ on $7,$ or $2$ on $6$ ; but not not $3$ on $1$ or $1$ on $2.$ The cost of any move is I ${?}^2.$

Instructions

I. $(35$ Marks$)$ Write a python program that that takes as input an instance of the problem as described above

and :

$($a$)$ Implements the following algorithms to solve instances of the problem:

depth$-$first search,

breadth$-$first search

greedy best first search

$A^{**}$

$($b$)$ Provides the user with the option of solving the problem using any of the search algorithms.

$($c$)$ Solves the problem using the chosen search.

$($d$)$ Outputs the solution path.

$($e$)$ Your program should work for $4,6,8$ and $10$ coins in the centre.

$($f$)$ A graphical interface is not required.

$(15$ marks$)$ Submit a report describing:

$($a$)$ The heuristic evaluation function used for the $A^{**}$ algorithm.

$($b$)$ A comparison of the performance of the three search methods in solving problems of differing difficulty.

Notes: