In plain words
Picture every possible arrangement of a game: every position, every score, every state of the world. That whole collection is the possibility space. Playing the game means walking through it.
See it
Tic-tac-toe has a tiny possibility space; most people have explored all of it by about age nine. Chess has one so vast that nobody will ever finish exploring it.
Why designers care
Designers shape possibility spaces. You decide how big the space is, how players move through it, and where the interesting places are. A space players exhaust quickly gets abandoned. A space with many worthwhile regions keeps them coming back.
Common mix-up
Bigger isn’t automatically better. A huge space where everything feels the same is less interesting than a small one full of surprises.