Оценка количества детей в игровом дереве лабиринта

Question

Предположим, у нас есть игра в лабиринт с 1 мышью и 4 кошками в 20х20-ми сетчатом лабиринте. Предположим, что каждый агент в лабиринте может перемещать N, E, S, W. Каково было бы ваше лучшее предположение относительно количества детей каждого узла в этом массивном игровом дереве?

Это мое лучшее предположение, но я не уверен, какие-то мысли?

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

Состояние игры определяется положением пяти агентов (1 мышь + 4 кошки). Каждый агент может двигаться в 4 направлениях и не может оставаться неподвижным. Таким образом, каждое состояние игры имеет максимум 5^4 детей.

Если агенты могут оставаться неподвижными, то у них есть 5 действий, поэтому каждое состояние имеет максимум 5^5 детей.

Это «максимумы», потому что некоторые из этих дочерних состояний могут быть повторениями друг друга или не разрешены, например, когда два агента пытаются переместиться в одно и то же место или агент не может двигаться, потому что он окружен, или они находятся на краю света.