ICFPC-2008：最初の印象

はじめに

このような年次プログラミングコンテスト、 ICFPコンテスト 、つまり、機能プログラミングコンテストに関する国際会議があります。 競争は非常に有名で、 Adeptレポートによってロシア語で一般化されました。そのため、基本的な原則を簡単に説明します。



コンテストは年に1回行われ、チームゲーム、タスクはコンテストのウェブサイトで発行され、そこで決定が送信されます。 ゲームは3日間続き、普通の人と同じように、ノンストップで生きて、眠って食べることができます。 :)いわゆるライトニングラウンドもあります。つまり、ゲームの初日に送信されたソリューションの中には、別の賞の場所があります。



有利な方向のタスクは、古典的なオリンピックの問題とは異なります。 2006年と2007年には、これらは難解な仮想マシン用の難解な言語のカスタムコンパイラを書くという素晴らしいプログラミングの探求でした。 以前および今年、仮想世界でのオブジェクトの動作のロジックをプログラミングしました。

今年

今年、タスクは最初から明確かつ完全に策定されました。 TCPソケットを介してローバーを制御するプログラムを作成する必要があります（ローバー、今後は習慣的にローバーと呼びます）。 ローバーとの通信プロトコルについて説明します。 ローバーは地球上で理想的なグリップを持ち、加速、回転、摩擦により徐々に減速し、減速することができます。 左右の回転方法を認識しており、ステアリングホイールには、右、右、左、完全に右、完全に左の5つの個別の回転値があります。 コマンドの実行には20ミリ秒以下の一定の遅延、遅延があります。 角速度は急激に変化することはありませんが、一連のラウンドの開始時には滑らかで線形および角加速度、および摩擦係数が不明であり、マップによって異なります。



火星には、ローバーが跳ね返り、速度を失い、方向を変える巨石があり、ローバーが死に落ちるクレーターがあり、ローバーのような物理学を持つ火星人がいて、バルサムの神にローバーを犠牲にすることを夢見ていますこれは、作家のエドガー・バロウズによる火星に関する空想科学小説のサイクルへの参照です。 ローバーに追いついたら、実際に何をしますか。 ローバーは、マップの表面の任意のポイントに配置されます。タスクは、座標（0,0）でベースに到達することです。 ローバーは、ローバーであるトリックの1つで、その視野（楕円）に該当するもののみを見ます。



ローバーが見るものに関する情報は、約100ミリ秒ごとに1回、テレメトリパケットの形式で送信されます。



ローバーは、異なるランダムなポイントで、同じカードに5回連続して植えられます。 各ラウンドの変更における火星人とローバーの位置、クレーター、巨石、物理定数は最初と同じままです。 ラウンドの結果については、基地への旅行が成功したか、クラッシュしたか、単にタイムアウトしたか（各カードの通過に最大時間があります）-5ラウンドすべてに加算されるポイントが付与されます。 ポイントが少ないほど良い。 基地に着くのが速いほど良い。 失敗した結果のうち、タイムアウトが最も有利であり、バルサム神を称えて死が続きました。最も恥ずかしく、失敗したのはクレーターに落ちることでした。 したがって、参加者の比較はこの方法で行う必要があり、すべてのローバーは同じカードで5ラウンドを実行し、最も成功した応募者のいくつかは次のカードに進み、残りは破棄されます。



それがおそらくすべてです。



主催者は、提示されたソリューションが起動されるシステムのイメージを、knoppixを備えたliveCDの形式で提供し、このシステム用にコンパイルされたサーバーとそのサンプルカードのセットを提供しました。 Xの下で起動されたサーバーは、同時にローバーで何が起こっているかを描いたウィンドウを表示しました。



チームの組織では、前の年とは2つの違いがありました。 まず、今年は参加の予備申請は不要で、すべての決定が期限前に送信されました。 第二に、彼らはチームのサイズに制限を導入しました;チームは5人以下でなければなりませんでした。



導入のこの抽象的な説明で、私は終了し、個人的な感情と思考に進みます。

組織に関する全般

今年ICFPCで起こったことすべてについての意見は大きく異なります。 たとえば、過去数年間の大会に参加した大多数の人々は、課題の公表のほぼ直後に、彼について否定的に鋭く語りました。 同様に、以前は良くなった。 私はそのような仕事を長い間夢見ていたので、退屈しませんでした。 そして歴史は、同様のタスクがICFPCにとっても非常に典型的であることを示しています。 一般的に、私はこのように話すように思われます、それは「本は映画よりも良かった」と言っているようなもので、プロットのこれら2種類のプレゼンテーションの基本的な比較不可能性を理解していません。



しかし、私は組織について言いたかった。 だから、私は肯定的なレビューを見ました。 しかし、主催者の仕事は私には不満のようでした。 x-guiでサーバーを起動することになっていたLiveCDは、最初はx-xsを起動しなかったため、公式FAQに設定手順を追加する必要がありました。 サーバー自体はオーガナイザーによって途中で追加され、多くのバグ修正が導入されましたが、公式データによると、競争は1月から準備されました。通常の実装を作成する時間があります。 たとえば、私たちのチームは、最初の日にテストサーバーの独自の単純なバージョンを投入しました。



さらに、サーバー自体は、コンテストの開始直後に投稿されませんでした。 そして、他のLinuxディストリビューションとMacOS X用の静的にリンクされたバージョン-1日程度の遅延もあります。 私たちのチームの少なくとも1人のメンバーにとって致命的なWindowsバージョンはありませんでした。彼のマシンは私のマシンのように仮想マシンを引っ張らず、自分のコードを実際にテストできなかったため競争から脱落しました。



その結果、多くのチームはプログラマーではなく「Linux管理者のプレイ」に初日を費やしました。



一方、オーガナイザーに敬意を表し、IRC、メーリングリスト、バグトラッカー、Wikiを通じて優れたフィードバックチャネルを提供し、外出先で本当に問題を解決しました。 もっと徹底的に準備すれば、これらの問題のほとんどを回避できると言いたいだけです。

ゲーム自体

5人という制限は、試合開始のほぼ半年前にゲームに集まっていたチームにとって不快な驚きでした。 ルールは、「より大きな作品に参加することはできますが、賞品に頼らないでください」と述べています。 10人のチームが1千ドルで1位を獲得したことは私たちにとって何かを意味するものではありません。喜びがより重要であるため、私たちは自分が行っている作曲で演奏することにしました。 しかし、誰かがタスクに失望し、すでに書いたように、誰かが技術的な理由で参加できませんでした。地平線からの道徳的および倫理的問題。 :)



私たちのチームの主な開発言語はpythonでした。 私たちの中に多くのpythonの達人がいたわけではありませんが、誰もが（主なことはゲームの楽しみだからです）迅速な開発に適した動的言語を使用したいと考えました。選択はrubyとpythonの間でした。 しかし、Rubyは難解すぎて、十分な優れたスキルを開発していなければ彼と一緒に仕事をすることができず、Pythonに対して特定の異論はありませんでした。 Pyrexを使用してボトルネックを最適化することを期待していましたが、後でこれは役に立ちませんでした。

初日

最初の夜（まあ、これは私のGMT + 6時間です）LiveCDとの対話と対話プロトコルの実装に費やしました。 この時点で、Pythonは動的型付けのすべての美しさを示しました-プロトコルパーサーを記述するテンプレートが同時にオブジェクトとイベントのクラスのフィールドを設定すると、これは歌です！ :)しかし、これはゲームの2日目の終わりのどこかで、より一般的なスタイルで書き直しました。



開始から約10時間後に、Cerebellumの最初のバージョン（「小脳」）が実装されました。これは、moveTo（x、y）などのコマンドを受信し、プロトコル自体のターンおよび加速コマンドに変換する低レベルローバーコントローラーです。 同じ頃、実際にCerebellumとプロトコルの実装を書いたVladには、OpenGL用のPython APIであるGLUTを使用して書かれたクライアント側のビジュアライザーも含まれていました。 あらゆる種類の中間データを地図上に表示し、発生していることに自分自身を向ける機会を得たので、これは後々に役立ちました。 もっと強く言います-そのようなビジュアライザーがなければ、デバッグロジックは不均衡に複雑になります。



叙情的な余談。 私は、タスクとチームワークが自己組織化された生物が本当に好きでした。 作業の重複は十分ではなく、それぞれが問題の個別の側面に関与し、同時にタスクを解決しました。 コードに何か足りないものがあれば、この問題について誰に連絡すればよいかがわかり、妥当な時間内に適切な解決策が得られることを知りました。 そして、このすべては、私たちの側に意識的な組織なしで、何とかそれ自体で起こりました。



そこで、Vladがスケッチしたものをなめるのに数時間費やし、まともなバグをとかし、アプリケーションの安定した動作を実現しました。



その後、静的オブジェクトの独自のマップの開発は正常に完了しました。オブジェクトは、レンダリング中の迅速な反復のための完全なリストとして、および現在のオブジェクトのセットのみを取得するバイナリツリーの両方に格納されました。



その結果、ローバーが最初に旋回し、ベースに向かって直線でのこぎりで回転しました。これはすべて、純粋に小脳のレベル、つまり「反射神経上」にありました。 当時の人々は、統計を収集するためのモジュールに従事していました-実際のレイテンシーに関するデータ、およびレイテンシーとテレメトリデータに基づいて加速度と摩擦係数を計算します。 したがって、私は座って、主流の結果として実際に残ったパスを選択する決定を投げました-決定はスリッパのように簡単です。



別の叙情的な余談。 私は、独創的なものはすべて単純であるという見解を持っています。 プログラミングでは、複雑な数学理論に基づいた普遍的なuberソリューションを信じていません（もちろん、データ暗号化やレイテンシおよび摩擦係数の計算などのタスクではなく、応用プログラミングについて話している）。 私は、単純なアイデアが対処できない場所での単純なアイデアと単純なハッキングを信じています。 私の解決策は単純で、単純なハッキングによってさらに改善されました。



私のナビゲーションアルゴリズムのローバーは単純なマップにうまく対処しましたが、すでにスパイラル（主題の人向け）で取り壊され、最大5つのうち1つに対処しました。最初の単純なハックはこのインジケーターを5つのうち3つに改善しました。



ローバーでさえ、私のアルゴリズムでは、火星人を事実として無視しました-ところで、多くのチームがこれをやったという噂やレビューによると 火星人は速く動きますが、緩やかな経路に沿って操縦が不十分で、通常は腕の長さでもローバーを捕まえられません。 つまり、火星への侵入は非常にまれで、純粋にランダムなイベントです。 私は、火星人が非常に近いときに戦術的な策略を使用することを考えていましたが、彼女の手は彼女の実現に決して到達しませんでした。

二日目

2日目、判明したように、私たちは単に負けました。 私は周りの状況を考慮して、より良い動きを実装するのを待っていました。たとえば、多くの障害物がある場合に、より正確なターンを行います。 彼らは未知のパラメーターの計算機を書きました。 Vladは、システムを最適化、つまり最速かつ最も正確な、一連のウェイポイントの通過を実現しようとしていました。 また、貯金箱に「帰宅する酔ったローバー」という移動アルゴリズムを追加しました。



一般に、有用なもの、つまり後で有用なものから、予測子がこの日にわたって書かれ、次の1、2秒でローバーの現在の物理的軌道を計算しました。 予測変数は統計モジュールからの何かを使用しました。 2日目の終わりまでに、私が既に言ったように、彼らはCerebellumとプロトコルをより正気で読みやすいものに書き直しました。 ほとんどの場合、私は2日目を逃しました-今週の週末は競技に関係のないケースが多くありましたが失敗しました。

三日目

3日目に、Vladは独自のモジュールを追加して軌道を追跡しましたが、まず、期待どおりに機能しませんでした。次に、ウェイポイントのスタックにロジックを配置するために必要なAPIを提供しませんでした。 その間、私のアルゴリズムがひどく不快な結果をもたらしたマップがありました。ローバーは交差するクレーターの概念を理解する上で深刻な問題を抱えていました。 私は新しいハックを探しに行きました。



より正確には、最初はクレーターチェーンを処理するロジックを記述し、クレーターチェーン全体を巡る極端なウェイポイントを見つけるのにかなりの時間を費やしましたが、このコードは期待どおりに機能しませんでした。 すでにコンテストの最後の3〜4時間で、このコードをデバッグしないことに気付き、アルゴリズムの別のハックを見つけました。これにより、この地獄のようなマップで結果を5分の3に改善できました。 その後、彼らはそのシンプルさと天才に優れたアイデアを思いつきました-クレーターをマップに保持し、その大きさを1メートル誇張しました。 うまくいきました！



コンテスト終了の約30分前に、試用版を選択委員会に送りましたが、まだ改善が望まれていました。 最後の30分で、衝突の可能性がある場合に緊急ブレーキのために軌道予測を使用しようとしましたが、これによりテストカードで追加の勝利ラウンドはもたらされませんでしたが、ブレーキによる1つのタイムアウトが追加されました。 競技終了の10分前に、私のコードの非常にまれでほとんど使用されていないブランチで2つのタイプミスが見つかりました。それらはほとんど機能しませんでしたが、ローバーのすべてのアクションをすべてのラウンドで殺しました。 公式マップではこのコードにはまったく届きませんでしたが、テスト用に生成したコードの1つに当てはまりました。 ギリギリで修正版をバージョンに詰めましたが、受付が閉じる前にコミッションを送信することができませんでした。 今、私たちは十字架で指を握り、このコードが機能する状況が起こらないことを望みます。 :)

より一般的に

一般に、障害をある程度まともに回避するための何らかのソリューションを作成することは難しくありません。 実際には、勝者の質問が詳細に決定されると確信しています。 ポイントシステムは、火星に1人でも落ちないように設計されており、火星との出会いは、マップ上で排除された人と勝者を区別できる可能性は非常に低いですが。 100％の結果でこれらのトラブルを回避することを学んだ人々の間では、すべてがルートの速度によって決定されます。 これは、軌道の通過の最大許容速度であり、最短経路の構築であり、単なる満足できる経路ではありません。 アクションと勝者コードを見るのは非常に興味深いでしょう。



そうそう、pythonは二度とありません。 実行前にタイプミスすら明らかにしない、この動的な型付けで地獄に。 来年、すべてをScalaで記述します-静的型付け、コンパイル、Javaのようなパフォーマンス、そしてPythonとHaskellの狂ったミックスのようなパワーと表現力。

フィードバック

今、私はさまざまなチームからそれがどうだったかについてのレポートを集めています。



さまざまなブログエントリから判断すると、単純なソリューションはそれほど悪くないかもしれません。 そのため、積極的な作業にもかかわらず、 彼らには決断を下す時間がありませんでした 。 私たちのコードの暫定版の送信を組織してくれたチームの人にはまだ感謝しています。 他の人は始めたようですが 、問題が完了したかどうかは明らかではありません。 Haskellを使用しようとする別のチームの試みも失敗し、Perl-eに予備の稲妻ソリューションを追加しました。 反対に、著者は、私のコードや真珠の解決策のように、些細なハッキングが悪であると考え、同じ美しい一般化された解決策を実装するつもりです。 シンプルなソリューションを選択した別のチームも、これについてそれほど悲しくはありません。 :)



一方、Schemeの関係者からは強力な解決策があります。 彼らが公開したテスト実行の結果はより良いようですが、最後の2時間で彼らは非常に重要なアイデアを実装することができました。 確かに、私はそれを異なる優先順位のチーム-戦略的、戦術的、シャンティング-ローバーの小脳として実装するつもりでした。

C ++のハリコフの人々は成功しました。 そして、普遍的なスマートアルゴリズムで、安心して、最後の数分で解決策を送ります。

誰かが楽しみのためだけに参加しました 。

Adeptはまだレポートを公開していません。



ここに記載されていないレポートへのリンクがある場合は、ご記入ください。リストに追加します。



一般に、それですべてです。 競技の公式ウェブサイトの情報によると、我々はすぐに結果を知りません-9月22-24日。 受賞者は、しかし、授賞式への旅行の準備をする機会を得るために、ずっと前に彼らの勝利について学びます。



UPD：このトピックのブログを作成し、そこに投稿を移動しました。

最後に

「デザート用」- コンテストの最後の10分間のアドレナリン 。