この連休は、毎年恒例 ICFP Programming Contest に出ていました。
ソースコード置き場。 今回のお題は Boulder Dash っぽいゲームのAI書けというものでした。ただしダイヤモンドではなく「λ」を回収します。 見た瞬間に、えっ無理だろそんなの、と思って思わず旅に出たくなってしまったりしていましたが、 やってみるとそれなりに手はあって、結局３日間ちまちまと改善を続けていました。 と言っても結局パッと思いつくことしかできていない…。
が基本方針で、ただしこれだと周りをまったく見ないで気づくと岩に埋まってるので、 このソルバーをラップして
としました。 動画の1:00過ぎの岩を落として一歩戻るとか、 3:40付近の一歩右に掘る動作が、 これが発動しているわかりやすい部分です。 元のソルバと比べてほとんど遅くならない割には局所的なハマりは抜けられるので便利です。
こういう、同じインターフェイスのソルバをラップして別のソルバを作る、 ソルバーデコレータみたいなの作るのが自分は好きすぎて、それに固執する癖があるのは自覚しているつもりなんですが、 なんだか他の考え方に頭がいかないのですよねえ。良くない。
で、まあ、スコア的には多分全然ダメだと思う。 実際、難しい問題のほとんどは、10手20手の局所的な推論じゃなくて、 「今この岩を動かしておかないと、以降何百ターン費やしてもここが通れなくなる」 のような、 マップの接続関係のグローバルな推論をしないと答えが出せない問題で、全く手が出ませんでした。 どうすればいいんだろう。
そうだ、今回の「期間中に仕様が４回に分けてアップデートされる」というのは、 「自明なルーチンだけさっさと実装して、あとはもっと複雑なことの実現方法が思い浮かばず手詰まり」 になっちゃうことが多い自分のような参加者には割と楽しめました。 何も考えないでできるタスクが向こうから降ってきてくれるわけなので、手が遊ぶ時間がなくてよい。 ただ、上位陣にはこれ邪魔なだけなんじゃないかなあ、とちょっと心配してしまう。 一番最初の仕様だけでも、とても３日で収束するようなゲームではないでしょうし、 色々やれることがあるチームには要らん手作業タスクが増えるだけになってしまわないだろうか。
という感じで、面白くなってくるまでに時間がかかりましたが最終日などはとても楽しかったです。
サンプルマップでの成績。 スコア総和 / ハイスコア総和 = 77% で、(スコア/ハイスコア) の平均だと82%でした。
自分 / ハイスコア (計算時間) contest1.map 212 / 212 ( 1ms) contest2.map 281 / 281 ( 86ms) contest3.map 275 / 275 ( 4ms) contest4.map 561 / 575 ( 3ms) contest5.map 1281 / 1303 ( 603ms) contest6.map 1163 / 1177 ( 475ms) contest7.map 867 / 869 ( 4ms) contest8.map 1291 / 1973 ( 731ms) contest9.map 3044 / 3095 ( 348ms) contest10.map 2340 / 3634 ( 549ms) flood1.map 937 / 945 ( 269ms) flood2.map 281 / 281 ( 81ms) flood3.map 852 / 1303 ( 578ms) flood4.map 982 / 1594 ( 316ms) flood5.map 561 / 575 ( 5ms) trampoline1.map 291 / 426 ( 599ms) trampoline2.map 1732 / 1742 (4911ms) trampoline3.map 3255 / 5477 ( 508ms) beard1.map 853 / 860 ( 78ms) beard2.map 4487 / 4522 ( 163ms) beard3.map 809 / 1789 ( 660ms) beard4.map 1997 / 3103 (1547ms) beard5.map 665 / 946 ( 275ms) horock1.map 728 / 762 (1806ms) horock2.map 235 / 747 (1008ms) horock3.map 1543 / 2406 (1521ms)
a * b+cis parsed asa*(b+c).
Merd という非常に面白いアイデアの散りばめられた言語がありまして、 色々面白いところはあるんですが、 その一つが、 上に引用した "Horizontal Layout" という考え方を入れた構文規則です。 インデントで文のグループの分け方を表す Python のような "Vertical Layout" と対比して、スペースの入れ方で式のグループの分け方を制御する、というわけです。
1+2*3 ====> 7
1+2 * 3 ====> 9
1+2 * 3+4 ====> 21
1+2*3+4 ====> 11
これがどう実装されているのか、 気になったのでソースを読んでみました。 以下、 自分が理解した限りでのまとめです。 例として Horizontal Layout 入り数式の計算を実装してみました。
// 数値か、左結合の二項演算子か、空白だけを考える世界の出来事です。
class Value {}
class Number : Value { int number(); }
class Operator : Value { int priority(); Number compute(Number a, Number b); }
class Space : Value {}
// 文字列を Value の列に分解。実装は適当に頑張る。
Value[] lex(string str) { ... }
// Value の列を構文解析して結果を計算。
int parse(Value[] values) {
Parser p = new Parser;
foreach(v; values)
if( cast(Space)v ) {
// 空白は何もしないで読み飛ばす
} else {
p.shift(v);
}
return p.final_result();
}
まずは、普通の、空白は完全に無視して読み飛ばす構文解析を書いてみます。 上昇型構文解析を手書きする会 の会員としては上昇型で書きますと、演算子の優先順位を考慮した構文解析は、こうなります。
class Parser {
// 今までに読み込んだ値たち
private Value[] values;
// 新しく一個読み込む
void shift(Value v) {
if( auto op = cast(Operator)v )
reduce(op.priority); // 演算子だったら、優先度を見て、その左を計算するかも
values ~= v;
}
private void reduce( int next_priority = int.min ) {
Number lhs, rhs;
Operator op;
// 最後に見た部分が "数値, 演算子, 数値" で、優先度の高い演算子なら
if( values.back_match(lhs, op, rhs) && op.priority>=next_priority ) {
values.length -= 3;
values ~= op.compute(lhs, rhs); // その部分を計算して置き換える
reduce(next_priority); // 繰り返し
}
}
// 最終的な計算結果の取り出し
int final_result() {
reduce(); // もう後ろに演算子は来ないので全部計算しちゃう
assert( values.length == 1 ); // Value がたくさん残ってたら構文エラー
auto n = cast(Number) values[0];
assert( n ); // 数値じゃなかったら構文エラー
return n.number;
}
}
これを Horizontal Layout 対応にするのは、実は驚くほど簡単で、これだけです。
int parse(Value[] values) {
Parser p_full = new Parser;
Parser p = new Parser;
foreach(v; values)
if( cast(Space)v ) {
p_full.shift(p);
p = new Parser;
} else {
p.shift(v);
}
p_full.shift(p);
return p_full.final_result();
}
class Parser {
...
void shift(Parser p) {
p.reduce(); // 強制reduce!!
foreach(v; p.values)
this.shift(v);
}
...
}
さっき作った普通の parser を、二段構えにする。 一段目 (p) は空白か入力の終わりが来たら強制 reduce して、結果を二段目に流し込んで自分はリセット。 二段目 (p_full) は完全に普通の元々の parser です。
この変形は任意の（空白を無視する）文法に対しておそらく適用可能ですし、 単純に二段ではなくn段構えにすればn種類の空白でまとまり方の区別をつけられそうです（意味があるかはともかく）。 面白い。