WL-Algorithm

AtCoderで出題されていて、topcoderでも紹介していたのでちょっとまとめてみました。2人が最適な行動を行ったとき、勝つか負けるかを判定する単純なアルゴリズムです。
WL-AlgorithmというとWang-Landau Algorithmを指すことが多いようなのですが、今回はtopcoderで紹介されていたこの名前で呼びます。

考え方

すごくシンプルな考え方です。

function isWinning(今の位置){
  for(現在位置からのすべての行動x)
    if(isWinning(x)は負け) return 勝ち;
  return 負け;
}

• 相手を必ず負けさせるような手が存在するなら現在の位置では勝ち決定。

→isWinning(x)が負けのとき

• そのような手がないないのであれば負け。

これを勝敗が決定する最後の手から考えていくと先手必勝か後手必勝かを判定出来ます。

実践例

今回はAtCoder Regular Contest 038のB-マス目と駒について考えます。
今の位置は(r, c)で表します(rは現在の行、cは現在の列)。現在位置からの全ての行動は(r + 1, c), (r + 1, c + 1), (r, c + 1)である(右、右下、下に移動可能)。するとコードは次のようになります。

string grid[]; //マス目の各列
int H, W;       //Hは行数、Wは列数
bool isWinning(int r, int c){
  if(r >= H || c >= W || grid[r][c] == '#') //この位置が盤外または障害物ならば勝ち扱い
    return true;
  if(isWinning(r + 1, c) == false)
    return true;
  if(isWinning(r + 1, c + 1) == false)
    return true;
  if(isWinning(r, c + 1) == false)
    return true;
  return false;
}

盤外と障害物の対処方法を加えていますがそれ以外は先ほどの考え方と変わりません。ただし、これだと計算量が多いのでメモ化をして改善したコードは次の通り。

string grid[MAX];
int H, W, m[MAX][MAX]; //mがメモ

bool isWinning(int r, int c){
  if(r >= H || c >= W || grid[r][c] == '#')
    return true;
  if(m[r][c] != -1)
    return m[r][c];
  bool result = false;
  if(isWinning(r + 1, c) == false)
    result = true;
  if(isWinning(r + 1, c + 1) == false)
    result = true;
  if(isWinning(r, c + 1) == false)
    result = true;
  return m[r][c] = result;
}

既に計算済みならばメモを残して再計算しないように工夫をしているだけです。