Reference no: EM133776611

Algorithms and Data Structures

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 search algorithm over Graphs.

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

In this programming assignment, you'll be expected to build an AI algorithm to solve Chessformer. The game, created by Robert Alvarez is a puzzle game using moves from the ancient classic Chess. Pieces are able to move in their normal patterns, but once they've made a move, they fall to the nearest platform. The objective is to take all the pieces in each puzzle. You can play our implementation inspired by the game by compiling the code given to you and playing using the keyboard, or try out the first 24 levels in an online version. The game can also be found on Steam.
The code in this assignment was adapted from the open-source terminal version of the classic puzzle game, Sokoban using ncurses made available by CorrentinB.

Game Rules

The game is played on a board of squares, where each square is open space or a wall/platform. Some spaces contain pieces, and one square will contain the player's piece. In the simplified AI approach we use, there may be multiple pieces that need to be captured but there will always be only one player piece.

Though Chessformer utilises many piece types, for simplicity of implementation, the player piece is always a special combination piece, which has the move options of a knight (moving two squares along either axis, followed by one square in the remaining axis - forming an 'L' shape) and queen (moving any number of squares along the horizontal, vertical or either diagonal) simultaneously. The player is confined to the board and may move using any of the possible moves onto empty squares (never through walls/platforms or capturable pieces). The player can capture a piece by moving onto its square.

The puzzle is solved when all capturable pieces have been visited by the player's piece.

Speedrun of Chessformer

Understanding the idea of puzzles in Chessformer can be seen through a short section of a speedrun of the first 24 puzzles in the game.

For the curious reader
The Science of Chessformer
Like a number of puzzles, the problem of finding the shortest Chessformer solution can be formulated as a decision problem. In simple terms, for a given puzzle, we can ask if a solution exists in n or fewer steps, we can then - in polynomial time - check that a solution of n or fewer steps is a valid solution (i.e. that each move made is valid and that the final state solves the problem).
NP-complete 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 and the shortest accepted solution. Hence,

be aware that your AI solver may struggle more as the number of capturable pieces 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 via an invited talk in week 12.

Deliverable 1 - Dijkstra Solver source code
You are expected to hand in the source code for your solver, written in C. Obviously, your source code is expected to compile and execute flawlessly using the following makefile command: generating an executable called chessformer . Remember to compile using the optimization flag
for doing your experiments, it will run twice as quickly as compiling with the debugging flag
(see Makefile , and change the variable accordingly). For the submission, please submit your makefile with option, as our scripts need this flag for testing. Your program must not be compiled under any flags that prevents it from working under gdb or valgrind.

Your implementation should work well over the capability layouts, but it will not be expected to find a solution to any arbitrary layout, as some layouts may exceed the available RAM in your computer before finding a solution. To test with other maps (e.g. to debug a particular solution path), all you have to do is to copy and paste a single map into a new file, and then call it with your solver.

Deliverable 2 - Experimentation
Besides handing in the solver source code, you're required to provide a table reporting at least the execution time and number of generated nodes (with and without optimisations). Include in the table only the puzzles that your solver finds a solution to.
Plot six figures, where the x-axis is:

the number of cells in the grid (for two of the plots) and
the number of ground cells (places a piece could theoretically be) in the board (for two of the plots),
the number of initial cells with capturable pieces (for two of the plots). and for each plot, the y-axis is one of:
the number of generated states and the solution time.
Explain your results using your figures and tables. If you have implemented the duplication check, plot this data on the same axes.
Answer the questions:

Which complexity growth does your data appear to show?
What's the computational benefit of the optimisation, does it decrease the growth rate?

this theoretically even if you did not implement the optimisation) Answer concisely.
If you decide to implement any further optimization beyond the instructions of the assignment, or change the default arguments please discuss their impact in the experimentation section as well.
My recommendation is that you generate the plots using any standard Python visualization library. See for example Seaborn or Matplotlib. Otherwise, there's always the old-school excel/open- office/google-sheets method.

Deliverable 3 - Submission Certification Form
Once you submit your code, please also fill out the form, no later than 24h after the deadline.

Rubric
Assignment marks will be divided into three different components.

Solver (8)
Finds solution for the capability test cases (6) No Memory Errors (1)
No Memory Leaks (1) Duplicate State Detection (2) Experimentation (3)
Code Style (2)

Please note that you should be ready to answer any question we might have on the details of your assignment solution by e-mail, or even attending a brief interview with me, in order to clarify any doubts we might have.
We will follow the same Ungrading approach used for Assignments 1 and 2. Note that not all marks are expected to involve the same time commitment.

The Code Base
You are given a base code. You can compile the code and play with the keyboard (arrows). You are

going to have to program your solver in the file ai.c . Look at the file know which function is called to call the AI algorithm.
(main function) to

You are given the structure of a node, the state and a hashtable implementation to check for duplicate states efficiently (line 23 in the Algorithm 2). Look into the files to know about the functions you can call to apply an action to update a game state. All relevant files are located in the folder src/ai/ .

In your final submission, you are free to change any file, but make sure the command line options remain the same.

Input
You can play the game with the keyboard by executing

where points to the file containing the chessformer problem to solve.

In order to execute your AI solver use the following command:

Where calls your algorithm. is optional, if typed in as an argument, the program will play the solution found by your algorithm once it finishes. All the options can be found if you use option -h :

Reflection
This form provides an opportunity to both look back at your work to reflect on it, as well as evaluate how you did.

Question 1

Finds solution for the capability test cases (6) No Memory Errors (1)
No Memory Leaks (1) Duplicate State Detection (2) Experimentation (3)
Code Style (2)

If you were assessing your assignment against these marking criteria, how many marks would you give your solution?
No response

Question 2
Learning and Challenges

Please include your top lessons learnt and challenges faced in this assignment.
No response

Question 3
Ideas that Almost Worked Well

If there were any ideas you tried or wanted to try, include them here and explain why they didn't make it.
No response

Question 4

New Test Cases Shared on Ed

Tell us about your test cases and why they were useful.
No response

Question 5
Justification

Let us know why you assigned yourself the marks you did.
No response

Question 6
(General) Understanding Demonstrated

Academic honesty is important, however there are academically honest ways to complete the assignment which do not demonstrate understanding (e.g. crediting a peer for the full implementation of your assignment may well be honest, but clearly may not be worth any marks!). In this question, reflect briefly on any assistance you made use of (e.g. Google, ChatGPT, workshop peer discussion, assignment consultations, Ed discussion, teamwork, prior workshop solutions). In particular, if you found yourself without this kind of assistance in the future, let us know if you think you would be able to complete a project with similar challenges. If you like, also let us know what you think is reasonable (i.e. even compiler feedback could be seen as a form of assistance - one form which you may not have access to in an exam situation).
No response

Question 7
Did you submit your code and README.md for marking by using the Mark button on the "Assignment Submission" slide?