ICFP Programming Contest 2013

今年ものとがわさんパンピーやった(1年ぶりn度目)


問題はここ.64bit非負整数に対する限られた関数と単純なlambda式からなるプログラムがコンテストサーバ側にいっぱいあってIDが付いている.サーバ側にある各プログラムの具体的な形はわからない.プログラムは全て 64bit非負整数->64bit非負整数 の型を持つ.サーバ側には

  • myprograms: プログラムのサイズや含まれてる関数などの一覧を取得するAPI
  • eval: あるIDのプログラムに,指定した入力を適用したときにの出力を一度に最大で256組取得するAPI
  • guess: あるIDのプログラムはコレじゃないの?と回答するAPI

などが用意されており,解きたい問題をmyprogramsから選んでevalでブラックボックスに入出力ペアを取得し,プログラムを推定して最初のevalから5分以内にguessする.正しければ1点ゲット.

  • train: 練習用のプログラムが得られるAPI

もあり,一応テストできるが,trainも含めAPIには1チームあたり20秒あたり5回までというアクセス回数制限がかかっている.

割と誰でも手をつけやすい敷居の低さで,しかも難しいものは難しく,それに対処したときの効果もわかりやすい.大きな難易度幅を持ち,参加者の思考を促すようなとても良い出題だったと思う.APIのアクセス回数制限によって,時間を消費させつつもできるだけ早くアイデアを形にしなければならないという煽りも秀逸.ただ多くの参加者が思うようにleaderboardが無い理由だけはよくわからなかった.

言語はHaskell

結果はこんな感じ.

リポジトリここで,コンテスト中に書いた分はだいたい以下の通り.

   53   235  2038 ./BV-proxy/main.hs
   49   286  1668 ./language-BV/Language/BV/Eval.hs
  155   967  5760 ./language-BV/Language/BV/Syntax.hs
  627  3510 26420 ./BV-infer/main.hs
  884  4998 35886 合計

1日目

問題を読んで,うーんこの.と思いながらとりあえずASTと評価器を作る.Haskell.特に問題無し.プログラムにはfoldがいっこしかないとかなので,"foldを含むかどうか",と"fold内にある式なのかfoldの外にある式(もしくはfold)なのか"をGADTsでタグ付けしたりTypeFamiliesとか使ってたりして型で区別しておく.これでプログラムにfoldを2つ埋めてしまうとかイロイロとミスできなくしておく.Eqとか後述のArbitraryのインスタンスにするとかが困る感じになったがまぁそのへんは雑に.

次に肝心のプログラム推定器だが,じゃあまず「運ゲー状況作るか!」といきなり思考停止.画面見ない勢の本領発揮.

おもむろにASTをTest.QuickCheck.Arbitraryクラスのインスタンスにして同じくTest.QuickCheck.sample'でランダムサンプリングしたプログラムがたまたまevalの結果と正しいかどうかをチェックしてguessするようなものを書いた.あるサイズ以下のプログラムをランダムに生成させたかったのだが,Arbitraryは型からしか情報が取れないので,手っ取り早くunsafePerformIOでIORefに「今解いてる問題の情報」を持ってしまうことにした.どうせアクセス回数制限と5分時間制限のせいで,複数の問題を同時に処理するつもりは無くなってたため,このunsafeはまぁそんなにunsafeじゃないだろうと.これで小さいプログラムに対しては大体解けるってくらいの運ゲー感.2日目3日目でコイツが大きなサイズをたまたま解いてる!?のを見るとかなり得した気分になる程度.

全体としてはシンプルでソルバを起動すると,

  1. myproblemsで問題を全部取得
  2. 解けそうなやつを選ぶ
  3. evalで人口的に適度にビット立てた256入力に対してサンプリング
    • ビット演算が主だったのでビットの位置関係に配慮した
  4. この256サンプルを満たすものを求める
  5. guess

で最後までこれはほぼ変わらない.毎回myproblemsするのも効率悪いけどマシン複数台使ったりとかそんなリソース無いし,これでもザックリ1時間で最速300問処理れるからまぁいいかなと.ゆっくりしていってね

とりあえずコレをmyprogramsの小さい問題やtfoldの問題を選んで回してlightning用とする.まだこの時点でアクセス制限対策は無く,1問トライしたら20秒待つという雑な仕事して夜は寝る.ただ変に回っちゃって易い問題を失敗で消費してしまうのも怖いので何かエラー想定外状況時はそこで見切りを付けて終わり.案の定起きたらmissmatchで止まってた.

2日目

さすがにちょっと運ゲーだけだとダメだよなーと少し真面目になる.反省

guessの結果がmissmatchだったらその反例も加えて再度ブン回す処理を追加.

あるサイズのプログラムを全列挙し初める.ただし探索するときは問題に与えられたサイズ以下のプログラムを小さいほうから探索する.1日目に運ゲーでtrainやmyproblemsを解いてるとき,

  • 問題のプログラムには無駄な演算が入っていることが多々ある
    • サイズや演算が必要最小限よりも大きく多くなっていることが多々ある
    • 2日目終わって寝てる間にヒントとして公式にアナウンスされた
  • 別にサイズや演算が同じでなくても同じ結果を与えればスコアになる

ことは気付いていたので,小さいプログラムで済むならそれが速い.演算の性質も鑑みて適宜枝刈りも入れていった.結局この全探索と運ゲーに加え,5分のタイムアウトをControl.Concurrent.Asuncで並列化.

パワーが足りなくなってきたのでVMへのリソース割り当てを増やす.メモリ8GB,8コアからメモリ32GB,12コアへ

また,20秒待つとか雑なコントロールを廃止し,アクセス制限対策のコントローラを書いて推定器とコンテストサーバの間に入れた,と言っても普通のサーバに20秒(安全のため+数秒してるが)で復活するリソースを5個持たせ,それがひとつ取得できるまでは接続されても何もせず待ち,取得できたらプログラム推定器からの通信をコンテストサーバに横流しし,コンテストサーバからの通信内容を推定器に横流しするだけ.STMモナド無い言語でこういうの書く気もうまるで起きないのですが皆様いかがお過ごしでしょうか?

おもむろにこのエントリを書きはじめる.

イロイロ微調整したりしてると夜になったので走らせて寝る.起きたらサーバから "Unable to decide equality" 出てきて止まってた.なんだこれ.

3日目

3日目開始あたりで11位から50位がスコアレンジ300-550にいるとのアナウンスが.あれ?案外点数低そう?上はもう1000余裕みたいな感じじゃないの?とか思ってた.

bonusとかいうのが出てていかにも重そうだったのでひとまず無視するコードを追加.

最終日だし翌日昼間の仕事もあるので休暇をとらねばと,何かエラー出ても無視するようにしてひたすらブン回しておき,自分はニコ動を見たり暑い中蛍光灯を買いに出たりといった功夫を積んで過ごす.マスターオブライフ

そろそろbonus以外の問題ひととおりトライし切るかなと思ったあたりでbonusについて考え初める.bonusの特徴は(lambda (x) (if0 P T F))に決まってるっぽかったので,まずは1問に対するevalの回数を増やし,決め打ちの256+ランダム256*3の1024サンプル取得するようにした.まずはT(もしくはF)の候補Eをサイズ1から生成していって(lambda (x) E)でサンプルを処理してみる.先頭がif0ということは,あるプログラム(lambda (x) E)が1024サンプルの半分以上をパスするのであれば,このEはT(もしくはF)の候補に価すると判断する.今度はパスしなかったサンプルだけかき集めて,これらを全て通すようなF(もしくはT)候補を求める,あとは(if0 E T F)か(if0 E F T)となるようなEがあればこのEをPとみてguessを投げた.これは30未満のbonusをサクサク解いていってくれた.さすがに31以上はキツいのかタイムアウト多い.

夜になったのでこれをブン回して寝る.朝起きて出社前にプログラム止めて最終スコア確認.bonusはbonusだけあってそれなりにおいしかったようだ.

やったことメモ

  • foldの含有,fold内外をGADTで型制約
    • ArbitraryとGADTスゲー相性悪い感があるけど自分だけですかね?
    • あとEqにも困った
    • 上手く使えてない感,反省
  • アクセス数制御対策のproxy
    • 作成中のサーバ用ライブラリがあったので,50行くらいで
  • プログラム中の変数はx,y,zだけ
    • fold が無い場合,式中の自由変数は高々1個(x)
      • プログラム先頭のlambdaが束縛する分
    • fold が有る場合,fold外の自由変数は高々1個(x)
      • プログラム先頭のlambdaが束縛する分
    • fold が有る場合,fold内のlambda内の自由変数は高々2個(y,z)?
      • プログラム先頭のlambdaが束縛する分(x)は入ってこない?
      • この制約は記述がたぶん無かったがtrainをいくら引いてきてもそうだったので決め打ち
    • tfold には shadowing があるので2個(x,y)
  • プログラム生成順序
    • 解こうとしてる問題サイズより小さいものから生成
    • fold > if0 > op2 > op1 の順に先頭への出現優先度 (気分)
    • 二項演算と単項演算については,できるだけ適用先でなく演算のほうが入れ変わるように (気分)
  • プログラム生成時の枝刈り
    • not . not
    • (and/or/xor) E E
    • (not以外のop1) 0
    • op2 0
    • if0 (0/1) T F
    • if0 P E E
    • shr*が適用され続けるときはshr1→shr4→shr16の適用順に正規化

やれてなかったことメモ

  • プログラム生成時の枝刈り
    • op2 a b と op2 b a を同一視する
      • なぜやってないことに気付いていなかったのか…
    • size nのプログラムを作るときにsize 1のもの(0/1/x/y/z)を含んでいた…
      • bonusやってるときに気付いて刈った
      • bonus以外は刈ってないものでやってしまった
      • どういうことなの?これものすごい計算無駄にしたのでは…

やらなかったアイデアとか

  • サイズ大きいプログラムは予めデータベース化しておく
    • 以下の情報を持たせてクエリできるようにしておく
      • サイズ
      • 含まれる演算
      • 決まった定数個のサンプルに何を返すか
    • 枝刈りwith全生成の質にもっと早く納得できればやってみたかも
  • モンテカルロ木探索的な生成
    • "有力な枝"を決める基準であまりよいものができなさそうだと感じた
  • GAやSA
    • "良いやつを少し変更したものも同じくらい良い"ような気があまりしなかった
    • 5分で辿り付けるかが疑問だった