まず、このテキストは、このコンテストの勝者のトピックに関する解説として書かれました。 しかし、最終的には、テキストのボリュームが非常に大きくなり、別のトピックとして割り当てることにしました。 そのため、読者は競争に気づいており、勝者のトピックを読んでいると想定されています。 30位の物語も読むことができます。
すぐにソースコードリポジトリへのリンクを提供します。ソースコード自体に加えて、コミットの全履歴があります。 たとえば、「スリープする時間です」というコメントでコミットが行われた時間は興味深いように見えるかもしれません。
一般的に、ほとんどのリーダーは最終戦略に対してほぼ同じ基本的なアイデアを持っていると感じていました。
- ウェイポイント間のマップパスを見つける
- 運動、衝突、その他の物理学のシミュレーション
- 現在の位置から未来への異なる軌道につながるさまざまなアクションの列挙
- 評価関数に基づいて最適なアクションまたは軌道を選択する
したがって、このトピックでは、これらのアイデアが私の場合にどのように実装されたかについてもう少し詳しく説明します。
道を探す
思ったよりも少し広くパスを見つける作業を検討しました。 このようなデータ構造とアルゴリズムを作成して、次の形式の質問に対する答えをすぐに見つけられるようにしました：「ポイントX、Yおよび次のウェイポイントNにいる場合、次のウェイポイントまであとどれくらい残っていますか？」 この要件は、受信した軌跡を評価する1つの決定の間に、そのような要求が「バスター」から数千回送信されるという事実から生じました。
最初のバージョンは、XYポイントが次のウェイポイントに到達する任意のセルからパスを検索するだけで機能し、パスの長さを回答として返しました。 同時に、セル内のXYポイントの相対位置にも一定のボーナスが与えられ、評価が連続評価に少し似たものになりました。
2回目のラウンドのどこかで、セルを通るパスのこのような単純な検索に問題があった場所にカードが現れ始めました。 例：
-どちら側でウェイポイントにアプローチしますか？
-ウェイポイントを取得するときに、直進して、ほとんど損失なしで小さな迂回を行うことができる場合、自動車は次のウェイポイントに戻ろうとしないことをどのように確認しますか？
-反転の反転を考慮してパス検索を行う方法は？
その結果、データ構造とクエリ自体を変更するというアイデアが浮上しました：「ポイントX、Y、 角度A 、次のウェイポイントNにいる場合、どれだけの量を完了できるか？」
このような要求に応答するには、グラフデバイスを作成する必要があり、それに沿ってパスが検索されます。 結果は次のとおりです。
-グラフノードは「方向のあるセル」です。サイズが400x400のセルで、8つの方向（45度単位）があります。
-このようなノードには6個の隣接ノードがありました。1個の隣接ノード-まっすぐ進む、2個の隣接ノード-まっすぐ進む、1個の隣接ノード-戻る、2個の隣接ノード-順番に戻ります。
-エッジの長さは、それぞれ、直接移動の場合は1、対角線の場合はsqrt（2）、逆の場合は他の定数を乗算しました。 最終バージョンでは、この定数は15でした。この値は、車が非常に長く後退せず、できるだけ早く向きを変えないように手で選択されましたが、同時に、現在の車の後ろの数タイルのあらゆる種類の馬鹿げたウェイポイントを取ることができました。
-「サブセル」400x400のレベルで不要な隣接セルを生成しないように、「大きな」800x400セルから壁を数えます。
そのような方法の検索には多くのバグがありました。 特に、要求ポイントからではなく、フィニッシュラインからパス自体が検索されたためです。 つまり、「ポイント0、0で、角度が0で、次のウェイポイントが1である場合」と尋ねられた場合、最初にフィニッシュライン（0番目のウェイポイント）から前のウェイポイント（N-1番目のウェイポイント）までの距離を見つける必要がありました、その後、前のウェイポイントから最初のウェイポイントへのパスを再帰的に見つけてから、最初のウェイポイントからリクエストポイントへのパスを探します。 このような検索は「終了」から「開始」まで行われたため、ノードの近隣の定義には多くの混乱がありました。近隣の方向を判断することは特に困難でした。
上記は、方向が90度の倍数であるノードの近傍の例です。 「対角線」方向の隣人は少し異なって見えますが、本質は同じです。
ファイナルに近づくと、そのようなメカニズムをデバッグすることができ、未知のマップでは車はかなり興味深い方法を選択したため、正しい順序で最小の後退ギアでウェイポイントを回ることができました。 同時に、最初はリバースギアのペナルティはそれほど高くなく、干渉がない場合、そのような決定はさらに速くなりました。 しかし、フィナーレでは、「問題のある」ウェイポイントには常にダンプとカオスがありました。そのため、速度を落として迂回することなく、そのようなウェイポイントをスキップする方がよいでしょう。これにより、ウェイポイントでのフリーマーケットが回避され、途中でボーナスが増えます。 また、軌道自体は車のあるポイントから得られた経路をたどる必要はないことを理解する必要があります。主なことは、最適な軌道が「フィニッシュラインに最も近い」ポイントにつながることです。
ここでどうにかして、それは自動車の現在のポイントから未来への「最良の方法」のように見えました。 あなたは、車がウェイポイントに「貪欲に」すぐに曲がるのではなく、その後ろから電話することにしたことに気付くかもしれません。
パス検索アルゴリズム自体は、すべてのパスが要求時に読み取られてキャッシュされるダイクストラアルゴリズムの遅延実装でした。 最後に、新しい未知のセルが開かれた場合、キャッシュが時々フラッシュされました。
ソースコード-クラスCWaypointsDistanceMapを参照
シミュレーション
当初、物理学は次のメカニズムの形式でのみ機能しました。「マシン」+「アクション」が入力に供給され、出力が「次のティック上の車」でした。 シミュレーションコード自体は、Mr.Smileからのフォーラムでのメッセージから正直に借用され、将来的に適応され、壁との衝突に対する最も単純なチェックを追加しました。この場合、検索は単に停止しました。 次に、ブレーキ、ニトロ、オイルの正しい計算がこのコードにゆっくりとねじ込まれました。 最終的に、衝突を正しく計算する必要が生じました。なぜなら、 いくつかのターンは、衝突なしの場合よりも衝突した場合の方が収益性が高かった。 特に最初は失敗したポジションで。
一般に、第2ラウンドの終わり頃に、notreal2dからコリジョンコードを見つけ出し、ほぼ絶対的な精度を達成し、さらにコードを単純化することもできました。結局、notreal2dはエンジンとしては「一般的」で、直線の垂直線または水平線、半径80の円、および凹状のアーチ。 凹状のアーチでは、スコアリングすることに決めました。 それらのコードは、安定して正確に動作するようにデバッグできませんでした。
しかし、世界のすべてのオブジェクト（すべての車、シェルなど）を同時にシミュレートするという考えも頭から離れませんでした。 最終的に、あるマシンのシミュレーターは「世界」のシミュレーターになりました。 彼は入り口で「平和」+「すべての車の行動」を与えられ、出口で「次のチックの平和」が出てきました。 敵車の行動は「床の上の滑り台」であると想定されていました。
このようなシミュレータの実装とデバッグには、おそらくほとんどの時間がかかりました。 摩擦係数は手動で選択され、衝突の検索および解決コードはnotreal2dからコピーおよびコピーされ、最終的に、衝突の検索は最適化のために手動で作成されました。 壁の「端」との衝突に関連した膨大な数のバグがありました-最後に、私は壁の端を取り除きました。 また、マシン同士の衝突やタイヤとの衝突を慎重にデバッグする必要がありました。 そして、ボーナスとの衝突は正しく書かれていませんでした。 VS 2015に組み込まれたプロファイラーによって、速度の多くの弱点が助けられました-彼に感謝します。
ソースコード-CWorldSimulatorクラスを参照してください。
選別機
santa324がしたことと比較すると、バスターが私の戦略の最も弱い点だったと言えます。 本質的に新しい何かをするためのアイデアがありました：遺伝的アルゴリズム、または「変異」ツリー、または他の何かが、強さが残っていませんでした。
一般的に、最終的に使用された並べ替えツールの主なアイデアは、いくつかの固定されたアクションセットを並べ替えることによって軌跡を検索することでした。 例：
- ブレーキ付き/ブレーキなしの0/7/15/40/60ティックを左/右にストレートで走行
- 次に、まっすぐ/左/右0/40ティックに進みます
- その後、再び直進/左/右0/40ティック
- 最後のステップとして、検索深度の最後までまっすぐ進みます
最初のバージョンの1つは1ターンと1ブレーキのみを整理することができましたが、これは「ターンから離れてから、大きな半径でターンに入る」またはドリフトなどの操作を実行するには不十分でした。 最終的に、上記の構造は3ターン/ブレーキと、探索深度の最後までの乗車（150ティックに等しい）で選択されました。 しかし、物理シミュレーションを衝突のない1台の車から衝突のある「全世界」のシミュレーションに変更した場合、そのような構造でさえも大幅に削減する必要がありました。 制限時間内に保つために、一部のブランチは50％の確率でオンとオフを切り替えました。 また、ランダム性を使用してアクションの長さが不鮮明になりました。
現在のティックで見つかったアクションの最適なシーケンスを次のティックでリコールするために保存し、すべてのアクションの持続時間をマイナス1で修正して再評価すると、軌道が大幅に改善されました。ランダム性のために、連続したいくつかのティックに新しい良好な軌道がなかった場合でも、多かれ少なかれ適切に操縦します。
さまざまな用語の合計が、セレクターの評価関数として機能しました。 主な用語は、「角度AでポイントXYに到達し、次のウェイポイントがNである場合、どれだけフィニッシュラインに残されますか？」です。 その後、ボーナス、水たまりへの進入、命の損失などの条件が追加されました-これにより、おそらくフィニッシュラインまでの距離の観点から最適な軌道を選択するのではなく、ボーナスを拾い、殻をかわし、水たまりを回避することができました。
また、最終的に、ニトロ/シューティング/水たまりのヒューリスティックを次のようにこの分類デバイスに移動することができました-見つかった最良の軌道について、「ニトロ/ショット/水たまりを今すぐオンにするとどうなりますか？」独自の評価。 この評価がしきい値を超えた場合、アクションが実行されました。
フィナーレ前の最後の瞬間でさえ、ピッカーに「長い後方」が追加され、現在のセルからの最良の方法が「戻る」場合に起動されました。 残念ながら、私のテストでは、このような「ロングリバース」による大幅な減速は見られませんでした。 ローカルでテストしたすべてのカードで、リバースギアは実際には使用されませんでした。 そして、それ以前のバックアップを担当したコードは、賢い男のスタイルの松葉杖のセットであり、したがって、実質的に時間を浪費しませんでした。 私が見逃した戦略時間の消費の増加は、最終カードの最初の波で時間制限の低下につながりましたが、それについては以下でさらに説明します。
評価機能の逆転と実験に多くの時間が費やされました。 結局のところ、そのような「全世界のシミュレーション」は大きな機会を提供しました。 たとえば、いくつかの実験の結果として、ジープは味方にタイヤを撃ち、より速く乗ることができました。 または、ジープの速度を特別に遅くして、ライフの1％で背後を移動している敵がジープに衝突して死亡した可能性があります。 または、開始時の車が極端な敵を押して壁に衝突しようとしたとき。 しかし、残念なことに、このような複雑な評価関数をデバッグできませんでした。 はい、すべての衝突の詳細なシミュレーションを行う余裕はありませんでした。「正直な物理学」の最終バージョンでは、最初の40ティックのみが2ポディックの精度で計算されました。 そして、衝突はすでに考慮されておらず、サブティックは1つしかありませんでした。
ジープで見つかった最適なパスと軌跡を視覚化したビデオ（残りは40ティックの軌跡を描きます）。
ソースコード-CBestMoveFinderクラスを参照
時間管理
ファイナルの最初の部分では、時間制限のために戦略が40ゲームを失いましたが、不注意のために制御できませんでした-戦略は1ティックあたり平均42msを消費し、1ティックあたり平均30msを割り当てました。 ファイナルの最初のカードの波は他のすべてのカードとは異なり、o-o-非常に遅く、ほとんどのカードは割り当てられたティックでエンドツーエンドになり、私の場合はエンドツーエンドでも失敗しました 割り当てられたプロセッサ時間が不足していました。 残りのカードでは、ほとんどの場合、割り当てられた時間より早く終了することができました。 「余裕を持って」割り当てられました。
KDPVでは、典型的なケースのスクリーンショットだけで、戦略はゴールに達しませんでした。 しかし、このゲームでは、Antmsuというあだ名で参加者からフィニッシュに追い込まれそうになりました。
だから私は
その他
今回は、戦略をテストし、物事が良くなるか悪くなるかを決定する方法が完全に不明確でした。 そのため、すべてのカードでローカルテストを実行し、サイトのインターフェースを介して最も近いライバルとのゲームを継続的に実行するための追加のスクリプトが作成されました。 さらに、結果をダウンロードして解析するための個別のスクリプト。 戦略コードもわずかに変更され、「リピーターからカードを保存する」ことが可能になりました。これはファイナルで完全にランダムでした。
notreal2dエンジン全体をクラス間で完全に書き直そうとする愚かな試みがまだありました。10時間かけてすべてが削除されました。
また、遺伝的アルゴリズムでピッカーを作り直そうとする試みもありました。この場合、遺伝子は持続時間を持つ1つのアクションです。 しかし、何か機能するものを達成することも、適切な交差操作を考え出すこともできませんでした。
少し残念ですが、MyStrategyには、マシンが長時間動かなかった場合の反転、および何らかの理由でピッカーがまったく良い軌道を見つけられなかった場合のスマートゲイスタイルの前進ギアのための松葉杖コードがありました。 ピッカーでそのような状況を正直に説明することはできませんでした。
合計
その結果、競争全体に非常に多くの時間が費やされました。 100時間以上ではなく、150時間以上です。 もちろん、このすべてがコーディング時間であるとは限りませんが、夢の中でさえ、脳は完全に動き続け、継続的に働きました。 一般的に、私は結果に満足しており、賞品を手に入れることができてとてもうれしいです。 私の以前のコンテストへの参加は2013年のみで、約30位に制限されていました。
主催者に感謝します-私の意見では、これは過去で最も壮観で、おそらく最も興味深い競技でした。 ライバルは非常に強く、彼らも「同じ場所にとどまるためにできるだけ速く走らなければなりませんでした」、彼らのおかげです。 さて、車の「運動の物理学」を以前にレイアウトしてくれたMr.Smile、ソケットの便利なビジュアライザーにJustAMan、興味深いビデオニュースにRomka、ブレインストーミングに同僚のAngorに感謝します。