ICFP日記

http://www.icfpcontest.org/

(徐々に書く)

まず最初に書いておくと、コンテストはもう始まっていて、がんばって挑戦するつもりの人はもうがんばり始めてるので、がんばるつもりがあればこのブログの更新を待たずに自分で上のリンクからたどるといいです。僕の目的はICFPってのがどんな物なのか体験してみることと日本語での紹介エントリーを書くことなので、家事をしつつのんびりと更新していくつもりです。

        • -

空き缶をリサイクルボックスに持っていった。暑い。暑い。暑い。

水だし麦茶をセットしてきた。

さて、とりあえずルールなどの解説。詳細はこちら： http://www.icfpcontest.org/rules.html
事前登録の必要はなく、7月14日(PDT)までに完成させてソースコードを応募すればOK。チームのサイズは５人までだけで、年齢や学生でないといけない的な制限はない。他のチームと話し合うのはOKだがコードの共有は禁止。

最優秀賞には$1000、最初の24時間で提出された中での最優秀賞に$500、審査員特別賞に$500がでるらしいけど、僕はがんばる気がないのでスルー。

デフォルトで使える言語は http://www.icfpcontest.org/live-cd.html の最後の方に書いてあるけども、これ以外の言語が使いたい場合はソースと一緒にコンパイル済みのバイナリとか他に必要なバイナリとかを送ってもいいらしい。主催者側と同じ環境は1CD Linuxとして配布されているので、バイナリで送りたい人はそれを使うことになるだろう。まぁ僕はPythonを使うつもりなので関係ない。

        • -

モニターのまわりにこばえがいてうっとうしいので掃除機で吸い込むなどした。マシンの調子が悪いので再起動しよう。

        • -

む、洗濯物を干したのに、雷鳴が聞こえる。。夕立が来るんだな、きっと。。


おわ、落雷きた、かなり近かった！音も鋭かった！

        • -

さて、それじゃ肝心の問題文の解説に入ろう。今回の問題は、火星探査機のコントロール。もちろん本物のじゃないので「火星探索ゲームをプレイする」と思ってもいいだろう。人間がプレイするんじゃなくて、プレイするプログラムを作る。これが課題。

詳細：http://smlnj.org/icfp08-contest/task.html

ゲームの目的は火星探査機(rover)をコントロールして目的地に行くこと。マップにはクレーターや大きな岩があるのでそれをよけなければいけない。しかも火星人がいて、火星人に探査機が捕まると即座に破壊されてゲームオーバーになる。

ゲームをうまくプレイできたかどうかは下の計算式で決まる(小さい方がいい)

  • タイムリミット以内にゴールインできたらその時間t (ミリ秒)
  • タイムリミットn以内にゴールインできなかったら n + 100
  • 時刻tに火星人に破壊されたら 2n - t + 600
  • 時刻tにクレーターに落ちたら 2n - t + 1000

-tが入っているところからわかるように、火星人に捕まるのが確実でも可能な限り逃げまわった方がスコアが高い。あと火星人に追われてクレーターに落ちそうなときは火星人に捕まる方がスコアが高い。まぁ、ゴールするのがもちろん一番いいんだけどね。

        • -

sudo port install gmpしないとhttp://smlnj.org/icfp08-contest/simulator.html に置いてあるシミュレータが動かなかった。

        • -

さて、実は問題を詳しく読んで、面倒になってきているのですが、まぁ、もうちょっとだけがんばってみよう。上のリンク先からダウンロードしたサーバを起動すると

$ ./server -v sample-maps/simple-small.wrld 
waiting for client connection on port 17676

という出力が出て待機状態になる。最低限何が必要かというと、まずはこの指定されたポートに接続してやり取りをするプログラムが必要だ。というわけでとりあえず指定されたポートにつないで読んでみる。ちなみに最終的に提出する物ではhostnameを指定できるようにしろ、と書いてあるのでそれもオプションに含めた。

import sys
HOSTNAME = sys.argv[1]
PORT = int(sys.argv[2])

import socket
s = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
s.connect((HOSTNAME, PORT))
print s.recv(1024)
s.close()

実行してみよう。お、GUIが立ち上がった。そして1秒くらいで閉じた。
出力結果

I 200.000 200.000 30000 30.000 60.000 20.000 20.0 60.0 ;

Call from C to SML raised exception.
unhandled exception: Fail: EOF
(以下略)

3.1 Messages from the server to the controllerを見ながらパースしようと思ったけど、それは「最低限必要なこと」じゃないので保留(ぇ)
とりあえず何も考えずに走り出してもらおう。

while 1:
    print s.recv(1024)
    s.send("ar;")

おおー、くるくるまわってるー。一応解説しておくと、サーバから送られてくるメッセージを全部printだけして無視し、ひたすら「まわれっ！」と叫び続けるというプログラム。ちなみに1回aを送るだけで「加速モード」に切り替わるので、何度も送っても意味はない。3.2 Messages from the controller to the serverに書いてある状態遷移図を参照。


さてさて、anemoが「適当に走るだけなら15分でできるよ」とか言うから試してみたけど、たしかに適当に走るだけなら15分でできるね。純粋にコーディングしている時間なら。ドキュメントを読む時間を含めると英文を速読できない限りちょっと無理。自分の書いたコードで探査機が走り回るのは面白い。

        • -


おー、敵もいる。

        • -

やっぱりこういうののパーサをさくっと書くのはML系の言語が一番楽なんだろうなぁ。今まで使った中ではHaskellで書くのが一番楽そうだ。でもHaskellでソケットうんぬんをする方法を調べるのが面倒なのでスルー。
Pythonでこういうのをパースするのが一番らくちんに書ける方法は何なんだろう。とかそんなこと考えてないで手を動かす方が速いか。そう、泥臭いことをやればできてしまうのでなかなか洗練したやり方にならない。LL Ringのじゃんけん2.0の時は正規表現の名前付きグループを使ったけど、今回のプロトコルは明らかに「スペース区切りのトークナイザを通してください」という設計になっているんでとりあえずスペース区切りにした。さて。。

        • -

ICFPとかどうでもよくてPython用のパターンマッチのコードを書きたくなってしまう自分がいるがとりあえず我慢して書いた。
telemetryのパースはこんな感じ。

def telemetry(xs):
    """T time-stamp vehicle-ctl vehicle-x vehicle-y vehicle-dir vehicle-speed objects ;"""
    keys = """time_stamp vehicle_ctl 
              vehicle_x vehicle_y 
              vehicle_dir vehicle_speed""".split(),

    memory.__dict__.update(zip(keys, take(xs, 6)))

    objects = []
    enemies = []
    while True:
        typ = xs.pop(0)
        if typ == ";":
            break
        if typ == "m":
            # m enemy-x enemy-y enemy-dir enemy-speed
            enemies.append(take(xs, 4))
        else:
            # object-kind object-x object-y object-r 
            objects.append((typ, tuple(take(xs, 3))))

    memory.enemies = enemies # latest data only
    memory.objects.update(objects) # keep unique (it is a set)

飽きてきた(またか)
タイムリミットが長いと途中でだれてしまう、、部屋で一人でやっているのも一つの理由なんだろうな。何人かで集まってわいわいやってたら楽しいかも。


と、とりあえずよそ見をするのは我慢して一番小さいマップでゴールインできるところまでは作ろう。そうしないと放り出してしまいそうだ。

        • -
>>> map(apply, [int, str, float], "1 1 1".split())
[1, '1', 1.0]

んー。

>>> [f(x) for f, x in zip([int, str, float], "12 34 56".split())]
[12, '34', 56.0]

んー。

        • -

とりあえず何も考えずにゴールするようにした。

    from math import sin, cos, pi
    rdir = dir / 180 * pi # radian
    speed = 1
    dx = speed * cos(rdir)
    dy = speed * sin(rdir)
    cp = -x * dy + y * dx
    print x, y, dx, dy
    if cp > 0:
        s.send("ar;")
    else:
        s.send("al;")

本当に何も考えずにゴールに向かって突き進むだけ。しかも角度が行き過ぎてから戻しているのでよたよたと頭を振りながら進む。かわいいw
よたよたしないようにするには、自分の現在の角速度を計算するようにして、それから回っているときの角加速度を求める必要があるな。

でもそれは最小限じゃないな。優先すべきなのはクレーターに落ちないことか。いや、それでもやっぱり自分がどれくらいの速度で回転しつつあるのかとかは必要か。

        • -

ああー。衝突が起きたときにB 777;T ...;とくるから単純にスペース区切りじゃダメなんだなぁ

        • -

角速度を計算するようにした。このまま進むと自分の位置がどこになるかをシミュレートする内部モデルを作るべきなんだけどめんどくさすぎる。
「この速度で進んでいたらクレーターをよけきれない！」というのが判断できないと。しかしめんどくさいぞ。