HAL PROGRAMMING CONTEST 2009

出題された問題はランダム値によって生成されています。配布プログラム同様、縦横40〜100のサイズのフィールドを作成し、穴を最大16個まで生成しています。また、ゴールに辿り着くことができる問題のみ採用しています。それ以外に、固定の問題を数問加えました。

実際には、評価時間削減のために予め問題を生成しておき、そのデータを用いて評価をしています。

解答アルゴリズムは、大きく分けて経路探索と、加速度制御の２つに分かれます。

経路探索では主にダイクストラ法やA*のようなアルゴリズムが用いられていました。ノードのとり方や、コストの計算方法に、各自の工夫が見られました。

加速度制御では、先に求まった経路を元に、どのような加速度を与えていくかを決定していきます。最もシンプルな方法としては、先で求まったノード間を直線的に移動するというものがあります。さらに効率的に移動しようとすると、カーブを描くように加速度を与えていく必要があります。このようなカーブの生成方法に様々なアプローチがあり、状況に応じてヒューリスティックに加速度を決定するものや、スプライン曲線に基づくもの等がありました。

それ以外には、ジャンプをいかに考慮するかという点や、限られた時間の中でどの処理に時間を費やすかという点にも、様々なアプローチが見られました。

まずはスタートからゴールまでの道のりを作成しなければなりません。そのために経路探索を行う必要があります。アルゴリズムとしてはダイクストラ法やA*のような、グラフ理論の最短経路を求めるアルゴリズムを利用したものが大半でした。

このようなアルゴリズムを用いる場合、点の集まりを定義する必要があります。
（以下の説明ではこの点のことを経路点と呼ぶことにします）
以下のような位置を経路点として採用していました。

• スタート地点
• ゴールの中心
• ゴールの４隅
• 穴の４隅の少し外側
• ゴール領域の辺上の数点
• 盤面の端の少し内側
• 格子点（X, Y座標が一定間隔の点の集まり）
• 上記で定めた経路点の周辺の点

最も基本的で、多くの参加者が採用していたのが、スタート・ゴール・穴の４隅です。それ以外のものは、参加者によって様々な組み合わせで用いられていました。

次に、コストの計算方法を決める必要があります。コストとは、何をもって最短（もっとも良い）とするかを表すものです。以下のようなものが、コストの計算に使われていました。

• 経路点間の距離
• その経路点上で曲がるべき角度（角度が緩い方が良い）
• 推定ターン数（直線的に移動した際のターン数）

多くの参加者が採用していたのが距離のみによるコスト計算です。距離と角度の組み合わせというのも比較的よく見受けられました。

また、これらの経路探索をいくつかの方式で試し、その中で最も良い結果を採用するということも行われていました。

このような経路探索の結果、スタートからゴールまでを線分で結ぶ経路ができます。ただし、この時点で既にカーブした経路を作成している参加者もいました。カーブについては後述します。

加速度の制御がこの問題で最も難しく、また人によって手法に差が出るポイントとなりました。先ほどの経路探索の結果を元に各ターンの加速度を決めていきます。

最も基本的な制御は、経路点間を直線的に動く制御です。可能な限り加速をし、制御点で一度止まるような制御をします。これは多くの参加者が実装していました。

次にカーブを描くような加速度制御です。まず特徴的なのが、ほとんどの参加者は投機的なアルゴリズムによって加速度を決定しているということです。投機的という意味は、直線的な動きの時はアルゴリズムに沿って一度処理をすれば必ず答えが出るのに対し、カーブの時はうまくいく可能性があるアルゴリズムを実行し、それに沿って球の位置をシミュレートし、成功したら採用、失敗したらもう一度別の方法を試す、という方法を用いるということです。このような方法になっている理由は、今回の問題が穴の存在、加速度・速度の制限、離散的な処理である等から、直接的に解くのが難しいためと思われます。

話は逸れますが、このような方法論のため、onStartOneGame()でそのゲームの加速度を全て決定してしまい、decideAction()では、それに従ってただ加速度を返すだけという処理になっているプログラムが多く見受けられました。

カーブの加速度を決めるアルゴリズムは、大別すると以下のようになります。

• 状況に応じた、ヒューリスティックな加速度の調整
• スプライン曲線等のカーブに合うような加速度の調整
• ランダムな加速度の調整

ヒューリスティックな加速度の調整とは、ある球の位置と速度から、次の目標となる位置と速度の状態になるように、状況に応じて場合分けをしながら加速度を決定していくというアルゴリズムです。これらの手法は参加者毎に千差万別ですが、例えば次の目標速度に合うように加速度を加えつつ、位置を調整していくというような方法がありました。この場合途中で穴に落ちたり、目標に合わせることができなかった場合には、加速度の加え方を穏やかにしたり、一度減速して再度挑戦するということをします。

スプライン曲線等のカーブに合うような加速度の調整とは、経路探索で求まった直線の経路から、スプライン曲線等を利用してカーブを先に決め、それに沿うように加速度を調整するというものです。カーブに合うような加速度を設定できない場合には、もっと前の地点で減速を試みて合わせる方法や、そもそもカーブを作り直すといった方法が取られていました。

ランダムな加速度の調整とは、文字通りランダムに目標を定めて加速度を設定する方法です。モンテカルロ法とも呼ばれる、ランダムな試行をたくさん行い、うまくいった結果を採用するというものです。

多くの参加者は、種類の異なるアルゴリズムや、異なるパラメータで試行をし、その中で最も良い結果を採用していました。アルゴリズムの適用に関しても一度にスタートからゴールまでの加速度列を生成する方法や、経路の一部にアルゴリズムを適用し、その改善された経路に対して再帰的にアルゴリズムを適用し、徐々に良い結果を求めていく方法もあり、アルゴリズムの適用方法についても参加者ごとに個性が表れていました。

その他には、多くの参加者が実装していたものとして、ある地点から直接ゴールに向かえるかをチェックし、可能ならばそれを採用するというものがあります。同様に、経路探索で求まった経路点のいくつかを飛ばすことで、より良い結果が得られるならばそちらを採用するという方法も取られていました。

この問題の特徴として、移動前と移動後の位置が穴の内側でなければ穴に落ちたとは見なされないという要素があります。つまり、穴をジャンプして越える事が出来るということです。これによって狭い穴や、穴の角を飛び越えてショートカットすることができました。

多くの参加者が実装していたのは、前述の加速度制御の中で結果としてジャンプできている場合があるという方法です。それ以外には、経路探索の時点でジャンプも考慮して経路点を結んでいるものもありました。

その他の特徴的な方法としては、経路探索の時点でジャンプできそうな細い穴を削除したり、穴のサイズを少し小さくしたりして探索を行うことで、穴の角を飛ばす可能性を高める方法を採用している参加者もいました。

前述のように、特に加速度制御では何度もの試行が必要なために、３分という制限時間にひっかかるケースが多く見られました。そのため多くの参加者が、高速化や、制限時間に収まるようにパラメータをチューニングしていました。

投稿プログラムとは直接の関係はありませんが、自分のプログラムの結果を視覚的に確認できるようにしていた参加者が多かったようです。自作のアプリケーションを作成したり、既存のツールを用いて視覚化を行っていたようでした。投稿プログラムの中にも、それらのツール向けに情報をダンプするための処理が埋まっており、これらのツールをいかに整備するかという点も、アルゴリズムを改良していく上で重要な要素となっていたようです。

当初、実行委員の間ではカーブやジャンプを考慮したアルゴリズムは相当難しいのではと考えられていたのですが、上位陣のプログラムはそれを難なくクリアしており、参加者のレベルの高さに驚かされました。

プログラムの結果を画像に出力して見てみると、美しく弧を描きながらゴールに吸い込まれていく様や、絶妙なショートカットを見つけて動いていく様等、何度見ても飽きないもので、実行委員一同楽しみながらプログラムのチェックをさせていただきました。

今回は様々なアプローチがあり、どのアルゴリズムが優秀と単純には決められないところがありますが、優勝者のishimura氏の取っていた、経路探索の時点でジャンプ等も考慮した理想となるカーブを求めるという方法は、一つの答えかもしれません。結果として、ishimura氏のプログラムが描くカーブは他の参加者よりも美しく、無駄の無い動きをして、安定したスコアを出していました。

最後になりますが、参加者の皆さん、たくさんの投稿をありがとうございました。また、長い期間お疲れさまでした。