Игры на графах

Понедельник, 27 апреля 2015
Таймс, ауд. 404

Описание

  • Доказательство ксора в функции Гранди методом таблички \(2^k \times 2^k\)

  • Задачи про Гранди

    • Ним: за ход можно брать любое число камней из кучки
    • Спички: за ход можно брать число спичек от \(1\) до k\( \)
    • Ним, плюс ещё один ход: можно делить кучку на две
    • Игра про Карлсона, Малыша и трёхмерную шоколадку
    • Игры про пешки \(3 \times N\)
    • Hacking Bush
  • Задачи про DP, терминатора и мужика

    • Базовая версия, дополняем несколькими выходами, заклинаниями и т.д., в конце выписываем состояний [x1,y1,x2,y2,...,who]
    • Кровожадный терминатор -- хочет как можно быстрее поймать
    • Терминатор издевается -- хочет как можно медленнее, но поймать
  • Игра на большом дереве

    • Игра путь из (1,1) в (N,N), первый минимизирует, второй максимизирует
    • Игра на дереве размера \(2^h\) за \(O(2^h)\)
    • Вероятностное решение за \(O(1.69^h)\)
    • Игра на дереве с весами = бинпоиск по ответу * \(O(1.69^h)\)