Haskilledとかいうチーム名で蟻作ってました。
コンテストについてはこちらを参照。
私と、某M君(名前はとりあえず伏せとく…)とでやってました。
提出したものはこちら。
説明ファイルはうそ英語が恥ずかしいので削除してます。
チーム名はもちろんHaskellのもじりです。
問題についての説明はどこか他を見てもらうとして…
とりあえずの方針は、
実はよくわからんのですが…
あんた何しとったんや、ちゅう話ですが、
ほぼずっと蟻言語作ってました。駄目やん…
とりあえず分かる範囲では
最初に巣の中央部に6匹で倉庫を作ります。
こんな感じ。餌は確実に守ります。
動く方向を二進で記録。あまったところに餌場フラグなどを書き込みます。 餌を発見すると餌があるというしるしをつけながらランダムな方向に移動。 他の蟻が発見しやすいようにしている模様。 巣への帰還時にランダムでマーカーを消す。 餌がないところに何匹も移動するのを防ぐ。
敵陣は認識していない模様。 普通に敵陣にも探索に行きます。 相手の巣にわながあったら怖い。 自陣にも倉庫しかない。 倉庫の餌場に運良く敵が侵入すると、その蟻を殺せるぐらい。
これが私のメインといえばメインなのですが。
蟻のプログラムを全部人手で書くこともできますが、無茶なので、
C様の言語を実装しました。
有限状態オートマトンとしてコードを生成しますが、
コードを多重に生成して変数を扱えるようにしているのが最大にして唯一の特徴。
スタックの状態とかを考えないので、再帰的な計算はできません。
まぁ、めんどくさいので。
マクロのような機能もあります。
仕様についてはアーカイブのdoc/以下にある言語仕様とか提出した蟻の
ソースを参照してください。
言語仕様はM氏が作ったプリミティブな言語を適当に拡張していったので、
微妙にいびつですが…
実装はHaskellで行いました。
パーザー書きやす過ぎ。ツリー構造扱いやす過ぎ。
とてもよいです。
実装は結構ナイーブです。
変数を複数使ったりすると指数関数的にコードが膨れます。
そういう理由で状態数10000を結構すぐに使い切ってしまうので、
オプティマイザを作りました。
割合簡単なアルゴリズムで冗長なジャンプ(flip 1 x x として内部的には生成)と
到達不可能なコードを削除します。
これはC++で作成…配列が使いたいんだよなぁ。
最初Haskellでシミュレータ作って、一日以上つぶしてしまった。 まだまだモナドの扱いに熟練していないので無理すべきではなかったかもしれません… 結局できたものはめちゃくちゃ遅い使い物にならないもの。 結局M氏の作ったVBのを使うことに。 コンパイラを作り始めてからは割合スムーズにことが進みました。 もうちょっと早くから方針が立ってたらなぁ…ああ。