【ミニマックス法】ABC201 - D - Game in Momotetsu World

igasu_7

2024年3月5日 19:16

理解に手こずった問題についてアウトプット。

ABC201 D問題: Game in Momotetsu World (diff 1317)

提出したコード
https://atcoder.jp/contests/abc201/submissions/50740547

$${H}$$行$${W}$$列のグリッドが与えられる。
マス$${(i, j)}$$には '+' か '-' が書かれている。
$${(1, 1)}$$に置かれているコマを右か下に動かして$${(H, W)}$$まで進める。
1Pと2Pが交互にコマを動かし、'+' マスなら+1点、'-' マスなら-1点。
両者が最適に行動したときの試合結果を出力してね。

本記事では先攻プレイヤー (高橋くん) のことを 1P、後攻プレイヤー (青木くん) のことを 2P と呼びます。

DP？

DPっぽい問題です。
$${H, W \leq 2000}$$なので仮に

$$
dp[i][j][k]: マス(i, j)におけるプレイヤー k の最高得点 (k = 0, 1)
$$

のようなdpをしようとしても計算量的には間に合いそう。
しかし、両者が最適な行動をとるので片方のプレイヤー目線での理想的な動きはなかなか起こりそうにないです。

自分の得点を増やしたい気持ちと相手の得点を増やしたくない気持ちの両方あり、単純なDPでどう解くのか難しいところです。

ミニマックス法

近年、将棋の対局を見ていると「評価値」なるものが表示されていることがあります。現在の盤面でどちらが優勢かを表すものですが、今回の問題はこのゲームにおける「評価値」を求めることを問われています。

$$
dp[i][j]: マス(i, j)における評価値
$$

将棋のような複雑なゲームでは簡単にはいきませんがこのゲームでどちらが優勢かどうかは 1P の得点と 2P の得点の差を考えるだけで良さそうです。つまり、

$$
dp[i][j]: マス(i, j)における1P の得点と 2P の得点の差の最適値
$$

を考えます。
ここで「最大値」ではなく「最適値」としているのは、奇数ターンは 1P の番、偶数ターンは 2P の番なので$${(i, j)}$$によって数値の捉え方が変わるためです。

1P 視点で考え、点差$${P}$$を$${P = (1Pの得点) - (2Pの得点)}$$とします。
1P のターンでは 1P が最も有利になる行動、すなわち点差を最大化する行動が最適です。
2P のターンでは 1P が最も不利になる行動、すなわち点差を最小化する行動が最適です。

これをミニマックス法といいます。

ミニマックス法（ミニマックスほう、英: minimax）またはミニマックス探索とは、想定される最大の損害が最小になるように決断を行う戦略のこと。

Wikipedia - ミニマックス法

評価値は先の展開も見据えて考えます。
あるターンの操作が最適かどうかを知るためにはその次のターンの盤面を知る必要があり、さらにその次のターンの…と続くことから再帰的に解くことができます。

しかしPythonで再帰関数を実装するとメモ化してもTLEになってしまったので普通にforループで実装します。終局のマス$${(H, W)}$$から処理を開始します。

""" ミニマックス法 """
inf = 1 << 60
Di = [0, 1]
Dj = [1, 0]
def solve():
    dp = [[-inf] * W for _ in range(H)]
    dp[H - 1][W - 1] = 0
    for i in reversed(range(H)):
        for j in reversed(range(W)):
            if i == H - 1 and j == W - 1:
                continue
            t = (i + j) % 2
            res = -inf if t == 0 else inf
            for di, dj in zip(Di, Dj):
                u = i + di
                v = j + dj
                if not(0 <= u < H and 0 <= v < W):
                    continue            
                add = 1 if A[u][v] == '+' else -1
                if t == 0:
                    res = max(res, dp[u][v] + add)
                else:
                    res = min(res, dp[u][v] - add)
            dp[i][j] = res
    return dp[0][0]

H, W = map(int, input().split())
A = [input() for _ in range(H)]
point = solve()
ans = 'Takahashi' if point > 0 else 'Aoki' if point < 0 else 'Draw'
print(ans)

ネガマックス法

ミニマックス法のコードでは

$$
P = (1Pの得点) - (2Pの得点)
$$

を考えていたためターンによってmaxを取ったりminを取ったりしてごちゃごちゃしていました。
2Pのターンは上の式を逆転して

$$
Q = (2Pの得点) - (1Pの得点) = -P
$$

と捉えると、実装がシンプルになります。これをネガマックス法といいます。

チェスなどパスのないゲームでは、ノードごとに評価値の正負を逆転させることで「相手は自分にとって損な手を探索する」のではなく「相手は相手にとって得な手を探索する」ように書き換えることができる。これをネガマックス(Negamax)法と呼ぶ。