@dalbio

В чём разница в скорости работы между перебором всех состояний игры и функций Шпрага-Гранди?

Вообщем гуляя по emaxx я наткнулся на функцию Шпрага-Грнади (перевод состояний любой игры в Ним-число),но я не понимаю,а зачем эта функция вообще нужна. Почему она лучше просто перебора,мы что там,что там перебираем все возможные состояния только в переборе мы не используем MEX,следовательно перебор должен быть ещё и быстрее.Тогда возникает вопрос: а зачем нужна эта функция? Буду очень благодарен за ответ.
  • Вопрос задан
  • 52 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Просто так примененная в лоб функция Гранди нисколько не быстрее обычных пометок "выигрышная"/"проигрышная" ситуация. Даже медленнее, потому что надо не просто смотреть, есть ли переход в выигрышную ситуацию, а надо смотреть в какие значения можно сделать переход и найти минимальное ими не покрытое.

Но она обладает замечательным свойством - если состояние игры можно разложить на несколько независимых игр и игорк в свой ход может сделать ход в любой из игр, то функция Гранди может быть подсчитана как xor значений для всех состояний. По умному это называется, что игра является суммой игр. В некоторых задачах это позволяет колоссально сократить простарнство состояний.

Один пример - игра Ним. Есть несколько кучек камней. За свой ход игрок может взять сколько угодно камней из любой кучки. Проигрывает тот, кому не останется камней. В простом переборе вам придется в качестве состояния хранить вектор количеств камней в каждой кучке. Но ведь тут стостяние очевидно раскладвается на под-игры: каждая кучка - своя отдельная игра. Причем, функция Гранди тут тривиальна - это просто количество камней. Вот и получается решение игры Ним - взять xor размеров всех кучек. Если не 0, то состояние выгрышное. Надо взять из какой-то кучки столько камней, чтобы получился xor, равный 0.

Еще пример - есть плитка шоколада. Игроки ее ломают вдоль клеток. За свой ход игрок может взять любой прямоугольный кусок и разломить его как-то вдоль клеток (если там более 1x1 клеток, конечно). Проигрывает тот, кто не сможет сделать ни одного хода. Опять же, при простом переборе пришлось бы хранить в состоянии размеры всех кусоков. Тут ОЧЕНЬ много вариантов. А с функцией Гранди - достаточно рассмотреть состояния вида "одна плитка размера n x m". После одного хода у вас будет 2 плитки, но меньшего размера. Вы уже знаете для них функцию гранди, XOR'ите их и получаете функцию для возможного перехода.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы