ICFP Programming Contest 2025におけるAIツールShinkaEvolveとの協働
我々チームUnagiはICFP Programming Contest 2025にて優勝することが出来ました。今回、私はこのコンテスト中に勤務先Sakana AIが開発するAIツール「ShinkaEvolve」を活用することを試みました。この記事では、ShinkaEvolveがコンテスト中に我々にどのように貢献したかを説明します。
ShinkaEvolveは我々の解法の中核である問題のSAT式へのエンコーディングを大きく改善し、解法全体を大幅（〜10倍）に高速化し、大規模な問題を最適に近いステップ数で解くことを可能としました。また、そこでShinkaEvolveが与えた知見が、その後に人間が設計した別の解法でもチーム内で活用されました。
（この記事は会社のブログリリースの元となった原稿です。会社からの許可に基づき、個人のブログ記事として投稿しています。）
ICFP Programming Contestとは
The ICFP Programming Contestは世界で最も有名なプログラミングコンテストの1つです。CodeforcesやAtCoderと異なり、ルールがほぼない点がユニークで、何人のチームでも、どんなツールを使っても、どれだけの計算資源を利用しても構いません。また、コンテストの問題が他のアルゴリズム系コンテストと比べて複雑であり、多面的で総合的な技術が求められます。
今年の問題
今年の問題は「歩き回って得られる曖昧なヒントを頼りに、未知の迷路の正確な地図を作り上げる」という問題でした。複数の問題があり、各問題はなるべく少ない回数の探検によって解けるほどスコアが高くなります。
我々は最終的にSATソルバーを中核に用いた解法を作成しました。SATソルバーは論理式を受け取り、その論理式を充足する変数割当を見つけるソフトウェアです。SATはNP完全ですが、現代的なCDCL-based solverは非常に効率的であり百万変数の問題を解けることもあります。そのため、様々な問題をSAT論理式に定式化し、SATソルバーを適用し解く、ということが行われています。
今回、観察により、極めて少ない回数のクエリによって問題が解けるであろうことが分かりました。全ての情報を1つのSATにエンコードしなるべく一括で解くことができれば、得られた情報を一切無駄にせず同時に活用することが出来ます。そうすれば、最適値に近いクエリ回数が達成出来るため、これが上位を取るために必須であると考えました。ICFP-PCは他のコンテストと違い利用物にルールがないため、普通のプログラミングコンテストよりも広い視野で、現実世界の問題解決に近いアプローチを考える事ができるのが面白い点です。
SATエンコーディングの重要性
一般に、SATソルバーを利用し問題を解く際、どのように「その問題をSATの論理式にエンコードするか」がSATソルバーが効率的に解けるかどうかを大きく左右することが知られています。
同じ問題をSAT式にエンコードしても、素朴なエンコード方法ではSATインスタンスのサイズが大きくなってしまい、ソルバーが解けない可能性があります。一方で、サイズを小さくすることが第一目標ではなく、SATソルバーの仮定や発見を伝播しやすくなる節や、重要な変数での分岐を促す変数は、むしろ追加によりSATソルバーを助けることになります。そのため、現実世界の問題をSAT式にエンコードすることは、知識と創造性と試行錯誤を要求するタスクです。
今回のICFP-PCの問題も、そもそもSATに正しくエンコードすること自体が非自明であり難しいことでした。チームメイトの1人がそれを完成させましたが、大きい問題に対してはSATソルバーが十分な速度で解くことができませんでした。
ShinkaEvolveによる試行錯誤
そこで、「SATソルバーが解くのにかかる速度」を目的関数とし、我々のコードベースのメインロジックであるSATエンコーディングの部分に関して、ShinkaEvolveを用いたLLMによる試行錯誤と最適化を自動的に行いました。
チームメイトのwataが完成させた最初のバージョンを初期解としました。ShinkaEvolveは320回の試行を行い、合計コストは $60 程度でした。
ShinkaEvolveによる高速化
試行錯誤の過程では、おおよそ6倍の高速化が達成されました。試行錯誤を高速に行うため、中規模の問題（具体的には部屋数18）での速度を測定しながら高速化を行わせました。人間が書いたものが2.86秒かかっていたものを、ShinkaEvolveは0.44秒まで縮めることができました。
更に素晴らしいのが、この高速化が、より大規模で高難度なケースに転移したことです。より大きな部屋数24のケースでは、元の解答が127秒だったものを、13秒に高速化することができました。これは10倍近い高速化です！そして、更に大きな部屋数30のケースでは、今まで一度も解き切ることができなかったのが、たまに現実的な時間で解けるようになりました。
これは即座に利用可能な結果であり、ShinkaEvolveで得られたコードをほぼそのまま投入しました。そのコードは少しずつ編集されながら、半分程度の問題で最終的な解法にそのまま貢献しています。
ShinkaEvolveの発見
更に興味深いのが、そこでShinkaEvolveが与えた知見が、その後に人間が設計した別の解法でもチーム内で活用されたことです。
ShinkaEvolveが作成したプログラムに含まれた改善・変更は何点かありましたが、特にそのうちの1つの「どのようにグラフ形状をSATで表現するか」は重要でした。もとの問題では「各頂点の各ドアはどの頂点のどのドアに繋がっているか」という変数のみを用い直接的に定式化していましたが、ShinkaEvolveはそこに「各頂点の各ドアはどの頂点に繋がっているか」のみを表す変数を追加しました。これにより、変数は増えるものの、節を減らすことができました。更に、この変数はSATソルバーの探索を助ける作用があるようです。一般に、元の問題の性質として重要な意思決定を1つの変数で表現すると、その変数を用いてSATソルバーが分岐することが出来るようになるため、問題を効率的に探索できるようになります。今回の問題でも、「どの頂点につながっているか」を決められれば「どのドアに繋がっているか」は後から比較的カンタンに決められるという性質がありました。そのため、「どの頂点につながっているか」だけを表す変数を追加することが、SATソルバーの探索を手助けする効果があるようでした。
この定式化のアイディアは汎用性があり、その後に拡張版問題を解くための解答プログラムを人間が作成した際にも、グラフに関する制約の部分についてはこのアイディアを利用しました。
終わりに
今回はShinkaEvolveの貢献に焦点を当てるために簡潔な説明をしましたが、実際にはコンテスト全体にはより多くの要素がありました。例えば、迷路内の探索プランをヒューリスティクスを用いて改善したり、「ラッキー」な状況のみに挑戦し「アンラッキー」な回をスキップする効率化を実装したり、協力や分析のためのプラットフォームを実装したりということをしました。多くの要素を総合的にうまくこなすことで、我々のチームは良い成績を達成できました。
素晴らしいコンテストを開催して下さったコンテスト運営の皆様、ShinkaEvolveを開発したSakana AIの同僚たち、開発中のShinkaEvolveを利用するアイディアを受け入れてくれたチームUnagiのチームメイトに感謝します。
ICFP Contest 2024 参加記
後から読んでどんな回だったかを思い出すための自分用のメモです。
概要
テキストを送るとテキストが返ってくるHTTP APIが提供されている。ICFP languageというラムダ計算っぽい簡単な言語で書かれたプログラムを送りつけると、向こうでプログラムが実行されて、文字列にされた上で、解釈される。例えば get index で現在自分が取り組めるタスクのリストを得たり、 echo hoge でそのまま hoge を返してくれたり。タスクは hello, lambdaman, spaceship, 3d, efficiency の5個がある。
やったこと
最初は主に新しい問題を発掘するために、作業に必要なツールを作りつつ、あれこれガチャガチャやっていた。 色々やった後、efficiencyを担当することになり、efficiencyをほぼ全問やった。Lightningが終わった後はlambdamanで線形合同法でランダムウォークしようぜというアイディアを考え実装したところかなり強かったため、基本それの周辺のことばっかりやっていた。
Efficiency
GPT4oくん達がかなり最強だった。チーム内にあるHaskellっぽい記法に直すツールをかました後でGPT4oくん達に読んで貰うと、大体どういうプログラムか理解してくれる。計算結果も考えようとしてくれるが、そこはだいたい外れる。細かいところをチェックしつつちょっとプログラム書いたりググったりするだけで大部分が解けた。最後の方のSAT, SMTは全部z3で解いた。数独だとは気づいたけど数独であることを使う意味は特に感じれれず。
Lambdaman
元Herbertガチ勢のchokudai先生がランダムウォークについて色々と考察し、連続した前進が出やすいなどといった「強そうなランダムウォーク」を実装しようとしていた。それを聞きながら、とりあえずもっと単純で短く書けそうなランダム解として線形合同法を書いてみたところ、これがなかなか強かったので、ランダムは基本的にこっちにシフトした。
+ 定数 の項は落とす、定数は可能な限り桁数が少なくなるようにする（特に初期値や係数や終了条件を1桁にする）、2倍で線形合同法する（2ステップ移動が必要なもののみ）、後置の再帰にすることにより終了条件に solve lambdaman を直接埋め込む、などといった気づきによりコードを短く出来た。ただし、Yコンビネータを直接利用しないほうが短くなるという点には気づけなかった。残念。
fn gen_step2(problem_id: i64, lcg: &LCGConfig) -> String { let a = lcg.a; let dm = lcg.m * 2; let dx0 = lcg.x0 * 2; let dxt = lcg.xt * 2; format!( r##" B$ B$ Lf B$ Lx B$ vx vx Lx B$ vf B$ vx vx Lf Lx ? B= vx {dxt} "solve lambdaman{problem_id} " B. B$ vf B% B* vx {a} {dm} BT 2 BD B% vx 8 "RRDDLLUU" {dx0} "## ) }
ちなみに、後置にした後も、逆元を使えば前向きにシミュレーション出来る。そっちのほうがちょっと速い。
3D
切り込み隊長だったので1を手動で解いたが、凄く辛かった。でも、問題としてはめちゃくちゃおもろいと思った。こんないい感じの言語、よく作れるなあ。
Lightningが終わった後、1をみんなでショートコーディングしてたけど、そこだけでもなかなか面白かった。右上3x3マスの、階上の掛け算と提出の分岐がキレイに融合しているところが気持ちいい。あと、余ってる場所に1や2の場合の答え埋め込むのもおもろい。
solve 3d1 . . . . 1 > . . . < A * . = -1 + . A . v S . . 1 = S . . -2 @ 3 A 1 @ 4 . 2 2 = S 2 .
他にも色々と面白い事があった気がする。例えば >>>> みたいなのを作ると勝手に遠くまで移動できて、これを使うと普通には難しい回路の立体交差が出来たりする。
Hello
hello はチュートリアル的な感じ。全チームチーム満点を取るので差がつかない。
最後のlanguage testは、複雑なICFP languageをこちらで実行した結果を返さないといけない。echo を使うと「自分で実行しろ」と怒られるのだが、tos先生が適当にいじったところフィルタを回避し答えが得られてワロタ。結局、ICFP languageの処理系はこれ以降の問題ではいうほど重要ではなかったため、language testをこれでやり過ごして後は echo とかうまく使ってやっていくのが正解だったと思う。
感想
新しい問題をどんどん開放していくワクワク感や、スコア設計によりどんどん新しい問題に取り組まないといけない忙しさなど、Lightningまでの間は神回だったなと個人的には思う。それ以降については、良くも悪くもいつも通りのICFPCの枠組みという感じではあったが、いつも通りのICFPCの中でも割と質が良い方だったと思う。オーガナイザの方々、素晴らしいコンテストをありがとうございました。
Preferred Networksを退職しました
2016年から約7年弱勤めたPreferred Networks (PFN)を退職しました。6/1より次の職場で仕事を開始します。次の職場については6月以降気が向いたときにTwitterかどこかに書きます。
PFNはどうだった？
PFNでの日々は、一言で言うと最高でした。技術的にも立場的にも多岐にわたる経験をさせてもらいました。そして、何より、めちゃくちゃ楽しかったです。PFNで働けたことは幸運で、心から感謝しています。今後も他の人に相談されたら多くの人に勧めると思います。
PFNでの思い出を色々書きたいのはやまやまなのですが、とても長くなりそうなので、別の記事にしようと思います。
では、なぜ転職するのか？
Generative AI
Generative AI (LLM, 拡散モデル)の最近のブレイクスルーに大きな衝撃を受け、Generative AI分野の研究開発に、私にとって一番望ましい形で関われそうな環境で仕事をしたいと考えるようになりました。
それにはいくつかの理由があります。まず、大きな社会的インパクトが期待できることや、技術的に面白いことは、当然挙げられます。それに加え、私は現在のこの分野のような状況での仕事が恐らく（自分の中で）かなり得意ということもあります。このような状況は今後の人生でそう何度も訪れるものではないだろうし、ここから数年の時間を後悔なく過ごすためにはリスクを取っても良いと考えました。
会社のフェーズ
PFNでの経験は常に素晴らしいものでしたが、その中でも私にとって特に一番楽しかったのは、やっぱり転職直後の数年間の時期かなと思います。
PFNは既に10年近い歴史を持ち、多岐にわたるプロジェクトや人材を有する大きな組織に成長しました。これだけ会社が続き、色々なものを築き続けて来たことは、本当に素晴らしいことです。しかし、そういった今のPFNが抱える課題や成長のために必要なこと、そしてそこから割り出される各々に求められるものを考えると、初期と比べ、企業としての焦点も変わってきており、求められる能力と私の強みとのギャップも広がってきたと感じます。
これは、決して会社が悪いように変化したという意味ではなく、自分の能力や嗜好の幅の狭さ、適応能力の低さに起因するものだと思います。また、そういったことをごまかさず、自分の得意不得意や好みを直視し素直に向き合っていこうと考え直した、という個人的な変化もあります。
経験社数
アカデミアを出て以来、フルタイムで勤めた会社はPFNが1社目です。昨年、機会に恵まれ知人の会社を何個か手伝わせてもらったこともあり、会社によって想像以上に色々な違いがある、ということを改めて認識しました。
今までもある程度意識してきたつもりではありますが、コンフォートゾーンを適度に抜け出すということはやはり自分にとって重要であり、あまり強い理由がなくてもそういった良い機会かなと思いました。
おわりに
関わりのあった社内外のすべての方々に、心からの感謝を述べます。PFNでの経験やそこで培われた皆さんとの関係は、私の人生において大切な宝物です。そして特に、代表取締役の西川さんと岡野原さんには深い感謝の意を表したいと思います。彼らのリーダーシップとビジョンは、常に私の挑戦の原動力となっていました。そのような素晴らしい環境で働くことができたことを、誇りに思います。
今後もPFNのことを応援し続けるつもりです。今まで本当にありがとうございました！
書籍「Kaggleに挑む深層学習プログラミングの極意」発売します
共著で執筆した書籍「Kaggleに挑む深層学習プログラミングの極意」が明日(2023/2/2)発売するのでそちらの紹介です。既に書店によっては店頭に並んでいるようです。
https://www.kspub.co.jp/book/detail/5305133.html https://bookclub.kodansha.co.jp/product?item=0000323307
どんな本？
Kaggleを題材に深層学習の技術・活用法を解説している本です。深層学習が得意な分野として、画像処理（画像分類・画像検索）と自然言語処理を扱っています。
3章以降では章ごとに1つのコンテストを取り上げ、必要な技術を解説しつつ、PyTorchを使い実際にある程度高いスコアが出るコードを作り上げる過程を解説しています。技術をカタログ的に紹介する書籍とは異なり、この本では、具体的な問題にアプローチするというストーリーの中で技術を紹介していきます。そのため、以下のような特徴があると思います。
- 技術自体をただ学ぶのではなく、それらを組み合わせる方法、適切なものを選択する方法、実際に活用する上での考え方や注意点などについても学ぶことができると思います。
- 実際にKaggle上で高いスコアが出せるところまで取り組むので、細かいところもごまかさず、精度を絞り出す過程について学ぶことができます。
- 執筆を通じて作成した、実際に高スコアを出すことのできるソースコードは、すべてGitHubで公開しています。必要となれば実装法についても学んで頂けると思います。
本書はu++さん、smlyさん、flowlightさんという錚々たるKaggle Grandmaster・Masterの方々との共著です。私は3章の画像分類の章を担当しました。
詳しい目次はこちらからご覧ください。
対象読者は？
以下のような方におすすめです。
- 画像処理や自然言語処理でより高性能なモデルを作れるようになりたい
- 自分の深層学習の知識や技術のレベルを1つ上げたい
- Kaggleのコンテストでより良い成績を収めたい
逆に、以下のような方にはおすすめできません。
- 深層学習について何も知らない → 深層学習の入門書を先に読んでもらう方が良さそうです
- 画像/自然言語処理の分野全体について網羅的に学びたい → 分野の教科書を読んでいただく方が良さそうです
- テーブル形式データのコンテストで勝ちたい → テーブル形式データのコンテストは本書で扱っていませんので、他の本を読んでいただく方が良さそうです（下記参照）
他の本との関係は？
Kaggleで勝つデータ分析の技術
伝説的名著「Kaggleで勝つデータ分析の技術」です。主にテーブル形式データのコンテストを対象とした本です。今回の「極意本」ではテーブル形式データのコンテストは扱っておらず、紹介する技術もほぼ全く被っていません。テーブル形式データの機械学習について学びたい方には、個人的にはこちらの本を強くおすすめします。「ジャンル問わずKaggleのようなコンテストで使われてる技術を色々知りたいな」という方には、こちらの「勝つ本」と「極意本」の両方を読んで頂くのがとても効率的なのではないかと思います。
PythonではじめるKaggleスタートブック
「機械学習とかやってみたいな〜」「Kaggleとかやってみたいな〜」みたいな方への最初の1冊としては、今回の「極意本」は難しすぎると思います。そういった方が機械学習の基礎を学ぶ方法は色々あると思うので、自分に合う方法を見つけて頂くのが良いと思います。特にKaggleをやりたいという強いモチベーションがある、手を動かしたい、というような方には、こちらの「PythonではじめるKaggleスタートブック」はおすすめだと思います。著者の一人の石原さん（u++さん）は極意本の著者でもあります。
Kaggle Grandmasterに学ぶ 機械学習 実践アプローチ
Kaggle GrandmasterのAbhishek Thakurさんが書かれた本を石原さんが翻訳したものです。極意本とスタイルはやや近く、コードも交えつつ、問題に取り組みながら技術を紹介していく本です。一方で、対象としている範囲が極意本よりだいぶ広く、その分、各章では核となるアイディアに絞り紹介するような内容になっています。また、そのため、Kaggleのコンテストで実際にある程度高いスコアを出せるようには取り組んでいないという点も、大きな違いかなと思います。
KDD'16 論文採択：省メモリなグラフスケッチのデータ構造
国際学会 KDD 2016 に論文が採択されました．KDD はデータマイニング分野の最も有名な会議です．発表は 8 月にサンフランシスコです．オーラル発表有りの採択です．
今回の論文は "Compact and Scalable Graph Neighborhood Sketching" というタイトルで，私が主著であり，研究室で特任技術専門員としてお手伝いしてもらっていた矢野さんとの共著です．内容はグラフ向けデータ構造 All-Distances Sketches の実用上の問題点である空間使用量を大幅に削減するための新しいデータ構造の提案です．以前に「大規模グラフのコンパクトでスケーラブルな全距離スケッチ」というタイトルで人工知能学会の人工知能基本問題研究会にて議論させて頂いていたものです．
背景：All-Distances Sketches とは？
All-Distances Sketches (ADS) は Min-Hash に基づくグラフ向けの乱択スケッチのデータ構造です．グラフ向けのデータ構造は私がずっと注力してきた分野ですが，ADS は数年前に浮上してきて以来ずっと注目してきた技術です．ADS は以下の魅了的な性質を取り揃えています．これらを満たすものはこれまで他にほぼ存在しませんでした．
- 二点間距離，近接中心性，近接関連性など，様々な指標の推定を行うことができる
- しかも，かなりの指標の推定において，推定精度に保証がつく
- 理論的には，空間や構築時間がグラフのサイズにほぼ線形である
詳しくは，IBIS 2014 で講演した際の以下のスライドをご覧下さい．
背景：ADS の問題点
ADS のこれらの魅了的な性質を知った当時の僕は，我先にと飛びついて実装をして試していたのですが，理論的にはほぼ線形であっても，実際にはスケーラビリティがあまり高くないという問題を発見しました．ほぼ線形というのは精度パラメータである k を定数だと考えた場合ですが，実用的には k も無視できない大きさを持つ，などが理由です．
これは実際に IBIS 2014 の講演でも最後のスライドで課題として取り上げています．この頃からずっと問題意識を持っていたんですね．
提案手法：Sketch Retrieval Shortcuts
誰かがすぐ解決しそうだと思っていたのですが，意外となかなかいい手法が出てこず，結局僕がやった，というのが今回の研究になります．実際，ADS は繰り返しが少なく切れ目の多いデータ構造なので，汎用の圧縮技術ではほとんど性能が出ませんでした．
そこで我々は，Sketch Retrieval Shortcuts (SRS) というデータ構造を提案しています．SRS は ADS の部分集合ですが，SRS を覚えておけば，1 頂点を指定された時，その頂点の ADS を瞬時に復元できるようになっています．復元した ADS は，オリジナルの ADS と全く同じく推定に使えますので，ADS の持つ推定能力をそのまま引き継ぐことになります．
実験では，数億辺規模のウェブグラフやソーシャルグラフにて性能を確認しています．サイズは数倍〜10倍程度小さく，数ミリ秒で ADS が復元できています．
感想など
ADS は近年浮上してきてから大変注目していた技術だったものの，なかなか自分が研究成果でそこに食い込んでいくことができていなかったので，ようやく ADS に関連した研究を発表できることとなり，とても嬉しいです．現在，他にも ADS に関連した別方面の研究も進めているので，そっちも早くお披露目できるといいなと思っています．
PHP の壊れた mt_rand の品質を統計的に検証した
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？
ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します．
壊れた mt_rand とは
PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．このバグのある mt_rand の実装をこの記事では「壊れた mt_rand」と呼びます．
今回話題となっている一連の騒動は，
- kusano さんが壊れている mt_rand を修正する pull request を送り，一度マージされた．
- でも，後方互換性を崩す，とリバートされた．
- それどころか，壊れていることが維持されるようにテストがついた．
といった感じだと思います．
詳しくは以下のブログ記事にまとまってますので是非．
なぜ擬似乱数の品質は重要なのか？
擬似乱数が「ちゃんと乱数に近い」ことは，統計的な実験やシミュレーション，確率的アルゴリズム，暗号，ゲーム等に欠かすことのできない要因です．
例えば最近だと，「グラブル問題」などソシャゲのガチャの確率の話をよく聞きます．意図的にガチャの確率を弄っている場合まだ良い（……良くはないですが少なくとも運営の意図通りではあるしすぐ直せる）として，擬似乱数の性質が要因でバグとして確率の偏りが起こってしまうと，とても悲惨だと思います．
BigCrush テストとは
ここ最近での乱数のテストといったら，BigCrush だと思います．
例えば，Google Chrome で採用され話題になった xorshift128+ の作者公式サイトでも，BigCrush でのテスト結果が（自慢気に）載ってます．
Here quality is measured using the powerful BigCrush suite of tests.
http://xorshift.di.unimi.it/
メルセンヌ・ツイスター作者の松本先生の最近の研究でも，品質で真っ先に言及されるテストが BigCrush です．
XORSHIFT-ADD は128ビットの内部状態空間と2128-1の周期を 持ち、 TestU01 の bigcrush test を通ります。
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/
BigCrush は，統計的なテストを大量に実行します．数学的に解析を行うことのできるシミュレーション等を擬似乱数を用いて実行し，「本当に乱数だったらこういう確率分布になるはず」という分布と実際の結果から検定を行います．
どういうメニューがあるかは，Diehard Test の Wikipedia 記事を見るとイメージが湧きやすいかも．BigCrush は 10 時間近く乱数を生成し続け 160 種類のテストを実行します．（Diehard より BigCrush のほうがテストが豊富）
結果
PHP の mt_rand のコードを取り出してきて，BigCrush に掛けるためのコードを書きました．
上述の xorshift128+ の公式サイトを参考にして，適当な 100 個のシードで BigCrush を実行し，落ちたテストの数を表にしました．
| アルゴリズム | 落ちたテスト（16000 個中） |
|---|---|
| 壊れた mt_rand | 230 |
| 修正済 mt_rand | 236 |
なんと，ほとんど差が無いんですね．むしろ「壊れた」って呼ぶのが失礼かもしれないぐらいです．上述の xorshift128+ 公式に載ってるメルセンヌ・ツイスターの結果とそこそこ合致してると思うので，テストは正しくできているのではないかと思います．あと，C 言語の stdlib の rand も実行してみましたが，こちらは一万個近く落ちる結果になりました．線形合同法は，厳しい．
ちなみに，もっと意地悪をしてみようと思い，生成した乱数を bit reverse して BigCrush にかける，というテストも実行しましたが，結果はやはり殆ど変わりませんでした．（例えば，XSadd は普通に BigCrush すると通るものの，こうやって reverse すると落ちまくるらしい．）
表の数字をよく考えると分かる通り，実はメルセンヌ・ツイスターは正しく実装されていても BigCrush が結構落ちます．特に，必ず落ちるテストというのが 2 種類あって，それが 100 シード全部で落ちるのでそれだけで 200 個落ちてます．その点，最近の xorshift128+，xorshift1024* は，同様のテストを実行しても，落ちるテストは数十個みたいです．
BigCrush テストの出力も同リポジトリ内に置いてますので，詳しい結果が気になる方は直接ご覧ください．特に，seed = 12345678 で実行した結果は，上述の集計には入れてませんが，テストでよく使われている（例1, 例2）みたいなので置いてみました．最初に出力してる 16 個がそれら 2 つと一致しているので，壊れてる mt_rand・修正後の mt_rand 共に，公式と一致する実装が取り出せてると思います．
雑談：mt_rand が奇数しか生成しない（値域の指定によっては）
これはやや別の話題ですが，「PHP の mt_rand が奇数しか生成しない」という現象がやや前に報告されていました．ここで話題になっているコードを実行すると，確かに今でも奇数しか出てきません．これ，ヤバくないですか……？（というか，もしそうなら，何故 BigCrush に通るの……？）
これは実は，mt_rand の引数で値域が与えられた場合に，乱数生成器の出力を値域内に縮めたり広げたりする操作が，めちゃくちゃ雑に実装されていることが原因です．この RAND_RANGE 関数ですね．例えば，2 倍の範囲に広げる際，単純に 2 を掛けるという極めて雑な実装になっているので，偶奇が固定されてしまうんですね．RAND_RANGE は mt_rand だけじゃなくて rand でも使われてるので，そっちでも同じことが起こります．今回の BigCrush テストは値域の拡大縮小部分は対象外ですので，この点は結果に表れませんでしたが，値域を指定して使うのは要注意だと思います．
ちなみに，ドキュメントをよく読むと，「注意」のセクションにこの現象に関するものと思われる記述があります．
警告
64 ビット版の PHP で max を 2^32 より大きくすると、mt_rand() の返り値の分布にバイアスがかかり、偶数よりになります。 max が mt_getrandmax() の返り値より大きくなると、 乱数生成器の出力をスケールアップする必要があるからです。
http://php.net/manual/ja/function.mt-rand.php
ただし，そこには値域を拡大する際の警告のみが書かれていますが，この実装では原理的には値域の縮小の際にも偏りが起こるはずなので，ヤバいことが起きてる事案がこれまでにあっても不思議ではないと思います．
その点，例えば C++ の std::uniform_int_distribution は，libc++ でも libstdc++ でも，値域を拡大させる際はもちろん，縮小させる際にも必要に応じて乱数を複数使うように書かれていました．安心．
ICFP Programming Contest 2015 優勝
— Eijiro Sumii (@esumii) 2015, 9月 2先月開催された ICFP Programming Contest 2015 の結果が本日発表されました．我々チーム Unagi は二度目の優勝を達成です！嬉しい！
ICFP とは？
ICFP とは The ACM SIGPLAN International Conference on Functional Programming の略で，関数型プログラミングに関する有名な学会です．分野としてはプログラミング言語になります．
ICFP Programming Contest とは？
学会 ICFP の名前を冠し，20 年近い歴史を持つ有名なコンテストです．結果は毎年学会 ICFP にて発表されます．
ICFP Programming Contest は「なんでもあり」が特徴の，他とは一線を画す特徴的なプログラミングコンテストです．
- プログラミング言語制限なし
- 計算資源制限なし
- チーム人数制限なし
- 72 時間ぶっ続け勝負
ICFP Programming Contest 2015 について
今年の問題は，テトリスに類似したゲームをできるだけ上手にプレイする AI を作成するという問題でした．
ただし，18 個の「秘密のフレーズ」が設定されており，操作シーケンスに秘密のフレーズが入るたびにボーナス点が入ります．
うまく秘密のフレーズを埋め込みながら，できるだけ長いことテトリスをプレイする，というゲームになっていました．
全世界から約 300 チーム，合計約 800 人が参加したとのことです．
チーム Unagi について
chokudai, imos, iwiwi, sulume, tos, wata の 6 人で参加しました（アルファベット順）．同じメンバーで 2013 に優勝，2014 に準優勝，一部共通するメンバーで 2011 に準優勝しています．
感想など
ICFPCに出場したチームUnagiのメンバーは@iwiwi @wata_orz @imos @sulume @chokudai @toslunarでした！世界一！めでたい！このメンバーで負ける気がしない！！（去年準優勝であったことを棚に上げて）
— 高橋 直大(chokudai) (@chokudai) 2015, 9月 2これだけのメンバーと一緒に参加出来て本当に幸せだなと思います．チームメンバーとは元々プログラミングコンテストでの繋がりなので，チーム内である程度共通したボキャブラリーや考え方を共有しているのがとても楽です．一方，単に「いわゆる」なプログラミングコンテストで強かったというだけでなく，みんな異なる強みを持っており，それでいて良好なチームワークが発揮できるのが素晴らしいなと毎年思います．
去年は惜しくも準優勝となってしまい連覇にならなかったので，次こそ連覇を実現するのが来年の目標でしょうか．頑張ります．
