machine-learning - ゲームの優れた評価関数を作成するにはどうすればよいですか？

Question

私は時々ボードゲームの変種をプレイするプログラムを書いています。基本的な戦略は、標準的なアルファベータ法または同様の検索であり、エンドゲームやオープニングへの通常のアプローチによって強化されることもあります。私は主に変則チェスをいじっていたので、評価関数を選ぶときは、基本的なチェス評価関数を使用します。

しかし、今はまったく新しいボードゲームをプレイするプログラムを書いています。良いまたはまともな評価関数を選択するにはどうすればよいですか？

主な課題は、常に同じピースがボード上にあるため、通常のマテリアル機能が位置によって変化せず、ゲームのプレイ回数が1,000回未満であるため、人間が必ずしも十分にプレイできるとは限らないことです。まだ洞察を与えるには。（PS。私はMoGoアプローチを検討しましたが、ランダムゲームが終了する可能性は低いです。）

ゲームの詳細：ゲームは、片面に6個固定された10x10のボードでプレイされます。ピースには特定の移動ルールがあり、特定の方法で相互作用しますが、ピースがキャプチャされることはありません。ゲームの目標は、ボード上の特定の特別な正方形に十分な数のピースを置くことです。コンピュータプログラムの目標は、現在の人間のプレーヤーと競争力のある、またはそれよりも優れたプレーヤーを提供することです。

Answer 1

私はいくつかの基本から始めて、後でもっと難しいものに移ります。

基本的なエージェントとテストフレームワーク

どのようなアプローチを取る場合でも、本当にシンプルで馬鹿げたものから始める必要があります。ダムエージェントの最善のアプローチはランダムなものです（可能なすべての動きを生成し、ランダムに1つを選択します）。これは、他のすべてのエージェントを比較するための開始点として機能します。比較のための強力なフレームワークが必要です。さまざまなエージェントを必要とし、それらの間でいくつかのゲームをプレイすることを可能にし、パフォーマンスのマトリックスを返すもの。結果に基づいて、各エージェントの適合度を計算します。たとえば、関数tournament(agent1, agent2, agent3, 500)はエージェントの各ペア間で500ゲームをプレイし（最初/ 2番目をプレイ）、次のようなものを返します。

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

ここでは、たとえば、勝利に2ポイント、ドロースコアリング関数に1ポイントを使用し、最後にすべてを合計してフィットネスを見つけます。agent3この表は、それが最良であり、実際にagent1はと変わらないことをすぐに教えてくれますagent2。

したがって、これら2つの重要な設定が完了すると、評価関数を試す準備が整います。

---

機能の選択から始めましょう

1. まず、not a terrible評価関数を作成する必要があります。これは、この関数が3つの重要な側面（勝ち/引き分け/負け）を正しく識別する必要があることを意味します。これは当たり前のことのように聞こえますが、作成者がこれら3つの側面を正しく設定できなかったボットを大量に目にしました。

2. 次に、人間の創意工夫を駆使して、ゲームの状態のいくつかの機能を見つけます。最初に行うことは、ゲームの専門家と話し、彼がそのポジションにアクセスする方法を尋ねることです。

3. 専門家がいない場合、または5分前にゲームのルールを作成したばかりの場合でも、パターンを検索する人間の能力を過小評価しないでください。いくつかのゲームをプレイした後でも、賢い人はあなたに彼がどのようにプレイすべきかについてのアイデアを与えることができます（それは彼がアイデアを実行できるという意味ではありません）。これらのアイデアを機能として使用してください。

4. この時点では、これらの機能がゲームにどのように影響するかを実際に知る必要はありません。機能の例：ピースの価値、ピースの可動性、重要な位置の制御、安全性、可能な移動の総数、仕上げへの近さ。

5. これらの機能をコード化し、それらを個別に使用して、何が最適に機能するかを確認したら（それ自体では適切に機能しない機能を急いで破棄しないでください。他の機能と組み合わせて使用​​すると役立つ場合があります）、組み合わせを試す準備ができています。

単純な機能を組み合わせて重み付けすることにより、より良い評価を構築します。標準的なアプローチがいくつかあります。

1. 機能のさまざまな組み合わせに基づいてuber関数を作成します。線形eval = f_1 * a_1 + ... f_n * a_n（f_i特徴、a_i係数）にすることができますが、何でもかまいません。次に、この評価関数の重みが完全にランダムな多くのエージェントをインスタンス化し、遺伝的アルゴリズムを使用してそれらを相互に再生します。テストフレームワークを使用して結果を比較し、2、3の明らかな敗者を破棄し、2、3の勝者を変更します。同じプロセスを続けます。（これは大まかな概要です。GAについてもっと読む）

2. ニューラルネットワークからのバックプロパゲーションのアイデアを使用して、ゲームの終わりからエラーをバックプロパゲーションし、ネットワークの重みを更新します。あなたはそれがバックギャモンでどのように行われたかをもっと読むことができます（私は似たようなものを何も書いていませんので、不足して申し訳ありません）。

評価関数なしで作業できます！これは、ミニマックス/アルファベータについてしか聞いたことがない人にとっては非常識に聞こえるかもしれませんが、評価をまったく必要としない方法があります。それらの1つはモンテカルロ木探索と呼ばれますそして、名前のモンテカルロが示唆しているように、ツリーを生成するために多くのランダムな（ランダムであってはならず、以前の優れたエージェントを使用できます）ゲームプレイを使用します。これはそれ自体が大きなトピックなので、私は本当に高レベルの説明をします。ルートから始めて、フロンティアを作成し、それを拡張しようとします。何かを展開すると、ランダムに葉に移動します。リーフから結果を取得し、結果を逆伝播します。これを何度も行い、現在のフロンティアの各子に関する統計を収集します。最適なものを選択してください。そこには、探査と搾取のバランスをどのように取るかに関する重要な理論があり、UCT（Upper Confidence Boundアルゴリズム）があります。

Answer 2

移動度（可能な移動の数）から対戦相手の移動度を引いたものなど、評価関数の候補をいくつか見つけてから、各メトリックの最適な重みを見つけてください。遺伝的アルゴリズムは、評価関数の重みを最適化するために非常にうまく機能しているようです。

ランダムな重みで母集団を作成し、限られた深さとターンで互いに戦い、敗者を勝者からのランダムな組み合わせに置き換え、シャッフルして繰り返し、世代ごとに母集団の平均を印刷します。結果に満足するまで、または一部のメトリックの範囲を調整する必要があることがわかり、1つのメトリックの最適値が初期範囲外であると思われる場合は、再試行するまで実行します。

後期編集：当時私が知らなかった、より受け入れられ、研究され、理解されたアプローチは、「差分進化」と呼ばれるものです。子孫は、平均への時期尚早な収束の問題を回避するような方法で、2つではなく3つの親から作成されます。

Answer 3

強化学習などの教師あり機械学習アルゴリズムを検討します。ボードゲームの強化学習をチェックしてください。それはあなたに調査するためのいくつかの良い方向性を与えると思います。

また、強化学習に基づくゲームオセロの戦略獲得（PDFリンク）をチェックしてください。ゲームのルールが与えられれば、優れた「ペイオフ機能」を学ぶことができます。これはTD-Gammonと密接に関連しています...

トレーニング中、ニューラルネットワーク自体を使用して両側の動きを選択します...かなり驚くべき発見は、生のボードエンコーディングを利用したゼロ初期知識実験でも、かなりの量の学習が実際に行われたことでした。

Answer 4

まだ誰もゲームを理解していない場合、まともな評価関数を取得する方法はありません。材料数のある標準のアルファベータは、チェスまたはその変種に適している、またはまともであると私に言わないでください（おそらく敗者のチェスは例外です）。

フィードバックまたは同様の機械学習アルゴリズムを使用してニューラルネットワークを試すこともできますが、通常、大量のトレーニングが行われるまでは効果がありません。この場合、おそらく利用できません。そしてそれでも、彼らが吸わなければ、あなたは彼らから知識を得ることができません。

ゲームをできる限り理解することは間違いないと思います。まず、評価関数で未知数をランダムのままにします（または、未知数がよりよく知られるようになるまで、画像から外します）。

もちろん、ゲームに関するより多くの情報を共有したい場合は、コミュニティからより良いアイデアを得ることができます。

Answer 5

私が理解しているように、ミニマックスツリーの葉で使用する優れた静的評価関数が必要です。もしそうなら、この静的評価関数の目的は、そのボードがコンピュータプレーヤーにとってどれだけ優れているかについての評価を提供することであることを覚えておくのが最善です。そうです

f（board1）> f（board2）

その場合、board2よりもboard1の方がコンピューターに適している（最終的には勝つ可能性が高い）ことは事実である必要があります。もちろん、静的関数がすべてのボードに対して完全に正しいわけではありません。

つまり、「ゲームの目標は、ボード上の特定の特別な正方形に十分な数のピースを置くことです」と言うので、f（board）での最初の刺し傷は、単にコンピューターがそれらに持っているピースの数を数えることです。特別な正方形。その後、さらにフィネスすることができます。

ゲームの詳細を知らなければ、より良い推測をすることは不可能です。あなたが私たちにゲームルールを与えてくれれば、stackoverflowユーザーはそのような機能のためのたくさんの独創的なアイデアを思いつくことができると確信しています。

Answer 6

さまざまな機械学習手法を使用して評価関数を作成できますが（gnubackgammonなどのプロジェクトで使用されるTD-Learningはその一例です）、結果はゲーム自体に確実に依存します。バックギャモンの場合、ゲームの確率的性質（サイコロを振る）により、学習者はやりたくない領域を探索する必要があるため、非常にうまく機能します。そのような重要なコンポーネントがなければ、おそらくそれ自体に対しては良いが、他の人に対しては良くない評価関数になってしまうでしょう。

物質的な違いは当てはまらないかもしれないので、モビリティの概念は重要ですか？つまり、可能な動きはいくつありますか？ボードの特定の領域を制御することは、通常、そうでないよりも優れていますか？ゲームをプレイする人々と話して、いくつかの手がかりを見つけてください。

できるだけ優れた評価関数を使用することをお勧めしますが、検索アルゴリズムを調整して、できるだけ深く検索できるようにする必要もあります。時々、これは実際にはもっと懸念事項です。なぜなら、メディコア評価関数を備えた深い検索者は、優れた評価関数を備えた浅い検索よりも優れている可能性があるからです。それはすべてドメインに依存します。（gnubackgammonは、たとえば1プライ検索でエキスパートゲームをプレイします）

検索の品質を向上させるために使用できる他の手法があります。最も重要なのは、検索結果をキャッシュするための転置テーブルを用意して、健全な前方プルーニングを行うことです。

これらのスライドを確認することを強くお勧めします。

Answer 7

また、選択には注意する必要があります。アルゴリズムが実際の値と既知の関係を持っていない場合、標準のAI関数は正しく機能しません。有効であるためには、評価関数またはヒューリスティックは一貫して実際の値と同じかそれ以下である必要があります。そうでない場合、奇妙な方法で決定を導きます（標準的なポイントは問題ないと思いますが、チェスについて議論する可能性があります） ）。

私が通常行うことは、何が可能で何が必要かを見つけることです。倉庫番などの一部のゲームでは、現在の場所から任意の目標の場所に1つのボックスを（単独で）取得するために必要な最小数のボックス移動を使用しました。これは必要な移動数の正確な答えではありませんが、過大評価することはなく、ボード全体に対して事前に計算できるため、かなり優れたヒューリスティックだと思います。ボードのスコアを合計する場合、それは現在の各ボックスの場所の値の合計にすぎません。

パックハンティングとパックディフェンスを進化させるために書いた人工生命シミュレーションでは、私が使用したスコアリングシステムは、進化を導くためだけであり、剪定は実行しませんでした。私は各クリーチャーに生まれるポイントを1つ与えました。彼らが彼らの人生で消費したエネルギーの各ポイントについて、私は彼らにもう1つのポイントを与えました。次に、それらの世代のポイントの合計を使用して、それぞれが再現する可能性を判断しました。私の場合、彼らが獲得した彼らの世代の合計ポイントの割合を単純に使用しました。回避するのが得意なクリーチャーを進化させたいと思っていたら、ポイントを食い尽くしてスコアを下げていただろう。

また、関数が目標を達成するのが難しくないように注意する必要があります。何かを進化させようとしている場合は、ソリューションスペースに適切な勾配があることを確認する必要があります。ランダムにヒットした場合に勝利を宣言するだけでなく、進化をある方向に導きたいと考えています。

あなたのゲームについてもっと知らなければ、関数を作成する方法をあなたに教えるのは難しいでしょう。勝ち負けを示す何かの明確な価値はありますか？ギャップを埋めるための最小コストを見積もる方法はありますか？

より多くの情報を提供していただければ、より多くの洞察を提供できるよう努めたいと思います。このトピックに関する優れた本もたくさんあります。

ジェイコブ

Answer 8

まともな評価関数が存在することさえ必ずしも真実ではないことを覚えておいてください。このステートメントでは、評価関数は複雑度（P）が低くなければならないと思います。