Show simple item record

dc.contributor.supervisor McLeod, Bob (Electrical and Computer Engineering) en_US
dc.contributor.author Hoque, Sanyat
dc.date.accessioned 2019-05-16T20:21:17Z
dc.date.available 2019-05-16T20:21:17Z
dc.date.issued 2019-02 en_US
dc.date.submitted 2019-02-22T01:09:32Z en
dc.identifier.uri http://hdl.handle.net/1993/33907
dc.description.abstract Video game technology has grown to include the development of more sophisticated game play by including computer controlled agents or Non-Player Characters (NPCs). Moreover, game environments provide ideal benchmarking tools to examine new and more sophisticated game related algorithms. Ideal testbeds are games like Pac-Man and Ms. Pac-Man. Ms. Pac-Man is a stochastic game played in a complex maze environment. In this thesis, a novel probabilistic tree search algorithm loosely based on the simulated annealing algorithm is used by the ghost agents that pursue Ms. Pac-Man in order to minimize the score of Ms. Pac-Man (the opponent). In general, simulated annealing is a non-deterministic search optimization algorithm to search for a global maximum/minimum in a non-convex discrete search space. A major advantage of simulated annealing over the tree search models used in past research (Ant Colony Optimization and Monte Carlo Tree Search) as applied to the ghost agents in Ms. Pac-Man is the time and memory complexity. Although simulated annealing is still computationally intensive, it is less so in comparison to the search algorithms mentioned above. Simulated annealing and variants are also excellent sources of easy-to-understand analogs. This thesis investigates the trade-off between exploration and exploitation phases of search algorithms used by ghost agents as they attempt to contain or constrain the movements of Ms. Pac-Man. New algorithms are developed and presented to better control the NPCs within Ms. Pac-Man. The proposed models or algorithms are evaluated on two different experimental setups; 1) maze navigation to test the convergence efficiency with respect to the number of iterations, and 2) within the game of Ms. Pac-Man itself to determine the effectiveness of attacking strategies such as flanking and blocking. These new algorithms may have application within similar types of problems. en_US
dc.rights info:eu-repo/semantics/openAccess
dc.subject Simulated en_US
dc.subject Annealing en_US
dc.subject Pac-Man en_US
dc.title Exploring exploitation and exploration algorithms in Ms. Pac-Man en_US
dc.type info:eu-repo/semantics/masterThesis
dc.type master thesis en_US
dc.degree.discipline Electrical and Computer Engineering en_US
dc.contributor.examiningcommittee Peters, James (Electrical and Computer Engineering) Mohammed, Noman (Computer Science) en_US
dc.degree.level Master of Science (M.Sc.) en_US
dc.description.note May 2019 en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

View Statistics