2010年12月16日

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 に参加できれば、ちゃんとルールを読んで 今度こそ優勝を狙います。

また、他の参加者の方も、ぜひコードを公開してください。 私のプログラム(の、PriorityQueueArrayDequeに変えて幅優先に戻したもの) といろいろなステージで再戦しましょう。


@methane
klab_gijutsu2 at 18:39│Comments(0)TrackBack(0)

トラックバックURL

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント