Pythonで「蓮と毛虫」ゲームの勝利に必要な期待手数を求めるプログラム

問題の概要

n行m列のグリッドを考えます。Amal（アマル）とBimal（ビマル）が、このグリッド上で次のようなルールのゲームを行います。

• Amalは白い「蓮（ロータス）」のタイルを最上行の任意のマスに置き、Bimalは「毛虫（キャタピラー）」のタイルを最下行の任意のマスに置きます。
• Amalが先手となり、交互に手番を進めていきます。
• Amalは自分のタイルを、現在いるマスに隣接する8方向（縦・横・斜め）のいずれかのマスへ移動できます。
• 一方、Bimalの毛虫タイルは、左右への移動またはその場にとどまることしかできません。

Amalの目的はできるだけ少ない手数でBimalを捕まえることであり、逆にBimalの目的はできるだけ長く逃げ続けることです。両者がそれぞれ配置する列をランダムに選んだ場合、Amalがこのゲームに勝つまでに必要となる手数の期待値を求めるのが本問題です。

例として、n = 5、m = 7 の場合、出力は 4.571428571428571 となります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• r を 0 で初期化します。
• l を 0 から m - 1 まで繰り返します。
  • temp := n - 1.0 とします。
  • l >= n の場合、temp に (l - n + 1) * ((l - 1) / m) を加算します。
  • l < m - n の場合、temp に (m - n - l) * ((m - l - 2) / m) を加算します。
  • r に temp / m を加算します。
• 最後に r を返します。

実装例

理解を深めるために、以下のPythonによる実装例を見てみましょう。

def solve(n, m):
    r = 0

    for l in range(m):
        temp = n - 1.0
        if l >= n:
            temp += (l - n + 1) * ((l - 1) / m)
        if l < m - n:
            temp += (m - n - l) * ((m - l - 2) / m)
        r += temp / m

    return r

n = 5
m = 7
print(solve(n, m))

入力

5, 7

出力

4.571428571428571