Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 30
Ну что сказать, сразу вспоминается «Ford Bayard» c игрой в палочки
Извините, но с вашей статьи трудно понять как применяется функция Шпраг-Гранди в теории игр в общем случае. В двух приведенных примерах даже не используется функции mex и xor (другими словами они могут быть решени без каких-либо знаний об игре Ним и функции Шпрага-Гранди).
Вот ссылка где очень доступно все объясняется: e-maxx.ru/algo/sprague_grundy
Вот ссылка где очень доступно все объясняется: e-maxx.ru/algo/sprague_grundy
Cпасибо за конструктивную критику! Да, на e-maxx довольно доступное объяснение, но примеров там тоже нет.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
Это уже лучший пример.
Хотя данная задача имеет тривиальное решение, поскольку количество ходов для кучки n всегда равно n-1. Тогда количество ходов для кучек (a, b, c) будет a+b+c-3.
Хотя данная задача имеет тривиальное решение, поскольку количество ходов для кучки n всегда равно n-1. Тогда количество ходов для кучек (a, b, c) будет a+b+c-3.
Верно :). Для доказательства достаточно представить, что кучки — это полоски бумаги состоящие из n клеточек в ряд, и за один ход разрешается разрезать на две любую из имеющихся бумажек, на длине от края кратной длине клеточки. Очевидно в игре изначально можно сделать (a — 1 + b — 1 + c — 1) разрезов, и игра закончится только в момент, когда все эти разрезы будут сделаны, а порядок их неважен.
Но хотелось проиллюстрировать именно решением с помощью Шпрага-Гранди.
Но хотелось проиллюстрировать именно решением с помощью Шпрага-Гранди.
Cпасибо за конструктивную критику! Да, на e-maxx довольно доступное объяснение, но примеров там тоже нет.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
Я не стал рассматривать в приведенных примерах функции mex и xor, потому что большую часть ним-подобных игр можно решить и без них.
Но можно рассмотреть и для mex с xor:
Пусть у нас есть 3 кучки из произвольного числа камней. Ход состоит в разбиении произвольной кучки на две в любом соотношении. Проигрывает тот, кто не может сделать ход, т.е. остались только кучки по 1 камню. Попробуем определить возможность выигрышной стратегии для игрока, делающего ход вторым.
Для трех кучек G(a, b, c) = G(a) xor G(b) xor G(с).
Если это выражение равно нулю, то второй игрок выигрывает, а иначе — проигрывает.
G(n) можно вычислить так:
G(1) = 0,
G(n) = mex { G(1)^G(n-1), G(2)^G(n-2), ..., G(n-1)^G(1) }
Таким образом, в зависимости от количества камней в кучках, находим «сумму игры», воспользовавшись mex и xor.
«Следовательно, состояние игры можно описать набором из N положительных чисел, а игра заканчивается, когда сумма этих чисел становится равной нулю», — несколько раз перечитывал эту волшебную формулировку, но так и не понял, КАК это может получиться.
Например, у нас есть кучки из пяти, шести и семи камней. Тогда состояние игры на данный момент можно описать как G(5, 6, 7), где «5, 6, 7» — тот самый набор положительных чисел, а N — количество кучек.
Когда сумма этих чисел становится равна нулю, можно сделать вывод, что камни закончились, т.е ход сделать невозможно. А если ход сделать невозможно, то игру можно считать оконченной.
Когда сумма этих чисел становится равна нулю, можно сделать вывод, что камни закончились, т.е ход сделать невозможно. А если ход сделать невозможно, то игру можно считать оконченной.
При всём уважении, я не понимаю, как складывая три положительных(!) числа, можно получить 0.
Хм, спасибо, исправил на «натуральных».
Тогда нулю сумма равна тогда и только тогда, когда все эти числа равны 0. Может лучше написать, что эти числа целые?
Натуральные и положительные числа в сумме не дают 0, если их самих не ноль. Это, хотел сказать GORKOFF. Если конечно там не имеется в виду xor-сумма, но вроде там еще рано.
Мне кажется эту фразу просто можно выкинуть.
Мне кажется эту фразу просто можно выкинуть.
Я думаю, что выкинуть эту фразу нельзя — именно в ней и заключается вся суть решения ним-подобных игр.
Не смотря на спорность этого вопроса, я отношу ноль к натуральным числам.
Натуральные и положительные числа в сумме не дают 0, если их самих не ноль
Не смотря на спорность этого вопроса, я отношу ноль к натуральным числам.
Тоже странное предложение:
Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.
1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
Предлагаю переписать, на что-то вроде:
Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.
1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
Предлагаю переписать, на что-то вроде:
Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
Тогда еще одно непонятное предложение:
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.
Как минимум надо переписать так:
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.
Как минимум надо переписать так:
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
На неком острове бушуют пожары. Робот смог затушить все города, кроме одного.
Пламя распространяется очень быстро, поэтому каждый день огонь пожирает все города,
соединенные дорогой с уже горящими городами. Тушить робот уже ничего не может,
единственное, что ему остается — это бежать от огня. Скорость робота совпадает со
скоростью огня, поэтому за один день робот может перебраться в соседний город.
Роботом посменно управляют два пилота Николай и Владимир, которые находятся на
естественном спутнике Земли. Не смотря на то, что робота уже не спасти и пользы от него
никакой нет, пилоты очень заинтересованы, чтобы он был уничтожен не в их смену. За
потерю робота полагается приличный вычет из заработной платы.
В первый день робот находится в столице (городе номер 1). Николай управляет роботом
в первый день и может направить его в произвольный город соединенный с 1. Далее пилоты
чередуются. Таким образом, каждый день единственное что может сделать робот — это
передвинуться на любой соседний с его текущим положением город.
В первый день горит только столица. Каждый следующий день дополнительно
загораются все города, соединенные дорогами с уже горящими.
Если пилот оставляет робота в горящем городе или направляет его в уже горящий
город, то робот не выдерживает огня и уничтожается.
По этой задаче можно кино снимать. Или даже минисериал.
Ага, или аниме.
Если интересно — посмотрите остальные задачи, которые были в этом году в списке вступительных:
lksh.ru/sis/2011/vstupit/prakt.pdf
Там есть и довольно интересные, на мой взгляд.
Если интересно — посмотрите остальные задачи, которые были в этом году в списке вступительных:
lksh.ru/sis/2011/vstupit/prakt.pdf
Там есть и довольно интересные, на мой взгляд.
Немного не понял, откуда в последнем примере взялось «a = n mod 6», это как-то связано с тем, что можно «за раз можно взять не больше четырех камней»?
Да, верно, связано.
Нам известно, что за раз можно взять не больше четырех камней. Тогда, если нарисовать граф состояний игры, будет очевидно, что из каждой вершины выходит не больше четырех дуг.
Так же известно, что
G(0, 1, 0) = 0 (по условиям).
Если теперь определить функцию для каждого состояния, то можно заметить, что функция оказывается периодической с периодом длины 6, из чего уже следует
a = n mod 6.
Нам известно, что за раз можно взять не больше четырех камней. Тогда, если нарисовать граф состояний игры, будет очевидно, что из каждой вершины выходит не больше четырех дуг.
Так же известно, что
G(0, 1, 0) = 0 (по условиям).
Если теперь определить функцию для каждого состояния, то можно заметить, что функция оказывается периодической с периодом длины 6, из чего уже следует
a = n mod 6.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Теория Игр и функция Шпрага-Гранди