Беспристрастность игр и теория/функция Шпрага-Гранди

[IlyaCk]

Пожалуйста, подтвердите/опровергните верность моего понимания нижеизложенных моментов взаимосвязи пристрастности/беспристрастности игр и теории Шпрага-Гранди. Ссылки на источники, где это объяснено, тоже приветствуются. Но именно источники, где объяснено и одно, и другое. Источники, где вводят "кто ходит" в состав позиции и не обсуждают Шпрага-Гранди, а также отдельно другие источники, где вводят теорию Шпрага-Гранди, изначально объявив "рассматриваем только беспристрастные игры", вроде бы и так известны.

Игра называется пристрастной, если перечень возможных ходов из одной и той же позиции может (хотя бы иногда) зависеть от того, кто из игроков ходит. Если таких зависимостей нет, игра беспристрастная.

В некоторых ситуациях, пристрастная игра может быть искусственно сведена к "как бы беспристрастной" путём того, что позиция включает в себя также и информацию о том, кто сейчас ходит. После такого уточнения понятия "позиция", ход начинает определяться только позицией. Если игра конечна, ациклична, завершается выигрышем одного игрока и проигрышем другого, и эти выигрыш&проигрыш не имеют числового или ещё какого-то выражения, а просто выигрыш/проигрыш -- вполне можно, например, расставить каждой позиции её выигрышность/проигрышность, действуя по обычным правилам "позиция проигрышна, если тот, кому она досталась, этим уже проиграл, или все допустимые ходы ведут в выигрышные позиции; позиция выигрышна, если тот, кому она досталась, этим уже выиграл, или есть хотя бы один допустимый ход, ведущий в проигрышную позицию". И тут пристрастность начальной формулировки игры никак всему этому не мешает, лишь бы было правильно проведено преобразование позиций и ходов. Причём, тут НЕТУ требования "проигрывает тот, кто не может походить" -- можно рассматривать хоть игры, в которых тот, кто не может походить, проигрывает, хоть игры, в которых тот, кто не может походить, выигрывает, хоть игры, в которых часть позиций, из которых нельзя походить, проигрышна, а часть выигрышна (лишь бы это чётко описывалось правилами игры).

Если функция Шпрага-Гранди формально вроде бы и используется, но особенности игры таковы, что фактически используется один только mex без ксора, то добавляется ограничение, что всё это справедливо только для игр, в которых тот, кому некуда ходить, проигрывает. Однако возможность сведения пристрастных игр к беспристрастным остаётся. С другой стороны, непонятно, чем такое использование Шпрага-Гранди вообще лучше одних только выигрышных/проигрышных позиций.

А в ситуации, когда функция Шпрага-Гранди используется полноценно, включая свойство "SG суммы игр равно ксору SG этих игр" -- вот тогда сводить пристрастные игры к беспристрастным нельзя. По крайней мере, нельзя вышеупомянутым способом, и не существует никакого известного другого. И нельзя потому, что когда происходит разбиение позиции на несколько независимых (SG которых ксорятся), теряется свойство "просто введём в позицию, кто ходит, и каждый игрок автоматически будет получать только те позиции, из которых ходит именно он".

Ещё раз: прошу прокомментировать верность/неверность такого понимания и дать ссылки на изложения, где обсуждаются и пристрастные игры, и теория Шпрага-Гранди.

[nya]

Я плохо понял вопрос. Как вы уже отметили, можно свести пристрастные игры к беспристратсным путём добавлении информации о том, кто ходит, после чего если вам эту новую игру получается представить в виде прямой суммы каких-то других игр, то SG этой новой игры равно ксору SG этих других игр.

[IlyaCk]

Я, конечно, могу ошибаться (потому и спрашиваю), но разве в доказательстве того, что можно ксорить, не используется, что любой игрок может воспользоваться любым ходом из позиции? И разве сведение пристрастных игр к беспристрастным не нарушает это свойство?

Рассмотрим такую игру. Есть полоска, вначале состоящая из N клеточек, расположенных одной непрерывной последовательностью. Алиса может на каждом своём ходу вычеркнуть любые идущие подряд 2, или 4, или 16 клеточек. Боб может вычеркнуть на каждом своём ходу любые идущие подряд 1, или 2, или 3 клеточек. Проигрывает, по-стандартному, тот, кому некуда ходить.

Пусть начальная позиция "ходит Алиса, один непрерывный кусок из 8 клеточек", что в терминах, использующих сумму игр и ксор результатов SG, было бы удобно обозначать как "(Алиса, 8)", а в терминах, не использующих сумму игр, например, как "(Алиса, 00000000)", где "0" -- чистая(целая), "1" -- "зачёркнутая". Среди ходов Алисы есть ход "разорвать полоску двумя клеточками, вычеркнутыми ровно посредине", т.е. перейти в позицию "(Боб, 00011000)". При переходе к сумме игр и ксору результатов SG должно быть сказано, что получается сумма двух игр "(Боб, 3)", и даже не важно, чему конкретно равно SG((Боб, 3)), всё равно ксор двух одинаковых чисел даст ноль, что будто бы доказывает, что такой ход Алисы приносит ей выигрыш. Однако, рассмотрев всё это без ксора SG, видим, что Боб из позиции (Боб, 00011000) может пойти в позицию (Алиса, 11111000), зачеркнув все три клеточки первой из "половин". Когда Алисе достаётся позиция (Алиса, 11111000), она может пойти ТОЛЬКО или в (Боб, 11111110), или в (Боб, 11111011), и после любого из этих ходов Боб зачёркивает одну последнюю клеточку и выигрывает.

Я не провёл анализ, может ли Алиса обеспечить себе выигрыш каким-то другим первым ходом; но ведь смысл всего этого примера -- показать, почему настолько просто совмещать сведение пристрастных игр к беспристрастным с теоремой Шпрага-Гранди вроде как не получается.

Или, что имелось в виду под "... если вам эту новую игру получается представить в виде прямой суммы ..."? Хотя бы на уровне примеров? Или имелось в виду, чтоб в совсем-совсем начальной формулировке зависимость от того, кто ходит, была, но в тех играх, в сумму которых распадается начальная игра, чтоб ужЕ не_было? А так вообще бывает?

[IlyaCk]

Прошу прощения, но меня опять интересует этот вопрос, так что прошу по возможности ответить.

[Iam]

По-видимому, с вашим вопросом связан этот пример https://en.everybodywiki.com/Risk-free_games беспроигрышной циклической игры коалиции из трех игроков против коалиции из четырех игроков даже при условии, что начальный ход (т. е. игрока, начинающего игру) выбирает коалиция с бОльшим числом игроков.
Для формализации ограничений на возможные ходы различных игроков используется понятие участник игры, который входит в одну из двух коалиций. В классе игр участникам могут присваиваться различные номера, под которыми они выступают в роли игроков.
Однако прямого использования функции Шпрага-Гранди там и в статье по ссылке не увидел.

[IlyaCk]

Что-то я не_понял, какое вообще отношение имеет Ваша ссылка к моему вопросу.
Я рассматриваю игру ДВУХ игроков, без коалиций. Но такую, что если не_включать в позицию "кто ходит", то получится, что множество возможных ходов первого игрока и множество возможных ходов второго игрока из одной и той же позиции могут различаться. Например, как уже упомянуто: пусть и Алиса, и Боб могут только вычёркивать подряд идущие клеточки, но Алиса только или 2, или 4, или 16, а Боб только или 1, или 2, или 3.

[Iam]

IlyaCk, коалиция - игрок в обобщенной игре (чтобы не запутать пусть суперигрок); игрок некоторой коалиции, делающий ход, - это позиция, в которой соответствующий суперигрок может делать ход. У каждого суперигрока свой набор позиций, в которых он может делать ходы - в принципе они определены рисунком. Хоть напрямую функция Шпрага-Гранди не упоминается, но анализ примера, по-видимому, к ней сведется.

-- 23.07.2019, 11:26 --

Маленькое дополнение. Если перевести пример на бескоалиционную игру, то он может трактоваться так. Вам предлагается сыграть в позиционную игру на некотором графе, где в в цикле длины 7 будете делать 4 хода в заданной последовательности, а противник 3. Кроме того, вам предоставлена возможность выбора 1-го хода с любого номера в цикле. В примере игрок, делающий 3 хода, всегда выигрывает. А за счет чего это происходит? Очевидно, за счет того, что в разных позициях игры игроки имеют различные наборы возможных ходов.