Игры на графах (28 апреля 2016)

  1. Задачи на Гранди
    1. Спичка: за ход можно брать число спичек от 1 до k
    2. Ним, плюс ещё один ход: можно делить кучку на две равных
    3. Ним, плюс ещё один ход: можно делить кучку на две не равных. Как решать? Динамика. Сгенерить числа, заметить закономерность.
    4. Игра про Карлсона, Малыша и трёхмерную шоколадку
    5. Hacking Bush
    6. Скамейка длины N. Мальчики и девочки по очереди садятся на скамейку. Садиться вполтную к кому-либо нельзя. Кто последний сел − выиграл. Кто выиграет, мальчики или девочки? За сколько работает?
  2. Задачи про DP и ретроанализ
    1. Игра с одной кучкой камней. У первого своё множество ходов, у второго своё множество.
    2. Игра с двумя кучками камней. У первого своё множество ходов, у второго своё множество.
    3. Игра с камнями с новыми правилами: кто не может сделать ход, тот выиграл; кто может ходить, обязан сделать валидный ход.
    4. Игра на матрице − идём из (1,1) в (N,N), идти только вправо-ввех, первый максимизирует, второй минимизирует
    5. Первый пытается дойти из (1,1) в (N,N), а второй пытается ему помешать
    6. Двое играют на шахматной доске 8×8 с дырками. Есть точка выхода и фишка на доске. Первый двигает фишку ходом коня, хочет выбраться. Второй двигает фишку ходом короля, хочет не дать выбраться.
    7. Ретроанализ: выиграть побыстрее
    8. Ретроанализ: выиграть помедленней (растянуть удовольствие)
  3. Игра на полном бинарном дереве глубины 40.
    1. Игра начинается в корне. Ход − спуск. В листьях числа 1 (первый выиграл) и 2 (второй выиграл).
    2. Аналогичная задача AND-OR tree
    3. Аналогичная задача первый минимизирует функцию в листе, второй максимизирует.
  4. Misere nim. Игра в Ним по новым правилами: кто не может сделать ход, тот выиграл. Решение: xor (ai - 1) = 0 − проигрышная позиция.