評価関数を作ってビームサーチした。
前提
収穫機を買うのをどこでやめるか問題はしばらく考えずに、収穫機も資金に換算したスコアで物事を考えることにした。
評価関数
収穫機を設置/撤去する場所の持つべき望ましい性質を列挙して、それらの組み合わせで評価関数を作る。評価はマス毎に行い、価値の高いマスに収穫機を設置して価値の低いマスから収穫機を撤去する貪欲法を前提とする。また、理想的には、収穫機のあるマスの価値の総和を取ると盤面の価値になっていてほしい。
以下の評価関数に従って貪欲法をするとして、収穫機を買うのを止めるタイミングを全探索すると2.6億程度のスコアになった。
マスの価値
基本的には設定の通り、マスを覆う連結成分のサイズ×野菜の価値がそのマスの価値と考えるとよさそう。まだ出現していない野菜については時刻が離れると価値が指数的に下がるとして調整した。時刻の値は野菜の出現日と消失日の2種類があるが、消失日に従って下がるとしたほうがよかった。
また、既に出現している野菜についても、やはり消失日が遠いと価値が指数的に下がるとしたほうがスコアがよいようだった。
マスの価値の伝搬
現在か近い未来に価値の高い野菜が生えるマスの周辺は価値が高いと考えられる。ただ、具体的に価値をどう伝搬するかが問題だった。周辺にどれだけ野菜が多かろうと1ターンで覆えるマスは1つだけなので、野菜が多いエリアを過大評価しないようにする必要がある。
いろいろ試した結果、最大連結成分からの最短経路DAGを作って、その逆順に各頂点$v$に$\max_{pはvの親頂点}(pの価値)$に減衰率を掛けたものを加算していくことにした。
- これだと距離について指数的に価値が減っていくことになるけれど、価値が3倍なら3ターン掛けてでもいくべき、と考えると反比例で減っていくほうが自然に思える。ただ、こちらは高速な表現ができなかった。
- 最大連結成分から到達する前に消失してしまう野菜の価値は伝搬しないようにする。
連結していることの価値
収穫機の連結性は維持したい。これを収穫機のないマスについて言い換えると、連結成分の隣は価値が大きい。収穫機のあるマスについて言い換えると、連結成分の関節点は非関節点より価値が大きい。
収穫機が数個のうちはいくつかの連結成分に分離して遠くの野菜を取りに行く可能性も考慮するつもりだったが、試してみるとそれで得られる利益がほぼないことがわかったので、最終的にはひとつの連結成分を伸縮することを前提とした方針に変えた。つまり、評価関数に含めるのではなく、収穫機を撤去するマスは非関節点で、収穫機を置くマスは連結成分の隣とした。
また、下記のビームサーチをする際には収穫機のあるマスの価値の総和を盤面の価値としたが、この時は非関節点が多い配置のほうが（次の撤去候補が多いぶん）やや良いという考えに基づいて、非関節点の評価値に1より少し大きい定数を掛けた。
ビームサーチ
上の評価関数を調整すると、局所的には明らかな問題が見つからなくなった。大きな改善があるとしたら「この日は上のほうに収穫機が集まっているけれど、長期的には実は下に集まったほうが得だった」のような状況をできるだけ減らすくらいで、これは適切に状態をまとめてビームサーチすることで実現できそうと思った。
ビームサーチの前提として似た盤面をまとめるために、全体を8×8の4個の領域に区切って、各領域に収穫機が何個あるかで盤面を同一視することにした。ただ、序盤についてはこの同一視はやりすぎで、区切る領域を少し増やしたほうが良いようだった。最終的には時間経過で16個→5個→4個と分割数を減らすように調整した。
終盤のほうが重要なのでビーム幅は終盤に大きいほうがよく、幅30から幅150まで増えていくようにした。
まだ収穫機を買うのをいつ止めるかという問題が残っている。今度は収穫機の調達数で全探索するわけにもいかないので、830日目以降は買わないという単純な仕組みにした。ここは時間があればもう少し詰めたかった。
