ICFPコンテスト2015の解決方法に関する小さなレポート。私たちはこのコンテストに初めて参加しましたが、結果はかなり良かったです。中間結果テーブルで「WILD BASHKORT MAGES」という名前で検索できます。最終結果は今後数週間のうちに、主催者がすべてのソリューションをすべてのテストでテストする予定です。

今年、タスクとして、六角形テトリス用の格子（またはAI、より便利な）を記述することが提案されました。すべてが通常のテトリスのようなものです-私たちは数字を入れ、塗りつぶされた線を削除し、このためのポイントを取得します。このソリューションは、さまざまなサイズの競技場とあらゆる構成の積み重ね可能なフィギュアで機能するはずです。数字付きのアクションコマンド（動きとターン）は通常の文字でエンコードされます。最終的には、解決策はコマンドラインです。パワーワードと呼ばれる決定ラインのキャラクターの特別なシークレットシーケンスの場合、追加のボーナスポイントが与えられます。プロットによると、これらの線はダバールと呼ばれ、主催者はクトゥルフの覚醒を遅らせるためにそれを収集しました。

はじめに

チームには、2匹の猫を除いて3人がいました-Damir、Maxim、およびme。ダミールと私はオリンピアードを引退し、マキシムはコンパイラの作成に多くの経験を持っています。予備的な準備として、gitリポジトリを上げ、暗号化に関する少しの情報を読みました（何らかの理由で発表で言及されていました）、Ubuntuが仮想マシンで動作することを確認しました（チームメイトとは異なり、Windupです）。もちろん、パフォーマンスの前によく寝ました。

競争は3日間続きましたが、このストーリーでは、タイムゾーンに関連してすべてが4日間に分割されます。現地時間によると、コンテストは金曜日の17:00に始まり、月曜日の17:00に終わりました。つまり、1日目と4日目はわずかにトリミングされ、正確に3日間になります。ストーリーの時間は概算であり、具体的には誰も書き留めておらず、gitリポジトリから復元されました。

ソリューションの技術的な詳細は、このようなフレームで強調されています。

技術的な詳細を掘り下げたくない場合は安全にスキップできますが、実装の詳細に興味がある場合は簡単に見つけることができます。このすべては、まだ注意を払う意味がある写真のためにネタバレに隠されていませんでした。

1日目

そのため、コンテストは17:00に始まりました。奴らはすでに集まっており、私はこの時点でまだ仕事中です。すでに去ります。去る前に、私は問題の状態に目を向けました。最初は、テトリスについて話しているという結論には至りませんでした。いくつかのユニットが移動する六角形のフィールドを扱っていることは明らかでした。「戦略のためのAI、書くことは必要ですか？」と私は考えました。彼は午後6時ごろにチームに引きずり込まれ、食料品やコーヒーなどの戦略的に重要なリソースを求めて店に向かう途中で一見した。

Damirは問題の状態について約1時間議論し、並行してPythonでビジュアライザーを記述します。 Pythonは最終的な解決策には遅すぎる可能性があることは明らかなので、C ++でフィールドと図を使用して基本的な操作を書き始めています。

マキシムは、OCamlでのみ同じことを書くことにしました。一度にいくつかの方向に進むと想定されていましたが、その後、明らかに見込みのないものは除かれます。はい、そしてコンテストの初めに特別なことは何もありませんでした。ユートピアオプションとして-次に、異なる言語でいくつかのヒューリスティックを組み合わせ、各テストですべてを実行してから、最適なオプションを選択できます。

19:30頃、ビジュアライザーの最初のバージョンの準備が整いました。オーガナイザーが準備したテストを確認できます。それらのいくつかのフィールドでは、奇妙なメッセージが表示されますが、それはパワーワードではありませんか？

ここでもこれを見つけました：

それまでの間、私は図の基本的なコマンドの実行をいじっています。六角形のグリッドに沿って図形をシフトすることは簡単ですが、それらを回転させることは完全に簡単ではありません。

その結果、紙の上にいくつか積み上げてケースを分析した後、次のコードが得られました。

void move_pnt( PAR & p, int dir, int d ) { if (d<0) { d *= -1; dir += 3; if (dir>=6) dir -= 6; } if ((pY & 1)==0) { if (dir==0) { pX -= d; } else if (dir==1) { pX -= ((d+1)>>1); pY += d; } else if (dir==2) { pX += (d>>1); pY += d; } else if (dir==3) { pX += d; } else if (dir==4) { pX += (d>>1); pY -= d; } else if (dir==5) { pX -= ((d+1)>>1); pY -= d; } } else { if (dir==0) { pX -= d; } else if (dir==1) { pX -= (d>>1); pY += d; } else if (dir==2) { pX += ((d+1)>>1); pY += d; } else if (dir==3) { pX += d; } else if (dir==4) { pX += ((d+1)>>1); pY -= d; } else if (dir==5) { pX -= (d>>1); pY -= d; } } }

これは非常に重要な機能です。彼女は、dirの方向にd個のセルにスリップしたポイントをシフトします。この後、並列シフト操作は完全に簡単になり、ターンは非常に簡単になります。これを行うには、図の各セルについて、2つの非共線方向の回転点に対するシフトを計算し、わずかに異なる方向にのみ同じ変位だけ回転点に対してシフトしたセルを見つける必要があります。

コードは午後10:00までに少し修正する必要がありました。すべてがテストされたと同時に、フィールドに新しい図形を挿入して配置する機能が追加され、壁と占有セルとの交差をチェックしました。 Damirは私のコードを受け取り、それをPythonで書き直してビジュアライザーに挿入します。マキシムはまた、彼のバージョンのソリューションで使用するためにOCamlで私のコードを書き直します。

そのような夕食はありませんでした。職場を離れることなく、ソーセージと紅茶/コーヒーのサンドイッチを中断しました。マキシムは、冷蔵庫の中に鶏肉があり、それが悪くなる前に調理して食べる必要があることを思い出しました。しかし、私たちは朝まで何も起こらないと決めました。

真夜中 Damirはビジュアライザーに意思決定を行う機能を固定しました。これで彼にdavarをフィードし、動きに従ってボード上で何が起こっているかを追跡できます。確かに、ダワールはありませんが、見るべきものは何もありません。

03:00までに、「フリーズ」する前にフィギュアを貼り付けることができるすべての位置を見つけるためのコードを完成させました。この位置につながる一連のコマンドとともに。マキシムはすべての基本操作をOCamlに実装し、同時にコードのいくつかのバグを修正しました。 Damirは、キーボードからビジュアライザーに図形をインタラクティブに制御する機能を追加しました。このテトリスを自然に再生できるようになりました。そして、決定を保存します。

残念ながら、ゲームにはまだ十分な強度がありません。今は眠る時間です。この日の夢の中で、私たちは救わないことにしました。

2日目：エピソード1：雷部門

午前11時ごろ起きます。朝のコーヒー-そして再び仕事のために。

Damirは、C ++ビンからJSONを操作するためのライブラリを取り出し、それをねじ込み、擬似乱数ジェネレーター、ダム移動選択ヒューリスティックを追加します（図が最終的に最も低くなるものを選択します）。そして、ここにあります-少なくとも何かをするソリューションが準備できています！少しのテスト、デバッグ、および資格テストの実行-そして、14：00までに最初のダワールがあります。

この間、Damirはアイドル状態になりません-ビジュアライザーをポンプでくみ、バグを修正します。今では、ステップごとに決定をスクロールすることができます。マキシムはこれまでずっとOCamlソリューションをいじっていました。

ランチタイム。昼食には、鶏肉は調理するのが面倒なので、ピザを2つ注文します。実際、時間はありません。17：00にいわゆるライトニング部門が終了します。これは特別な指名であり、たった1日で書かれた決定がなされ、権力の言葉を考慮に入れずにすでに何かを解決します。そして、特に何かがすでに手元にあったので、私は本当にそこに何かを送りたかった。

最初の決定が得られるとすぐに、マキシムは「ダバーは決定を送信する方法は？」という質問を整理し始めました。そして、ダミールと私は、私たちの愚かなソルバーが私たちのために解決したビジュアライザーを見ています。原則として、それはかなり適切に動作し、いくつかのポイントを獲得します。一部のテストでは、ピボットポイントがフィギュア自体から遠く離れているフィギュアに対して、面白い量子トンネル効果が示されています。

午後3時45分までに、ピザの吸収と並行して、解決策が追加されました。ソリューションにヒューリスティックを追加しましたが、これは行方不明の行を追加で考慮し、Damirは仕様に応じたコマンドラインの作業をソリューションにねじ込みました。

それでは、Lightning Divisionのアーカイブを準備します。マキシムはMakefileとREADMEを作成し、tarballを収集します。ダミールと私は、最後の決定から受け取ったダワールを見ています。エラーはなく、tarballが組み立てられ、テストされているようです。16：47に、アーカイブを最新のソリューションとともにオーガナイザーサーバーに送信します。

ここで、ダミールは明らかに不十分なダワールを見つけます。ある時点から始まって、決定は非常に奇妙に振る舞い始めます-穴を逃し、天井に数字を彫る。そして、この不名誉は、2つの隣接する行が完全に埋められて削除された後に発生します！すぐに、これは、塗りつぶされた行が削除された場所のC ++コードのバグに過ぎないことが明らかになりました。つまり、ビジュアライザーではすべての行が正しく削除されますが、私の実装では行の1つが残っているため、非同期です。

その後、ハリウッド映画のようにすべてが起こります（タイミングは概算です）：

16:50すぐにですが、バグを慎重に修正し、すべてのタスクを新しいバージョンでテストします。

16:54 gitでkommichuが変更され、Damirは私の修正をドラッグしてビジュアライザーでチェックしようとします。しかし、彼はいくつかの変更を行い、駐車場でそれらをコミットするのを忘れました。その結果、引っ張った後、彼は何らかの混乱を起こし、ひどいマージを解決する必要があります。ダミールは生涯にわたってhgに座っていて、gitで手を満たしていないだけです。

16:55マキシムは急いでダミールを助け、彼が何らかの錫を持っていることに気付き、彼のコンピューターに急いで戻ります。それまでの間、私は問題テストを自分で実行します-これ以上グリッチはありません。

16:56マキシムは編集内容をドラッグアウトし、新しいtarballをすばやく収集します。

16:58はスクリプトを開始して、最後の決定をサーバーに送信します。

16:59はtarballをサーバーにアップロードしますが、その間、ここの時間に従います。ダバールを送信するためのスクリプトでは、個々のテストの間に遅延があるため、不注意で禁止されないようになっています（神経を台無しにしました！）。したがって、送信は遅くなります。スコアはすでに数秒間続いています：5、4、3 ...

わあ、時間がある！締め切りの3秒前。道徳：なじみのないツールを使用すると、重大な瞬間に突然問題が発生する可能性があります。

少し後、主催者に時間があるかどうかを尋ねました。答えが来ました：

<galois_kiniry>チームから11:47および11:59に2つのtarballが送信されたことがわかります。両方とも整形式です。

<galois_kiniry>しかし、C ++は本当にハッカーを識別するためのプログラミング言語として最適ですか？ ;）

2日目：エピソード2：ヘビ、シリンダー、およびステートマシン

さて、最も緊張した瞬間の1つ、通常の解決策を考え出す時です。たとえば、パワーワードの使用を考慮に入れています。実際、このアイデアはコンテストのほぼ最初の数時間に長い間空中にありましたが、ライトニングラウンドの後に開発することを決めました。そのため、パワーワードの使用は必要ありませんでした。私たちは1時間座ってアイデアを形式化し、結果は次のようになりました。

どういうわけか図を最終的な位置に置いて、「フリーズ」しましょう。非常に多くの方法でこの位置に来ることができます-最初にフィールド全体にフィギュアをドラッグし、適切な場所に置く前にパワーワードを詰め込むことさえできます。動的計画法を使用して、この最適なパスを検索できます。

フィギュアの位置に関するすべての情報をダイナミクスの状態に押し込む必要があります。つまり、転換点の位置、現在の回転、および一連のコマンドで新しいパワーワードの出現をキャッチするためにすでに入力したコマンドに関する情報。

状態の2番目の部分では、次のように構築された有限状態マシンが優れた仕事をします。 n個のべき乗語があり、オートマトンの状態は長さnのベクトルとして表すことができます。そのi番目の要素は、すでに入力したi番目のべき語の接頭辞の長さを示します。状態遷移は、コマンドラインに新しい文字を追加すると発生します。同時に、すでにダイヤルされたプレフィックスの一部は1つ拡張され、他のプレフィックスは短縮されるか、長さゼロにリセットされます。パワーワードが完全に入力されると、この情報をマシンでマークし、プレフィックスとして最長を示します。これはサフィックスと一致します。

オートマトンを構築する例は、下の写真で見ることができます。ここでは、 aba 、 acacおよびbcの 3つの単語が使用されます。エッジは私たちがたどる文字を示し、括弧内に入力した単語の番号が示されています。

私たちにはパワーワードがほとんどなく、その中の文字もあまり多くないので、マシンを額の上に構築することができ、ソリューションの有効性を本当に心配することはありません-それでも高速です。

ダイナミクスの状態の最初の部分で汗をかかなければならなかった。実際のところ、図を目的地に移動するとき、同じ状態になってはいけません。合計で、図のアクションには6つのオプションがあります：左に移動、右に移動、上下に移動、左右に移動、時計回りに回転、反時計回りに回転。「上下に移動」と「左右に移動」を使用すると、すべてが明確になります-フィギュアを下に移動するとすぐに、ドラッグして上に戻すことはできません。繰り返しは、フィギュアを同じラインで左右に動かし、回転させるときに起こります。

次のことがわかります。行の図のすべての位置は、長方形の表として表すことができます。その幅はフィールドの幅であり、その高さは可能なターン数です（1、2、3または6-図形の対称性に応じて）。同時に、テーブルの上側が底に接着されます-一種のシリンダーが得られます。そして、エッジに沿って隣接するセルから自分の動きで動きます。その結果、競技場の1行でのすべての動きは、シリンダーに沿ってい、尾を噛まないようにしようとする蛇として表すことができます。

残念ながら、このアプローチでは、各シリンダーのすべての訪問済みセルをダイナミクスの状態に維持する必要があります。この場合、状態の総数は指数関数的に増加します。私たちはそれについて何かをしなければなりませんでした。次のようにヘビの動きを制限することにしました。ラインを離れた場合、二度とそのヘビを訪れることはありません。その後、あらゆる種類の蛇行が縮退して、次の形式の波状になります。

すでに訪れたすべてのラインは、特定のセグメントを形成します（ヘビは、たとえばラインを通してテレポートできません）。ここから-訪れた行を覚えておくために、最大36の州が必要です。パラメーターをもう1つ追加します。どこから来たのか—左側、右側、または競技場の上部/下部/ c-another-line-で-これは、ヘビが尻尾を切り落とさないようにするのに十分です。

もちろん、コマンドの可能なすべてのシーケンスからはほど遠いので、すべての可能な単語を考慮することはできません。しかし、私たちはこれまでに発見された潜在的な力の言葉をすべて引き出し、「 スイカ」という言葉だけを入力できないことを見ました。今のところ、それなしで実行できると判断しました。

ダイナミクスの合計状態：

x、y //図形の位置、またはむしろその回転点

回転//現在の回転

rot_seg_left、rot_seg_right //すでに訪れたターンのセグメント

from //元の場所：left、rightまたはtop / bottom / c-another-line-of-the-board-field

ノード//ステートマシンからの頂点番号

各状態で、3つのパラメーター、つまり、図を「フリーズ」するときの運動場の評価、使用されるパワーワードの最大長、および使用されるすべてのワードの合計に従って、重み付け評価関数を考慮しました。将来のために2番目のパラメーターが追加されました：ダイナミクスで以前に使用されていない単語を含むパスを選択するために（主催者は各パワーワードに300ポイントを与え、それが少なくとも1回発生すると追加のポイント（ワード内の文字数を2倍に））、繰り返し）。

ダイナミクスの本質：各状態について、現在の状態からある種の「凍結」状態に移動することで得られる評価関数の最大値を考慮します。あらゆる種類の動きを作り、再帰的に処理し、現在の動きで単語が終わったら評価関数を更新し、最大値を選択して保存しようとします。熟考のための非常に微妙な瞬間：どの単語が再帰を介した直接の通過から終了したかについての情報を得るように思えますが、実際には、ダイナミクスの状態自体がすべての必要な情報を保存します。まあ、私たちはそれらの終わりの逆の順序で見つかったすべての単語を考慮します。

ダイナミクスは、メモ化を使用して怠 consideredと見なすことができます（最後に、少なくとも機能主義のヒントがあります！）。図形の最初の位置から開始するだけで... ...その後、図形のすべての位置を計算し、そこで「凍結」することができます。最適な状態を達成するために必要なシンボルを各状態に追加すると、目的のコマンドシーケンスを簡単に復元できます。

19:00のどこかで決定は正式になりましたが、それを書くだけです。ダミールは座って有限状態マシンを記述し、ダイナミクス自体を記述します（より正確には、ダイナミクスの状態が与える制限を考慮してほとんどの時間を費やしました）。マキシムはOCamlでの実装を引き続き選択します。

20:45までに、Damirはマシンを追加し、数分後にダイナミクスを追加します。コードを保持して、何が起こったのか見てみましょう。スタックオーバーフローが判明しました。まあ、私はダイナミクスのどこかで台無しにしたので、サイクルします。バグを探すためにかなり多くの時間が殺されました（それは馬鹿げたタイプミスであることが判明しました）。その後、あらゆる種類のテストを実行し始め、ソリューションがどこでもクラッシュしないことを確認しました。 23:45に修正されたソリューションをテスト0のdavarとともにコミットします。サーバーに送信し、このテストの最初の行に移動します。

この時点で、チームの名前を変更します。実際、元々はチームバシコルトスタンと呼ばれていました。そして、テスト0の最初の行に達したとき、その名前はなんとなく創造的ではないと考えました。 WILD BASHKORT MAGESに名前が変更されました。私たちは鶏肉を思い出しました、それをどうするかを考えます。彼らが決めたのは、明日それを捨てないなら、明後日に捨てるということです。

私はダイナミクスのバグを見つけることに愚かだったが、ダミールは怠idleではなかった：私はオートマトンの構築を少しねじり、ビジュアライザーにパワーワードのサポートを追加し、ダバーに与えられるべきポイント数を計算するためのモジュールを書いた（このモジュールはビジュアライザーでさらに使用された、および外部から自動的にポイントを計算し、比較用のプレートを生成します）。ビジュアライザーでこれ以上快適に作業できる場所はありません。

マキシムは、テスト0をサーバーに送信する瞬間まで、OCamlの決定に悩まされ続けました。その後、彼は開発にスコアを付け、ソリューションのテスト（「改善」の後にソリューションを壊したかどうかを追跡するため）に集中し、新しいパワーワードを検索するという強い意思を決定しました。 OCamlでソリューションを作成することは時間の浪費であるとは言えません-むしろ、C ++でのソリューションに困った場合の保険でした。

00:15のどこかで、評価関数に別のヒューリスティックを追加しました。すなわち-フィールドの塗りつぶされた部分に「穴」を作成するための罰金。ヒューリスティックの本質は非常に単純です。そのような隣接セルの数を考慮し、それらの1つが満たされ、もう1つは空です。その後、フィールドに残った「穴」が1つあれば、6のペナルティが与えられます。その後、決定はより良くなり始めました。

ソリューションはテスト0には適していましたが、他のテストにはいくつかの困難がありました。事実は、現在の解決策が抑制されたということです。テスト14では、3時間働きました。おかしい瞬間：私は実際にテスト13のソリューションを立ち上げたいと思っていましたが、これははるかに小さく、100の動きしかありません（14のテストは500の動きで上の写真の五gram星です）が、テスト番号を少し混ぜました。まあ、私はそれがカウントされるのを待って座っています。しかし、それはすべてを数えるわけではありません。プログラムの30分後、完了を待つことはすでに原則の問題になっています。そして打ち上げの1時間後、13ではなく14回目のテストを実行したことがようやくわかりました。明らかに、疲労はすでに影響を及ぼしていました。 03:45までにカウントされました。

不運な14回目のテストの終了を待っている間に（もう待つことはできませんでしたが、眠りにつくことはできませんでした）、マキシムは正しいソリューションでさらにいくつかのテストを実行し、サーバーに送信しようとしました。彼らはカップルをチェックすることができましたが、後者はチェックすることを望んでいません。より正確には、彼に何が起こっているのか明確ではありません-結果テーブルは単に更新されません。さらに、すでに行われたいくつかのテストによると、結果テーブルと私たち自身のスコアは少し一致しませんでした。 Damirはアカウント評価モジュールのエラーを探しています。すでにすべてをダブルチェックしたようです-エラーはありません。その後、結果の表は完全に落ちます-誰かが間違ったダワールをサーバーに送信し（悪いダワール、低品質）、それによってテストシステムを壊したことが判明しました。主催者はすぐにバグを修正し、テーブルを復元し、参加者は送信しないようにもっと悪いと言われました。

テーブルのバグは、14回目のテストがカウントされたのとほぼ同時に修正されました。更新された表では、各テストのスコアはローカルで計算されたものと一致しました。バグは私たちのものではなく、私たちはそれを無駄に探していました。

14回目のテストが送信され、非常に良い結果が得られました。その後、06：00に計算されたばかりのダバールを送信するまで、マキシムは手で新しいパワーワードをチェックして検索しようとしました。残念ながら、新しいものはありませんでしたが、テストで見つかったすべての単語（「Ei！」、「Ia！Ia！」、「R'lyeh」、「Yuggoth」）は、本当にパワーワードであることが判明しました。

明日の目標が明確になりました：現在のソリューションをスピードアップします。幸いなことに、最適化の余地はかなりありました。

3日目。最適化と改善

15:30頃に目が覚めました。マキシムは少し早く起きて、ついに鶏肉を調理しました。ジャガイモ入り。ダミールと私が目を覚ますのにちょうど間に合います。私たちは朝食をとりました（ただし、おそらく昼食をとった（または夕食をとった方がいいでしょう））。

16:00に決定に戻ります。ダミールは昨日眠れず、朝6時に寝なかったことが判明した。この間、彼は私のソリューションを最適化しました。評価関数は、値の計算を別の手順に取り出してキャッシュしました（これにより、同じ計算が大幅に削減されました）。構造の比較を高速化する（およびstd :: mapで検索する）ために、すべてを1つのint64に圧縮しました。ダイナミクスにヒューリスティックを実装して、以前に使用されていないパワーワードを優先するようにしました。彼はまた、最適化のために私のダイナミクスを書き直しましたが、そこで何かを壊しました。結果は、昨日よりもはるかに高速に動作するソリューションですが、ポイントははるかに少なくなります。

ダイナミクスを最適化した後に正確に壊れたものは、まだ理解できていませんでした。すべての新しい最適化に加えて、古いコードからダイナミクスを単純に取得して慎重に転送しました。修正は17:00までに完了しました。そして今、昨日3時間を数えた同じ14のテストが5分で数えられます！

すべてのテストの実行を開始します。この大量のテストは、タグ「apocalypse_1」の下に表示されました。

この頃、Gitを介してカウントされたダバールを運ぶことは非常に便利ではないという理解が得られます。毎回、現在の変更をコミットしてプッシュし、残りをリポジトリから残りにプルする必要があります。そして、現時点ではすでに不安定な変更があり、リポジトリにプッシュしないようにする必要があります。要するに、面倒です。したがって、ドナのストレージをgitからDropboxに転送することにしました。2日前に何らかの形ですでに自然発生的に発生しました。計算されたドナは「solution_％PROBLEM_ID％タグ（互いのdavarを上書きしないようにするため）。 1時間、すべてが再構成されました。そして突然、それはすぐにもっと便利になりました。あなたは座って静かにコードを書き、その時にDropboxはコーナーに「そのようなドナーが数えられた」と書いて、対応するパパに入れました。余分なジェスチャーはありません！

Dropboxを支持するもう一つの小さなこと。私たちはどういうわけか、コンテスト期間中はクラスターを借りることを考えず、3台のラップトップを使用しました。私はi5で、ダミールはi3で、マキシムには別の古代のものがあります。そして、マキシムが彼のソリューションを開始したとき、他のすべてが減速し始めました。そして、ここでマキシムはビンからリモートサーバーを取り出します。もちろん、彼はクラスターではありませんが、自分のマシンの速度を落とすことなく、現在のソリューションのテストを組織化することができました。さて、競合が発生するリスクがあるリモートサーバーをプルおよびプッシュすることはお勧めできません（ターミナルで解決する必要があります）。そして、Dropboxはすでにそこにありました。すぐに言ってやった。短いセットアップの後、リモートサーバーはフルセットのテストでソリューションのテストを開始し、生成されたDavarをDropbox経由でマシンに自動的にドロップしました。美人！

この時点で、完全なテストスイートでのテストは完了です。ダワールをサーバーに送信し、上位3位に入ります。 Fhtagn！

それまでの間、私たちのソリューションで改善できることはまだたくさんあります。主に2つの方向があります：std :: mapをハッシュテーブルに置き換え、評価関数の計算を高速化します（O（フィールドサイズ）に対して計算されましたが、O（図の要素数）に対して計算できます）。ハッシュテーブルを作成し、ソリューションに固定します。また、評価関数に4番目のパラメーター、いわゆる「ポテンシャル」を追加します。これは、未完成のパワーワードのプレフィックスの全長です。これにより、移動の間に単語をさらに収集できます。22:30にすべてが準備できたようです。ハッシュテーブルでは、テスト14は3分の分と見なされます。

この間、マキシムはオーガナイザーのサーバーの「ハンマー」を作成して、新しいパワーワードを決定しました。その原理は非常に簡単です。

電力特性が疑われる単語のリストからソリューションを開始します。
, .
.
, .
«» .

一方、Damirは、ビジュアライザーで以前に取得したdavarを調べました。結局のところ、多くの空きスペースが私たちにとって良いテストでした-私たちのダイナミクスはそれを最大限に使ってパワーワードを埋めました。しかし、テストは悪いことが判明しました。十分なスペースがなく、フィギュアはあらゆる種類の複雑な形状であり、配置する必要があるフィギュアの総数は多かったです。私たちの愚かな評価関数は、どういうわけかそこにそれらを入れて、フィールドがかなり早く詰まったので、これらのテストでいくつかのポイントを得ました。特に、このようなテストは、4、9、13、および23番のテストでした。2回の小さな動きに対して誤算を固定することにしました。

新しいダワールを送信する過程で、トップ5の「プールをハックする」と「ループをハックする」という2つのチームに気付きます。そして少し決めるいたずらをするために ...私たちは「Hoop the poop」に改名されました。ここに、私たちのフーリガニズムの神格化があります。

公式のircチャットで、管理者の1人は「どのような不名誉ですか？」とinしていますが、禁止されていません。数時間後、それらはWILD BASHKORT MAGESに名前が変更されました。彼らは笑った-それで十分だ。

午前03:00 2つの前進を実装しました。実際、かなり早く書かれていましたが、いつものようにバグが発生しました。それらの最初の-今ではすべてが動作しているように見えますが、動作しません！最初、彼らは一般的にある種の悪魔だと思っていました。それから、私たちはばかだということに気付きました-2番目の動きのために、フィールドの上部に新しいフィギュアを作成する必要がありました。このバグが修正されたとき、動作しているように見えました。

しかし、それは何とかこのように機能しました：

: « , — ...». . : « , — ...». . , : « , !». , power-word'. « »: , - , , .

新しいソリューションは、4つのテストでさらに良くなりました。しかし、残念ながら、まだ完全ではありません。 Damirは、ビジュアライザーで初期ランダムシードのさまざまな値をチェックインすると、「ここでも、フィールドが詰まっています」と言います。私は確認します：「はい、フィールドは隅に散らばっており、そこから抜け出すことを恐れています。」私たちはまだ3つの手先をチェックすることを決めました。残念なことに、2歩先へのバスティングは既に決定を大幅に遅らせているため、さらに加速する必要があります。しかし、もう1つアイデアが残っています。評価関数の計算の高速化です。

私が2手先に進んでいる間に、Damirはテスト9を克服するためにヒューリスティックを思いつきました。このテストの本質は、安定してラインを収集し、可能であれば失敗しないレベルでより多くのスティックを投げることでした。私たちのソリューションは次のようなものでした：

同時に、可能性のある400のうち35回目の移動で崩壊しました。残念なことに、Damirはその夜遅くに機能するものを思いつきませんでした。

マキシムは、これまで、疑わしい単語を収集し、それらがパワーワードであるという事実についてテストしました。 03:00までに、6個または8個のそのような単語が見つかりました（以前に見つけた4個とともに）。並行して、彼はより多くの「魔法」の言葉を見つけて私たちのソリューションを立ち上げ、受け取ったダワールをサーバーに送りました。したがって、さらに3つの黙示録が合格しました。最後の大量テストタグは「apocalypse_4」でした。

午前3時の夕食後（今回は冷凍野菜+キノコ+粉砕されたソーセージがあり、すべてフライパンで一緒に加熱されていました）Damirは就寝しました（前夜はあまり眠りませんでした）そして、評価機能を高速化するために座った。

評価関数は、5時頃にO（フィールドサイズ）からO（図の要素数）に書き換えられました。Chased-より速いように見えるので、すでに3ターンでスイングを試みることができます。今日、私はもはや手を振る力がなくなり、3〜4時間寝ます。

4日目。最終スパート

私は午前9時から10時のどこかで目を覚まします。

マキシムは夜眠れませんでした（そして、コンテストが終わるまで起きているつもりでした）。夜中に、彼はさらにいくつかの「魔法の」言葉を見つけ、クトゥルフに何らかの関係があるウィキペディアの記事全体をほぼ解析しました。見つかったpower-words'ovの総数は10になりました。

えーい！

ヤゴト

ia！ia！

r'lyeh

ネクロノミコン

プラネット10

モンキーボーイ

ジョンbigboote r'lyeh

で彼の家で死んだクトゥルフは夢を待っています。

ヨーヨーダイン

残念ながら、コンテスト後に判明したように、これらの単語を見つけるアプローチは最後まで完璧ではありませんでした。たとえば、「Yog-Sothoth」という単語はハイフンが含まれていたため削除されました。「YogSothoth」（ハイフンなし！）がパワーワードであることが判明しました！一般に、マキシムは余分なハイフンを単に投げることに気づきませんでした。別のポイント：マキシムは「ランドリー」という単語をチェックしましたが、「ランドリー」という行には力がありました。また、「ph'nglui mglw'nafh cthulhu r'lyeh wgah'nagl fhtagn」で誤解が起こりました。このフレーズは「魔法のような」ものでしたが、何らかの理由でこの手順はこれを確認しませんでした。

夜でさえ、マキシムは5つの黙示録を費やして、10個の「魔法の」言葉を見つけました。

朝、ダミールと私が目を覚ましている間、マキシムはパワーエンジニアのために店に駆け込み（新鮮な空気の中を散歩しました）、最終的なジャークに十分な強さを持っていました。

作業は3つの方向に進みました：私はブルートフォース3の動きを書き始め、ダミールは9回目のテストのためにヒューリスティックで遊び続け（彼はいくつかの新しいアイデアがありました）、マキシムは以前のダバールをすべて解析し、各テストを選択するスクリプトを書き始めました/シード最大値とそれをすべて一緒にもたらします。

12:30頃に、Damirは最終的に評価関数の通常のヒューリスティックを作成しました。これはテスト9で非常によく機能します。さらに、Damirはソリューションの検索を2回開始するコードを作成しました。最初は新しい評価関数で、次に古い評価関数で。どちらの場合も、ポイントの数をカウントし、それに応じて、より多くのポイントがあるオプションを表示します。その後、DamirとMaximは最終的なtarballのレイアウトに切り替え、審査員向けのREADMEをゆっくりと書きます。

3ムーブの検索を14:00までに終了します。私はそれをいじらなければなりませんでした：プロセスをスピードアップするために、いくつかの最適化を追加します。さらに、3番目の移動の検索を少しカットする必要がありました（それ以外の場合は完全に禁止されていたため）。つまり、最も有望なブランチについてのみ3番目の移動をチェックします。つまり、最初に2番目の移動検索「アイドル」を開始し、3番目の移動を開始せずに評価関数の値を計算します。得られた値のうち、最大10個をふるいにかけ、すでに「戦闘中」の2番目の動きのソートを開始します。同時に、同じ約10個の最適な状態からのみ3番目の動きを試みます。

起こったことは、4番目のテストを非常にクールに解決します。ほぼすべてのオプションについて、ランダムシードは200から200の動きで解決策を見つけます。同時に、ビジュアライザーで受信したダバールを追跡することは非常に興味深い

ものでした。すべてがそれほど困難なく進むようです。マキシムはスクリプトを完成させて、最適なダバールを構築します。結合された最適なdavarはタグ「panopticum」の下に置かれ、サーバーに送信されます。

フルセットの最後のソリューションを開始します。締め切り（17:00）は約2時間です。

ここでいくつかの議論があります：実際には、どのソリューションをtarballに詰めるべきですか？あなたが今手に入れたものか、私たちが朝持っていたものですか？事実、新しいソリューションはまだテストされていないため、朝のソリューションとは異なり、+新しいソリューションは朝のソリューションよりも著しく遅くなっています。つまり、正常にテストし、最終的に仲良くなる時間がないというリスクがあります。そして、私たちが午前中に持っていたものは、すでにテスト済みの安定したリリースのようなものです。それでも、新しいオプションを用意することにしました。

それまでの間、新しいソリューションはテストされており、そのパフォーマンスから判断すると、期限までに解決しない可能性があることが明らかになりました。急いで、さまざまなマシンでさまざまなテストの計算をばらまきます。その結果、締め切りの1時間半前に、4、6、24を除くすべてのテストがカウントされました。実際、4と6のテストはフィールドサイズが小さいため、3ターン先に検索を開始します。さらに、それぞれに150または200の移動に対して50のサブテスト（さまざまなランダムシード）があります。 3手前の検索には1ターンあたり約1秒かかるため、たとえば、4回目のテスト全体で約3時間かかることがわかります。そして、私たちには3時間の時間がありません！ 24のテストでは、状況はわずかに異なります。テストは1つしかありませんが、非常に大きなフィールドがあり、1620が処理に移動します。これも約3時間かかります。

その結果、テスト6と24でスコアを付け、4番目のテストを5つのサブタスク（それぞれ10個のサブテスト）に並列化し、異なるマシンで数え、すべてを接着することにしました。すぐに言ってやった。数えます。午後4時頃（終了の1時間前）、Damir は過熱によりラップトップで死亡します。まあ、完全に死ぬことはなく、再起動するだけなので、5つの並列ブランチのうち2つが失われます。さて、何もすることはありません-ダミールは新たに枝を数え始めます。考慮されている間、Damirはラップトップを2つのメガネに置き、熱放散を良くするために気流を作り出します。16時20分までに、すべてが私たちのために数えられました、そして同時に。まあ、私たちにできることは、私たちのソリューションにはint64で多くの操作があり、Damirは64ビットLinuxを持ち、32ビットWindowsを持っています。

最後のdavarを送信し、tarballを完成させて送信します。数分後、マキシムはREADMEファイルで文法エラーを見つけて修正し、修正されたtarballを終了の1分前に送信します（最後に何かがあります）。

エピローグ

最後のdavarを送信したとき、資格表の2行目にありました。彼らのダバールがウナギを送って少し後に私たちを三行目に移動させました。

コンテスト終了後すぐに、そば鍋をシチューで調理しました（このレポートでは、コンテスト中の食べ物のトピックは完全に公開されていると思いますが、写真が十分でないことを除きます）。

リポジトリはgithubで見つけることができます（コンテスト中、彼は別のプライベートな場所にいたので、今はgithubに転送されました）。私たちのソリューション/ビジュアライザーを運転/研究することができます。下の表では、コンテスト終了後に知られるようになった18のすべてのパワーワードで実行されているソリューションの一部を見ることができます。

最後まで読んでくれたみんなに感謝します！

銀行のクトゥルヒ：ICFPC 2015の決定方法