The image below is from a Berkeley AI course pdf I found.

enter image description here

My question is, why do the terms accounting for the ghosts and pellets come in raised to the number of units?

For example, there are two ghosts so the exponent is 2, there are 30 foods so the exponent is 30.

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $2^{30}$.

New contributor
user1029384756 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $2^{30}$.

Let's try it with 3 pellets. If you are right there would be $2 \times 3 = 6$ states, if the authors are right there would be $2^3 = 8$ states.

Using * for a pellet, and - for a space, we have the following states:

  1. * * *
  2. * * -
  3. * - *
  4. * - -
  5. - * *
  6. - * -
  7. - - *
  8. - - -

That's 8 states. The authors are correct.

In this case, intuitively the state is essentially one long 30-bit number - you can replace pellets with 1 and spaces with 0. In general, the rule is that if some component of the state can vary into $n$ different sub-states independently of other components, then the size of the whole state space multiplies by $n$.

There is a slight oversimplification, in that the pacman might not be able eat the pellets arbitrarily (although in the example given it looks like they can). Some states might not be reachable. However, trying to figure out all the reachable states and enumerate them in a useful way so that there is still a simple vector model to learn from would be complicated - possibly more complicated than solving the reinforcement learning problem for the same game. It is easier to simplify the state representation and have a larger overspecified state space.

  • 1
    $\begingroup$ Wonderful. Thank you for the explanation. I have accepted the answer. $\endgroup$ Jan 13 at 22:43

Your Answer

user1029384756 is a new contributor. Be nice, and check out our Code of Conduct.

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.