I am thinking of a modified version of pacman. In this version, it will be a two-player game. Each player will have one pacman and one ghost. So there are 2 pacmans and 2 ghosts in the board at a time. No additional ghost is there. A player will control both his pacman and ghost separately- there is no predefined or random move of ghosts. Ghost of a player will try to catch the opponent's pacman. Pacman of a player will try to avoid the ghost of the opponent. Collision of ghost and pacman of the same player won't affect anything. So the pacman and the ghost of the same player need to cooperate with each other. "Moving Target Search" seems promising for the ghost, but what about the pacman? Will minimax (with alpha beta pruning) work in this multi-agent cooperative environment? I am saying this cooperative because my ghost will try to catch the opponent's pacman and my pacman will use this opportunity to eat more food. I have separate functions for the pacman move and the ghost move to simplify the gameplay. So returning a single tuple (including the moves of both pacman and ghost) from a function is not possible here.


This is an adversarial game problem where you need to find the optimal behavior from each position. There are several approaches to attack such problem.

You can do Minimax with alpha beta pruning to find the best move. It will provide you an optimal move after exploring the entire tree up to some level (not too deep if the branching factor is too high, here your branching factor is $4*players$) using a handcrafted heuristic by you. So the quality of the results heavily depends on the quality of the heuristic. If you improve the pruning you can achieve better results, as you can explore more.

Another approach is Montecarlo Tree Search. This algorithms performs really good in several games, and doesn't depend on any previously knowledge of the game. Roughly speaking, it seeks the best option by expanding the tree from the state you are in and calculates the quality of a state by performing a random simulation of the game.

There is a novel approach, Reinforcement learning, that you can use to find the answer. The idea behind it is approximate the optimal policy that gives you the maximal reward. Here you can understand by policy the action you will make at any position an the rewards are the points you get after each action. You can read more about it here.

  • $\begingroup$ Thanks for the answer. I have already learnt minimax with alpha-beta pruning. So here the order will be like max (my pacman) -> max (my ghost) -> min (opponent pacman) -> min (opponent ghost) ? I have separate functions for the pacman and the ghost to simplify the gameplay. $\endgroup$ Dec 21 '17 at 2:57
  • $\begingroup$ That is exactly how it will work. Max for your players and Min for opponent players. $\endgroup$ Dec 21 '17 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.