ゲームの必勝法

プログラミングコンテストチャレンジブック

4.2のゲームから4.3のグラフに入ったところ。いよいよ佳境に。

そのゲームの2番目の問題はこんな感じのもの。石をn個円形に並べる。2人が交互に石を1個か並んだ2個を取る。最後に石を取ったほうが勝ち。さて、双方最善を尽くしたときどちらが勝つか。

わからないとき、Project Euler脳だととりあえず素直に組んでみる。

def solve(n):
    def gen_next(a):
        for k in xrange(n):
            if a[k]:
                yield a[:k] + (False,) + a[k+1:]
                if k < n - 1 and a[k+1]:
                    yield a[:k] + (False, False) + a[k+2:]
                if k == n - 1 and a[0]:
                    yield (False,) + a[1:k] + (False,)
    
    def wins(a):
        if not any(a):
            return False
        elif a in memo:
            return memo[a]
        else:
            b = any(not wins(b) for b in gen_next(a))
            memo[a] = b
            return b
    
    memo = { }
    return wins((True,) * n)

N = 20
for n in range(1, N + 1):
    print n, solve(n)

20までで約1分かかるが、これで傾向がつかめて、だいたい答えがわかる。ちなみに、メモ化をもう少し適正にするとn = 20で100倍速くなるが、どっちにしても30までで1分以上かかるのであまり意味がない。
ここでページをめくってみると、あー！って感じ。Nimを考えていたときはこれに気がついたのに。