コンピュータ プレイヤー向けの AI を含むRISK ボード ゲームを開発したいと考えています。さらに、これとこれに関する 2 つの記事を読み、モンテカルロ シミュレーションとマルコフ連鎖の手法について学ぶ必要があることに気付きました。そして、これらの手法を併用する必要があると思いましたが、遷移状態に関する確率を計算するための別の手法だと思います。
では、両者の重要な違いと長所と短所を説明できる人はいますか?
最後に、AI for RISK ゲームを実装する場合、どの方法を優先しますか?
ここでは、リスク ボード ゲームでの戦闘の結果について単純に決定された確率と、使用されるブルート フォース アルゴリズムを見つけることができます。考えられるすべての状態を指定するツリー図があります。このツリーでモンテカルロまたはマルコフ連鎖を使用する必要がありますか?
さて、記事をざっと読んで、彼らが何をしているのかを把握しました。あなたが尋ねた用語の私の概要は次のとおりです。
マルコフ連鎖は、システムがどのように状態から状態へと移行するかをモデル化したものです。マルコフ モデルをゼロから作成するのは難しい場合がありますが、一度作成すると、比較的使いやすく、比較的理解しやすいものになります。基本的な考え方は、ゲームには特定の状態が関連付けられているということです。ゲームの一部として、州から州へと移動します。そして重要なのは、この状態から状態への移動が確率に基づいて発生し、これらの確率を知っていることです。
その情報を取得したら、すべてをグラフとして表すことができます。ここで、ノードは状態であり、状態間のアーク (確率でラベル付けされています) は遷移です。また、特定の制約を満たす行列、または他のいくつかのより風変わりなデータ構造として表すこともできます。
短い記事は実際にはすべてマルコフ連鎖アプローチに関するものですが、これは重要なことですが、このアプローチは、軍隊 A が領土を攻撃し、軍隊 B が防御している場合に何が起こるかを推定する簡単な手段としてのみ使用されています。これはこの手法の優れた使用法ですが、リスクに対する AI ではなく、攻撃の可能性のある結果を把握するのに役立つ AI の単なるモジュールです。
対照的に、モンテカルロ法は推定器です。マルコフモデルであろうと他のモデルであろうと、何かのモデルを取得すると、それについて何かを推定したいという立場になることがよくあります。(十分に目を細めれば、たまたまその形式で扱うのが非常に難しい何かの積分の形に入れることができるものであることがよくあります。) モンテカルロ法は、ランダムにサンプリングして結果を集計するだけです。何が起こるかの見積もりに。
私の意見では、モンテカルロ手法は AI 手法ではありません。これらは、たまたま AI に役立つ非常に汎用的な手法ですが、AI そのものではありません。(マルコフ モデルについても同じことが言えますが、マルコフ モデルは AI での計画に非常に有用であり、AI の哲学全体がこの手法を中心に構築されているため、声明はより弱くなります。ただし、マルコフ モデルは他の場所でも使用されます。 )
それが彼らです。また、リスク AI を実装する必要がある場合、どれを使用するかという質問もありました。まあ、どちらも十分ではありません。私が言ったように、モンテカルロは AI 技術ではなく、一般的な数学ツールです。マルコフ モデルは、理論上はリスク ゲーム全体を表すことができますが、最終的には非常に扱いにくくなります。つまり、ゲームのすべての状態を表す必要があります。手札のカード数など (ここでは多くの詳細を説明しています: このアプローチには他にも多くの問題があります。)
Wolf の論文の核心は、マルコフのアプローチでもモンテカルロのアプローチでもなく、実際には彼が評価関数として記述したものです。これが AI の問題の核心です。つまり、どのアクションが最適かを判断する方法です。ブラットの論文のモンテカルロ法は、アクションの期待される結果が何であるかを把握する方法を説明していますが、それはどのアクションが最適かを把握することと同じではありません。さらに、Wolf の論文には、ゲーム ツリーが非常に大きくなるため、Risk で先読みを実行するのが難しいという控えめなステートメントがあります。
したがって、私の本当のアドバイスは次のとおりです。ミニマックス、アルファ ベータ プルーニング、特に期待ミニマックスなどの検索ツリー アプローチについて調べてください。Russell と Norvig やウィキペディアでも、これらの適切な処理を早期に見つけることができます。これらの手法が一般的に機能するのに、リスクにとって扱いにくい理由を理解してください。これにより、ボードの評価手法についての議論につながります。次に戻って、Wolf の論文を見て、彼の行動評価関数に焦点を当てます。そして最後に、彼が良い評価関数 を自動的に学習しようとする方法に注目してください。
それは大変な作業です。しかし、リスクは AI を開発するための簡単なゲームではありません。
(ただし、特定の攻撃の予想される結果を把握したいだけなら、モンテカルロを選ぶと思います。モンテカルロはクリーンで、理解するのが非常に直感的で、実装が非常に簡単です。大きな 1 つは、良い結果を得るために十分な試行を実行することです)。
マルコフ連鎖は、過去の出来事の記憶がないと仮定して、単純に一連の遷移とその確率です。
モンテカルロ シミュレーションは、一連の確率でのランダム ウォークのサンプリングの繰り返しです。
マルコフ連鎖を使用して確率をモデル化し、次にモンテカルロ シミュレーションを使用して予想される結果を調べることで、両方を一緒に使用できます。
リスクについては、利点が見当たらないので、マルコフ連鎖を使用しないと思います。可能な動きのモンテカルロ分析は、適切なフィットネス関数と組み合わせてかなり優れた AI を考え出すのに役立ちます。
私はこれが多くのことを知っていますが、それが役に立ったことを願っています.