Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

「最強のAIを作ろう!」のソースコードと解説

プログラミングコンテスト ~最強のAIを作ろう!~」のソースコードを公開します。

時間がない中で作成したので,コメントは簡単にしか入っていません。また,今回はC++が使えず,Java初挑戦で書きました。このようなことから,コードは読みづらいかと思います。

今回こそRubyを使うチャンスかとも思いましたが,コードが長くなる予感と期間が短いことから冒険はしませんでした。

基本戦略

ひたすら攻める,攻め重視のアルゴリズムとしました。これは,次の考えからです。

・ 防御しても,同時に複数で責められたら防御しきれないはず
・ 攻めるために道を作ると,敵国の道を崩すことになる

nextCursorAction()では,ひたすら最短コストで道を作成します。nextSoldierAction()では,道が完成したところまでどんどん進みます。

nextCursorAction()の処理

  1. 状態の評価
    ・自兵がゴール(敵Gate横)地点に到達 → 防御動作
    ・自兵が3ターン以上同じ位置 && カーソルが敵と競合している → ターゲット強制変更
    ・自兵が16ターン以上同じ位置 → ターゲット強制変更
  2. ルート評価 6点((敵大ゲート+敵小ゲート) × 3国)
    ・評価方法は配布資料の通り
    ・cost評価値によるターゲット変更は直前の変更から3歩動くまでは抑止する
    ・「大ゲートのコスト」が「小ゲートのコスト+3」以内の場合は大ゲートを狙う
  3. 移動タイルの決定
    ・選択ルートに対して,まだルート上に自陣タイルが置かれてないマスで,自兵に最も近いマスを
     移動対象とする
    ・対象のタイルが移動できない場合は,次に近いマスを移動対象とする
    ・自兵がいるために移動できない場合は,自兵の回避フラグを立てる
    ・全てのマスが移動できない(もしくは移動の必要がない) → 防御動作
  4. タイルの移動方向
    ・移動先が斜め方向の1つ先 & 隣接タイルあり → 隣接タイルとペアで回転

    ・移動先が1つ先 & 入れる先が自陣に挟まれている
     (ルート上なので,他のタイル配置を崩さないようにする)
    -隣接タイルあり → 隣接タイルとトリプルで回転

    -隣接タイルなし → 一旦横へ移動

    ・横方向の道へのタイル → y方向の移動を優先 : 最後の1手に斜め移動パターンを当てはめやすい

    ・縦方向の道へのタイル → x方向の移動を優先
     
  5. カーソル属性の決定
    ・移動対象タイルとルートとの位置関係によって,カーソルの位置と回転方向を決める
     ルート上のタイルに影響を与えないように移動させる

    ・カーソルに自陣が3点含まれる場合,4点含まれる場合
    回転処理が同じ場所でループしないようにカーソルをずらす。

  6. 防御動作
    ・自国のゲートの直前に自陣タイルがないマスで,最も敵が近いマスを防御対象とする
    ・最も近傍のタイルをゲートの前に移動させる
nextSoldierAction()の処理

  1. 自兵がスタート地点 → 一歩前へ進む
  2. 自兵が敵ゲートの隣 → 敵ゲートへ進む
    ・小ゲートがターゲットでない場合は,小ゲートには入らない
    ・残りターンが150~160のときは,150になるまで待つ(スーパー兵士待ち)
  3. 自兵回避フラグON
    ・カーソルに重ならない位置へ移動可能 → 移動する
    ・移動不可能 → 該当タイルは使用しないようにする(別のタイルを持ってくる)
  4. その他のケース
    ・2歩先までの道が完成している場合は1歩進む
     道作成の最前線までは進まない。最前線のタイルはペアで回転させるケースがあるため,
     自兵がいると邪魔。
  5. 15ターン自兵が同じ場所に留まる → 左右上下の順で行ける場所へ移動する(無限ループ状態の回避)
スポンサーサイト

楽天テクノロジーカンファレンス2010

プログラミングコンテスト ~最強のAIを作ろう!~」の決勝戦が行われることから,「楽天テクノロジーカンファレンス2010」に参加してきました。

基調講演はRubyのまつもとさんで,話を聴くのは今回が初めてだったのですがとても面白い講演でした。講演タイトルは「グローバル・エンジニア」で,Ustreamで見られるようです。

さて,肝心のコンテストですが,運良く決勝戦まで残れましたが,残念ながら決勝戦で負けてしまいました。結果はこんなかんじとなりました。決勝に残ってきた「Wantz」と優勝の「ウサギィ」は攻守のバランスがよく,1,2回戦を見ながらこのチームには勝つのは苦しいなあと思っていましたが,やはり歯が立ちませんでした。

1回戦で当たった「Tsurumi99ers」の人は,このブログを読んでくれているとかで,かなりビックリしました。懇親会でも話す機会があったので,いろいろ聞くとTopcoderやICFPCをやっていたりとのことでした。

コンテストの優勝の賞品は,まつもとさんのサイン付きHappy Hacking Keyboard無刻印モデルでした。これはなかなかの貴重品,あと一歩で手が届かなかったと思うと悔しいです。

コンテスト参加者のみなさん,コンテスト実行委員のみなさん,お疲れ様でした。また来年も是非やりたいですね。


その後の懇親会のじゃんけん大会では, 見事まつもとさんサイン付き「コードの世界」を頂きました。これはかなり嬉しい!

プログラミングコンテスト ~最強のAIを作ろう!~

プログラミングコンテスト界隈ではICFPCの結果発表やTCO Finalで盛り上がっておりますが,国内では楽天と早稲田大学によるコンテストが(ひっそりと)盛り上がりを見せています。

この大会にTeam「Hayabusa」として参加しています。まぁ,Teamと言っても一人での参加ですが・・・
いまのところ予選ではGroup B トップ通過と幸先のよいスタートを切っています。

さきほど,公開された予選の内容を見たのですが,私の予想に反して防御型のプログラムが多いなあという印象。
みんなで点を取り合う激しい試合展開を想定していただけに見込み違いでした。

私のプログラムは攻撃に特化しているので,防御型とのせめぎ合いがどうなるか。決勝は10/16(土)となっています。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。