Clever Geek Handbook

ミニAIカップ＃3：トップボットの作成







初秋に、ボットのミニAIカップ＃3 （別名Mad Cars）を作成するためのコンテストが完了し、参加者は車で戦わなければなりませんでした。 参加者は何がうまくいくか、何がうまくいかないかについて多くのことを議論しました。アイデアは単純なifからニューラルネットワークのトレーニングまで表現され、テストされましたが、いわゆる「シミュレーション」を持つ人がトップを占めました。 それが何であるかを理解し、1位、3位、および4位のソリューションを比較して、他の可能なソリューションについて議論してみましょう。







免責事項



この記事はAlexei Dichkovsky（Commandos）およびVladimir Kiselev（Valdemar）と共同執筆しました。







受賞者の決定について読みたいだけの人には、「シミュレーション」の項目からすぐに始めることをお勧めします。







問題の声明



今回、世界のメカニズムはDrive Aheadモバイルゲームに非常に似ていました。プレーヤーにはボタンが付いた車が与えられました。 タスクは敵のボタンを彼がするよりも速く押すことです。 600ティックで誰も勝てない場合、カードはゴミの山に突入し始め、ボタンを押すこともできます。 つまり、ボタンを敵、周囲の世界、ゴミの山から守る必要があります（必須）。 各プレイヤーに5回のライフが与えられ、ゲームは5から9ラウンドになりましたが、誰かがライフを終了することはありませんでした。 各ラウンドは、両方の参加者に同じランダムなマップと車で開催されました。 合計で6種類のカードと3種類の車があり、合計18種類の組み合わせがありました。







各ラウンドはティックに分割されます。 ティックは、チェスのように1つの動きです。 唯一の違いは、両方のプレーヤーが同時に行くことです。 全員が交代する競技会があります。または、数回移動するたびにアクションを実行し、フレームでユニットを強調表示することができます。

ボットへの各ティックには平和状態があり、3つのアクションを実行する機会が与えられます：



、



、



。 これらのアクションは、車をいずれかの方向に移動させ、同時に地球の車輪に触れない場合、身体全体に少し回転を与えます（アーケード物理学の少し）。 両方の対戦相手がアクションを選択すると、ゲームワールドのシミュレーションが開始され、新しい状態が考慮されてプレーヤーに送信されます。 誰かがボタンをクリックすると、ラウンドは終了し、次のラウンドが始まります。 すべてがシンプルですが、ニュアンスがあります。







より完全なルールはこちらにあります 。 そして、 ここで決勝戦を参照してください 。







一般的なソリューションの説明



ほとんどのボット作成競技は非常によく似ています：ダニの数には限りがあり（1ラウンドで最大約1,500個あります）、可能なアクションの数には限りがあります。そのようなアクションのシーケンスを選択して、対戦相手よりも優れている必要があります。 少し後で、より良いことの意味に戻りますが、今のところ、主な問題に対処する方法を考えます。膨大な数のオプション：最初は1つの初期状態があり、その後、各マシンは3つの異なる方法で移動できます。は2台の車に9種類の組み合わせを提供します。1500番目の動きまでに9 ^ 1500種類の組み合わせになります...これは、宇宙の存在中にそれらを整理することを計画している場合よりも少し多くなります。







ここで、 シミュレーションとは何かについて説明します 。 これは、ある種のアルゴリズムではなく、ゲームのルールを十分または完全な精度で再現し、ソリューションをソートできるようにすることです。 もちろん、すべてのソリューションを検討するのではなく、その一部のみを検討します。 これには検索アルゴリズムが使用されます-ゲームの状態ツリーでは、私たちにとって最適なものを探しています。 多くのアルゴリズム（ミニマックスからMCTSまで）があり、それぞれに独自のニュアンスがあります。 過去のAIコンテストの参加者が書いた決定に精通することをお勧めします。 これにより、アルゴリズムが機能する条件とそうでない条件の基本的な理解が得られます。 特別なリポジトリには、このための多くのリンクがあります 。







アルゴリズムを選択するときは、次のことを考慮する必要があります。









この競技では、1ティックで約10〜13ミリ秒（ゲーム全体で2分）が与えられました。 この間、ボットはデータを読み取り、決定を下し、移動するコマンドを送信する必要がありました。 これは約500-1000の動きを刺激するのに十分でした。 すべての状態で繰り返します。 最も単純な検索アルゴリズムは、「50ティックが左に行く」、「50ティックが右に行く」、「50ティックがクリックストップ」の3つの移動オプションの比較のように見える場合があります。 そして、どんなに単純に聞こえても、勝者の決定からそれほど遠くない。







なぜなら 50の移動だけをカウントします。ほとんどの場合、ゲームの終了までカウントされません。その後、世界の状態がどれだけ良いか悪いかを評価する関数が必要です。 ほとんどの場合、それはヒューリスティックに基づいて構築され、勝利に重要なものを理解します。 たとえば、2014年のロシアAIカップ大会にはレースがありましたが、最後に到着した場合、ボーナスポイントを獲得すれば勝つことができます。 これは、評価関数が高速道路での高速移動に加えてポイントの収集も刺激する必要があることを意味します。 スコアは、シミュレーションの最後の状態（50ティック後）でのみ、または中間状態の推定値の合計として計算できます。 多くの場合、推定値は時間とともに「フェード」し、それにより、より早く発生する状態がより影響を受けます。 なぜなら 敵を確実に予測することはできません。そうすれば、将来の選択肢が生じる可能性は低くなり、それらに大きく依存することはありません。 また、この手法により、ボットはタスクをより速く完了し、後ですべてを延期することはありません。 しかし、ボットはその後の利益のためにリスクを軽減することに注意する価値があります。







私たちは自分の行動に応じて世界の状態を予測するので、何らかの形で敵の行動をモデル化する必要があります。 複雑なことはなく、一般的なオプションがいくつかあります。









上記の手順をすべて実装すると、特に優れた評価関数を選択できる場合は、非常に優れたボットが得られる可能性が高くなります。 しかし、彼の戦いを通して見ると、特定の状況で彼が奇妙に振る舞うことに気付くことができます。 これらの状況の評価関数を修正することは困難な場合があります。または、別のロジックを壊すリスクが高くなります。 ここで松葉杖とifsが助けになります。 はい、競技の最後の日は、特定の条件で欠陥を修正するために、松葉杖とifを書くことになります。 個人的には、私はこの部分が本当に好きではありませんが、トップ10の場所の配置に影響を与える可能性があるのは決勝戦で松葉杖であることに何度も気付きました。つまり、書かれていないifが賞金を払う可能性があることを意味します美しいアルゴリズムとソリューションも大好きです）。







Q：シミュレーションなしで実行することは可能ですか？

A：はい、ヒューリスティック（意思決定ツリー、多数のifなど）の決定を使用できます。 ヒューリスティックに関するAIアーキテクチャに関する優れた記事があります。







Q：ヒューリスティックアプローチよりもシミュレーションの使用の方がどれくらい優れていますか？

A：すべてはタスクに依存します。 たとえば、ここでは、カードと車のいくつかの組み合わせをifsでハードコーディングし、常に勝つ（または引く）ことができます。 ただし、シミュレーションでは、自分で考えるのが難しい、またはヒューリスティックを実装するのが難しいソリューションが見つかることがよくあります。 このコンテストでは、別の車を裏返すと、シミュレーションのソリューションが敵の車輪にホイールを置きます。これにより、「空中」のフラグがオフになります。つまり、敵は体の回転を適用できず、車輪を戻すことができません。 しかし、この決定はこの意味を考慮していませんでした。敵が屋根の上でより速く落ちてボタンを押すオプションを見つけました。













Q：ニューラルネットワークとRL？

A：これがどれほど人気が​​あったとしても、ボット競技では、そのような決定はめったに現れません。 ニューラルネットワークはシミュレーションを必要としませんが、なぜなら 現在の状態の入力パラメーターに基づいてアクションを発行するだけで、まだ何かを学ぶ必要があります。そのため、多くの場合、ローカルで何千ものゲームを駆動するシミュレーターを作成する必要があります。 個人的には、彼らには可能性があると信じています。 おそらく、彼らは問題の一部を解決したり、非常に限られた応答時間の条件でそれを使用することができます。







ご注意

限られた数の可能なアクションに関して、いくつかのパラメーターを「スムーズに」調整できる場合があることを明確にする価値があります。 たとえば、単に前進するだけでなく、ある程度のパワーで前進します。 この場合、結論の数の「有限性」は、いくつかの値、たとえば0％、25％、50％、75％、100％を使用するだけで簡単に達成できます。 ほとんどの場合、「完全にオン」と「完全にオフ」の2つだけで十分です。







シミュレーション



このコンテストでは、既製のシマリス物理エンジンを使用しました。 主催者の期待は、彼が年をとっており、実績があり、多くのラッパーがいるため、誰もがそれを決定に含めることができるということです...







厳しい現実では、エンジンは毎回異なる値を生成したため、動きのオプションを計算するためにエンジンを再起動することは困難でした。 この問題は「正面から」解決されました-メモリアロケータがCで記述され、世界の状態のメモリが完全にコピーされました。 このようなアロケーターは、C ++以外の言語でソリューションを作成する機能に終止符を打ちました（実際、可能ですが、非常に面倒であり、アロケーターはCで作成する必要があります）。 さらに、予測の精度は、ゲームワールドに要素を追加する順序の影響を受けました。これには、ゲームの計算にオーガナイザーが使用したコードの非常に正確なコピーが必要でした。 しかし、彼はすでにPythonを使用していました。 他のプログラミング言語のcoの最後のハイライトは、エンジンが古く、物理シミュレーションの独自のトリミングバージョンを取得するために競争中に正確に再現できない多くの最適化が含まれていることです。







その結果、すべての参加者に動きをシミュレートするための平等な条件を与えるはずだったエンジンが、このための最も困難な障害になりました。 リーダーボードの最初の7つの場所は、正確なシミュレーションを行った人だけが撮影したもので、このような競技会での重要性を示す証拠となります。







シマリスの内部に入り、その状態のコピーを最適化することができた2、3の参加者を除いて、残りはほぼ同等のパフォーマンスのシミュレーションを行いました（これは、競合が決定アルゴリズムのためであり、 「動きをもっと数える人」）。







相手の検索アルゴリズムと予測



この時点から、ソリューションの個別の説明が開始されます。 アルゴリズムはその作者に代わって説明されます。







ウラジミール・キセレフ（バルデマール）4位



ソリューション空間の検索には、ランダム検索（モンテカルロ）が使用されました。 アルゴリズムは次のとおりです。







  1. ランダムなデータ-ゲノム-60ティックのアクション（左、右、停止）のシーケンスを初期化します。
  2. 見つかった最高のゲノムを取得する
  3. いずれかのアクションをランダムに変更します
  4. 評価関数を使用して、新しいゲノムがどれだけ優れているかの指標である数値を取得します
  5. より良い解決策が得られたら、最適な解決策を更新してください。
  6. ステップ2から繰り返します


私のシミュレーターは、1秒間に平均で約12ミリ秒あることを考慮して、1秒で100,000の世界のシミュレーションを作成しました。 つまり、1ティックで、約20回フルサイクルを実行できます。







最適なソリューションを見つけるには、この反復回数では明らかに不十分でした。 したがって、「ストレッチ」アクションのアイデアが実現しました。60の動きのゲノムの代わりに、12の「ストレッチ」の動きのチェーンで動作します-各アクションは5ティック連続して続くと信じています。

さらに：ゲノムの長さを短くすることで突然変異の質を改善し、シミュレーションを5ティックごとに実行し、20ではなく100のゲノムをチェックすることもできます（制限時間の低下を避けるため、最終的に70で停止しました）。

少ない：ストレッチアクションは、最適なソリューションにならない可能性があります（たとえば、安定したラックではなく、バンパーを振る）







アルゴリズムの品質を大幅に改善した手法に注意する必要があります。









競技中、彼はローカル開発用のツールを積極的に使用しました。これにより、バグをすばやく見つけ、戦略の弱点に集中することができました。









mortido：

5ティックごとにカウントすることは、特に敵が予測したオプションから遠く離れている場合は危険です。 一方、このゲームの世界では5ティックの間、あまり起きませんでした。

また、私の決定では、ティックごとにランダムな組み合わせを追加しましたが、これが決定にどのように影響したかについては正確には言いません。



コマンド：

このような数のシミュレーションでいくつかのアクションを変更しても、1つのアクションで発生する変更はほとんどないため、あまり意味がありません。 しかし、1つのアクションを5ティックの意味に引き伸ばすと、さらに多くのように見えます。

また、アイデア自体も好きではありません。最初に最適なセットを使用して、どこかで編集しようとします。 最初の目盛りを変更すると、後続の目盛りが少なくとも比較的適切なままになるというのは非論理的なようです。


アレクサンダー・キセレフ（mortido）3位



他のコンテストの勝者による記事を武器に、遺伝的アルゴリズムを使用することにしました。 しかし、ランダム検索またはアニーリングの模倣に似たものが判明しましたが、それについては後で詳しく説明します。







ソリューションを40個の数字の配列でエンコードします。-1、0、および1は、



、



および



動きに対応します。







各ラウンドの開始時に、ゲーム全体にすでに費やした時間を数え、さらに残りのラウンド数に基づいて新しい制限時間を数え、各ラウンドが1200ティックであると想定しました。 T.O. 最初は、1ターンあたり11ミリ秒以下を費やそうとしましたが、前のラウンドが1200ティックよりも速い場合、最後に少し歩き回ることができました。







バルデマール：

興味深いことに、このチップはゲームを悪化させました。 最初に11より20〜30ミリ秒を費やす方が常に良いことがわかり、最後に60

この時間の3分の1で、敵の最高の動きを探していましたが、残りは自分の決定を計算することになりました。 敵の動きを検索するとき、私の行動は、最後の動きから1ティックシフトしたものとして最高のものとしてモデル化されました。 つまり まるで最後のティックで作成された計画に従って行動し続けているように、彼は私に抵抗しようとしています。







ソリューション自体の検索は、それ自体と対戦相手の両方で同じでした：







  1. 私たちは最後の動きから決定を取り、それを1つの動きでシフトします（すでに行っています）
  2. すべてを満たすまでランダム解の母集団に証明する
  3. すべての決定をシミュレートし、評価関数を使用して適合度を設定します。 最高を覚えています。
  4. 計算の時間がありますが

    1. ヒント、常に現在の最適解の1つの突然変異を母集団に追加し、それがより良い場合はそれを覚えておいてください
    2. 新しい人口に場所があり、計算の時間が超過していない限り（人口のある階に行くことができます）

      1. 私たちは2人の異なる個人を取り、最高のフィットネスで出発します-ママ
      2. 私たちは2人の異なる個人を連れて、最高のフィットネスで去ります-お父さん（お母さんと一致しないはずです）
      3. それらを渡ります
      4. RND <



        場合にRND <



      5. ソリューションをシミュレートし、それが最良の場合はそれを記憶します


その結果、最適と見なされる一連のアクションを返します。 最初の動きはボットアクションとして送信されます。 残念ながら、私の計画には重大な欠陥がありました。 ティックで実行できるシミュレーションの数は非常に少なく（長い評価機能によるものを含む）、競争サーバーでは4ポイントが1回しか実行されず、敵に対してはまったく実行されませんでした。 これにより、アルゴリズムはランダム検索またはシミュレートされたアニーリングのようになりました（ソリューションを最後の動きから1回変異させることができたため）。 何かを変えるにはもう手遅れだったので、なんとか3位をキープしました。







初期ランダム解の交差、突然変異、生成のためのアルゴリズムを実装することが重要です。 どの決定がテストされるかに依存し、完全にランダムな決定は、一見すると思われるほど良くありません（それは動作しますが、より多くのオプションが必要です）。







最終バージョンでは、セグメント内でランダムな決定が生成されましたが、「ジャーク」ソリューションは1か所で除外されました。







  1. ランダムチームが選択されました
  2. ソリューションの長さ全体（40移動）

    1. 現在のコマンドをセルに書き込みます
    2. 10％の確率で、現在のチームをランダムに変更します


同様のテクノロジーによると、突然変異も発生しました。ソリューションのランダムセグメントがランダムコマンドに置き換えられました。 交差は、1人の親から決定が行われたポイントを選択することによって行われ、2番目から決定されました。







最善の解決策を見つけるために、私たちができる限りの時間を費やすことが好きでした。 ソリューションが最良ではない場合、それは大したことではありません-次のティックでそれを改善することができます 最適化はやがて「ぼやけ」ます。 , . , - , . ,







Valdemar:

1 , , .



Commandos:

— - .

— , . , … , . " ”. -.


(Commandos) 1



( ), n m . 3^2=9 . m + n 40 .







: 







 |----------- n  -----------|---------- m  --------| |   ...   |   ...   |


: , , . ( ).







n m , . , .







:







  1. , ( , ):

    • , , , .
    • , , . . . , , , .
    • . ; ( ).
  2. n m . , .1, , . - ( ) , — , ;
  3. . , — . , ( ).


Valdemar:

, 2 . . , .



mortido:

わあ！ , . . , 2 , 40-60 . , 3 .

n + m == const ?

. n + m != const



, . , . - .









(Valdemar) 4



, . , ( , , ..) [0..1].

. : , .

, , : , .







, :









, 2 , .







.







:









mortido:

, .. , .



Commandos:

, . -


(mortido) 3



, chipmunk. . , , , , . .







3 .







, ( , , ):









, , (, , )







Valdemar:

. , “ , , ” , ( ..) .

, , . .







Commandos:

, , “”… ? , “” .


(Commandos) 1



SquaredWheelsBuggy



, .. , . Buggy , , ( /).

簡単に：







  1. ;
  2. ; — , , 1 0; .. ;
  3. . ; 10 ( );
  4. ( , );
  5. (, );
  6. — - , ;
  7. / ; , — ; .


1-5 , . 2 “ ”.







Valdemar:

, . , .



mortido:

, 10 .


IF'



(Valdemar) 4



, if'. 3 , , . , , -.

: , “” — , - , ( , ) — .







:









, : . , , if' .







mortido:

, . .



Commandos:

if'. , , … , , .


(mortido) 3



- .







3 . . . “”, . , , .







, “” . . , , , - . . , , .. .







, , , , , . … . - — , ( , ).







Valdemar:

, . . “” , if'. , — .

, + . , .







Commandos:

… , - — , , . , , .


(Commandos) 1



. (, , ). ( ) /.







pill carcass map , , ( ). island map, , .







island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .







(Pill map, Bus) , ( / 100% ).







pill hubble map. , ( ), . .







— , ...







, . , . ( ).







Valdemar:

, — . , .



mortido:

, “” .


感情



Valdemar:

. , . ( ) .

. “”, , , , :)

, mailru , .



mortido:

: , … , , ( ). , 3 , , … .



Commandos:

- , . , , , . … . — , .

— ++. . , . 1 -.


だから



, . , . , , .







Mail.Ru Group .







ボーナス



Valdemar

mortido







,











































More articles:


All Articles