Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

2014-07-30

ICFP Programming Contest 2014 感想など

15:44 | ICFP Programming Contest 2014 感想など - (iwi) { 反省します を含むブックマーク はてなブックマーク - ICFP Programming Contest 2014 感想など - (iwi) { 反省します ICFP Programming Contest 2014 感想など - (iwi) { 反省します のブックマークコメント

去年同様,適当に書きたいことだけ書きます.


チーム

去年と完全に一致です.今年は 6 人とも 72 時間参加.

今年もチームの持つ幅広い面での力が発揮でき良かった.あと,チームが ICFPC にだいぶ慣れてきてかなりスムーズになってきた.皆,自分が何をやれば良いのかや他人の好み・使える/使えない(使うことを拒む)ツール等を概ね理解している.


やったこと

言語の策定などの方針会議(全員)
  • 例年問題文は長いので問題を解読するのに時間がかかる(仕方ない).CPU 仕様が 2 つもある.
  • GHC (Lambda-man AI) 用のプログラミング言語の策定が最重要の議題
  • CPU 仕様を考えると Lisp にしたくなる(し実際に Lisp 系を採用したチームも多かったっぽい)ので弊チームでも Lisp という声は上がる
  • しかし C ライクのプログラミング言語を作ろうという提案があり,検討の末,そちらを選ぶ
    • メンバ(特に AI を書くことになるであろう岩田とチョクダイ)の慣れ具合からいって Lisp は多分作った後がヤバイ
    • C ライクな言語でもコンパイラ作業はそんなにやばくなさそう
    • C++ へのトランスレータを簡単に作れる仕様にしておけばインタプリタ無しで実行したりシミュレータと結合したりできる
  • プログラミング言語はチーム内で B と呼ぶことに決定した
    • 勿論 B という言語が昔存在したことは皆知っているので正式名称は B14 ということにした
コンパイラ(wata + iwi)
  • Lightning に AI を出すために最も重要な部品ということで集中的に開発するために岩田と俺でのペアプロで開発した
  • 岩田をメインコーダーとして Java で開発
  • 翌日午前 6 時頃にはだいたいできた
  • その後はちょくちょく機能追加しつつ使用
  • マシンの仕様を上手く活用してグローバル変数を実現したりした
    • 普通にやると,グローバル変数を置いた場所が何段親のフレームだかわからなくなるので LD/ST できない
    • 関数を呼ぶ際に毎回 LDF するのではなく,最初の init 時に全関数 LDF して RAP しておくと,親フレームが共通になるので,親フレームの変数をグローバル変数として用いることができる
トランスレータ(tos
  • トランスレータというか include すると B のプログラムがそのまま C++ でコンパイルできるようにするものを作ってもらった
  • これでライブラリ開発等が手元でテストできるようになったし,シミュレータと結合すれば爆速実行できるようになった
ライブラリ (tos + iwi)
  • 主にデータ構造などの共通のパーツを Standard B14 Library,略して SBL として提供
  • 初日に必要そうなものは一通り揃える
  • 間接アクセスがマシンに無いのでランダムアクセスのためのデータ構造として tree のアクセスコストが重要になる
  • というわけで 2 日目に俺が固定長(2べき)の tree のライブラリを再帰呼び出しを完全に展開したベタ書きアセンブラとして生成するスクリプトを書いた
    • get は一段 5 clk で処理できる(256 だったら 8 段なので 40 clk +定数ちょい)
    • set はもう少し複雑(葉にたどり着いた後で新しいツリーをまた構築しないといけない)で確か一段 12 clk
シミュレータ,評価システム (imos + sulume)
  • コンソールでコマンドを打ち込むとエスケープシーケンスとかの色付けを使ってコンソール上でいい感じにゲームが表示されて見れる
    • 公式の Javascript 実装は計算を結構行うラムダ AI を突っ込むととてもじゃないけど遅すぎてやってられない
    • 一方,我々の実装ではサイクルリミットぎりぎりの AI でも割と見てられるような速度で動く
  • 公式の Javascript 実装と動作を完全に一致させた(!)
    • 公式 Javascript のキャンバスの出力をキャプチャしたものをデータにしてそれと完全に一致するように自動でテストを行う
    • 公式の処理系は undocumented っていうかもうバグとしか思えないものが結構あるのでそれをわざわざインプリするという作業があったらしいw
    • しかし公式 JavascriptHaskell かなんかから生成されているっぽいので実際の評価も恐らく全く同じ環境で行われるためこれは有益
  • その後,適当にラムダマン AI やゴーストを比較するために一杯実行してデータを並べるシステムができた
    • イモスが多分また金に物を言わせて分散しまくってる(いい話)
ゴースト AI (chokudai → tos → iwi)
  • 初日は B コンパイラができるまでの暇つぶし?でチョクダイがグリーディに近づくものをとりあえず書いてた
  • その後トス先生がそれを少しいじって先回りするものを作っていた
  • 最終日気がつくといつのまにかトス先生もラムダ AI を作り始めていて誰もゴーストを更新してない
  • ゴーストもかなり重要だろうということで俺がゴースト担当に回ることになって色々いじっていた
    • 基本的にはグリーディに近づくのだけれどマンハッタン距離にちょっと手を加えると近づく速度が上がった
    • あとは食われないように逃げる,ID を使って若干の多様性を持たせて散開させる,ぐらいしかやる時間がなかった
ラムダマン AI (chokudai vs. wata vs. tos → chokudai + wata)
  • チョクダイの AI は周りを若干 BFS したりして見て評価関数や特別処理を激しく tweak している系だと思う(多分)
    • 結構いい感じに動いて敵からも逃げるしそこそこ取るんだけど取り残しが結構多くて大きな盤面になってくるとゴーストが弱くても全クリはできない
    • 特に,周りを少ししか見ないので,周りを食べ終わってしまうと敵が追っかけてきてくれたりしないと硬直状態になってしまって点が凄い低くなったりする
    • 試しに敵から逃げまくるゴーストっていうのを放り込んでみたらものすごく点が低かった
      • これ故に一時期は逃げまくるゴーストを提出するのが正解なんじゃという主張もチームの中で結構あった
      • 後述の通り対策が実装されると共にこれはやめた
  • 岩田の第一世代 AI は遠い薬への行き方も上手く把握して効率的な全クリを目指すもの
    • 本当は全体での BFS がしたいのだが計算コスト的にできない,ランダムアクセスのために log がかかるため
    • ので BFS の代わりに適当に伝搬させるアルゴリズムにより毎ターンちょっとずつ情報を更新する
    • 伝搬にすればリストをなめながらうまくやれば線形時間でできる
    • (ただし BFS も実はできたのかもしれない:https://twitter.com/wata_orz/status/494306461200027648
    • 結構きれいにごはんをたべる,ただし逃げたりは未実装なので敵に即食われる
  • 岩田の第二世代 AI は上の伝搬計算をローカルに限る代わりに敵の情報もそこに入れるもの
    • 敵から巧妙に逃げるしご飯も効率良く食べるのでかなり強い
    • が,計算コストがやばくてなかなかサイクルリミットに納められない,収めようとすると見る領域がかなり小さくなってしまって結果として弱くなってしまう
    • ギリギリまで粘ったが上手く行かず残念ながら諦めることに
  • tos 先生の AI は盤面の危険度をグローバルに評価する何らかの関数を作る感じだったっぽいが間に合わなくて断念っぽい
  • 最終 AI はチョクダイの AI に岩田の第一世代 AI を追加で組み込んで合体
    • 硬直状態っぽい感じ(長いこと点が取れない)になったら岩田にバトンタッチする
    • 岩田の AI でグローバルな視点によりご飯に向かう
    • ご飯を食べ始めたらまたチョクダイにバトンタッチ
    • (実は評価を行う暇なく提出したのだが,終了後に出てきた評価の結果を見るに)特に弱いゴースト相手での結果が凄まじく向上

感想など

何よりヤバかったのが最終提出.岩田が第二世代を諦め,それではバトンタッチ機構で行こうと決めたのが 20:00.岩田とチョクダイのバトンタッチ AI 最終版ができたのが 20:55.残りの 4 人で提出のための作業をできるだけ即座に行えるように構えていたが,俺が submit ボタンを押すころには 20:59 を示していて本当に手が震えていた.それまでに何度か提出を済ませてはいたが,バトンタッチ機構はみるみる進化して行っていたのでできるだけ最終版を出したかった.終了後に行った最終的な評価結果を見ても性能は明らかに向上していたのでチーム全体の最後のこの頑張りは報われたと思う,本当に良かった.(ま,もっと早く判断しろっていう話は勿論ありますが,第二世代も結構行けそうだった(し行けてたら明らかに超強い)から難しい判断だったし,結果オーライってやつです.)

ライバルであるチョクダイと岩田の AI が最終的に力を合わせお互いの欠点を補いあうって少年漫画的な展開で燃えますよね.

最初は若干劣化マラソンの年に見えなくもなかったけど,なんやかんや結構面白かった.普通に良かったと思う.変わった CPU 仕様や計算資源への絶妙な制限が普段と違う考え方を要求してくるのが(辛かったけど)やっぱり面白いんだと思う.あとこれは毎年 ICFPC に共通だけど,普通のプログラミングコンテストは AI なら AI を書くだけで終わるが,AI を書くためのツール(e.g., コンパイラ, 評価システム)の能力やそれを作るまでの時間というのがどのぐらいの AI を書けるかに寄与してくるっていう総合力勝負っていうか多階層っていうかそういうところがやっぱり楽しいなって思う.

いろんな要素がある年はやっぱり人数(及び人材の能力の幅)が効く.6 人を超えるといろんな面で破綻すると思うし,今年もチームは極めて最善に近かったと思う.個人的には今年はいろんな貢献ができてよかった.コンパイラ(Java)もオリジナル言語(B14)もシミュレータ用ライブラリ実装 (C++) もラムダマン AI アセンブラ(GHC)もゴースト AIGCC)もそれらを生成するスクリプト(Ruby)も触ったのでかなり色々やった.AI にも自分のアイディア(伝搬)も入ってるし.(まあ個人参加の人は当然全部やるわけだけど)

結果には正直去年ほどの自信はないけど,それでも結構期待してます.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/iwiwi/20140730