墨尔本大学COMP20003Assignment2课业解析 题意： 为Pacman吃豆人游戏实现AI算法寻找得分最高的策略 解析： 原游戏中，玩家控制Pacman在没有出口的迷宫里收集豆子dot（C表示玩家，‘.’表示豆子），尽可能得到更高的分。同时要躲避四个不同颜色的幽灵（&代表），碰到它们就会死亡（玩家有3条生命），敌人不会摧毁豆子，但会暂时占据豆子的位置，幽灵自动追杀Pacman。玩家并不是待宰的羔羊，迷宫里散布着一些水果（*表示），Pacman吃下水果后变身超人，在一定时间内所有幽灵会变成深蓝色并逃离Pacman，但它们速度更慢，Pacman可以杀死它们并获得高额奖励分。同一个水果持续的超人时间内，连续击杀幽灵奖励翻倍，第一个幽灵200分，第四个幽灵就是1600分。现在要求你实现给出的GraphSearch算法，为Pacman找到得分最高的路径。 涉及知识点：Dijkstra算法、图、队列 更多可加微信讨论 微信号g19963812037pdf
COMP20003 Algorithms and Data StructuresSecond (Spring) Semester 2019[Assignment 2]Solving Pac-Man:online Graph SearchHanded out: Thursday, 10 of OctoberDue: 00:00, Thursday, 24 of OctoberPurposeThe purpose of this assignment is for you to:• Increase your proficiency in C programming, your dexterity with dynamic memory allocation andyour understanding of data structures, through programming a search algorithm over Graphs.• Gain experience with applications of graphs and graph algorithms to solving games, one form ofartificial intelligence.Assignment descriptionIn this programming assignment you’ll be expected to build an AI algorithm to solve Pac-Man. Thegame invented in 1980 is one of the classics among arcade games. You can play the game compilingthe code given to you using the keyboard, or using this web implementation.The code in this assignment was adapted from the open-source terminal version made available byMike Billars1 and the original version can be installed as a standard package in Ubuntu2.The Pac-Man gameAs explained in the wikipedia entry, The player navigates Pac-Man through a maze with no deadends. The maze is filled with Pac-Dots, and includes four roving multi-colored ghosts: Blinky, Pinky,Inky, and Clyde.The objective of the game is to accumulate as many points as possible by eating dots, fruits, andghosts. When all of the dots in a stage are eaten, that stage is completed, and the player will advanceto the next. The four ghosts roam the maze and chase Pac-Man. If any of the ghosts touches Pac-Man,a life is lost. When all lives have been lost, the game is over.Pac-Man can eat a fruit first and then eat the ghosts for a fixed period of time to earn bonus points.The enemies turn deep blue, reverse direction and move away from Pac-Man, and usually move moreslowly. When an enemy is eaten, its eyes return to the center ghost box where the ghost is regeneratedin its normal color. The bonus score earned for eating a blue ghost increases exponentially for eachconsecutive ghost eaten while a single energizer is active: a score of 200 points is scored for eating oneghost, 400 for eating a second ghost, 800 for a third, and 1600 for the fourth.The level id and a scoreboard can be found on the lower part. The information in the last three linesof the screen reveals information about the algorithm execution.The game is won when all dots have been eaten. An AI agent or human player can change the directionof Pac-Man movements.1https://sites.google.com/site/doctormike/pacman.html2https://packages.ubuntu.com/xenial/games/pacman4consoleFigure 1: The UI of the Terminal version. c is pacman, & are ghosts, * are fruits, and . is a regularfood.The AlgorithmEach possible configuration of the Pac-Man game 29×28 grid and other relevant information such asthe direction of pacman movements, number of lives left, etc. is called a state. The Pac-Man GraphG = 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 movements (right, left, up, down).Your task is to find the path leading to the highest score, i.e. leading to the most rewarding vertex(state). A path is a sequence of movements. You are going to use a variant of Dijkstra to explorethe most rewarding path first, up to a maximum budget B of expanded/explored nodes (nodes forwhich you’ve already generated its children).Every time the game asks you for a movement (action), you should explore all possible paths untilconsuming the budget B if possible. Once you finished generating all the paths, you should return thefirst action only of the path leading to the highest score vertex. This action will then be executedby the game engine.You might have multiple paths with the same maximum score. If more than one action (left,right,upor down) begins paths with the same maximum score, you’ll have to break ties randomly.Make sure you manage the memory well. Everytime you finish running the algorithm, you have tofree all the nodes from the memory, otherwise you are going to run out of memory fairly fast or causememory leaks.GraphSearch(Graph; start; budget)1 node start2 explored empty Array3 frontier priority Queue Containing node Only4 while frontier 6= empty5 do6 node frontier:pop()7 explored:add(node)8 if size(explored) < budget9 then10 for each APPLICABLE action a 2 fLeft; Right; Up; Downg11 do12 newNode applyAction(node)13 propagateBackScoreToFirstAction(newNode)14 if lostLife(newNode)15 then16 delete newNode17 else18 frontier:add(newNode)1920 freeMemory(explored)21 bestAction select best action breaking ties randomly22 return bestActionFigure 2: Online Graph algorithm variant of DijkstraEvery time that you consider all the actions that can be applied for a given node, only use the onesthat will face Pac-Man towards a free tile. For example, in Figure 1 you should only consider theactions Left, and Right.When you applyAction you have to create a new node, that1. points to the parent,2. updates the state with the action chosen,3. updates the priority (used by the priority queue) of the node to be the negative node’s depth d(if the node is the dth step of the path, then its priority is -d). This ensures the expansion ofthe shortest paths first, as the priority queue provided is a max heap;4. updates the reward to be r(n) = (h(n) + score(n) - score(nParent)) × γd(a) the heuristic value h(n) that biases the reward to account for losing lives and eating fruits,plus(b) the change in score from the current node and the parent node(c) times a discount factor of γ = 0:99d, where d is the depth of the node,5. updates the accumulated reward from the initial node up to the current node, and6. updates any other auxiliary data in the node.The heuristic function is h(n) = i - l - g, where i = 10 if Pac-Man has eaten a fruit and becomesinvincible in that state; l = 10 if a life has been lost in that state; and g = 100 if the game is over.Otherwise i = l = g = 0.You are going to need some auxiliary data structures to update the scores of the first 4 applicableactions. The function propagateBackScoreToFirstAction takes the score of the newly generatednode, and propagates back the score to the first action of the path.This propagation can be either Maximize or Average :• If you Maximize, you have to make sure that the first action is updated to reflect the maximumscore of any of its children.• If you Average, you have to make sure that the first action is updated to reflect the averagescore taking into account all its children.Deliverables, evaluation and delivery rulesDeliverable 1 { Solver source codeYou are expected to hand in the source code for your solver, written in C. Obviously, your source codeis expected to compile and execute flawlessly using the following makefile command: make generatingan executable called pacman. Remember to compile using the optimization flag gcc -O3 for doingyour experiments, it will run twice faster than compiling with the debugging flag gcc -g. For thesubmission, please submit your makefile with gcc -g option, as our scripts need this flag fortesting. Your program must not be compiled under any flags that prevents it from working under gdbor valgrindYour implementation should work well over the standard levels, but might fail to perform well in someof our provided t *.dat levels. The t * levels are specifically designed to test challenging situations.Try different budgets and explain why your agent works well (or doesn’t) in each of the test cases.Base CodeYou are given a base code. You can compile the code and play with the keyboard. The default solverchooses an action randomly. You are going to have to program your solver in the file ai.c. Look at thefile pacman.c (MainLoop function) to know which function is called to select an action to execute.You are given the structure of a node, the state, and also a priority queue implementation. Look intothe utils.* files to know about the functions you can call to apply an action to update a game state.You are free to change any file.InputYou can play the game with the keyboard by executing./pacman
