3

私の学士論文では、ストラテゴのゲームをプレイすることを学習する遺伝的アルゴリズムを書きたいと思います（このゲームを知らない場合は、チェスと言ったと仮定しても安全です）。私はこれまで実際のAIプロジェクトを行ったことがないので、実際に実装についてほとんど知らないことを知るのは目を見張るものです。

私がこだわっているのは、実際の戦略の良い表現を考え出すことです。私はおそらくいくつかの思考エラーを犯していますが、私が遭遇するいくつかの問題：

  • 取締役会のポジション間のトランジションがたくさん含まれている表現があるとは思いません。
  • デシジョンツリーのブランチはどのように見えるでしょうか？私が思いついた表現には、交換可能なブランチがありません...明らかに一般的でもあるビット文字列を使用する場合、ビットは何を表しますか？
  • 特定のピース間の距離にスコアを割り当てますか？それをどのように表現しますか？

私は3年以上の研究の後にこれらのことを知る必要があると思うので、私はかなり愚かだと感じます-これは私にはまったく手がかりがないように見えるに違いありません。それでも、Googleに何をするかについてのヘルプやヒントをいただければ幸いです。

4

5 に答える 5

5

意思決定モデルを定義して、そのモデルのパラメーターを最適化することができると思います。多段階の意思決定モデルも作成できます。私はかつて、動的ダイヤルアライド問題 (論文はこちら) を 2 段階の線形決定問題としてモデル化することで、同様のことを行いました。例を挙げると、次のことができます。

  1. それぞれのフィギュアについて、次に移動するフィギュアを決定します。各フィギュアは、ボード上のその位置から派生​​した特定の機能によって特徴付けられます。たとえば、スコアを作成する能力、危険、他のフィギュアを保護する能力などです。これらの各機能を (たとえば、線形モデルで、ニューラル ネットワークを介して、シンボリック式ツリー、デシジョン ツリーを介して ...) 組み合わせることができ、次にどの図を使用するかのランクを与えることができます。

  2. 選んだフィギュアで演技。繰り返しますが、実行できるアクションには特定の数があり、それぞれに特定の機能があります。繰り返しますが、それらを組み合わせてランク付けすると、1 つのアクションが最も優先度が高くなります。これは、実行するために選択したものです。

抽出する機能は、非常に単純なものでも非常に複雑なものでもかまいません。それは、何が最も効果的であるかと、計算にどれだけの時間がかかるかによって異なります。

決定モデルの品質を評価して改善するには、対戦相手とのいくつかのゲームでこれらの決定をシミュレートし、これらの機能を組み合わせて動きをランク付けするモデルのパラメーターをトレーニングします (たとえば、GA を使用)。このようにして、指定された対戦相手に対してできるだけ多くのゲームに勝つようにモデルを調整します。これまで見たことのない対戦相手と対戦することで、そのモデルの一般性をテストできます。

Mathew Hall が言ったように、これには GP を使用できますが (モデルが複雑なルールの場合)、これはモデルの 1 種類にすぎません。私の場合、重みの線形結合は非常にうまくいきました。

ところで、興味があれば、GA や GP などを提供するヒューリスティック最適化に関するソフトウェアも用意しています。それはHeuristicLabと呼ばれます。これは GPL でオープン ソースですが、GUI (Windows) が付属しています。外部プログラムでフィットネス関数を評価する方法 (プロトコル バッファーを使用したデータ交換) についてのハウツーがいくつかあるので、シミュレーションと意思決定モデルに取り組み、HeuristicLab にあるアルゴリズムにパラメーターを最適化させることができます。

于 2012-01-04T11:51:32.220 に答える
4

ヴィンセント、

まず、愚かではありません。あなたは（私が推測するように）基本的なコンピュータサイエンスを3年間勉強しています。今、あなたはそれらの基本的な技術をかなり専門的なものに適用しています-狭い分野（人工知能）の特定のアプリケーション（Stratego）。

次に、アドバイザーがStrategoのルールを完全に理解していることを確認してください。ストラテゴは、チェスよりも多くの駒（およびより多くの種類の駒）を備えた、より大きなボードでプレイされます。これにより、法的な立場のスペースが大幅に拡大し、法的な動きのスペースが大幅に拡大します。それは隠された情報のゲームでもあり、難易度をさらに高めます。アドバイザーは、プロジェクトの範囲を制限したい場合があります。たとえば、完全に観察されたバリアントに集中することができます。ピースの動きが少し簡単なことを除けば、なぜこれが簡単だと思うのかわかりません。

第三に、最初に行うべき正しいことは、AIの分野でゲームが一般的にどのように扱われるかを調べることだと思います。ラッセルとノーヴィグの第3章（一般的な背景用）と第5章（二人ゲーム用）は非常にアクセスしやすく、よく書かれています。2つの基本的なアイデアが表示されます。1つは、基本的にツリーで大規模な検索を実行して勝利を探していること、2つは、重要なゲームではツリーが大きすぎるため、特定のゲームを検索することです。深さを確認してから、「ボード評価関数」を使用して、そのうちの1つを探します。あなたの3番目の箇条書きはこの静脈にあると思います。

ボード評価関数は魔法であり、おそらく遺伝的アルゴリズムまたは遺伝的プログラムのいずれかを使用するための良い候補であり、どちらもニューラルネットワークと組み合わせて使用​​される可能性があります。基本的な考え方は、ボードの位置を入力として受け取り、単一の数値を出力する関数を設計（または実際には進化）しようとしているということです。大きい数字は強い位置に対応し、小さい数字は弱い位置に対応します。チェッカーのゲームでこれを行う方法を示す、ChellapillaとFogelによる有名な論文があります。

http://library.natural-selection.com/Library/1999/Evolveing_NN_Checkers.pdf

これは素晴らしい論文だと思います。敵対的検索、遺伝的アルゴリズム、ニューラルネットワークというAIの3つの優れた要素を結び付けています。ボードを表現する方法、ボードの評価について考える方法などについて、いくつかのインスピレーションを得ることができます。

ただし、あなたがやろうとしていることは、ChellapillaやFogelの仕事よりもかなり複雑であることに注意してください。それは大丈夫です-結局のところ、それは13年後です、そしてあなたはしばらくの間これにいるでしょう。AIプレーヤーは対戦相手の状態について不完全な知識を持っているため、ボードの表現にはまだ問題があります。最初は位置以外は何も知られていませんが、最終的には競合がなくなると、一階述語論理または関連する手法を使用して個々の部分を絞り込み、場合によっては確率的手法を使用してセット全体に関する情報を推測することができます。（これらのいくつかは、学部生のプロジェクトの範囲を超えている可能性があります。）

于 2012-01-04T20:26:04.597 に答える
2

実際の戦略の表現を考え出すのに問題があるという事実は、それほど驚くべきことではありません。実際、それはあなたが試みていることの中で最も難しい部分であると私は主張します. 残念ながら、Stratego のことは聞いたことがありません。

問題は、チェスの戦略がかなり複雑なことです。GAのボード位置間の多くの遷移を含む回答で提案しますが、チェスボードには宇宙の原子の数よりも多くの可能な位置があり、これは明らかにうまく機能しません。あなたがする必要がある可能性が高いのは、ボードの位置を取り、移動を開始する何かに関連付けられている一連の重み/パラメーターを GA でエンコードすることです。これは、2 番目の提案で示唆していることだと思います。

おそらく最も簡単な提案は、ニューラル ネットワークのような一般的な関数近似を使用することです。パーセプトロンまたは放射基底関数が 2 つの可能性です。さまざまなノードの重みを GA にエンコードできますが、ニューラル ネットワークをトレーニングするためのかなり適切な方法は他にもあります。バックプロパゲーションを参照してください。代わりにネットワーク構造をエンコードすることもできますが、これには、遺伝的アルゴリズムを使用してニューラル ネットワークを開発するためにかなりの量の研究が行われていると確信しているため、完全にゼロから始めることはないという利点もあります。

ボードをニューラル ネットワークに提示し、その結果を解釈する方法を考え出す必要があります。特にチェスでは、多くの動きが不正になることに注意する必要があります。ボードをエンコードし、結果を解釈して、正当な動きのみが提示されるようにできれば、非常に有益です。システムの仕組みを実装してから、さまざまなボード表現で遊んで、何が良い結果をもたらすかを確認することをお勧めします。あなたが始めるための頭の中で考えられるいくつかのアイデアは次のとおりです。

  • 64 個のすべての正方形が次々に表示されるビット文字列で、各正方形に何が存在するかを示す数字が表示されます。最も明白ですが、違法な動きを除外するには多くの作業が必要になるため、おそらくかなり悪い表現です。
  • 64 個のすべての正方形が次々に表示されるビット文字列で、各正方形に移動できるものを表す数字が表示されます。これには、駒でボードをできるだけ多くカバーするチェスのカバー コンセプトを具現化するという利点がありますが、違法な動きや味方/敵の駒の扱いにはまだ問題があります。
  • 32 個すべてのピースが次々と並べられたビット列で、各マスにあるそのピースの位置を示す番号が付けられています。

一般に、チェスは最初はかなり複雑なゲームであると思いますが、ランダムよりもはるかに優れた標準的なゲームをプレイするのはかなり難しいと思います。Stratego がシンプルかどうかはわかりませんが、かなりシンプルなゲームを選ぶことを強くお勧めします。これにより、実装の仕組みを正しく理解し、ゲームの状態を表現することに集中できます。

とにかく、それがあなたの助けになることを願っています。

編集:簡単な追加として、標準的なチェスの AI がどのように機能するかを調べる価値があります。ほとんどの場合、ある種のMinimax システムが使用されていると思います。

于 2012-01-04T11:14:17.773 に答える
1

「戦術」とは、ゲームをプレイするための一般的なアルゴリズムをGAに提供させたい（つまり、AIを進化させる）ことを意味しますか、それともゲームがGAを使用して可能な動きの空間を検索して各ターンで移動しますか？

前者をやりたい場合は、遺伝的プログラミング（GP）の使用を検討してください。これを使用して、固定ツリーサイズで可能な限り最高のAIを生成することができます。JGAPにはすでにGPもサポートされています。この例については、 JGAPRobocodeの例を参照してください。このアプローチは、Stratego AIにドメイン固有言語が必要であることを意味するため、ボードとピースをどのように公開するかを慎重に検討する必要があります。

GPを使用するということは、事前にプログラムされた一定数のゲームでAIがどれだけうまく機能するかということを意味しますが、それには、優れたAIプレーヤー（または非常に忍耐強い人間）が必要です。

于 2012-01-04T11:35:15.813 に答える
0

@DonAndreの答えは、動きに対して絶対に正しいです。一般に、状態ベースの決定を含む問題は、GA でモデル化するのが難しく、何らかの形式の GP (明示的または @DonAndre が示唆するように、本質的に宣言型プログラムであるツリー) を必要とします。

一般的なストラテゴ プレーヤーは非常に難しいように思えますが、合理的なストラテゴ プレイ プログラムがある場合、「ストラテゴ ボードのセットアップ」は GA の優れた問題です。ピースの最初の位置が表現型になり、外部の Stratego 再生コードの結果が適合度になります。ランダムなセットアップは、いくつかの「良いアイデア」を持つセットアップよりも不利であり、小さな「良いアイデア」を組み合わせてフィッター アンド フィッター セットアップにすることができる可能性が直感的にあります。

...

決定木とは何かという一般的な問題について、単純な例を考え出そうとしても、十分に小さい例を思いつくのに苦労し続けましたが、同じランクのオブジェクトを攻撃するかどうかを評価している場合は、ピース (IIRC はあなたと他のピースの両方を破壊しますか?):

double locationNeed = aVeryComplexDecisionTree();
if(thatRank == thisRank){
   double sacrificeWillingness = SACRIFICE_GENETIC_BASE; //Assume range 0.0 - 1.0
   double sacrificeNeed = anotherComplexTree(); //0.0 - 1.0
   double sacrificeInContext = sacrificeNeed * SACRIFICE_NEED_GENETIC_DISCOUNT; //0.0 - 1.0  
   if(sacrificeInContext > sacrificeNeed){
      ...OK, this piece is "willing" to sacrifice itself

いずれにせよ、基本的な考え方は、ストラテゴプレイのコーディングがまだたくさんあり、結果を変えるパラメーターを挿入できる場所を探しているだけだということです。ここで私は、自分自身を犠牲にする「基本的な」気質（おそらく一般的な作品ではより高い）と、作品が犠牲の必要性を「受け入れるか拒否する」かを重み付けする「割引」の遺伝的に決定されたパラメーターのアイデアを思いつきました。

于 2012-01-04T20:00:15.860 に答える