graph - 迷路ゲーム ツリーの子の数の推定

Question

20*20 グリッドの迷路に 1 匹のネズミと 4 匹の猫がいる迷路ゲームがあるとします。迷路内の各エージェントが 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

ゲームの状態は、5 つのエージェント (1 つのマウス + 4 つの猫) の位置によって与えられます。各エージェントは 4 方向に移動でき、静止することはできません。したがって、各ゲーム ステートには最大 5^4 の子があります。

エージェントが静止できる場合、エージェントには 5 つのアクションがあるため、各状態には最大 5^5 の子があります。

これらは「最大」です。これらの子状態の一部は、相互に繰り返されるか、許可されない可能性があるためです。たとえば、2 つのエージェントが同じ場所に移動しようとした場合、またはエージェントが囲まれているために移動できない場合、または世界の果て。