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