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

Доказательство ксора в функции Гранди методом таблички \(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)\)