День 10. Игры на графах.

  1. [Игорь Лабутин] Симметричные и несимметричные на ацикличном графе: win[state], win[state,who]
    1. Пример: кучка из n камней, за ход можно брать ai первому игроку, bi второму

  2. [Игорь Лабутин] Ретроанализ для симметричной игры на графе с циклами
    1. Вычисление за O(V+E) dfs/bfs-ом с конца результата игры из каждой вершины
    2. Вычисление длины игры, если из WIN-позиции игрок минимизирует длину игры, а из LOSE-позиции максимизирует

  3. [Игорь Лабутин] Гранди
    1. Ним: xor выигрывает c доказательством
    2. Определяем функцию Гранди: mex
    3. Замечаем, если она ноль, то LOSE, иначе WIN
    4. Учимся считать Гранди за O(E)
    5. Рисуем табличку: Функция Гранди для суммы двух Нимов
    6. Доказываем, что Гранди от суммы игр равна XOR.

  4. [Игорь Лабутин] Задачи
    1. Ретроанализ на графе с ребрами двух цветов
    2. Ретроанализ, который считает наидлиннейший выигрышный путь (иногда WIN∞)
    3. Жестокая задача: Штирлиц и Мюллер стреляют по очереди, в очереди N человек
    4. Гранди: пешки на доске 3 × N для N ≥ 109
    5. Гранди: из i-й кучки можно брать от 1 до ki камней за ход. Количества камней в кучках ni ≤ 1018

  5. [Сергей Копелиович] Задачи посложнее
    1. Hucken Bush: Grundi(1+T) = 1+Grundi(T)
    2. Ним, в котором кучки должны иметь неубывающие размеры
    3. Ним, в котором брать можно из не более чем двух кучек за ход (как факт, без доказательства)

  6. [Сергей Копелиович] Кое-что ещё
    1. DP, Ретро, Гранди → а для сложения независимых игр на графах с циклами есть функция Смита
    2. Шахматы без правила о трёх ходах: остались (K, Q), (K, P) → ретроанализ даже запущенный в лоб даст 224 состояний и понимание, кто выиграет, какой ход сделать.
    3. Игры на слишком больших графах: шахматы, крестики-нолики... Функция оценки позиции + перебор только k лучших ходов + перебор игры на глубину d