Project 1 Solution

Description

This assignment covers the topic of AI search. It will reinforce your understanding of this topic. In the assignment you will write a program to find a solution to the game of Peg Solitaire. A description of this board game follows:

The board consists of peg holders. A peg holder can either be empty or hold exactly one peg. In Figure 1 below “○” and “●” correspond to an empty and a filled peg holder respectively. The other blank spaces in the board that are neither empty or filled are unusable – these are the 2 x 2 squares on the four corners of the board. The objective of the game is to remove all except one peg from the board. The rule for removing a peg is this: If X, Y and Z are three consecutive peg holders with X and Y holding a peg each and Z is empty then the peg in X can jump over Y and fill Z. In the process Y is removed from the board. The peg holders X and Y become empty and Z now holds a peg. Note that only horizontal and vertical moves are allowed.

There are several variants of the game with differing board sizes and shapes. For this assignment we will use the 7 x 7 board as shown in Figure 1 below with the 2 x 2 squares on the four corners unused, i.e. they are not peg holders and hence unusable by our definition. In our game the objective is to remove all the pegs in the board except one. The final peg should be placed in the center peg holder in order to win – see Figure 1(b).

The board’s configuration can be represented by a vector of string characters, one string per row.

The configuration in Figure 1(a) above will be represented as:

<–000–,–0X0–,00XXX00,000X000,000X000,–000–,–000–>

0 and X denote an empty and filled peg holder respectively and (–) denotes an unusable peg holder. In this assignment you can use your own configuration (test set) to test your algorithm. Use an array of strings to represent the test set (the input of your function).

You should number the peg holders as shown in Figure 2 below:

You are required to implement AI search algorithms to solve the peg solitaire game as specified above. Your program will take a given initial configuration of the board and will output a sequence of valid moves that will result in a solution, if one exists. A valid move is one that results in removing a peg (every move must remove a peg from the board). A move will be a pair (X,Y) where the peg in peg holder numbered X is moved to the peg holder numbered Y. For the initial board configuration in Figure 1(a) the following sequence of valid moves will result in the configuration in Figure 1(b) which is also the solution to the game with Figure 1(a) as the initial configuration: <(9,7),(23,9),(10,8),(7,9),(4,16)>. You will use two search strategies:

1. Iterative Deepening Search (uninformed)

2. A* with two kinds of heuristics (your choice), one more informed than the other

For each search strategy – IDS and A* with the two heuristics – your program should generate the number of nodes expanded, memory usage and running time.

Extra points (up to a maximum of 25) will be given if your program uses tricks to prune searches and not revisiting expanded nodes.

Notes:

1. Your program should be written in Python3.

2. For more information about peg solitaire see: h%p://en.wikipedia.org/wiki/Peg_solitaire

Submission:

Submit by 11:59 pm on due date via Black Board. Put all the documents in a folder and zip it.

The file name should be LastName_FirstName_HW1.zip.

• Source code with good documentation. Make sure it compiles.

• A trace of the execution for each search strategy

• Test set

• A report with the required statistics generated, heuristics used, prune method (if any) and any other detail you want to mention.