Skip to content

Implementation of a utilty agent, a rule-based agent and learning agent for the game PacMan using javascript

Notifications You must be signed in to change notification settings

Lamonkey/ai-pacman

Repository files navigation

Pacman Ai

What is this Project

Implemented three different agents, utility, simply-rule-based and learning agents for the game pac-man.
Check out the Demo

Installation

clone the repo and open index.html using browser. All codes are in Vanilla JS

Credit

The PacMan game is forked form:

adeyinkaezra123/Pacman

Introduction

Rule Based Agent

rule_based.gif

Only two rules

  1. if no ghost are approaching then seeking pellet
  2. else run evasion algorithm

Seeking Pellest

Two strategies were considered. Chose the second approach due to better performance

  1. Find a random pellet
  • Within the food pellets list, return a random pellet to seek
  • Pro: faster, since we just had to sample a random index in the array
  • Con: Often made pacman seek a pellet in a far away corner, reducing the efficiency
  • Mean 2203 Max 5480
  1. Find the nearest pellet
  • We utilize the manhattan distance from pacman to a tile to get the distance to food
  • Return the pellet with minimum distance
  • Pro: Have pacman be more efficient since he seeks the closest pellet
  • Con: O(n) time where n is the number of pellets
  • Mean 3936 Max: 7720

Evasion

Used BFS to find the safest tile within x radius of pacman

The safest tile is the tile which has the max minimum distance between all ghost

The result shows as below

Untitled

Analysis

Untitled

Why we use 8 as the minimum distance

The corner and long aisle is the easiest place for pacman to be flanked (And the length of those is around 8 )

Increasing the range for evasion can improve prediction result, but Pac-Man will spend more time escaping instead of seeking pellets.

Utility Agent

  • Generate a utility score for each available tiles adjacent to PacMan
  • u = tile value + safety value
    • tile value = k distance to pellets
    • k is a constant value for weighting the distance value
    • safety value = m a x ( f ( distance to ghost ) ) or a v e r a g e ( f distance to ghost )
  • PacMan always move to the tile with max utilty
  • I experimented different function for f
    • Linear scaled
    • exponential scaled
    • logarithmic scaled
    • Logistic scaled

Mitigate Oscillation

osicllation.gif

When two tiles have same utility pacman man will oscillate between them as show above.

  • It is not a problem when equal utility is caused by safety_value.
  • It is a problem when equal utility is caused by tile_value

To mitigate I tried two methods

  1. Give a penalty if pacman move backward,
  2. Give a preference [0.1,0.2,0.3,0.4] for each direction, the preference will be shuffled when pacman move to a new tile.

Going Back Penalty 1

going back 1.gif

Going Back Penalty 2

going back 2.gif

Shuffling Preference

pref_shuffle.gif

I conclude the going back penalty and direction preference will not mess up the utility function as long as these value no larger than the derivative of tile value function.

However preference shuffle will be a better solution

Pick of f

Three goals f should achieve

  1. Don’t bump into ghost in order to pick up pellets
  2. Can seek pellet even if it means we get closer to a ghost
  3. Agent will collide with ghost if ghost is scared

I will only show the analysis why I picked logistic function

Screenshot 2023-01-01 at 1.12.19 AM.png

  • Green derivative of utility function
  • Red is utility function
  • Purple is Y = 0.5, derivative of tile_value.
  • Safe_distance where purple and green intercepted
  • X < safe_distance risk averse.
  • X >= safe_distance can be made as risk neutral by ignoring safety value below certain threshold, in this case 0.496
  • Obviously goal 1 and goal 2 can be achieved.

and when ghost are in flee mode(PacMan obtain power pellet)

by simply negate the utilty function, pacman will prioritize to pursued ghost when within the safe distance.

Untitled

here is the demo

logistic_emo.gif

Learning Agent

I took a very naive approach on learning agent.

  • Based on Logistic Utility Agent I implemented an learning agent.
  • Because the nature of vanilla javascript this is very rudimentary approach.
  • Run 200 iteration and log every location pacman died.
  • Add dead_count / (1+ghost_distance) to that tile to indicate those tiles are dangerous

Untitled

Result Comparision

Screenshot 2023-01-01 at 1.19.15 AM.png

About

Implementation of a utilty agent, a rule-based agent and learning agent for the game PacMan using javascript

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published