5

カードゲームのDominionを実行する F# プログラムが動作しています。遺伝的アルゴリズムを使用して、プレイの最適な戦略を決定したいと考えています。しかし、AIや遺伝的アルゴリズムについてはよくわかりません。手始めに良い文献を教えてもらえますか？

プレーの戦略は、与えられたハンドへの反応で構成されます。各ターンで、ボットに 1 枚のカードが配られます。配られたものに基づいて、アクション カードをプレイするか、新しいカードを購入するかを選択できます。目標は、できるだけ多くの勝利点カードでゲームを終了することです。

ハードコーディングされたアプローチは次のようになります。

def play(hand, totalDeck):
    if hand contains Smithy then use Smithy
    if hand contains enough coins for Province then buy Province
    if more than 30% of the totalDeck is Smithy, then buy coins

各カードのデッキ全体のターゲット部分のベクトルの観点から戦略を説明することを考えていました。

[Smithy, Province, Copper, ...]
[.3, .2, .1, ...]

次に、ボットを変異させるには、そのベクトルを変更して、変異したバージョンの方がうまくいくかどうかを確認します。フィットネス関数は、Dominion を他のさまざまなボットと対戦させた平均スコアです。(1 つのボットのスコアは対戦相手によって異なりますが、多くのボットに対して多くのゲームをプレイすることで、これが均等になることを願っています。)

これは理にかなっていますか？私は正しい道を進んでいますか？

4

3 に答える 3

5

ドミニオンは素晴らしいゲームですが、遺伝的アルゴリズムを使用して最適化するのは難しいでしょう。特定のゲームの入力はゲーム (使用されるカード セット) によって異なり、最適な戦略はゲームの過程で変化し、最適なプレイは特定の状況は、遺伝的検索にゆっくりと現れるだけです（GAとゲームの両方についての私のかなりの理解に基づいて、直感的に）。

Dominion へのより良いアプローチは、単純なヒューリスティック (ルールベース) アプローチか、非常に興味深いことに、モンテカルロ検索 (たとえば、http://cacm.acm.org/magazines/2012/3を参照) のいずれかになると思います。 /146245-the-grand-challenge-of-computer-go/fulltext )。モントカルロ検索が魅力的である理由は、まさに次のとおりです。

  • Dominion では、ランダムだが正当な一連の動きを簡単に生成できます。
  • そのようなシーケンスの「価値」を判断するのは、少なくとも簡単です (VP の増加)。
  • 「ベストプレイ」のルールをアプリオリに構築するのは難しい（それがゲームを優れたものにしている）

これは非常に良い挑戦です。経験をブログに書いてください。

于 2012-06-04T18:54:10.207 に答える
4

他のボットはどこから引き寄せますか? それらを静的に保ちますか？もしそうなら、訓練されたボットはゲーム自体で「上手」になることはなく、ダミーボットを悪用するのが得意になるだけです. そうでない場合、他のボットも進化し、他の制約が適用されない限り、勝率は品質の良い指標にはなりません。完璧なスキルを持つボットでいっぱいの人口では、お互いに対するパフォーマンスが平凡に見えることを常に認識してください!

共進化的アプローチを取ることができます：

  • 十分に大きな集団ですべてのボットを変異させます。
  • ラウンド ロビン トーナメントで繰り返し対戦させます (例: 100 回)
  • 最もパフォーマンスの悪いボットをいくつか排除し、
  • いくつかの最高のボットをそのままにしておく (エリート主義)
  • 残りの人口を、優れたボットの突然変異とクロスオーバーで補充します。

または、固定ベンチマークに対してトレーニングすることもできます。

  • ゲームの知識を使って、良さそうな手作りのポリシーでボットを作成します
  • または、人間のプレイヤー (自分自身?) に動きを提供してもらいます。これは、ボットのトレーニング経験の良いソースになるかもしれませんが、(専門家の) 人間の動きの大規模なデータベースにアクセスできない限り、非常に遅くなります。
  • ベンチマークに対してトレーニングする
  • 最高のパフォーマーの選択、変異など
于 2012-06-03T15:27:58.770 に答える
2

ゲームが非常に直線的でない限り、ベクトルは本当に良い結果につながらないと思います。次のルールベースのアプローチをお勧めします。

各ターンでカードのセットを保持し、プレイするカードを決定するか、カードをプレイしない場合は新しいカードを引きたいと考えます。必要なのは、どのカードをプレイするのが最適かを示すある種の優先機能です。このような優先度関数は、遺伝的プログラミングによって記述できます。設定されたレベル (例: 0) を超える優先度を持つカードがない場合を除き、常に最も優先度の高いカードをプレイします。その場合、新しいカードを引きます。遺伝的プログラミングを使用して、その優先機能を進化させることができます。

F# を使用しているため、 HeuristicLabでこのアプローチを試すことをお勧めします。これはC#で書かれています。そこにプログラムを問題として実装し、評価関数にそのゲームのシミュレーションを実行させることができます。ルールの文法とインタープリターを作成します。プライオリティ ルールが意味のある決定を下せるように、いくつかのパラメータを定義します。たとえば、プレイされたカードの数、残っている州などの一般的なゲーム情報や、そのカードをプレイすることの影響 (勝利の観点から) などのカード関連の情報などです。 -points) など。これらは、優先値を計算するインタープリターへの入力変数です。最も優先度の高いカードが選ばれます。次に、戦略を評価するために、たとえば、そのような問題を作成するときに 10 個のランダムなソリューションを定義し、評価で各ソリューションをそのランダムなボットと競合させます。ランダムボットのそれぞれを倒した量を測定し、勝てば勝つほど、より多くのボットを倒せば、フィットネスは向上し、勝てば勝つほどスコアは悪くなります。次に、アナライザーを問題に追加して、問題のランダムなソリューションを最適なパフォーマンスのソリューションで更新することもできるため、これらも時間の経過とともに進化させます。

必要に応じて、ターゲット部分のアイデアを使用することもできます。その場合、エンコーディングは RealVector になります。HeuristicLab で最適化することもできます (Evolution Strategy、Particle Swarm Optimization、または Genetic Algorithm を使用します)。

于 2012-06-03T20:26:07.287 に答える