# Reducing amount of possible states solving Pacman by searching

I consider simplified Pacman game:

• movement is discrete (on the grid),
• ghosts move deterministically based on difference between their and Pacmans coordinates,
• ghosts move every second turn,
• ghosts always chase Pacman, never reversed,
• the maze has no exit, success is when Pacman collects all the dots.

The most natural representation of the states space is a bit big as it consists of:

1. Pacmans position,
2. ghosts positions,
3. boolean if ghosts have moved in previous turn,
4. remaining dots positions.

Hence I want to reduce it significantly, but I have no idea how to do it.

• What makes you think someone can reduce the state-space? What is 'big' could depend on what you want to do. What do you want to know? Simulate Pacman? Play it optimally? Play it well? What do you want to use the state-space for? Exhaustive search? A heuristic? Please specify your question. Mar 4 '18 at 16:30
• @Discretelizard I want to play it optimally and the state space is to be used for search.
– user84912
Mar 5 '18 at 7:53