AI in Game Programming: PacMan character, optimal next direction

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.