ICPC 2010 アジア地区予選東京大会に行ってきました
KLabは去年からICPC国内予選のスポンサーをしています。 スポンサー企業からは観戦に行くことができたので、元競技プログラマ （といってもICPCではなく高専プロコンですが）の私をはじめ、 KLabのプログラマ3人で観戦に行ってきました。
なのですが、ICPC国内予選で毎年行われている JavaChallenge というおまけのプロコンに、今年から Special League というスポンサー、OB 枠が追加されたので、観戦というよりも参加者の気持ちで参加してきました。
2010年夏の国内予選時のJavaChallengeの結果やプログラムは公開されているので、 今回の JavaChallenge そのうちプログラムが公開されると思うのですが、 先行して私の提出したAIコードを公開します。
アルゴリズムは基本的には min-max 法なのですが、先に状態のツリーを探索しながら 静的評価関数を適用し、制限時間が来たら min-max で最善手を選ぶというものになっています。 α-βを利用していないのは、時間制限のある場面でのα-βの実装をすぐに思いつかなかったので 状態の探索と最善手の評価を分けているためで、最善手の評価だけをα-βにしても ほとんど性能には影響しません。 (後で考えると、反復深化α-βが最適だった気がします) 状態探索部分は、静的評価関数の結果がいい状態を選ぶ最良優先(best-first-search) を使っています。
結果ですが、7チーム中3位という、平凡な結果に終わってしまいました。
これには裏話があり、実はコード提出の10分前くらいまでは状態探索は幅優先 (breath-first-search)だったものを、最良優先に変更して、逆に弱くなってしまっていました。 あとで試してみたところ、20ラウンド中16ラウンドは幅優先の方が強かったです。
今回のコンテストで配布されたプログラムは、ドキュメントには書かれていないものの、 設定ファイルを編集することで4プレーヤー同時対戦ができたり、ステージを切り替えることが 可能でした。本戦では小さめのステージで2プレーヤーだけの対戦なのですが、私はルールを 勘違いしていていろんなステージで4プレーヤーが同時に対戦すると勘違いしてしまいました。
4プレーヤーを広いステージで対戦させると先読みの深さがすごく少なくなったり、 静的評価関数がすごく重くなったりしてしまいます。 選んだ最善手のつもりの手が先でどん詰まりになることがあり、実際に最善手を 選ぶ前に少しでも先を読んでおきたいというつもりで、最良優先探索に切り替えてしまいました。
非常に悔しいので、もし来年も JavaChallenge に参加できれば、ちゃんとルールを読んで 今度こそ優勝を狙います。
また、他の参加者の方も、ぜひコードを公開してください。
私のプログラム（の、PriorityQueueをArrayDequeに変えて幅優先に戻したもの）
といろいろなステージで再戦しましょう。
