0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard ♦
    Mar 4 '18 at 16:30
  • $\begingroup$ @Discretelizard I want to play it optimally and the state space is to be used for search. $\endgroup$
    – user84912
    Mar 5 '18 at 7:53

Your Answer

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