Очередь - 2

На этот раз я немного отойду от темы блога и опубликую алгоритмическую задачу.

Как и в предыдущей задаче, Штирлиц и Мюллер по очереди стреляют по очереди. На этот раз в очереди N человек. Нужно написать программу, которая для каждого из чисел 0 <= N < 1000 вычислит, кто выиграет при оптимальной игре обоих игроков.

Сразу скажу, что решить эту задачу прямолинейным поиском в глубину не получится. Мой вариант на Java тратил больше 10 минут уже при сравнительно небольших N в пределах 40.

Решение
Для решения этой задачи нам пригодится функция Шпрага-Гранди. Строгое доказательство её свойств можно посмотреть здесь, я же ограничусь только формулировками.

Пусть $x$ - некоторая позиция в нашей игре, а $F(x)$ - множество всех позиций, в которые можно перейти из $x$ за один ход. Тогда по определению$$G(x) = min\{n \geq 0: n \neq G(y), y \in F(x)\}$$Другими словами, $G(x)$ это наименьшее целое неотрицательное число, которое не встречается среди значений Шпрага-Гранди для позиций, достижимых из $x$ за один ход.

Для проигрышных позиций значение Шпрага-Гранди равно нулю. Соответственно, выигрышная стратегия заключается в том, чтобы после своего хода оставлять противнику позицию с $G(x)=0$.

Если у нас есть $n$ игр $Г_1,...,Г_n$, то можно рассмотреть игру-сумму, в которой игровое поле состоит из совокупности игровых полей. За один ход игрок выбирает некоторое $i$ и делает ход на поле игры $Г_i$. Проигрывает тот, кто не может сделать хода ни на одном из полей. В этом случае значение Шпрага-Гранди для игры-суммы может быть вычислено как$$G(x) = G(x_i) \oplus G(x_2) \oplus ... \oplus G(x_n)$$Здесь $x$ - объединённая позиция, $x_i$ - позиции на каждом из полей, $\oplus$ - побитовое исключающее "или".

Теперь вернёмся к нашей задаче о расстреле очереди. Если один из игроков убивает человека в середине очереди, то очередь распадается на две части. При этом эти части никак не зависят друг от друга, и мы можем рассматривать возникшую позицию как совокупность двух игр.

Это наблюдение позволяет нам значительно сократить объём перебора. Если очередь распалась на два меньших куска, то нам достаточно будет посчитать значение Шпрага-Гранди для каждого из них по отдельности. Это значительно проще, чем пытаться анализировать совокупную позицию.

Теперь, собственно, код на Java:

import java.util.*;

public class Game {

    private static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
    
    public static void main(String[] args) {
        for (int i=0; i<1000; i++) {
            int g = G(i);
            if (g > 0) {
                System.out.println(i + ": First player wins");
            } else {
                System.out.println(i + ": Second player wins");
            }
        }
    }

    private static int G(int n) {
        if (!cache.containsKey(n)) {
            int g = calculateG(n);
            cache.put(n, g);
        }
        return cache.get(n);
    }
    
    // Calculates G when there are exactly n persons in the queue
    private static int calculateG(int n) {
        if (n == 0) {
            return 0;
        }
        
        Set<Integer> subValues = new HashSet<Integer>();
        for (int i=0; i<n; i++) {   // i is the number of the victim we are going to kill
            int leftPart = i;
            int rightPart = Math.max(n-i-1, 0);
            
            if (leftPart == 1) {
                leftPart = 0;   // The leftmost guy runs away
            }
            
            if (rightPart == 1) {
                rightPart = 0;  // The rightmost guy runs away
            }
            
            int g = G(leftPart) ^ G(rightPart);
            subValues.add(g);
        }
        
        int i=0;
        while (subValues.contains(i)) {
            i++;
        }
        
        return i;
    }
}

Несколько первых результатов:

0: Second player wins
1: First player wins
2: First player wins
3: First player wins
4: Second player wins
5: First player wins
6: First player wins
7: First player wins
8: First player wins
9: First player wins
10: First player wins
11: First player wins
12: Second player wins