PacMan character AI suggestions for optimal next direction

Question

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 programming 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 a 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 that is frightened: plus 200
   5. Has a ghost travelling toward PacMan: subtract 200
   6. Has a ghost travelling away from PacMan: do nothing
   7. Has a ghost travelling perpendicular: subtract 50
   8. Multiply the cell's value times a pecentage 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.

   and enqueue the three possible directions from the current cell.

4. 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.

---

FYI, this was originally posted on StackOverflow

Answer 1

Tandem's idea of hill-climbing algorithm is good. Another is: some variation on A* to see how far you can go to see how you can get the highest score over the next N turns, where N is tuned to give the desire result.

The scoring values you give can be thought of as "cost to move" -- you're basically on the right track, but you'll have to tweak the values until you get the result you want.

In general (not PacMan specific) terms, you need to allocate appropriate values for

• Wounded the to other guy.
• Killed another guy.
• Achieved some other goal (other than killing)
• Got wounded.
• Got killed.

and then look for the move that will lead to the maximum score N turns in the future. You may also want to avoid moves that lead to any score below X (say, the cost of dying) N turns into the future.

Once you've scored all the possible moves, added bonuses for how well it might turn out in the future and deducted for how poorly it might turn out in the future, then you just sort the array and take the best move.

Let us know how it turns out!

Answer 2

Definitly take a look at this video: http://www.youtube.com/watch?v=2XjzjAfGWzY

You will probably want some sort of hill-climbing path-finding algorithm.

Answer 3

You're going to perform a search.

• Node/State: Pacman location, Ghost locations, Pellet locations, Total score, Total lives.
• Transition: Pacman moves up, down, left, or right. If Pacman moves into a wall and does change locations that is totally fine (it might lead to some really interesting stalling strategies). If Pacman hits a ghost, remove a life and move him and ghosts to the origin.
• Cost: If Pacman moves onto a pellet 1, if he moves onto an empty space 2.
  The cost is a bit tricky, as it's non-obvious. The cost function I described will encourage Pacman to finish the level. This preclude a possible strategy and just camping out waiting for bonus fruit to appear. But I think we want the AI Pacman to finish the maze even if it yields a lower score.
• Goal: maximum score reached. That means all the pellets, fruit, and power pellets are eaten.

A* or UCS are great when seeking a goal. The way I've described the State/Transition/Goal will find a great walk path for Pacman the AI doesn't need to specifically consider avoiding death or seeking fruit. It will do that on it's own. Since the game is completely deterministic you could "search" from Pacman's starting location and find the optimal walk path to end (all pellets consumed) as a pre-computation and just have AI Pacman walk that path, no on the fly AI. The major drawback this approach is this could easily get out of hand in the cpu time and memory consumption.

Instead of dedicating the CPU and memory to performing a complete search you could perform partial search on the fly.

You can still use UCS/A* but stop searching after inspecting N nodes have been inspected and just use the best path found so far. This approach is nice in that you can tune N to find the balance between speed and precision.

Another method I'm particularly fond of is Monte-Carlo Tree search. In this method you let Pacman perform a random walk of N moves. After each random walk you record his initial move and final score. Perform M random walks (or just keep doing them until you're out of time or what ever). Pick the initial move with the best average of the random walks.

These partial searches have a serious drawback. If searching with UCS and Pacman doesn't score at all in the first N nodes inspected he'll get stuck and as all moves are equally bad.
A* wouldn't have this issue as long as the heuristic was careful to move Pacman closer to uneaten pellets.
MCTS might be able to avoid this issue if random walk is biased to move towards uneaten pellets and random walk never stops before scoring (ie the random walk keeps going if Pacman has 0 score.