ICFP 再考前編 - 純粋関数型雑記帳

来年度のFirst Prize獲得(?)に向けてちゃんと復習をしておこう…
まず、各々の強さの分析を。
(result等は昨日の日記を参照されたし)

resultのページには得点で成績が書かれているので、これを勝敗数にしてみる。
各蟻の評価は、361匹による総当たり戦、それぞれ100個のマップで戦い、
それぞれの位置を変えてさらに戦う。(結局一匹相手に200回戦う)
勝つと2ポイント獲得。負けると0ポイント。引き分けると両者が1ポイントを獲得する。
360匹相手に200回づつ戦うので結局72000回戦っていることになる。
引き分けがあるので、正確な勝敗数は分からないが、引き分けをとりあえず
高々1ということにして計算してみた。

Dunkosmiloolump-1    71073 勝  926 敗 1 分
Dunkosmiloolump-2    70973 勝 1026 敗 1 分
Fractionless Bananas 69153 勝 2847 敗 0 分
haskilled            68809 勝 3190 敗 1 分
anichkov             68490 勝 3510 敗 0 分

づんこの勝率はほとんど9割9分に近く、やはり圧倒的な実力であることが分かった。
うちの蟻は何発入れることが出来たのだろうか…。
ところで、resultの表にApproachという欄が有る。
higherとか、preとか、書いてあるところである。
下のほうを見ていくと、mutとかhandとかがあることに気付く。
一応、確認できるものを列挙すると、
higher pre mut hand oth unkn …が有るようである。
hand…は、手書きか。
mutは語感から言って遺伝的アルゴリズムだろう。
othはothers,unknはunknown,
ということはhigherは高級言語、preはプリプロセッサか。

と、それを踏まえて、結果を見てみる。
まず、Lightning Division。うちはシミュレータを作るだけで
一日以上かかってしまったのでこれには提出してないんだけど…
一位のところがhigher、二位以降がずらーっとpreで続いている。
使用言語は、Perl,Ocaml,Ruby,Perl,Scheme,…と。
なるほど。この辺の言語は高速プロトタイピングにはやはりそれなりに有効なのかな?
我らがHaskellは…21位のTeam Lone Haskellerがトップと。
(一人ぼっちのHaskell使いとは…泣けるなぁ)
と、それはいいとして。
意外だった、Lightning Divisionですらhandは良い成績を残せていない。
今回の問題、手書きは駄目だったようである。
手書き解は全体を通しても、C++の25チーム、Ocamlの24チームに次いで
23チームが採用と、採用者自体はとても多いのだが、
どうやら、安易に手書き解で出してしまう人が多かっただけのようである。
アプローチのほうは、トップのRedTeamがhigherなのでなんともいえないが
それ以降のチームがほとんどpreなので、preのほうが平均的に
良好な結果が残せるかもしれない。
しかも、RedTeamはhigher採用しているといっても、チーム人数が7人と大所帯で
物量作戦が使えるので、その辺を考慮すると小規模チームにおける参考にはならないかもしれない。
2、3人で戦う場合、やはり24時間以内でシミュレータ作成、
高級言語コンパイラ作成、蟻実装は難しいのではなかろうか。
単純なプリプロセッサをちょちょいと実装して蟻を頑張って
でっち上げるほうが何とか成る蓋然性が高そうだ。

次に本題、Main Divisionのほうである。
今度は先ほどの結果とはうって変わってアプローチはhigher一色となる。
上位30匹中、higherが24匹、preが6匹となっている。
preの最上位は7位でThree-headed monkeyチームのもの。
ちなみに、このチームはLightning DivisionでPreを採用したチームのうちで
順位的に一番踏みとどまったチームである。
使用言語もこれまた先ほどとはがらりと変わり、
Haskell、C/C++、が上位のほとんどを占める。
OCaml,Perl,Python,Scheme,Lispがその合間をぽつぽつと。

まず、分かりやすい、アプローチによる考察から。
これは制限時間が3日ともなると、プリプロセッサと高級言語の間に
生産性の差が生じてくるということであろう。
要するに24時間という厳しい時間制限でとりあえず何か
作らないといけない場合、言語設計に時間を割くよりも
貧弱な(?)言語で蟻そのものを作る時間を増やすほうが良好な結果が出せて、
全体の時間がそれなりにある場合は言語設計にもそれなりに時間を割いた方が
絶対的には良好な結果が出やすくなるということであろうか。
しかしまぁ、うちのチームはおそらくpre→higherというように途中で変わった。
というよりも、私がどんどん蟻言語を機能強化していき、
某M君は刻々と変化する蟻言語で蟻実装を…という感じで。
まぁ、なるべく変化による負担は無いようにはした…つもりではある。
結果的にhigherが上位のかなりを占めているということから、
最初preでやっても、途中で言語の強化にも多少の時間を割いたほうが
結果的に良いものを作れた確率が高かったということだろう。

higherとpre以外、
例えばmutは今回の問題ではイロモノだったようである。
M君も少しmutでチャレンジしたらしいが、体系的に
強い蟻を生成することには成功しなかったようである。
(一応別チーム名で送ったようだけど…あんまり強くないね)
handはhigher>preと考えるならこれまた論外である。
othの人はどんなアプローチなのだろうか。結構気になる。
othは一チームしかいない上に全然強くないのだが…

次に、先ほど置いておいていたMain Divisionによる言語間の差異を考えてみる。
Lightning Divisionで猛威を振るった(?)スクリプト言語を振り払い、
HaskellとC/C++が上位を占めている。これはどうしたことだろうか…。
Lightning DivisionでトップだったRedTeam以外のLightning Division
の上位チームは大体preを採用している。
で、Main Divisionでは上位にランクインするにはhigherのほうがラク?
だったようである。Lightning Divisionでわりと上位にいた蟻も
preの縛り?によりことごとく順位を落としている。
やはり蟻の絶対的強さを上げるためには言語の支援が必要だと。
私の適当な予想だと、Perl、Python、Scheme、等の構文解析があまり得意ではない言語
(かどうかはよく分からんです…よく分からんのにこんなこと書いちゃいかんわな…)
においては、高級言語コンパイラを作るのが多少大変なのではなかろうか。

その点では、Haskellはおそらく最強クラスに入る。
パーザコンビネータというアイデアは柔軟性、記述の容易さともにすばらしい。
C++においてはC++そのものの力というよりもyacc/lexといった
超定番パーザジェネレータの存在が大きいだろう。
それ以外なら、OcamlはOcamlyacc/lexがあったような気がするし、
これも普通のyacc/lexと同様に使えたはずである…がOcamlが
ふるっていないのはこれいかに。(不調?)
Perlは正規表現でがしがし…は明らかに力不足。
でも、構文解析ライブラリがあるらしい…?
(ごめんなさい…Perlあんまり詳しくないので詳細は知りません…
PythonもRubyなどにもライブラリありますね…)

で、結局のところなにが言いたかったのかというと、
今回のは、higherな…あるいは十分にリッチなpreなアプローチ
(…をhigherというのか?)をとりやすい言語が有利だったのだろうか、ということで、
そうするとHaskellとC++、おおよそかけ離れた言語が
今回の2強の言語になっているのもそうそうおかしな話ではないのかもしれない。
(いや…おかしいか…?)

長々とよく分からない話を展開して来たが、
ここでいきなりHaskell限定の話に切り替え。
Haskellでのhigherアプローチの方法論を考える。
考える…というか、これに参加した当時の私には
文法設計〜コンパイラ作成、の流れがほとんど自明な
手法だと思っていたのだが、トップチーム、づんこのとっている方法、
あるいはHaskell標準の数々のコンビネータライブラリを考えると、
もっと別なやり方で高級言語を設計できることに気が付いた。
(気が付くも何もあらへんけど…)
というわけで、Haskell特有のその辺の話を次回に。
(いや、Ocamlでも出来るのかな…。あるいはSchemeでも…。
まぁ、その辺はどうでもいいや)