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

Предположим, у нас есть игра-лабиринт с 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

nodes graph estimation tree game-theory
person Community    schedule 05.08.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

person Jose M Vidal    schedule 05.08.2012