ICFP Programming Contest 2011

http://www.icfpcontest.org/

今年は会社の同僚と6人で、チーム名 widecat で参加しました。

成績は…よくわかりません。けっこう相性で勝敗が決まるので。とりあえず上位30チームの決勝には残れてるんじゃないかと思います。

AIの戦略

開始直後はまず、復活用の魔法を準備します。

  • 1 ターンで発動し、スロット 0〜82 を revive、さらに inc する
  • 1 ターンで発動し、スロット 192〜255 を revive、さらに inc する

この2種類を用意し、さらにそれぞれのコピーを作っておきます。使うときはコピーの方を使い、オリジナルから複製し直すことで作り直しの手間を少なくしています。

inc で体力を 2 まで回復させているのは、生き返らせたあとに dec ですぐまた殺されるのを防ぐためです。まあ 2 回 dec されるとアウトなんですが。

これを作り終わるまで 75 ターン。その頃には 255 が殺されていることも多いですが、敵のゾンビの初撃には十分間に合います。

次に attack 0 0 8192, attack 1 0 8192 で相手の 255 を殺します。もちろんゾンビを送り込むためです。

その後ゾンビを作ります。こんなコード。

f = '(\i. help i i 8192)'                # f i = help i i 8192
g = '(S %s succ)' % f                    # g n = f n; return n+1
twice = '(S (S (K S) K) I)'              # twice f x = f (f x)
x256 = '(S (S I I) (S I I) %s)' % twice  # x256 f x = f^256 x
gx256 = '(%s %s)' % (x256, g)            # gx256 x = g^256 x
make_zombie = "\start. zombie 0 (S (K %s) (K start))" % gx256

これで make_zombie に数値を適用すると、その番号のスロットから順番に help で殺していく (1 回に 82 体ほど殺せる) ゾンビを敵の 255 番スロットに送り込みます。

このゾンビコードの構築には 110 ターンほどかかります。ちょっと遅いですね。
ゾンビの挙動は自分のスロットに入れておいて、copy で持ってくるというのが定石だったみたいですが、うちのチームは最後まで気づきませんでした。

何もしない敵を倒すには結局 292 ターンほどかかっていました。

やったこと

主に式からコマンド列へのコンパイラを書いてました。
あとチーム内で SKI 経験者（って何だ）は自分だけだったので、S (K f) (K x) で遅延できるよーとかイディオム的なのを紹介したり。
他には AI の回復系の処理を作ったり、他のメンバーが書いた式を軽くゴルフして縮めたりしてました。

感想

チーム参加ってどんな感じだろうと思って初チーム参加だったわけですが、良い点も悪い点も色々見えて興味深かったです。

まず戦略考えるのは複数人のほうが絶対いいですね。自分じゃ思いつかないようなアイデアもいくつかありました。

それと、下回りを作ってくれる人がいると楽だなーと思いました。今回はシミュレーターとか各種ツールをかなりしっかりと作ってくれていて、快適に作業できました。

逆に個人参加のほうが良かった点は、当たり前ですが一人当たりのパフォーマンスは個人参加のときのほうが高かったなあと。昼も夜もなく、コーディングしては寝て、目が覚めたらまたコーディング…という濃密な 72 時間が ICFPC の醍醐味だと思うのですが、今回は昼間はチームで集まって作業、夜は自宅で寝るというスタイルだったのでそんな感じではなかったです。合宿形式だったらまた違ったかもしれませんが。

あとチームで分業するにはあらかじめタスクを分割しておかないといけないので「作りながら考える」方式が使いにくいなあと思いました。一人のほうが早く作り始められるので、実は lightning division は一人でも勝ち目があるのかも。

あとこれは今回の反省点ですが、ICFPC 初参加のメンバーが何人かいたんですが、その人達が面白さを感じられるようもっと配慮してあげられたら良かったなと。

ともあれ、今回の問題は最高に良く出来てて楽しかったです。ジャッジの皆さん、参加者の皆さんお疲れさまでした。また来年お会いしましょう！

Marathon Match 70

TopCoder

２年ぶりのマラソン。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=16072&rd=14525 (要ログイン)

  • 一本のDNA（A,T,G,C からなる文字列）と酵素の集合が与えられる。
  • 酵素は固有のパターンを持っていて、そのパターンが現れた位置でDNAをカットする。
  • カット後のDNA片が与えられた条件を満たすような酵素の部分集合を求めよ。

条件は8種類。

  1. DNA片の数の最小値。
  2. DNA片の数の最大値。
  3. DNA片の長さの最小値。
  4. DNA片の長さの最大値。
  5. DNA片の長さの比の最小値。長さが近すぎる２つのDNA片があったらダメ。
  6. 酵素のパターン長の最小値。
  7. 酵素の数の最大値。
  8. DNA位置の範囲（0〜3つ）。指定された範囲内に少なくとも1つのカットが必要。

あとはDNAは環状になってるかもしれないとか、酵素は順方向と逆方向でマッチが可能とか細かいルールが色々。

得点

返した酵素の部分集合の数（最大１００個）が得点となる。ただし、実行時間が0.3秒を超えると得点が減っていく。

解き方

前処理部分と探索部分に分けて考える。

前処理

条件6を満たすそれぞれの酵素に対して、DNAをカットする位置を求める。
パターンマッチは酵素ごとにDFAを作った。いくつかの酵素はワイルドカードが多くてDFAの状態数が膨大になるので、それらについてはナイーブな strstr的方法で。改善の余地はだいぶあるけど、どうせ前処理部全体で0.1秒以内で終わるのであまりここは凝らなかった。

また探索を高速化するために、いろいろ計算しておく。

  • カットの結果、条件2より多くのDNA片ができたら、その酵素は使えないので捨てる。
  • カットの結果、条件3より短いDNA片ができたら、その酵素は使えないので捨てる。
  • 酵素のペア (A, B) のカットの和集合が条件2, 3を満たさない場合、Aを選んだらBは使えない（その逆も）。すべての酵素についてこの関係を記録しておく。
探索

酵素をカットの数が多い順に並べて、深さ優先で探索していく。マラソンでDFSで解けるってかなり珍しいんじゃないだろうか。

改良

TopCoderの実行サーバーで0.3秒を超えると点数が下がるので、時間がかかるテストケースを探しては遅くなる原因を探して枝刈りを追加、というくり返し。

枝刈りの例を挙げると、以下のような場合に探索を打ち切るようにした。

  • 残りの酵素で条件8を満たせなくなった場合
  • 条件4より長いDNA片をすべてカットすると条件2を満たさなくなる場合
  • 残りの酵素で条件1と条件7を同時に満たせなくなった場合
  • 残りの酵素で目いっぱいカットしても、条件1または条件4を満たせなくなった場合

最終的には、手元の環境で 200,000 ケース実行して解があるケースで 0.1 秒以上かかるものは無し、解なしのケースでは0.2秒台が1つだけになった。

結果

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14525

1位! …だけど同点1位が16人というアレな結果に。
Forumを見ると100万件とかテストしてたりマッチングを超頑張ったりしてる人も居たけど、5000件程度の system test では差がつかなかったようだ。少々可哀想な気もする。

あと賞金貰うにはコードの解説を提出しないといけないらしい。めんどい…

ブロックスデュオ

Blokus


今さらですが、ブロックスデュオ大会に参加したプログラムとブラウザ上で対戦できるものを作りました。

http://irorin.org/blokus.html

ブロックスデュオのルールはこちらで紹介されています。

操作方法
  • 難易度と Violet(先手)・Orange(後手) を選んでゲームを開始します。
  • 自分のピースをドラッグして盤面に置いていきます。
  • ピースはダブルクリックで左右反転、マウスホイールで回転します。Shift+クリックでも回転します。

(2011/07/09更新)
対戦結果をツイートできるようにしてみました。勝ったら自慢しましょう。

(2012/02/05更新)
ソースコードはこちらです。 https://github.com/irori/blokus

ICFP Programming Contest 2010

http://icfpcontest.org/
今年も時系列でお送りします。問題については konnさんの翻訳 など。

  • 18日21時 開始。
  • 19日0時 回路の構文がなんとなくわかった。ゲートの入出力表作成に入る。
  • 19日2時 入出力表できたー！と思って手元で17文字計算してみると結果が合わない。ショック。
  • 19日4時 手計算の間違いに気づく。どうして2cmしか離れてない場所に写す文字を間違えるのか…！ともかく一区切りついたので寝る。
  • 19日8時 起床。keyを出力する回路を考える。
  • 19日12時 むずいー。
  • 19日18時 わかんねー。
  • 19日22時 やめたくなってきた…。
  • 20日2時 ようやく使えそうな方法を思いついたので回路生成スクリプトを書く。
  • 20日3時 keyが通った！達成感がハンパない。
  • 20日4時 3進数コード解析のため、車のコードを集めたりしつつ寝る。
  • 20日10時 おはようございます。ずいぶん出遅れてしまったけれど頑張ります。
  • 20日14時 車のエンコーディングは分かった。次は燃料。
  • 20日15時 最初の燃料を提出。これでやっとスタートラインという感じ。
  • 20日16時 環境整備。車の取得と燃料の提出をするスクリプトを書く。
  • 20日17時 80個ほど提出。そろそろまぜろよ(AA略)
  • 20日22時 単純なソルバを書いたり適当に手で解いて提出してみたり。
  • 21日2時 寝る。にはスコアボード１画面目まで上がれるといいなあ。
  • 21日11時 よくねた。寝てる間に増えた車の分を一気に提出。
  • 21日15時 賢いソルバを書こうとして失敗。
  • 21日18時 やっぱり最後は力技。車取得＆燃料提出スクリプトを回しつつ手動で問題を解いて提出していく。
  • 21日20時 100個くらい解けたけど、今からじゃスコアにほとんど影響しないだろうなあ。
  • 21日20時半 サーバー頑張れ超頑張れ。
  • 21日21時 終了。

結果、1644種類の車を解いて696点でした。スコアボードで上から24番目だから29位でしょうか。回路の作り方が思いつかなくて土曜一日潰したのが痛すぎでした。
今回並列で出来る作業が多いのと提出の早さが重要ということで、複数人のチームに有利だった印象です。燃料産業は個人事業主には厳しいですね。

時間がなかったのと今回 100% Ruby だったので凝ったソルバは作れませんでした。代わりに irb 上からこんな風に提出できるようにして、人力で計算して提出していました。

irb(main):066:0> s.submit(59899, [[[2**17+1]], [[2]]])

係数の調整も手動です。 OpenOffice Calc に式を入力して調整したりしてました。


おまけ。時間ごとの提出数。
半分くらいは最後6時間で提出してるのでスコア的にはあまり効かなそうです。寝てる間スクリプトを回しておかなかったのが悔やまれます。
あとみんな終了間際に車追加しすぎです。

ブロックスデュオ大会2009

Blokus

結果出てました。9勝1敗で優勝でした。

http://hp.vector.co.jp/authors/VA003988/gpcc/09g3b.htm

今年は東京農工大の会場に行ってきました。他の予定があったので途中で抜けてしまいましたが…。運営の皆さんお疲れ様でした＆ありがとうございました。

提出したプログラムはこちら。

hm5.zip (2013/09/04 UNLICENSE.txt を追加。ご自由にご利用ください)

昨年からの改良点は2つだけです。正直あんまり強くなってません。

  • 盤面評価を約 15% 高速化
  • 序盤の動きをあらかじめ計算して持っておくようにした

opening_book というファイルが序盤の着手データベースで、以下のようなテキストファイルになってます。

66t0
66t0 99t7 A7q1
66t0 99t7 A7q1 B7l4 7Al1
66t0 99t7 A7q1 58k2 BAk0
66t0 99t7 A7q1 58o6 BAk0
66t0 99t7 A7q1 68p2 BAo5

例えば一番下の行は、4手目まで 66t0→99t7→A7q1→68p2 という展開だったら BAo5 を置く、という感じです。

序盤データベースの作成方法はこの辺りを参考にしました。
http://www.cs.ualberta.ca/~mburo/ps/book.pdf
http://www.google.com/search?q=Generating+an+Opening+Book+for+Amazons

今回作った opening_book は各局面で深さ5の探索を行って次の手を決めています。PCを1ヶ月くらい回して生成したもので、最大6手目までのデータベースになってます。勝手にデータベースが成長してくれるので楽でしたが、夜にマシンがうるさくて困りました。

ICFP Programming Contest 2009

http://icfpcontest.org/
年に一度のお祭りに参加してました。

  • 27日1時 3時開始だがどうにも眠いので寝る。今にしてみればこれは正しい選択だった。
  • 27日7時 起きて問題文を読み始める。
  • 27日10時 VMを実装してみたが動かない。あれー？ と思ったら仕様の訂正が出ていた。遅くスタートすると他の人が先にバグに当たってくれるので精神衛生上良い。
  • 27日12時 なるほど Hohmann 軌道。
  • 27日13時 ビジュアライザをでっちあげる。VM とソルバは C で書いたので、ソルバから位置を出力してパイプでRubyのビジュアライザに流すようにした。
  • 27日15時 100x が解けた。
  • 27日18時 なぜか submit すると CRASH になるなー、と思ったら config 番号を入れるのを忘れていた。
  • 27日19時 いまさら Point クラスを作る。
  • 27日20時 なんか噴射 1.1 倍とかにすると 100x の点数上がるなー。
  • 27日21時 200x に取りかかる。多分タイミングを計って Hohmann 遷移すればいいんだよね。
  • 27日23時 計算合わない病に冒される。
  • 28日1時 わかんね (;_;) 寝る
  • 28日8時 今日も一日がんばりましょう。
  • 28日10時 分かった！符号間違ってんじゃん！
  • 28日11時 2003 はターゲットのほうが低い位置にあるのか。さんざん悩んだから今度は間違えないぞ…あ、あれ？
  • 28日16時 200x はこんなもんでいいや。300x はどうやるのかちょっと分からないなあ。
  • 28日18時 だらだらする。
  • 28日21時 pepsiso にあやかろうと思ってペプシしそを買ってくる。これは…しそだ…！
  • 28日23時 ニコ動を見る。
  • 29日2時 寝て起きたらなんか思いつくかもしれんし寝るか…
  • 29日10時 寝過ぎた。
  • 29日11時 わかった。ターゲットの近地点で接近するように、近地点を含む軌道に遷移するタイミングを調整すればいい。
  • 29日12時 3003 できた！
  • 29日15時 さて 400x ですが残り 12 時間でどこまでいけるやら。
  • 29日19時 ターゲットがほぼ円軌道な 4004 が一番簡単そう。自機と回転方向が逆だけどまあ接近してからの調整でなんとかなるだろう。
  • 29日21時半 4004 でデブリ5個回収できた。この時点で21位。20位以内に入ったら記念撮影しようと思ってたのに！
  • 29日22時半 4001 と 4003 でなんとかスコア獲得して20位。やったー
  • 29日22:56 10位！自分をほめてあげたい！
  • 29日23時 スコアボードが凍結された。なんか7位になってるけど上位がちょうど submit ト中で一時的に点数下がってるっぽい。
  • 29日23時 あれ、10 位ってことは validation のことも考えないといけないのか。コードに直に回収する順番書いてあるんですけど！
  • 30日0時 頑張って general な解き方に直していく。こんなことしてる間に絶対順位下がってるよなあ。
  • 30日1時 ここに来てまさかの謎CRASH。
  • 30日3時 終了。回収する順番を探索するようにして裏で回しておいたら少しスコア上がった。

物理とか幾何とか苦手意識があるんですが、それでも3日間挫折せずに続けられたので難易度設定は絶妙だったと思います。
参加してた皆さんお疲れさまでした。

追記

ひっそりとソース追加。やる気ない感じなのがバレバレですな…
icfp09-irori.tar.gz