Number states of the env

[thanhthanhhp123]

How I can get the number states of env? I try to used policy iteration and value iteration to solve this!

[schefflaa]

Here's what I'd say, you may want to cross-check this.

Consider a random room from the standard Sokoban-v0 environment. To calculate the combinatorial possibilities of arranging $1$ player, $3$ identical boxes, and $26$ identical floor tiles, we need to consider the total number of items and the number of each item type.

The total number of items is the sum of the item type counts:
$$\text{total items} = 1 \text{ player} + 3 \text{ boxes} + 26 \text{ floor tiles}$$

Note that box-targets are technically just regular floor tiles, as they can be either empty, occupied by a player or a box.

To calculate the number of arrangements, we can use the concept of permutations of multisets. Since the boxes are identical, the arrangements of the boxes themselves do not contribute to different possibilities. Furthermore, we know that the floor tiles are also identical and cannot be distinguished from one another. Therefore, the number of arrangements can be calculated like this:

$$\frac{30!}{1! * 3! * 26!}$$

Or, more generally. if the multiplicities of the elements of a finite multiset $M$ (taken in some order) are $m_{1}, m_{2}, ..., m_{l}$ and their sum (that is, the size of $M$) is $n$, then the number of multiset permutations of $M$ is given by the multinomial coefficient:

$$ {n \choose m_1, m_2, \ldots, m_l} = \frac{n!}{m_1!, m_2!, \cdots, m_l!} = \frac{\left(\sum_{i=1}{m_i}\right)!}{\prod_{i=1}{m_i!}}. $$

For Sokoban, the room size, box amount and even player amount can vary. So let's define a function that calculates the state space given an arbitrary environment to find out how many possible states there are.

def calculate_state_space(env_or_obs):
    # allow for both env and observation as input
    if isinstance(env_or_obs, gym.Env):
        arr_walls, arr_goals, arr_boxes, arr_player = env_or_obs.render(mode='raw')
    else:
        arr_walls, arr_goals, arr_boxes, arr_player = env_or_obs # assuming render mode is 'raw'

    room_size = int(np.sum((arr_walls-1)*-1))
    boxes = int(np.sum(arr_boxes))
    players = int(np.sum(arr_player))
    floor = room_size-boxes-players
    state_amount = math.factorial(room_size) / (math.factorial(players) * math.factorial(boxes) * math.factorial(floor))
    return int(state_amount)

env = gym.make('Sokoban-v0')
env.reset()
print(calculate_state_space(env))