n-knuu's logs

憧れ駆動。だいたい競プロ

Win-Lose Algorithm

はじめに

この記事は、Algorithm Games – topcoderに書いてあるWL-Algorithm(要はゲーム系の問題で、後ろから探索するもののうち単純に再帰して深さ優先探索していくやつ)についての備忘録です。*1
深さ優先探索、メモ化再帰pythonについて知っていれば、この記事は読めます。


概要

競技プログラミングにおいて、ゲーム系の問題は、ARC038の解説でもあるように、大体は以下の3つで解けると言われている。

  1. 後ろから探索する
  2. Grundy数を求める
  3. adhocな必勝法を見つける

この記事では、1の後ろから探索する場合で、特に深さ優先探索していくものについて考える。

Win-Lose Algorithm

ここで行うゲームとは

  • 2人で行う
  • 現在の状態から遷移できる状態がどのターンでも両者ともわかる
  • 終了状態で勝ち負けが決まる

というものである。例えばトランプの大富豪はここでいうゲームには入らない。

このアルゴリズムでは、関数isWinningを定義し、初期状態を引数としてisWinningを計算する。
isWinning(state): 現在の状態(state)で、勝つ(True)か負ける(False)かを返す
この関数は以下のように動作する。

  1. 現在の状態が終了状態なら負け*2
  2. 現在の状態から遷移できる状態を全て求める
  3. 全ての状態についてisWinningを計算する
    1. 3で計算したisWinningで、1つでも負け(False)があれば勝ち(True)を返す
    2. それ以外は負け(False)を返す

pythonで書くと以下のようになる。

def isWinning(state):
    """現在の状態(state)で、勝つ(True)か負ける(False)かを返す"""
    if state == 終了状態:
        return False # 負け

    nextStates = (stateから遷移できる全ての状態)
    for nextState in nextStates:
        if isWinning(nextState) == False: # 次の状態が負け
            return True # 勝ち
    return False # 負け

このアルゴリズムを使うときに考えるべきは、以下の3つである

  • ゲームの初期状態は何か
  • ゲームの終了状態は何か
  • 現在の状態から遷移できる状態を全て列挙できるか

また、メモ化を行うときは以下のようになる。

# memo[state]: 状態stateにおける勝ち負けで、最初はNoneが入っている
def isWinning(state):
    """現在の状態(state)で、勝つ(True)か負ける(False)かを返す"""
    if state == 終了状態:
        return False # 負け
    if memo[state] != None:
        return memo[state]

    nextStates = (stateから遷移できる全ての状態)
    for nextState in nextStates:
        if isWinning(nextState) == False: # 次の状態が負け
            memo[state] = True
            return True # 勝ち
    memo[state] = False
    return False # 負け

B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder
H行W列のマス目と駒が1つ与えられ、2人で順番に駒を動かしていく。駒は最初(1, 1)にあり、いくつかのマスには障害物がおいてある。駒が(i, j)にあるとき、(i, j+1)、(i+1, j)、(i+1, j+1)の3つの場所に移動可能である。ただし、移動先の場所に障害物がある場合は移動できない。
与えられた盤面で、先手(First)と後手(Second)のお互いが最善を尽くしたとき、どちらが勝つか求めよ。

解法

この問題においてWin-Lose Algorithmを用いる。(簡単のため、0-indexとする)
ここでいう状態とは、マスの座標のことである。

  • ゲームの初期状態は何か
    • (0, 0)
  • ゲームの終了条件は何か
    • 現在の位置(i, j)がi == Hもしくはj == Wであるか、(i, j)に障害物が置かれるかである。この場合、相手が移動できない位置に駒を移動させているため、勝ちである。
  • 現在の状態から遷移できる状態を全て列挙できるか
    • 現在の状態(i, j)に対して、移動可能な状態は(i, j+1)、(i+1, j)、(i+1, j+1)の3つである。

これを元に、isWinning関数を書くと以下のようになる。

# board[i][j]: マス(i, j)の状態を表す
# board[i][j]が'#'ならば、(i, j)には障害物がおいてある
def isWinning(i, j):
    if i == H or j == W or board[i][j] == '#':
        return True

    dij = [(1, 0), (0, 1), (1, 1)]
    nextStates = [(i+di, j+dj) for di, dj in dij]
    
    for nexti, nextj in nextStates:
        if isWinning(nexti, nextj) == False:
            return True
    return False

メモ化を行う場合は以下のようになる。

# memo[i][j]: (i, j)における勝ち負け(初期状態ではNone)
def isWinning(i, j):
    if i == H or j == W or board[i][j] == '#':
        return True
    if memo[i][j] != None:
        return memo[i][j]

    dij = [(1, 0), (0, 1), (1, 1)]
    nextStates = [(i+di, j+dj) for di, dj in dij]
    
    for nexti, nextj in nextStates:
        if isWinning(nexti, nextj) == False:
            memo[i][j] = True
            return True
    memo[i][j] = False
    return False

最後に

自分のような競プロ初心者はゲーム系の問題でよく出て来る(らしい)Grundy数とかいう大層なものの以前に、これが直感的に理解できないので書いて整理しておきたかった。
Algorithm Games – topcoderについては、grundy数を習得したかった - nanikakaのAOJ航海日誌が詳しい。
topcoderData Science Tutorials – topcoderでいろいろなアルゴリズムについて解説しているので蟻本とあわせて読んでいきたい。

*1:この名称は一般的ではなさそうなのでこの記事は釣りっぽい

*2:ゲームによっては勝ちである場合もある