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

StackOverflow https://stackoverflow.com/questions/1291377

質問

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

しかし今、私は全く新しいボードゲームをプレイするプログラムを書いています。良い評価関数、あるいは適切な評価関数を選択するにはどうすればよいでしょうか?

主な課題は、同じ駒が常にボード上にあるため、通常の物質関数が位置に基づいて変化しないこと、およびゲームのプレイ回数が 1,000 回未満であるため、人間が必ずしも十分にプレイしているわけではないことです。まあ、洞察力を与えるのはまだ先だ。(追伸。MoGo のアプローチも検討しましたが、ランダムなゲームは終了しそうにありません。)

ゲーム詳細:ゲームは、各面に 6 つのピースが固定された 10 × 10 のボードでプレイされます。駒には特定の移動ルールがあり、特定の方法で相互作用しますが、駒が捕捉されることはありません。ゲームの目標は、ボード上の特定の特別なマスに十分な駒を配置することです。コンピュータ プログラムの目標は、現在の人間のプレーヤーと競争できるか、それよりも優れたプレーヤーを提供することです。

役に立ちましたか？

解決

機動力 (可能な手の数) から相手の機動力を引いたものなど、評価関数の候補をいくつか見つけて、各指標の最適な重みを見つけてみます。遺伝的アルゴリズムは、評価関数の重みを最適化するのに非常にうまく機能するようです。

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

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

他のヒント

いくつかの基本的なことから始めて、後でより難しいことに移ります。

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

どのようなアプローチをとるとしても、本当に単純で馬鹿げたものから始める必要があります。愚かなエージェントに対する最善のアプローチは、ランダムなアプローチです (可能なすべての動きを生成し、ランダムに 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 係数）、何でもかまいません。次に、この評価関数に対して完全にランダムな重みを付けて多数のエージェントをインスタンス化し、遺伝的アルゴリズムを使用してそれらを相互にプレイします。テスト フレームワークを使用して結果を比較し、明らかな敗者のいくつかを破棄し、勝者のいくつかを変更します。同じプロセスを続けます。(これは大まかな概要です。GA について詳しくはこちらをご覧ください)

  2. ニューラル ネットワークからの逆伝播のアイデアを使用して、ゲームの終了から誤差を逆伝播し、ネットワークの重みを更新します。それがどのように行われたかを詳しく読むことができます バックギャモン （似たようなことは書いていないので、短くて申し訳ありません）。

評価機能なしでも働けます！ ミニマックス/アルファベータについてしか聞いたことがない人にとっては非常識に聞こえるかもしれませんが、評価をまったく必要としないメソッドもあります。そのうちの1人はこう呼ばれます モンテカルロツリー検索 そして、モンテカルロという名前が示すように、ツリーを生成するために多くのランダム (ランダムであるべきではなく、以前の優れたエージェントを使用することができます) ゲーム プレイを使用します。これ自体が大きなトピックなので、非常に高度な説明をします。根っこから始めてフロンティアを作り、それを拡大しようとします。何かを展開すると、ランダムにリーフに移動します。リーフから結果を取得し、その結果を逆伝播します。これを何度も繰り返し、現在のフロンティアの各子に関する統計を収集します。最適なものを選択してください。そこには、探索と活用の間のバランスをどのように取るかに関する重要な理論があり、UCT (上限信頼限界アルゴリズム) について読むとよいでしょう。

私は、このような強化学習と教師あり機械学習アルゴリズムを見てみます。強化は、ボードゲームの中で学習noreferrer"> 戦略取得をチェックアウト/ゲームのルールを与えられたA>（PDFリンク）は、優れた「ペイオフ機能は」学ぶことができます。これは密接に関連している TD-ギャモンに...

  

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

誰もまだゲームを理解していない場合は、

、あなたはまともな評価関数を得ることができる方法はありません。材料数の標準α-βは（多分敗者チェスは例外です）良いかチェスまたはその変種のためにも、まともであることを教えないでください。

あなたはフィードバックまたは類似の機械学習アルゴリズムとニューラルネットワークを試みることができるが、彼らはこのケースではおそらく利用できないトレーニングのトンを持ってまで、彼らは通常吸います。彼らは吸うしていない場合でも、その後、あなたは彼らから知識を得ることができません。

私は（未知数よりよく知られているになるまで、あるいは単に絵の外に）あなたがして、スターターのために、評価関数にランダムとしての未知数を残すことができる最高のゲームを理解する短い方法はありませんだと思います。

あなたがゲームについての詳細情報を共有したい場合は、

もちろん、あなたがコミュニティからのより良いアイデアを得ることができます。

私はそれを理解したよう

、あなたは良い静的評価関数は、あなたの最小 - 最大ツリーのリーフで使用したいです。もしそうなら、それはこの静的な評価関数の目的は、ボードは、コンピュータプレイヤーのためのものであることをどのように良いのとしての評価を提供することであることを覚えておくことが最善です。そうです。

F（board1）> F（board2）

それは、コンピュータのためのより良いboard1であることは事実でなければなりませんboard2よりも（最終的に勝つ可能性が高いです）。もちろん、静的な機能は、これまでのすべてのボードに完全に正しくありません。

だから、あなたは、単に作品のコンピュータの数をカウントすることであろう、F（ボード）のように最初に刺す「ゲームの目標は、ボード上の特定の特別な正方形であなたの作品を十分に持っていることです」と言いますこれらの特別な正方形の上に持っています。あなたは、より多くのそれをフィネスすることができます。

より良い推測を与えるために、そのことは不可能、ゲームの詳細を知らず。あなたは私たちにゲームのルールを与えた場合、私はstackoverflowのユーザーが、このような機能のための独創的なアイデアのトンが付属してすることができるだろうと確信しています。

あなたは評価関数を思い付くために、様々な機械学習方法を使用することができますが、

、結果は間違いなくゲーム自体に依存している（例えばgnubackgammonなどのプロジェクトで使用されるTD-ラーニング、その一例です）。ゲーム（ロールサイコロ）の確率的性質は、それが何をしたくないかもしれ領土を探索する学習者を強制するためにバックギャモンのために、それは、本当によく働きます。そのような重要なコンポーネントがなければ、あなたはおそらく自分自身に対してではなく、他の人に対して良い評価関数となってしまいます。

素材違いは適用できない場合がありますので、

、重要なモビリティの概念です - あなたが利用可能な、すなわちどのように多くの可能な動き？ないよりも通常より良いボードの一定の面積を制御していますか？ゲームはいくつかの手がかりを見つけるために遊ぶ人に相談します。

それはすることができますように評価関数のように良いを持っていることが望ましいですが、あなたができる限り、の深くのように、検索することができますので、

、あなたも同調するように、検索アルゴリズムを必要とします。 medicore評価関数との深い探索が良い評価関数と浅い検索をoutplayことができるので時々、これは、実際には懸念の詳細です。それはすべてのドメインに依存します。 （gnubackgammonは、例えば、1プライの検索と専門家のゲームを果たしている）

サウンド前方刈り込みを持っているキャッシュ検索結果に移調テーブルを持つことが、最も重要なのは、検索の品質を向上させるために使用することができ、他の手法があります。

私は非常に上でこれらのスライドを見てお勧めします>。

また、あなたの選択に注意する必要があります。あなたのアルゴリズムは、実際の値と既知の関係を持っていない場合は、標準のAI機能が正しく動作しません。有効であるために、あなたの評価関数、またはヒューリスティックは一貫として、または実際の値以下同じであること、または、それは私が基準点は大丈夫だと思うにもかかわらず、人はチェスを主張できた（奇数方法であなたの決定を導くだろう持っています）。

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

私はパックの狩猟とパックの防衛を進化させるために書いた人工生命のシミュレーションでは、私が使用されるスコアリングシステムは進化を導くために、あらゆる刈り込みを実行するだけでなくでした。私が生まれたことのために各クリーチャー1ポイントを与えました。彼らは彼らの生活の中で消費されるエネルギーの各点について、私は彼らに一つの追加点を与えました。私はその後、各再現した方法可能性を決定するために彼らの世代のポイントの合計を使用しました。私の場合、私は単に彼らが獲得していた彼らの世代の合計ポイントの割合を使用していました。私は回避で素晴らしかった生き物を進化させたいと思っていたら、私はそれらのオフに食べポイントを取得するためにダウン得点だろう。

また、あなたの関数がヒットする目標をあまりにもハードではないことに注意する必要があります。あなたが何かを進化しようとしている場合は、解空間がまともな傾斜を有することを確認します。あなたは、方向に進化を導くことがランダムにヒットし発生した場合だけではなく、勝利を宣言したい。

は、あなたのゲームについての詳細を知らなくても、私はハードどのように機能を構築するためにあなたを伝えるために押されるでしょう。勝敗を示す何かのそこに明確な値はありますか？あなたはギャップを埋めるために、最小のコストを推定する方法を持っていますか？

あなたはより多くの情報を提供する場合は、

は、私が試してみて、より多くの洞察を提供するために幸せになります。優れた図書の多くは、同様のトピックにあります。

ヤコブ

それはまともな評価関数も存在していることnescessarily真実ではないことに注意してください。この文のために私は評価関数は、低複雑（P）でなければならない、と仮定します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top