Оценка на броя на децата в лабиринтно игрално дърво

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