Game state representation

Each game state is represented as a character array, representing the tile types and their position on the board. ln the visualizer and interactive sessions, the tile descriptions are graphical assets, whereas in the input ile these are single characters.

Levels can contain the tile types described in Table 1.

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 satisied  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.

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  .txt

where .txt is a valid testcase ile from the support code with path relative to the current directory, e.g. testcases/L1.txt

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

DRAGONGAME as a search probIem

ln this assignment, you will write the components of a program to play DRAGONGAME, with the objective of inding 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 eicient.

what is provided to you

we provide supporting code in python, in the form of:

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

一 The constructor takes an input ile (testcase) and converts it into a DRAGONGAME map

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

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

4. A solution ile 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://gitlab.com/3702-2023/a1-support. please  read  the README.md  ile  which  provides  a  description  of  the  provided  iles.    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 Dragon) 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  DRAGONGAME  into  a  search  problem,  you  will  have  to  irst deine the following agent design components:

.  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 (utility function); the cost of each movement is given in TabIe 2

Note that a goal-state test function is provided in the support code. once you have deined 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 impIemented in the compute heuristic method and caIIed 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://gitlab.com/3702-2023/a1-support.

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 Nick collins for his eforts 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.AcTloNs).

This is handled as follows:

.  The ile 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 ile, or if you create your own additional python iles they must be invoked from this ile.

.  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 ile = a ilename of a valid testcase ile with path relative to the tester.py script (e.g . testcases/L1.txt)

- if -v is speciied, 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/L1.txt  –v

Note that the GameEnv class constructor ( –– init––（self,  filename）) handles reading the input ile and is called from tester.py

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

. You can inspect the testcases in the support code, which each 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 iles or alter the methods in game-env.py or game state.py .

More detailed information on the DragonGame implementation is provided in the Assignment 1 support code README.md, while a high-level description is provided in the DRAGONGAME Al Environment description document.

Grading rubric for the programming component (totaI marks: 60/100)

For marking, we will use 6 testcases of approximately ascending level of diiculty to evaluate your solution.

Note that a Ⅴalid solution means returning a list of actions that complete a testcase (i.e.  collect all gems and get to the exit), while the optimal path cost refers to returning a list of actions which provide the minimum cost solution.

There are 10 criteria for each testcase based on the accuracy and eiciency of your solution, each worth 1 mark:

.  Ucs valid solution

.  Ucs path cost (vs optimal cost)

.  Ucs runtime (vs benchmark)

.  A* heuristic admissible

.  A* heuristic path cost when used with reference A* (vs optimal cost)

.  A* heuristic runtime when used with reference A* (vs benchmark)

.  A* heuristic nodes expanded when used with reference A* (vs benchmark)

.  A* search valid solution

.  A* search path cost (vs optimal cost)

.  A* search runtime (vs benchmark)

partial marks are available for the path cost, runtime and nodes expanded criteria.  For each case, a minimum target (where scores worse than the minimum receive 0 marks) and a maximum target (where scores better than the maximum receive full marks) are provided; scores between the minimum and maximum targets are interpolated linearly.

There will be a total of 60 code marks.

Part 2 — The report

The report tests your understanding of the methods you have used in your code, and contributes 40/100 of your assignment mark. PIease make use of the report tempIates provided on BIackboard, because Gradescope makes use of a predeined assignment template.  submit your report via Gradescope, in .pdf format (i.e. use “save as pdf”or“print-to-ile” functionality), and named according to the format a1-COMP3702-[SⅠD].pdf. Reports will be graded by the teaching team.

your report task is to answer the questions below:

Question 1. (5 marks)

state the ten dimensions of complexity in DRAGONGAME, and briely explain your selection.

Refer to the P&M textbook https://artint.info/3e/html/ArtⅠnt3e.Ch1.S5.html (and tabular sum- mary in Figure 1.8) for adescription of each dimension (modularity, planning horizon, representation, computa- tional limits, learning, sensing uncertainty, efect uncertainty, preference, number of agents, and interactivity).

Question 2. (5 marks)

Describe the components of your agent design for DRAGONGAME.   speciically, the Action space,  state space, Transition Function and utility Function.

Question 3. (15 marks)

compare the performance of uniform cost search and A书 search in terms of the following statistics, presenting the numerical results in tabular format:

a)  The number of nodes on the fringe/frontier when the search terminates

b)  The number of nodes explored/expanded when the search terminates

c)  The  run time of the algorithm.  Note that you can report run-times from your own machine, not the Gradescope servers.

Discuss and interpret these results.  ln your discussion, you may describe the purpose of the heuristic function h（n) in A* search, whether it achieved its intended beneits and any trade-ofs.

Question 4. (15 marks)

some  challenging  aspects  of  designing  a  DRAGONGAME  agent  are  the  asymmetric movement  dynamics (moving up behaves diferently to moving down), the problem of choosing the order in which to visit and collect each gem, and the large number and difering cost of available actions.

Describe the  heuristics  (or  components  of a combined  heuristic function) that you  have  developed  in  the DRAGONGAME search task that account for these aspects or any other challenging aspects you have identiied of the problem.  your  documentation should  provide a thorough explanation of the rationale for using your chosen heuristic(s) considering factors such as admissibility and computational complexity.

References and Generative AI

At the end of your report, please cite any references, and if you utilised Generative Al to assist in producing your solution or report, please describe how you utilised such tools and how you veriied the answers, citing the version and date.

Academic Misconduct

The university deines Academic Misconduct as involving  “a range of unethical behaviours that are designed to give a student an unfair and unearned advantage over their peers.”  uQ takes Academic  Misconduct very seriously and any suspected cases will be investigated through the university,s standard policy (https:// ppl.app.uq.edu.au/content/3.60.04-student-integrity-and-misconduct).  lf you are found guilty, you may be expelled from the university with no award.

lt is the responsibility of the student to ensure that you understand what constitutes Academic Misconduct and to ensure that you do not break the rules.  lf you are  unclear about what is required, please ask.

lt is also the responsibility of the student to take reasonable precautions to guard against unauthorised access by others to his/her work, however stored in whatever format, both before and after assessment.

ln the coding part of cOMP3702 assignments, you are allowed to draw on publicly-accessible resources and provided tutorial solutions, but you must make reference or attribution to its source, by doing the following:

.  All blocks of code that you take from public sources must be referenced in adjacent comments in your code or at the top of your code.

.  Please also include a list of references indicating code you have drawn on in your solution.py docstring.

lf you have utilised Generative Al tools such as chatGPT, you must cite the tool and version in your code as well as describe in the report. A failure to reference generative Al use may constitute student misconduct under the student code of conduct.

However, you must not show your code to, or share your code with, any other student under any circumstances.  You must not post your code to pubIic discussion forums (incIuding Ed Discussion) or save your code in pubIicIy accessibIe repositories  (checK your security settings). You must not IooK at or copy code from any other student.

All submitted iles (code and report) will be subject to electronic plagiarism detection and misconduct proceed- ings will be instituted against students where plagiarism or collusion is suspected.  The electronic plagiarism detection can detect similarities  in code structure even  if comments, variable  names,  formatting etc.   are modiied.  lf you collude to develop your code or answer your report questions, you will be caught.

For more information, please consult the following university web pages:

.  lnformation regarding Academic lntegrity and Misconduct:

一 https://my.uq.edu.au/information-and-services/manage-my-program/student-integrity-and-

conduct/academic-integrity-and-student-conduct

一 http://ppl.app.uq.edu.au/content/3.60.04-student-integrity-and-misconduct .  lnformation on student services:

一 https://www.uq.edu.au/student-services/

Late submission

students should not leave assignment preparation until the last minute and must plan their workloads to meet advertised or notiied deadlines.  lt is your responsibility to manage your time efectively.

lt may take the autograder up to an hour to grade your submission.  lt is your responsibility to ensure you are uploading your code early enough and often enough that you are able to resolve any issues that may be revealed by the autograder before the deadline. submitting non-functional code just before the deadline, and not allowing enough time to update your code in response to autograder feedback is not considered a valid reason to submit late without penalty.

Assessment submissions received after the due time (or any approved extended deadline) will be subject to a 100% late penalty.  A one-hour grace period will be applied to the due time after which time the 100% late penalty will be imposed. This grace period is designed to deal with issues that might arise during submission (e.g.  delays with Blackboard or Turnitin) and should not be considered a shift of the due time.  please  keep a record of your submission time.