Estimate of the number of children in a maze game tree

Question

Suppose we have a maze game with 1 mouse and 4 cats in a 20*20 grid maze. Assume each agent in the maze can move N, E, S, W. What would your best guess be as to the number of children of each node in this massive game tree?

This is my best guess but I'm not sure, any thoughts?

4 possible mouse moves *
(4 directions) * (4! possible cat1 moves) *
(4 directions) * (4! possible cat2 moves) *
(4 directions) * (4! possible cat3 moves) * 
(4 directions) * (4! possible cat4 moves)
= 339738624 children in 1 node

Answer 1

The game state is given by the positions of the five agents (1 mouse + 4 cats). Each agent can move in 4 directions and cannot stay still. Thus, each game state has a maximum of 5^4 children.

If the agents can stay still then they have 5 actions, thus each state has a maximum of 5^5 children.

These are 'maximums' because some of those child states might be repeats of each other or not allowed, for example, when two agents try to move to the same spot, or an agent cannot move because it is surrounded, or they are at the edge of the world.