COMP20003-Assignment 3 Algorithms and Data Structures Solved

Purpose
The purpose of this assignment is for you to:

Increase your proficiency in C programming, your dexterity with dynamic memory allocation and your understanding of data structures, through programming a traversal algorithm over Graphs.

Gain experience with applications of graphs and graph algorithms to solving games, one form of artificial intelligence.

Assignment description
In this programming assignment you’ll be expected to build an AI algorithm to solve Peg Solitaire (known as Brainvita in India). The game was invented in the XVII century in Madagascar. The first reference to the rules appeared in 1687 in a french cultural magazine. It is one of the classic board game puzzles, and several boards that differ in shape and size appeared through time. You can play the game using the keyboard and compiling the code given to you, or using this web implementation.

The Peg Solitaire game enginge code in this assignment was adapted from the open-source terminal version made available by Maurits van der Schee[1].

The Peg Solitaire game
As explained in the wikipedia entry, The player can move a peg jumping on top of another adjacent peg, if there is a free adjacent cell to land. There are 4 valid jumps: Left, Right, Up and Down.

The objective is to clean the board until there is only 1 peg left. Some variants require that the last remaining peg sits on the middle of the board. In this game we ignore that variant and win the game if only 1 peg is left, no matter its final position. An AI agent or human player can chose the sequence of jumps to win the game.

Solving Pegsol belongs to the class of problemns known as NP-Complete problems (paper). NPcomplete problems are hard to solve. The best algorithms to solve NP-Complete problems run in exponential time as a function of the size of the problem. Hence, be aware that your AI solver will struggle more as the number of pegs increases. We talked in the lectures about the Travelling Salesman Problem as one example of an NP-Complete problem. In fact, many real-world problems fall under this category. We are going to learn more about NP-Complete problems in the last lecture of the course.

As a curiosity, you can see the number of distinct board positions on the standard 33-hole cross-shaped layout as an entry on the encyclopedia of integer sequences.

Human Player Mode
In the code provided, you can move the cursor in four directions using the arrow keys: up, down, left, and right. Use the enter/return key to select (or deselect) a peg. Pegs can then be moved using the arrow keys. Quit, restart and undo keys are ’q’, ’r’ and ’u’. A peg can only move if it can jump over a adjacent peg and land on an empty space. A peg is represented by a circle and a empty space by a dot. You win the game when you end with one peg (anywhere in the board). When there are no more moves possible the game is over.

The Algorithm
Each possible configuration of the Peg Solitaire (Pegsol) is a tuple made of: m × m grid board, the position of the cursor and whether the peg under the cursor has been selected. This tuple is called a state. The Pegsol Graph G = hV,Ei is implicitly defined. The vertex set V is defined as all the possible configurations (states), and the edges E connecting two vertexes are defined by the legal jump actions (right, left, up, down).

Your task is to find the path leading to the best solution, i.e. leading to the vertex (state) with the least number of remaining pegs. A path is a sequence of actions. You are going to use Depth First Search to find the best solution, up to a maximum budget of expanded/explored nodes (nodes for which you’ve generated its children).

When the AI solver is called (Algorithm 1), it should explore all possible paths (sequence of jump actions) following a Depth First Search (DFS) strategy, until consuming the budget or until a path solving the game is found. Note that we do not include duplicate states in the search. If a state was already generated, we will not include it again in the stack (line 21). The algorithm should return the best solution found, the path leading to the least number of remaining pegs. This path will then be executed by the game engine.

You might have multiple paths leading to a solution. Your algorithm should consider the possible action by scanning the board in this order: traverse coordinate x = 0,...,m first, and then y = 0,...,m looking for a peg that can jump, and then selecting jumping actions left, right, up or down.

Make sure you manage the memory well. When you finish running the algorithm, you have to free all the nodes from the memory, otherwise you will have memory leaks. You will notice that the algorithm can run out of memory fairly fast after expanding a few milion nodes.

When you applyAction you have to create a new node, that

1.    points to the parent,

2.    updates the state with the action chosen,

3.    updates the depth of the node.

4.    updates the action used to create the node

 

Algorithm 1 AI Peg Solitaire Algorithm

1: procedure PegSolver(start, budget)

2:               n ← initNode(start)
3:
stackPush(n)
 
4:
remainingPegs ← numPegs(n)
 
5:
while stack 6= empty do
 
6:
n ← stack.pop()
 
7:
exploredNodes ← exploredNodes + 1
 
8:
if numPegs(n) < remainingPegs then
. Found a better solution
9:
saveSolution(n)
 
10:
remainingPegs ← numPegs(n)
 
11:
end if
 
12:
for each jump action a ∈ [0,m) × [0,m) ×{Left,Right,Up,Down} do
13:
if a is a legal action for node n then
 
14:
newNode ← applyAction(n,a)
. Create Child node
15:
generatedNodes ← generatedNodes + 1
 
16:
if won(newNode) then
. Peg Solitaire Solved
17:
saveSolution(newNode)
 
18:
remainingPegs ← numPegs(newNode)
 
19:
return
 
20:
end if
 
21:
if newNode.state.board seen for the first time then
. Avoid duplicates
22:
stackPush(newNode)
. DFS strategy
23:
end if
 
24:
end if
 
25:
end for
 
26:
if   then
 
27:
 
. Budget exhausted
28:
end if
 
29:          end while 30: end procedure