優勝作品と解説

まず目につくのがウサギの位置が浮動小数点数で表現されているところだと思います。ウサギの座標が常に整数の場合、比較的簡単に巡回セールスマン問題（Traveling Salesman Problem, TSP）に帰着できるのですが、ウサギが連続的に移動でき、さらに同じマスにさえ着地すればそのマスの巻物を取得できるため「必ず通らなければいけない点」が始点以外に存在せず、非常に複雑な問題となっています。

加えて、最終的な評価スコアがジャンプ回数という離散的な値になっており、

• 連続的な移動経路
• 離散的な評価値

を同時に考えなくてはなりません。これは非常に難しいので、まずは評価値を連続にした問題を考えます。すなわち、ジャンプ回数ではなく「移動にかかった時間」を評価値として用います。このとき、単位距離を進むのにかかる時間を地質に応じて

• 平地: 1.0
• 茂み: 1.666...
• 砂地: 3.333...
• 池: 10.0

と設定します。しばらくはこの連続的な評価値の上で解法を考えていきます。

最終的な目標は全ての巻物を取る経路を求めることですが、まずは2点間の最短経路を求めることを考えます。

光学的解法

評価値が連続になっている場合、最適解を求めるのに光の屈折を利用することができます。光の経路は到着点までの所要時間が最小となるよう決定される（フェルマーの原理）ので、単位距離を進むのにかかる時間を屈折率として屈折をシミュレートすることで2点間の最短経路を割り出すことができます。

しかしながら、地質の配置によっては計算が困難になる上に、そもそも光が到達しないことがある（屈折や全反射によって目的地が「見えなく」なる）ため、結局のところこの方法を使うことはありませんでした。

グラフによる解法

一般に2点間の最短経路を求めるのは困難であることが分かったため、近似解を求めることにします。まず思いつく方法として、フィールド（修行の地）に道を張り巡らせ、経路を道上に限定したうえで2点間の最短経路を求める方法です。これはグラフを構築することで、Dijkstra 法によって高速に解くことができます。

フィールド上のマスの頂点を上下左右および対角線で繋いだグラフ（King's graph）を作成し、さらに (±1, ±2), (±2, ±1) だけ離れた頂点を繋ぐ辺を追加します（Knight's graph）。辺のコストには「頂点間を移動するのにかかる時間」を設定しますが、2つの地質の境目をなぞる辺については、より効率の良い地質に従ってコストを計算します。これは、ウサギの着地位置をわずかに変動させることで効率の良い地質のマスの上で移動することができるためです。

この方法で、（グラフ上に存在する）2点間の最短経路の近似値を求めることができました。

求めた経路はグラフ上の距離を最小にするものだったので、ユークリッド距離を最小にするよう手直しします。具体的には、取り除いても異なる地質を跨がないような経路上の点をすべてスキップします。この操作で、三角不等式により経路がさらに短くなります。

連続的な評価値を用いた場合の2点間の最短経路の近似値を求めることができたので、それを使って巻物を全て取る経路を構築します。まず、巻物の数は最大で20個と十分に少ないので、全ての巻物・ウサギの初期位置間の最短経路を上記の方法で求めておきます。このとき、巻物はとりあえずマスの中央に存在するものとしておきます。

全ペアの最短経路と（グラフ上の）距離を求めたら、全ての巻物を最短距離で取る順序を求めます。これはTSPと同様に動的計画法で解くことができますが、最終的には 頂点入れ替え＋1.5-opt＋2-opt のヒューリスティクスにより求めました（20頂点程度では動的計画法より数十倍高速に、かつほぼ確実に最適解を出すことができます）。このとき、巻物を取った個数 n に応じて距離を 1.1^n で割って短くします。

求めた順序により巻物を訪れる経路を結合することで、全体の経路が求まります。この経路に沿ってウサギを移動させることで問題を解くことができます。ただし、経路の頂点がマスの境界上に存在する場合、より効率の良い地質側にわずかに頂点を移動させてジャンプ回数を減らします。この時点でスコアは 30,000 ターン程度となります。

ここで目を背けていた離散的な評価値に向き合います。離散的な評価値の下では、

• 効率の悪い地質を飛び越す
• 効率の悪い地質の直前で一旦止まってから飛び込む

といった行動が有利になることがあります。これらを考慮した最短経路を最初から構築するのは困難なため、連続的な評価値を基準に得られた経路を初期解として、離散的な評価値の下で局所改善を行うことで経路を最適化します。巻物を取得する位置の調整もここで行います。

経路は出発点と中間点（必ず着地して向きを変える点）、巻物取得点（必ず着地して巻物を取得する点）の列からなり、局所改善は

• 開始点を同じマスの中でランダムに動かす
• 巻物取得点を同じマスの中でランダムに動かす
• 中間点をランダムに増やす
• 中間点を削除する

操作からなります。これらの操作を開始点から順に適用していき、ジャンプ回数が非増加であれば逐次経路の更新を行います（同スコアへの移動を許す山登り法）。ランダムに位置を動かす操作については、繰り返し回数を重ねるごとに変化量を小さくしていきます。この調整は焼きなまし法を意識しています。焼きなまし法にしなかった理由としては、

• 初期解がある程度効率的で、スコアを下げる方向への移動があまり効果的でないため
• 局所的には問題の凸性が高いため
• スコアが離散的であり、同スコアへの移動を許すことで十分な探索範囲の確保ができるため
• 実際に焼きなましてみたところ、あまりうまくいかなかったため

などがあります。

細かい改善方法の工夫により局所改善の効率を大幅に上げることができますが、詳しい方法はソースコードを見てみてください。この段階でスコアは 25,000 ターン程度となります。この辺りから改善がかなり厳しくなってきます。

局所改善の効率を上げるため、一定間隔で経路を細かく分割し、全ての着地点が経路の中間点に含まれるようにします。この操作により、任意の着地点で方向転換をする局所改善が可能になり、探索範囲が大きく広がります。中間点の削除も局所改善に含まれているため、不要な中間点は自動で消えていきます。これにより数百ターン程度スコアが改善します。

局所改善による効果には限界があるため、初期解の質を向上させることでスコアを伸ばすことを狙います。

初期解の構成に用いたグラフは連続的な評価値を用いて辺の重みを決定していましたが、ここに離散的な評価値による影響を加えます。離散評価値上で有利になるウサギの行動に

• 効率の悪い地質の直前で一旦止まってから飛び込む

というものがありました。これが有利になる状況を考慮し、

• 効率の良い地質と効率の悪い地質の境界上に開始点があり
• 効率の悪い地質上を移動する

辺について、ジャンプ1回分の移動距離を効率の良い地質側で計算します。この変更で、対称だった距離行列は非対称になります。スコアは数百ターン程度改善します。

同じ初期解から始めても、途中の乱数によって改善結果が変わってきます。そのため、同じ初期解に対して複数回の局所改善を行い、その中で最もスコアがよかった解に対してさらなる局所改善を行う2段階の局所改善を行います。1つの解に連続して適用する局所改善の回数は減りますが、運の悪さが分散するため平均すると良い解が得られます。この考え方はビームサーチに共通するものがあります。この変更により百ターンほどスコアが改善します。

浮動小数点数の性質上、不等式制約が含まれる場合は「小さな値」を利用して誤差を吸収するようなプログラムを書くことが普通です。この小さな値を適切に設定しないと、演算中に生じた誤差により実行不可能な解が計算される可能性があります。

が、今回の問題では「小さな値」をギリギリまで小さくすることでターン数を1程度減少させられるようなステージが多くあり、誤差の限界を攻める価値があります。そこで、ジャッジプログラムと全く同じ順序で計算して解の実行可能性を調べるプログラムを作成し、失敗した場合に前の状態に巻き戻すフォールバックを用意したうえで、「小さな値」を非常識なほど小さく設定します。これで百ターン程度スコアが改善します。

局所改善では巻物を訪れる順序は変わらないため、初期解を決定した時点でより良い巻物の訪問順序を見落としている可能性があります。そこで、2点間の距離をランダムに変動させてTSPを複数回解き、得られた複数の初期解についてそれぞれ局所改善を行います。ここでヒューリスティクスによるTSPソルバが威力を発揮します（非常に高速で、かつ最適解に近い解を複数得られるため）。全体で数百ターン程度スコアが改善します。

天に祈りつつ乱数のシードを変更します。数十ターン程度スコアが改善します。

最終的なスコアは 24,115 ターンになりました。25,000 ターンを切ったあたりでかなり限界を感じていたものの、最後まで地道な改善を重ねることでさらに 900 ターン近く削減することができたため、非常に満足しています。今回の問題は幾何学的な要素も強く、ビューアを眺めることで非効率な部分を見極め、それを改善するような手法を考えることがかなり重要だったと思います。

最後に、試してみたがうまくいかなかった方法をいくつか挙げておきます。

巻物の取得個数に応じて2点間の異なるパスを用意する

巻物の取得個数によってジャンプ幅が異なるため、巻物の取得個数に応じて辺の重みを計算し直し、複数の最短経路を使い分ける方法を試しましたが、計算時間の割にスコアがほとんど改善せず、ボツになりました。

初期解の生成に用いるグラフをより複雑にする

King's graph と Knight's graph のシンプルな組み合わせで生成していたグラフを、無駄な辺を減らしてより遠くの点と線分で結ぶグラフに変更してみましたが、こちらも計算時間の割にスコアがほとんど改善せず、ボツになりました。

連続的な評価値上で局所改善を行う

最終的な評価値が離散値であっても連続的な評価値上で最適化を行うことでより良い結果が得られる場合がありますが、この問題では探索範囲が狭まってしまい、かえって結果が悪化してしまいました。