ICFP プログラミングコンテストに 言語で参加してみた @kinaba (稲葉 一浩)

自己紹介 D言語の言語仕様の日本語訳をしています 最近更新が遅くてすみません

日本語訳ページの紹介 去年から github に 翻訳レポジトリを 置きました。 １Clickで 誤訳等の 修正リクエスト できます。

本題

ICFP とは λ計算 型システム Haskell, ML, Scheme プログラム 検証

ICFP Programming Contest 6月か7月に開催 (の年が多い) 72時間勝負 (の年が多い) チーム人数制限なし (の年が多い) コンテストで競うテーマは年によってさまざま （ゲームの AI を作ることが多い）

勝つと、使った言語が表彰されます 使用言語は自由（関数型言語に限りません！） In addition (to 賞金), the organizers will declare ... the first place team's language is "the programming language of choice for discriminating hackers", the second place team's language is "a fine tool for many applications“, and ...

各言語のコミュニティで話題になれます

自分の戦績 2003 : OCaml 2004 : JavaScript 2005 : JavaScript 2006 : D, (Ruby, Java) => 2位 2007 : C++ 2008 : JavaScript 2009 : Java 2010 : D, Ruby, (OCaml, Java) 2011 : (出題) 2012 : D => 6位

今年の問題

今年の問題の入出力仕様 標準入力でマップのデータが渡される 標準出力に文字列で操作列を出力 アスキーアート 標準出力に文字列で操作列を出力 [UDLRS]* 制限時間160秒が近づくと SIGINT シグナルで 知らせるので適切に終了 という動作をする、Debian 32bitで動く 実行ファイルを提出すれば良い

www.kmonos.net/repos/icfpc12 やったこと

gui.d 「可視化」は超重要

google: icfp visualizer

gui.d DFL を使いました http://www.dprogramming.com/dfl.php https://github.com/Rayerd/dfl

gui.d の雰囲気 this.keyDown ~= (Control c, KeyEventArgs ev) { switch(ev.keyCode) { case Keys.DOWN: do_manual_command('D'); break; case Keys.UP: do_manual_command('U'); break; ... };

やりたかったけど できなかったこと

util.d いつも自分がつかっているユーティリティ

p.toString == “Point(x: 12, y:345)” util.d クラス定義に一行足すと、色々なメソッドを 自動定義します 名前は Haskell の deriving (Eq, Ord, Show) 由来 class Point { public immutable int x, y; mixin DeriveCreate; mixin DeriveCompare; mixin DeriveShow; } new Point(12, 345) (p1 == p2), p1.toHash() p.toString == “Point(x: 12, y:345)”

util.d の雰囲気 template DeriveShow() { override: string toString() const { string str = typeof(this).stringof ~ "("; foreach(i,mem; this.tupleof) { if(i) str ~= ", "; str = str ~ this.tupleof[i].stringof[5..$] ~ ":" ~ text(mem); } return str ~ ")";

solver.d がんばりました

solver.d 戦略 “一番近い 「λ」 へ最短で突き進む”の繰り返し 盤面が大きく変化しそうなルートは距離を大きく とる 20手先読みして Game Over なら ランダムに数手 動きを変える

戦略 そんなに賢いことはやっていない 実行速度が重要だった  72時間なので、他のチームもそんなに大したことはできない。当たり前のルーチンを確実に 実装するだけでそこそこな順位を取れる 実行速度が重要だった 最大 1000 × 1000 = 1MB のマップを160秒で 探索しきれないといけない

(実は久しぶりにそれなりの規模のD プログラムを書いてみて) 不満だったところ const なオブジェクトを 指す書き換え可能な変数が欲しい 昔は const Type と const(Type) の区別が できた気がする・・・ const(Point2d) p = new Point2d; p.x = 100; // ERROR. GOOD!! p = new Point2d; // ERROR! WHY?

余談 (去年の7月のコードを今のdmdでコンパイルしてみたら どうなるか） 今日の準備中にきづいたこと 余談 (去年の7月のコードを今のdmdでコンパイルしてみたら どうなるか）

2.059 -> 2.062 extern(C) static void catch_sigint(int) { ... } core.stdc.signal.signal(SIGINT, &catch_sigint); output.d(85): Error: function core.stdc.signal.signal ( int sig, extern (C) void function(int) nothrow @system func) is not callable using argument types (int,extern (C) void function(int _param_0)) Error: cannot implicitly convert expression (& catch_sigint) of type extern (C) void function(int _param_0) to extern (C) void function(int) nothrow @system

？ 2.059 -> 2.062 a.d(6): Error: &a is not an lvalue import std.typecons; void main() { Tuple!(int,int)[] a, b; (true ? a : b) ~= tuple(1,2); } a.d(6): Error: &a is not an lvalue a.d(6): Error: __error is not an lvalue a.d(6): Error: cannot append type Tuple!(int, int) to type Tuple!(int, int)[]* ？

まとめ

ICFPコンテストは 関数型言語の会議ですが… ゲームAIを作れというタスクが多いですが… どんな言語で参戦しても OK! みなさまの好きな言語 (D!) を宣伝しましょう ゲームAIを作れというタスクが多いですが… 短期間の戦いなので、GUI や管理Webサービスなど、人間とインタラクトできる環境が簡単に作れることが重要 ゲームAIの知識はほとんどいらない 高機能で高速な言語は当然有利 (D!)

今年もあるようです（多分6月か7月） Let’s join and enjoy!!!

おまけ

全自動ソートキラー http://www.kmonos.net/wlog/128.html#_2343121201 ソートアルゴリズム非依存で sort 関数の最悪ケース 「を発見するアルゴリズム」

std.algorithm.sort #cmp array size