Back

Explore Courses Blog Tutorials Interview Questions
0 votes
2 views
in AI and Deep Learning by (50.2k points)

Firstly, this is AI for PacMan and not the ghosts.

I am writing an Android live wallpaper which plays PacMan around your icons. While it supports user suggestions via screen touches, the majority of the game will be played by an AI. I am 99% done with all of the programmings for the game but the AI for PacMan himself is still extremely weak. I'm looking for help in developing a good AI for determining PacMan's next direction of travel.

My initial plan was this:

  1. Initialize a score counter for each direction with a value of zero.

  2. Start at the current position and use a BFS to traverse outward in the four possible initial directions by adding them to the queue.

  3. Pop an element off of the queue, ensure it hasn't been already "seen", ensure it is a valid board position, and add to the corresponding initial directions score value for the current cell-based on:

    1. Has a dot: plus 10

    2. Has a power-up: plus 50

    3. Has a fruit: plus fruit value (varies by level)

    4. Has a ghost traveling toward PacMan: subtract 200

    5. Has a ghost travelling away from PacMan: do nothing

    6. Has a ghost travelling perpendicular: subtract 50

    7. Multiply the cell's value times a percentage based on the number of steps to the cell, the more steps from the initial direction, the closer the value of the cell gets to zero.

  4. and enqueue the three possible directions from the current cell.

  5. Once the queue is empty, find the highest score for each of the four possible initial directions and choose that.

It sounded good to me on paper but the ghosts surround PacMan extremely rapidly and he twitches back and forth in the same two or three cells until one reaches him. Adjusting the values for the ghost presence doesn't help either. My nearest dot BFS can at least get to level 2 or 3 before the game ends.

I'm looking for code, thoughts, and/or links to resources for developing a proper AI--preferably the former two. I'd like to release this on the Market sometime this weekend so I'm in a bit of a hurry. Any help is greatly appreciated.

1 Answer

0 votes
by (108k points)

Pick a random move and mark it with a score of 0.

For each step:

  1. Run the scoring function over the possible moves.

  2. If the highest score is x% greater than the record score then overwrite the record score and move with this one.

  3. Apply the move.

This will now no longer pick the "best" move on each step, but it doesn't seem like a greedy local search would be optimal anyway. It will make PacMan more consistent and stop the twitches.

Also, you should take a look at the top Artificial Intelligence Skills to master.

Browse Categories

...