COMP3702 Artificial Intelligence (Semester 2, 2023) Assignment 1: Search in DragonGame
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP3702 Artiicial lntelligence (semester 2, 2023)
Assignment 1: search in DRAGONGAME
key information:
. Due: 3pm, wednesday 23 August 2023
. This assignment assesses your skills in developing discrete search techniques for challenging problems. . Assignment 1 contributes 20% toyour inal 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 ind 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://gitlab.com/3702-2023/a1-support.
. your report (part 2) should it the template provided, be in .pdf format and named according to the format a1-COMP3702-[sⅠD].pdf. Reports will be graded by the teaching team.
The DRAGONGAME AI Environment
“untitled Dragon Game”1 or simply DRAGONGAME, is a 2.5D platformer game in which the player must collect all of the gems in each level and reach the exit portal, making use of a jump-and-glide movement mechanic, and avoiding landing on lava tiles. DRAGONGAME is inspired by the “spyro the Dragon” game series from the original playstation.
To optimally solve a level, your Al agent must ind a sequence of actions which collects all gems and reaches the exit while incurring the minimum possible action cost.
Levels in DRAGONGAME are composed of a 2D grid of tiles, where each tile contains a character representing the tile type. An example game level is shown in Figure 1.
Figure 1: Example game level of DRAGONGAME, showing character-based and Gul visualiser representations
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
where
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.
ln the event of exceptional circumstances, you may submit a request for an extension. You can ind guide- lines on acceptable reasons for an extension here https://my.uq.edu.au/information-and-services/manage-my- program/exams-and-assessment/applying-extension. All requests for extension must be submitted on the UQ Application for Extension of Assessment form at least 48 hours prior to the submission deadline.
2023-08-19