楽天テクノロジカンファレンス2010、AIプログラミングコンテストに参加してきた
プログラミングコンテスト ～最強のAIを作ろう！～
4人でする対戦ゲームのAIを作れというもの。
ゲームのルールは、
- 壁、タイル、門で構成される正方形のマップの上で試合を行う
- 兵士が敵の門に突入すれば得点(得られる得点は相手のスコアに比例)
- タイルには所有者が設定されている。兵士はプレイヤーが所有するタイルの上しか移動できない
- マップ上の、指定した2x2の領域を回転させることができる。
- ターン制で、各プレイヤーは交互に動作する。
- プレイヤーは、1ターンごとに、指定した領域の回転、兵士の移動の二つの動作を行う。
みたいなかんじ。
提出したプログラムはこれ。
GitHub - todesking/rakuten-rtc2010-contest
時間やら能力の制約があって、まともに動くようになったのは提出締め切り30分前くらい。で即座に予選敗退しましたね……。一チームキャンセルが出たおかげでなぜか本選に出場できたものの第一試合で敗退……。
アルゴリズムについて
ターゲットの決定
攻撃対象(兵士の移動地点)を決定する。
今回は右か左の敵の小門に固定。一定ターンおきに対象を考え直す(相手のスコアを考慮)
目標とするタイル配置の決定
兵士からターゲットまで道ができるように、目標とするタイル配置を決定。
目標配置に近づけるためのタイル移動
目標のタイル配置と異なる場所のうち、兵士からもっとも近いものを選択。そこを自国のタイルで埋めるような回転操作を行う
兵士の移動
ターゲット座標までの距離(タイル配置とか考慮せず、マンハッタン距離)が近くなるような方向に進む。
反省
- デッドロック(自分がタイル動かす→他プレイヤーがタイル戻す→永遠に繰り返す)回避策を入れるべきだった(1回戦序盤で速攻そのパターンにはまり何もできず敗北)
- 経路決定がいちいち非効率(兵士からゴールへ一直線。タイルの移動を少なくするような探索を行うべきだった)
- ターゲットへの道がすでにできてたら壊さない(それくらいやれや)
- 攻撃されたら一定ターン防衛モードになるようにしていたが、ターンを管理する変数をリセットし忘れててまったく機能せず(……)
改善できそうな点は山ほどあったので、時間に余裕を持って実装を開始できればよかったですね……。
感想
- 面白かったので次回があったらリベンジしたいですね。
- 懇親会でいろいろな方に声をかけていただいたが、どう考えてもチーム名のせい。名前負けしないようにがんばります……。
プログラミングコンテストというドメインにおけるソフトウェア開発手法について
基本的に、アルゴリズムコンテスト系とTDDは相性が悪い。
TopCoder SRMみたいな問題設定の場合、「なるべく短時間で要求を満たす必要十分なコードを書く」ということが求められる。問題の規模を考えると、テストやリファクタリングはオーバーヘッドが大きすぎて使い物にならない。訓練して一発で完璧なコードを書けるようになることが重要。
では今回のような中期間で最適解の出ない問題を解く場合はどうか。部分問題(たとえば、ある座標に近いタイルを列挙する)に対してはTDDが適用可能だが、全体に適用するにはやはりオーバヘッドが大きい。最初は何を作るべきかがわからないし、開発中に仕様(実装すべきアルゴリズム)が高速で変化するためテストの保守コストに耐えられない。
しかし何らかの方法で品質を高める必要はある。おそらく有効なのは、アサーションによる状態のチェック(printfデバッグによる人力チェックも含む)および静的な型チェックだろう。何を実装するかはコロコロ変わるが、プログラマがいまこの瞬間書いてるコードが何を目的としていてどういう前提を期待しているかは記述可能なはず。実装と同じ場所にあれば高速な仕様変更にも耐えられる。
でも、この程度の規模だとまだ気合でバグのないプログラムが書けるよう訓練したほうが効率的だって気も。カウボーイ的な開発が割に合わなくなるのは規模がどの程度に達したときなのか。短期集中型は気合で十分で、中長期的な保守や断続的な仕様変更が入ってきてはじめてヘヴィな手法が効果を発揮するのか。いずれにせよ、短期間でゾーンに入ってノーテストで完璧な実装できるよう訓練しておいて損はないが。
