TryAlgo

Sprague-Grundy theorem

Given a 2 player impartial game, decide for a given configuration if there is a possibility for the first player to win assuming the second player plays perfectly.

Summary

See the corresponding wikipedia page for more details.

The theory says the following. Suppose you have a directed acyclic graph, with a pebble on a cell. Two players move in turns the pebble along an outgoing arc to a successor vertex. The first player who cannot move the pebble anymore looses.

Which are the winning and which are the loosing configurations? Well this can be determined recursively. Vertices with zero outdegree are loosing vertices. Vertices that lead to a loosing vertex are winning vertices. Vertices that lead only to loosing vertices are loosing vertices.

Now we can augment this binary information by replacing it by a non-negative integer, called the Grundy number or nimber. Vertices with zero outdegree get the number 0. In general the number assigned to a vertex is the smallest non-negative integer which does not belong to one of the reachable vertices. Clearly a vertex is winning iff its nimber is positive.

These number became interesting when combining two games, and this is the purpose of the Sprague-Grundy theorem. Suppose you combine two DAGs into one game. Now there is a pebble in each graph, hence a game configuration is a pair of vertices, one from each graph. A valid move is to move one of the pebbles to a successor, and to leave the other pebble untouched. This is a game that could be decribed by a much bigger and single DAG. The Sprague-Grundy theorem says that the nimber of configuration (u,v) is simply the bitwise exclusive OR of the nimbers of u and of v.

Example

See this page for an excellent and more detailed explanation of a solution to the following problem.

You are given a row of cells, some of which are marked. Two players in turn each marks a cell. The first player who reaches a configuration with 3 adjacent marked cells wins. The goal is to list all cells such that if the first player marks one of those, then he can always win the game.

intial configuration: .....X.
player 1:             ..X..X.
player 2:             ..X.XX.
player 1 wins:        ..X.XXX

Basically you first need to detect patterns where the first player can immediately win, namely .XX, X.X or XX. Then by adding X.. to the left and ..X to the right we end up with a string of the form X..?X..?X etc, where every sequence of points has some length at least 2. These sequences form sub-games, where the 2 first and 2 last points are forbidden cells, since the opponent can then immediately win. The trick is then to compute the nimber for configurations of the form X.{k}X for every k up to 200. Then you can combine these numbers with XOR in order to decide whether some configuration is loosing or not.

The following code solves this problem in time .

from sys import *

def readint():    return int(input())
def readstr():    return input().strip()
def readarray(f): return map(f, input().split())


N = 205  # compute nimber until until 200 + 2 + 2 for the added border

# number[i] is nimber number of game on X.{i}X
nimber = []

for L in range(N):
    reachable = set()                # compute nimber numbers for accessible states
    for i in range(2, L - 2):        # i = allowed position to play (not too close to border)
        reachable.add(nimber[i] ^ nimber[L - i - 1])
    val = 0                          # find smallest value NOT in set reachable
    while val in reachable:
        val += 1
    nimber.append(val)


def solve(config):
    """ This part has complexity O(N)
    """
    # if "XXX" in config:              # should never happen, but who knows
    #     return []
    sol = set()                      # first test if player can win right now
    pattern = [".XX", "X.X", "XX."]
    for i in range(3):
        last = config.find(pattern[i])
        while last != -1:
            sol.add(last + i)        # position of . in pattern in config
            last = config.find(pattern[i], last + 2)  # +2 because X.X?? matches ??X.X
    if sol:
        return sol
    config = "X.." + config + "..X"  # this trick avoids particular processing at border
    sizes = []                       # sizes of subgames
    s = 0
    for z in config[1:]:             # avoid initial X
        if z == 'X':                 # determine sizes of . sequences delimited by X
            sizes.append(s)
            s = 0
        else:
            s += 1                   # count the z='.'
    current = 0                      # compute nimber of given configuration
    for s in sizes:
        current ^= nimber[s]
    start = -2                       # start of current . sequence
    for s in sizes:
        for j in range(2, s - 2):    # compute nimber of playing j in this . sequence
            if current ^ nimber[s] ^ nimber[j] ^ nimber[s - j - 1] == 0:
                sol.add(start + j)   # is loosing configuration for second player
        start += s + 1
    return sol


for testcase in range(readint()):
    sol = solve(readstr())
    if sol:
        print("WINNING")
        format = "%i"
        for i in sorted(sol):
            print(format % (i + 1), end='')
            format = " %i"
    else:
        print("LOSING")
    print()