Geekly Articles each Day

ミニ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


,







Source: https://habr.com/ru/post/J430466/

More articles:


All Articles