0

次のゲームの AI を構築したいと考えています。

  • M x Nボードに 2 人のプレーヤーがいる
  • 各プレイヤーは上下または左右に移動できます
  • ボードにはさまざまなアイテムがあります
  • できるだけ多くのカテゴリで他のプレイヤーよりも多くのアイテムを持っているプレーヤーが勝ちます (1 つのカテゴリでより多くのアイテムを持っていると、このカテゴリの勝者になり、より多くのカテゴリを持つプレーヤーがゲームに勝ちます)。
  • 1ターンで、立っているアイテムを拾ったり、移動したりできます
  • プレイヤーの動きは同時に行われます
  • 同じフィールドに立っている 2 人のプレイヤーは、両方がそうする場合、0.5 のピックアップ チャンスがあります。

次のいずれかの条件が満たされた場合、ゲームは終了します。

  • すべてのアイテムがピックアップされました
  • 1 人のプレーヤーが半分以上のカテゴリの半分以上のアイテムを持っているため、すでに明確な勝者が存在します。

AI についてはよくわかりませんが、少し前に機械学習のクラスを受講したことがあります。

  1. このような問題に取り掛かるにはどうすればよいですか?

  2. この問題の一般化はありますか？

4

3 に答える 3

2

あなたが提案したような敵対的な検索ゲーム（2人のプレーヤーのゼロサムゲームと呼ばれる）の標準的な選択は、ミニマックス検索と呼ばれます。ウィキペディアから、ミニマックスの目標は

最悪の場合（最大損失）のシナリオで発生する可能性のある損失を最小限に抑えます。あるいは、最小ゲインを最大化することと考えることもできます。

したがって、それはミニマックス、またはマキシミンと呼ばれます。Max基本的に、レベルのツリーを構築しますMin。各ノードには、各ターンで可能なアクションの数（この場合は4）に等しい分岐係数があります。各レベルはプレイヤーのターンの1つに対応し、ツリーはゲームの終了まで延長されます。これにより、対戦相手も最適にプレイしていると仮定して、各ターンで最適な選択肢を検索できます。対戦相手が最適にプレーしていない場合、あなたはより良いスコアを出すだけです。基本的に、各ノードで可能なすべてのゲームをシミュレートし、現在のターンに最適なアクションを選択します。

可能なすべてのゲームを生成するのに長い時間がかかるように思われる場合、あなたは正しいです、それは指数関数的な複雑さのアルゴリズムです。ここから、アルファベータ法を調査する必要があります。これにより、これまでに見つけた値に基づいて列挙している可能性のあるゲームの一部を本質的に排除でき、ミニマックスのかなり単純な変更です。このソリューションは依然として最適です。詳細については、ウィキペディアの記事を参照してください。

そこから、ノードを削除するためのさまざまなヒューリスティックを試してみてください。これにより、トラバースする多数のノードのツリーが削除される可能性がありますが、ヒューリスティックを介してノードを削除すると、最適ではないが、それでも適切なソリューションが生成される可能性があることに注意してください。あなたのヒューリスティックに。一般的な戦術の1つは、検索ツリーの深さを制限することです。基本的には、5移動先の各プレーヤーのスコアの推定値を使用して、5移動先を検索し、現在の最良の移動を決定します。繰り返しますが、これは微調整できるヒューリスティックです。そのターンにゲームが終了したかのようにゲームのスコアを単純に計算するようなもので十分かもしれません。これは間違いなく良い出発点です。

最後に、確率が関係するノードの場合、Expectiminimaxと呼ばれるMinimaxのわずかな変更があります。これは、ランダムな選択を選択する「3番目の」プレーヤーを追加することによって本質的に確率を処理します。この3番目のプレーヤーのノードは、ランダムイベントの期待値を値として受け取ります。

于 2013-01-12T02:44:26.957 に答える
2

このような問題に対する通常のアプローチは、生きている対戦相手と十分長くゲームをプレイして、勝利に導くヒューリスティックな解決策 (短期的な目標) を見つけることです。次に、これらのヒューリスティックをソリューションに実装します。非常に小さなボード (1x3) と少数のカテゴリ (1) から始めて、プレイして何が起こるか見てから、より複雑なケースに進みます。

ゲームをプレイしないと、アイテムが少ないカテゴリの方が価値があると想像できます。また、アイテムが現在あなたに近いカテゴリ、およびアイテムがあなたから最も離れているが、対戦相手よりもあなたに近いカテゴリでもあります。

すべてのカテゴリにはコストがあり、それはそれをコントロールするために必要な移動の数ですが、あなたのコストは対戦相手のコストとは異なり、移動ごとに変化します. あなたのコストが対戦相手のコストに近いが、それでも対戦相手のコストよりも低い場合、カテゴリはあなたにとってより大きな価値があります。

移動するたびにカテゴリの値が変わるため、ボードを再計算し、そこから次の移動を決定する必要があります。目標は、対戦相手があなたと同じアルゴリズムを使用すると仮定して、あなたの値を最大化し、対戦相手の値を最小化することです。

複数のターンを事前に探索すると、ベスト ムーブの検索はより複雑になりますが、より効果的でもあります。この場合、同じアルゴリズムを使用して対戦相手の動きをシミュレートし、対戦相手が最も弱いカウンター ムーブを持っているムーブを選択する必要があります。この戦略はミニマックスと呼ばれます。

これはすべて実際には AI ではありませんが、アルゴリズムのロード マップです。他の回答で言及されているニューラル ネットワークは AI に似ていますが、私はそれらについて何も知りません。

于 2013-01-12T01:49:42.017 に答える
1

AI の目標は、常に勝利条件を維持しようとすることです。

実用的である場合 (アイテムの場所の保存方法によって異なります)、各ターンの開始時に、残りのすべてのアイテムまでの距離が AI に認識される必要があります。理想的には、これはゲームの開始時に 1 回計算され、ターンごとに再計算されるのではなく、AI が移動する場所に基づいて単純に「調整」されます。また、AI が自分の状況だけを考慮しないのであれば、AI にプレイヤーに対して同じことをさせるのは賢明ではありません。

そこから、次の考慮事項の最適化として、どのアイテムをピックアップする必要があるかを決定する問題があります。

  • AI が現在持っているアイテムとアイテム カテゴリは何ですか?
  • プレーヤーが現在持っているアイテムとアイテム カテゴリは?
  • AIに近いアイテムとアイテムカテゴリは？
  • プレーヤーの近くにあるアイテムとアイテム カテゴリは何ですか?

これを正確にどのように行うかは、AI を打ち負かすのがどれだけ難しいかによって大きく異なります。

簡単な方法は、貪欲なアプローチを使用して、単に「現在の」最良の選択を追求することです。これは、プレーヤーが現在非常に多くのアイテム (おそらく 1 ～ 3) で勝っているカテゴリに属していない、最も近いアイテムを見つけるだけで実行できます。これにより、勝とうとする AI が生成されますが、先のことを考えないため、予測が容易になります。

貪欲なアルゴリズムが複数のターン先をチェックできるようにすることで、アルゴリズムが改善され、プレイヤーが何をするかを考えると、アルゴリズムがさらに改善されます。

ヒューリスティックは、より現実的な AI と打ち負かすのが難しい AI につながります。打ち負かすことはおそらく事実上不可能です。

于 2013-01-12T02:04:28.347 に答える