Key information:

•  Due Date:  1pm,  Friday 29 August 2025

•  This assignment assesses your skills in developing discrete search techniques for challenging problems.

•  Assignment 1 contributes 20% to your   nal grade.

•  This assignment consists of two parts:  (1) programming and (2) a report.

•  This is an individual assignment.

•  Both the code and report are to be submitted via Gradescope (https://www.gradescope.com/). You can   nd a link to the COMP3702 Gradescope site on Blackboard.

•  Your code (Part  1) will be graded using the Gradescope code autograder,  using the testcases in the support code provided at https://github.com/comp3702/A1-Support-Code-2025.

• Your report (Part 2) should   t the template  provided,  be  in .pdf format and named according to the format a1-COMP3702-[SID].pdf.  Reports will be graded by the teaching team.

The CheeseHunter AI Environment

CheeseHunter is a 2.5D platformer game in which the mouse player must activate all the levers in a level before collecting a wedge of cheese.  The player must choose which actions to perform, including walking, sprinting, climbing, jumping and dropping movements, to navigate a maze including drawbridges and trapdoors (i.e.,  “traps”).  The traps are toggled  between  locked and unlocked by activating their corresponding levers using the activate action.  Each action incurs a di  erent cost, which requires clever problem solving to not only complete a level, but also solve it with the minimum cost!

Your task is to design an AI agent to optimally solve levels through Search,   nding a sequence of actions for the player to activate all levers and then reach the cheese, while minimising the total action cost.

Levels in CheeseHunter are composed of a 2D grid of tiles, where each tile contains a character representing the tile type as well as a schematic indicating which  levers correspond to which traps  based on  matching numbers (i.e., lever 1 toggles trap 1).  In the graphical visualiser, the blue levers correspond to Trapdoors, while red levers correspond to Drawbridges, and are numbered sequentially from 0 for the two trap types. An example game level is shown in Figure 1.

Figure 1:  Example level of CheeseHunter, showing character-based and GUI visualiser representations.

Game state representation

Each game state is represented by a character array representing the tile types and their position on the board, as well as the state of each trap (whether it has been locked or not, by activating its corresponding lever).    In the visualizer, the tile descriptions are graphical assets, whereas in the input file these are single characters. Levels can contain the tile types described in Table 1.

Table 1: Table of tiles in CheeseHunter, their corresponding symbol and effect

Actions

At each time step, the player is prompted to select an action. Each action has an associated cost, representing the amount of energy  used  by  performing that action.   Each  action  also  has  requirements which  must  be satisfied  by the current state  in order for the  action to  be valid.   The  set  of available actions,  costs and requirements for each action are shown in Table 2.

Table 2: Table of available actions, costs and requirements

Interactive mode

A good way to gain an understanding of the game is to play it.  You can play the game to get a feel for how it works by launching an interactive game session from the terminal with the following command:

$ python play_game.py <input_file>.txt

where <input_file>.txt is a valid testcase file from the support code with path relative to the current

directory, e.g. testcases/level_1.txt

Depending on your python installation, you should run the code using python, python3 or py.

In interactive mode, type the symbol for your chosen action in the terminal (e.g.  ‘wl’) and press enter to perform the action. Type ‘q’ and press enter to quit the game.

CheeseHunter as a search problem

In this assignment, you will write the components of a program to play CheeseHunter, with the objective of finding a high-quality solution to the problem using various search algorithms.  This assignment will test your skills in implementing search algorithms for a practical problem and developing good heuristics to make your program more efficient.

What is provided to you

We provide supporting code in Python, in the form of:

1.  A class representing the CheeseHunter environment and a number of helper functions (in game env.py)

2. A class representing the CheeseHunter game state (in game state.py)

3.  A graphical user interface for visualising the game state (in gui.py)

4. A solution file template (solution.py)

5. A tester (in tester.py)

6.  Testcases to test and evaluate your solution (in  ./testcases)

The support code can be found at: https://github.com/comp3702/A1-Support-Code-2025.  Please read the README.md file which provides a description of the provided files.  Autograding of code will be done through Gradescope, so that you can test your submission and continue to improve it based on this feedback — you are strongly encouraged to make use of this feedback.

Your assignment task

Your task is to develop a program that implements search algorithms and outputs the series of actions the agent (i.e.  the Mouse) performed to solve the game, and to provide a written report explaining your design decisions and analysing your algorithms’ performance. You will be graded on both your submitted code (Part 1, 60%) and the report (Part 2, 40%). These percentages will be scaled to the 20% course weighting for this assessment item.

To turn CheeseHunter into a search problem, you should first study the supplied code and documentation and identify where and how the following agent design components are defined:

•  A problem state representation (state space),

•  A successor function that indicates which states can be reached from a given state (action space and transition function), and

• A cost function (the opposite of the utility function)

Note that a goal-state test function is provided in the support code (in the is_solved() method of the envi- ronment. Once you have identified the components above, you are to develop and submit code implementing two discrete search algorithms in the indicated locations of solution.py:

1.  Uniform-Cost Search (UCS), and

2.  A* Search

Note that your heuristic function used in A* search must be implemented in the compute heuristic method and called from your A* method, and any pre-processing-based heuristics should be implemented in preprocess heuristic (optional).  This enables consistent evaluation of your heuristic functions, inde- pendent of your A* implementation.

The  provided tester can assess your submitted  UCS or A* search  based on the  ‘search type’ argument. Both UCS and A* will be run separately by the autograder, and the heuristic function will also be assessed independently.

Finally, after you have implemented and tested the algorithms above, you are to complete the questions listed in the section  “Part 2 - The Report” and submit them as a written report.

More  detail  of what  is  required  for  the  programming  and  report  parts are  given  below.    Hint:   Start by implementing a working version of UCS, and then build your A* search algorithm out of UCS using your own heuristics.

Part 1 — The programming task

Your program will be graded using the Gradescope autograder, using the testcases in the support code provided at https://github.com/comp3702/A1-Support-Code-2025.

Interaction with the testcases and autograder

We now provide details explaining how your code will interact with the testcases and the autograder (with special thanks to Winston Niogret for the game design and efforts making this work seamlessly).  Your solution code only needs to interact with the autograder via your implementation of the methods in the Solver class of solution.py.  Your search  algorithms, implemented in search ucs and search a   star, should return the path found to the goal (i.e. the list of actions, where each action is an element of GameEnv.ACTIONS).

This is handled as follows:

•  The file solution.py, supplied in the support code, is a template for you to write your solution.  All of the code you write can go inside this file, or if you create your own additional python files they must be invoked from this file.

•  The script tester.py can be used to test your code on testcases.

After you have implemented UCS (uniform cost search) and/or A* search in solution.py you can test them by going to your command prompt, navigating to your folder and running tester.py:

Usage:

$ python tester.py [search_type] [testcase_file] [-v (optional)]

{  search type = ’ucs’, ’a star’

{ testcase file = a filename of a valid testcase file with path relative to the tester.py script (e.g.

testcases/level   1.txt)

{  if -v is specified, the solver’s trajectory will be visualised

For example, to test  UCS after you  have written the code for  it, you can type the following  in the command prompt:

$ python tester.py ucs testcases/level_1.txt -v

Note that the GameEnv class constructor (__init__(self, filename))  handles  reading the  input file and is called from tester.py

•  The autograder (hidden to students) handles running your python program with all of the testcases.  It will run your submitted solution.py code and assign a mark for each testcase.

• You can inspect the testcases in the support code, which include information on their optimal solution cost and test time limits.  Looking at the testcases might also help you develop heuristics using your human intelligence and intuition.

•  To ensure your submission is graded correctly, write your solution code in  solution.py, and do not rename any of the provided files or alter the methods in game env.py or game   state.py.

More detailed information on the CheeseHunter implementation is provided in the Assignment 1 Support Code README.md, while a high-level description is provided in the CheeseHunter AI Environment description document.