300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Общее количество прослушиваний: 775601
Общее количество побед: 486693
Общее количество побед: 486693
Как играть:
- Каждый игрок по очереди берет конфеты с доски.
- Удаление конфеты зависит от квадранта, из которого была выбрана конфета.
- Верхний левый квадрант удаляет все конфеты сверху и слева от выбранной конфеты, верхний правый удаляет сверху и справа, нижний левый удаляет нижнюю и левую, а нижний правый удаляет нижнюю и правую часть выбранной конфеты.
Как выиграть:
- Игрок, который уберет последнюю плитку, выигрывает игру.
Ход игрока 1
Ширина борта:
Высота борта:
Доступ к 'Пище для размышлений' (SFFT) для игры iChomp можно приобрести в интернет-магазине
Алгоритм, который вы узнаете в этом уроке, способен оптимально играть в большой класс игр, поэтому он окупится потраченным на его изучение временем. Ключом к разгадке станет знаменитая теория Спрага-Гранди. Если вы хотите узнать советы по игре в iChomp без изучения теории Спрага-Гранди, то прокрутите вниз до соответствующего раздела. Прежде чем углубляться в детали, нам нужно прояснить несколько терминов.
Нотация
-
Комбинаторные игры: игры для двух человек с идеальной информацией и выигрышным или проигранным исходом и отсутствием случайных ходов.
Беспристрастные игры: комбинаторные игры, в которых допустимые ходы зависят только от позиции, а не от того, какой из двух игроков в данный момент ходит. Кроме того, выплаты симметричны. Другими словами, единственное различие между игроком 1 и игроком 2 заключается в том, что игрок 1 ходит первым. Пример: Chomp.
Partisan Games: игры, которые не являются беспристрастными. Пример: шахматы.
Обычная игра: ВЫИГРЫВАЕТ игрок, сделавший последний ход, т.е. игрок, который не может сделать ход, т.е. которому нечего отнять, проигрывает.
Misère Play: Игрок, сделавший последний ход, проигрывает.
Chomp: игра, представленная на нашем игровом сайте, которая использует один квадрант и Misère Play.
В игре Nim в том виде, в котором она представлена на нашей странице игры, используется нормальная или мизерная игра?
- В нашей игре Nim используется misère play, потому что игрок, который берет последний матч, проигрывает партию.
В игре Chomp в том виде, в котором она представлена на нашей странице игры Chomp, используется нормальная или мизерная игра?
- Игра Chomp в том виде, в котором она представлена на нашей странице игры, использует misère play, так как игрок, который берет последнюю конфету, проигрывает.
Почему не имеет смысла использовать обычную игру для Chomp?
- Использование обычной игры означает, что побеждает тот, кто возьмет последнюю плитку. Поэтому игрок, который ходит первым, может мгновенно выиграть, заняв плитку в левом верхнем углу.
Используется ли в игре iChomp в том виде, в котором она представлена на этой странице, Normal или Misère Play?
- В iChomp побеждает игрок, который берет последнюю плитку, поэтому в этой игре используется обычная игра.
Есть ли у вас предложение о том, как можно изменить доску Chomp, чтобы использовать обычную игру и продолжать играть в ту же игру?
-
Можно начать с позиции, где (отравленная) конфета в верхнем левом углу уже отсутствует с самого начала. Взятие последней конфеты с такой доски означает, что вы выиграете в обычной игре. В Misère Play и с этой плиткой другой игрок должен будет взять ее и проиграть, что приведет к тому же результату.
Таким образом, наличие плитки в левом верхнем углу и использование Misère Play или отсутствие этой плитки с самого начала игры и использование обычной игры — это одна и та же игра.
О компании iChomp
- Игра iChomp создана для объединения четырех Чавкать игры, в которые играют одновременно, и все это по правилу обычной игры. Это делает игру более красивой в двух аспектах, о которых будет рассказано ниже. Кроме того, в iChomp играть не сложнее, чем в Chomp, если применить теорию Спрага-Гранди, которая также описана ниже.
О теории Спрэга-Гранди
-
Класс игр, к которым он применяется: Беспристрастные комбинаторные игры. Эта теория делает для нас две вещи:
- Он дает нам алгоритм, который определяет для каждой игры (т.е. для каждой позиции) число (назовем его SG-значением) таким образом, что число равно 0 тогда и только тогда, когда это проигрышная позиция (в литературе по комбинаторной теории игр называется «P-позицией», где «P» указывает на то, что «p» игрок сделал выигрышный ход). Это означает, что если это SG-значение равно 1, 2, 3, ... то это выигрышная позиция (в литературе она называется 'N'-позицией). В этом случае, тот, кто делает ход, может обеспечить выигрыш, если играет оптимально.
- Вторая цель SG-теории — описать, как выиграть игру, состоящую из нескольких позиций, играемых одновременно. Ход в такой комбинированной игре делается путем совершения одного хода в любой из комбинированных позиций.
Что нужно знать, так это SG-значение каждой из объединенных позиций. Чтобы их получить, нужно знать SG-значение после каждого хода в любой из этих комбинированных позиций. Они также необходимы для оптимальной игры.
Например: В игре Ним у вас есть одна, две или более стопки спичек. Если мы знаем SG-значение для игры в каждую отдельную стопку по отдельности, то SG-теория подсказывает нам, как оптимально играть со всеми этими стопками, убирая соответствующее количество совпадений из любой из этих стопок.
Почему iChomp?
-
iChomp - это новая версия Chomp, представленная Caribou Contests, в которую можно играть на этой веб-странице. Буква «i» в iChomp означает «изотропный», т.е. все направления рассматриваются одинаково.
В обычном Chomp удаление одной плитки также удаляет все клетки к востоку и югу от нее. Так, направления на Восток и Юг играют особую роль.
В iChomp все плитки в других направлениях также могут быть удалены, в зависимости от того, где удаленная плитка находится ближе всего к центру. Если эта плитка находится, например, в северо-западном направлении от центра, то все плитки на севере или западе также удаляются.
Исключение искусственных правил, например, правила о том, что Восток и Юг являются особенными, обычно считается математически более красивым.
Есть еще одно украшение, которое есть у iChomp по сравнению с Chomp.
В Chomp плитка в левом верхнем углу играет особую роль по сравнению с другими плитками. Если это единственная плитка на доске, игра окончена. Если другая плитка удалена, игра продолжается. Можно начать Chomp без этой угловой плитки, чтобы все плитки обрабатывались одинаково, но это само по себе было бы искусственным правилом, почему начинать игру без этой плитки, а не без других плиток.
В iChomp все плитки присутствуют в начале и обрабатываются одинаково. Любая плитка может быть удалена без автоматического завершения игры.
Возникают некоторые вопросы:
Является ли iChomp тривиальной игрой, потому что это комбинация или 4 тривиальные игры Chomp в «Обычной игре»?
-
Мой ответ – нет. Например, игра Ним с одной стопкой спичек тривиальна. В разделе "Обычная игра" можно убрать всю стопку за один ход и выиграть. В Ниме под «Пьеса Misère», Можно снять все, кроме одного матча, и выиграть. Тем не менее, комбинация таких игр Nim с 1 ячейкой и игрой Nim с несколькими стопами, как на нашей странице игр Nim, не является тривиальной.
То же самое и здесь: игра на один кусок с использованием угловой плитки и «обычной игры» тривиальна, потому что можно убрать все плитки за один ход и выиграть. Но комбинация из 4 таких игр не тривиальна.
Резюме сравнения
- IChomp математически красивее Chomp, потому что он искусственно не выделяет юго-восточные направления и не отводит одной плитке особой роли. Цена, кажется, в том, что в iChomp играть намного сложнее, чем в Chomp, но SG-теория помогает. Достаточно знать SG-значение позиций Chomp с точностью до некоторого размера, чтобы легко рассчитать SG-значение позиций iChomp до 4 раз большего размера и, таким образом, знать, как оптимально играть в iChomp до этого в 4 раза большего размера.
-
Мой ответ – нет. Например, игра Ним с одной стопкой спичек тривиальна. В разделе "Обычная игра" можно убрать всю стопку за один ход и выиграть. В Ниме под «Пьеса Misère», Можно снять все, кроме одного матча, и выиграть. Тем не менее, комбинация таких игр Nim с 1 ячейкой и игрой Nim с несколькими стопами, как на нашей странице игр Nim, не является тривиальной.
В SG-теории требуется математическая операция, называемая XOR. Если вы с ним не знакомы, вам будет полезен следующий раздел.
Что такое XOR?
-
Исключающее или, или сокращенно XOR, — это логическая операция, выполняемая над двоичными данными. Используя двоичные данные, мы можем иметь одно из двух значений: true (=1) или false (=0). Операция XOR над двумя двоичными значениями определена в следующей таблице.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
Хотя эту операцию легко использовать для значений 1 (true) или 0 (false), для наших вычислений нам необходимо иметь возможность выполнять XOR для двух чисел. Это тоже можно сделать, однако требуется новый шаг, прежде чем мы сможем выполнить XOR.
Сначала необходимо преобразовать числа в двоичные, т.е. преобразовать их из основания 10 в основание 2.
Как можно преобразовать число из основания 10 в основание 2?
-
Следующий алгоритм может быть использован для преобразования числа n по основанию 10 в формат с основанием 2. (Напоминаем, что 20 = 1):
- Найдите наибольшую степень p, равную 2, так что 2p ≤ n.
- Запишите a 1 и вычтите 2p из n.
- Если p = 0, то stop else вычитаем 1 из p и продолжаем.
- Если 2p > n, то запишите 0, иначе вычтите 2p из n и запишите 1.
- Вернитесь к шагу 3.
Последовательность 1 и 0, записанная в соответствии с этим алгоритмом, будет двоичным представлением числа n. Пример:
Преобразуем число 13 в формат по основанию 2. Мы начнем с нахождения наивысшей степени 2, равной или равной 13, то есть 23 или 8. Затем мы записываем 1 и вычитаем 8 из 13, что дает нам 5. Далее проверяем 2(3−1) =2 2 = 4. Поскольку 4 ≤ 5, мы записываем 1 и вычитаем 4 из 5, что дает нам 1. Следующая меньшая степень 2 — 21 = 2. 2 > 1, поэтому мы записываем 0. Следующая степень 2 равна 20 = 1, что равно нашему n от 1, поэтому мы записываем 1 и вычитаем 1 из 1, получая 0. Так как p = 0, мы останавливаем алгоритм. Следовательно, 13 (основание 10) = 1101 (основание 2).
После того, как мы преобразовали два числа в двоичное представление, мы можем выполнить операцию XOR над соответствующими цифрами двух двоичных чисел. Результатом является двоичное число, которое затем может быть преобразовано обратно в основание 10, если это более удобно для будущего использования этого значения XOR. Пример:
Вычислим XOR чисел 6 и 13. Двоичное представление этих двух чисел равно 6 = 110, а 13 = 1101. Сначала мы добавляем 0 слева от меньшего числа, чтобы оба имели одинаковое количество цифр, поэтому 6 = 0110. Затем мы можем выполнить XOR, выровняв их и выполнив операцию над каждой из отдельных цифр:
0110 XOR 1101 ------ 1011
Таким образом, 6 XOR 13 = 1011 (основание 2) = 1×23+0×22+1×21+1×20 = 8+2+1 = 11 (основание 10).
Давайте проверим наше понимание XOR с помощью нескольких вопросов.
Что такое m XOR m для любого числа m?
- Для любого числа m мы имеем m XOR m = 0, потому что 0 XOR 0 = 0, а также 1 XOR 1 = 0.
Является ли n XOR m = m XOR n для любых чисел n, m?
- Да, потому что 1 XOR 0 = 0 XOR 1 (=1).
Что такое 0 XOR m для любого числа m?
- 0 XOR m = m, потому что 0 XOR 0 = 0 и 0 XOR 1 = 1.
Если число m преобразуется в XOR с числом от n до m XOR n, то какие цифры m переворачиваются?
- Если цифра в m обозначается XOR 0, то цифра не изменяется (потому что 0 XOR 0 = 0 и 1 XOR 0 = 1). Если цифра в m преобразуется в XOR с 1, то цифра переворачивается (потому что 0 XOR 1 = 1 и 1 XOR 1 = 0). Таким образом, XOR n переворачивает все цифры, для которых соответствующая цифра в n равна 1.
-
Следующий алгоритм может быть использован для преобразования числа n по основанию 10 в формат с основанием 2. (Напоминаем, что 20 = 1):
Алгоритм вычисления значения SG для позиции Chomp.
-
Следующий алгоритм вычисляет SG-значение любой позиции P в любой беспристрастной комбинаторной игре. Объясняем это с помощью игры Chomp.
- Каждая игровая позиция, которая является проигрышной, получает SG-значение 0. В Chomp одна фишка (в северо-западном углу) является единственной позицией без последующего хода и, следовательно, является убыточной позицией со значением SG 0.
- Нам нужны SG-значения всех позиций, которые можно достичь из позиции P за один ход. Таким образом, если позиция P имеет n плиток, то есть n-1 возможных ходов: за исключением плитки в северо-западном углу, все остальные плитки могут быть удалены вместе со всеми плитками к югу/востоку от этой плитки.
- SG-значение позиции P — это наименьшее неотрицательное число, которого нет в этом списке n-1 достижимых SG-значений.
Этот алгоритм является рекурсивным, потому что для вычисления SG-значения позиции P нам нужны SG-значения всех позиций, достижимых из P за один ход. Это по-прежнему работает, потому что необходимые SG-значения относятся к меньшим позициям меньшего количества тайлов, а SG-значение минимально возможной позиции (одна клетка в северо-западном углу) известно.
Попробуйте проверить 3-е свойство в игре выше, выбрав большую ширину и высоту доски и нажав «Рандомизировать доску».
- Когда вы наводите мышь на плитку, эта плитка и другие плитки, которые должны быть удалены, выделяются. Число на этой плитке — это SG-значение квадранта в разделе «Обычная игра» (а не «Misère Play»), которое будет получено, если щелкнуть по этой плитке. Вы можете проверить, что число, отображаемое в тексте «SG value Base Ten:» рядом с квадрантом, является наименьшим числом, не показанным в квадранте. Вы также можете проверить, что если вы нажмете на плитку, то число, которое было в ней, теперь отображается как «Значение SG Base Ten:» новой позиции.
Как ускорить определение SG-значений:
Поскольку одна и та же позиция может быть достигнута из разных позиций за один ход и может повторяться при вычислении SG-значения более крупной позиции, было бы пустой тратой усилий вычислять его снова и снова. Следовательно, после того, как SG-значение позиции P рассчитано, его следует сохранить для последующего использования.
Если кто-то хочет вычислить SG-значение для всех позиций с точностью до некоторого размера, то полезен следующий подход. Начнем с того, что присвоим единственной позиции с одной плиткой (в северо-западном углу) нулевое значение SG. Затем с помощью описанного выше алгоритма мы вычисляем значения SG для всех позиций с 2 плитками, затем с 3 плитками и так далее.
Алгоритм вычисления SG-значения позиции iChomp
-
Позиция iChomp состоит из 4 позиций Chomp, по одной в каждом квадранте доски.
- Сначала мы определяем SG-значение для каждой из 4 позиций Chomp с помощью правила Chomp 'Misère Play'. Пустой квадрант не является позицией Chomp, поэтому мы присваиваем ему значение −1.
- Затем мы прибавляем 1 к каждому значению.
- Для каждого из 4 результирующих чисел мы вычисляем двоичное представление.
- Мы вычисляем значение XOR для 4 двоичных значений и получаем SG-значение этой позиции (в двоичной форме). Если это значение равно нулю, то это убыточная позиция, в противном случае – выигрышная.
-
Мы добавляем 1 для того, чтобы получить SG-значение позиции Chomp в разделе "Normal Play" из значения SG в поле "Misère Play". Следующая теорема объясняет это.
Теорема:
--------
Чтобы получить SG-значение позиции Chomp в режиме "Normal Play" (т.е. взятие последней плитки приводит к победе в игре, что не является распространенным способом игры в Chomp), необходимо прибавить 1 к SG-значению той же позиции в режиме "Misère Play" (т.е. взятие последней плитки проигрывает, что является обычным способом игры в Chomp).
Можете ли вы попробовать доказать теорему с помощью индукции?
-
Доказательство (путем индукции (и более подробно)):
Базовый корпус (1 плитка):
-------------------
При "обычной игре" пустая доска без плитки является проигрышной позицией и, следовательно, имеет нулевое значение SG. Кроме того, в разделе "Обычная игра" для доски с одной плиткой (в верхнем левом углу) единственным возможным ходом является удаление этой плитки, что приведет к позиции со значением SG 0. Таким образом, при "Нормальной игре" наименьшее неотрицательное значение SG, которое не может быть достигнуто ходом, равно 1, так что это значение SG позиции с одной клеткой в разделе "Нормальная игра".
В режиме "Misère Play" наличие одной плитки является проигрышной позицией с SG-значением 0.
Таким образом, для 1 фишки SG-значение "Normal Play" на 1 больше, чем значение "Misère Play".
Индуктивный шаг
---------------
Гипотеза индукции (n плиток):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Мы предполагаем, что существует число n, так что для всех позиций с ≥1 и ≤n плитками значение SG в разделе "Normal Play" на единицу больше, чем в поле "Misère Play". Заявка на индукцию (n+1 плиток):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Мы покажем, что это также верно для всех позиций с n+1 плитками.
Шаг индукции (n плиток → n+1 плиток):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Для любой позиции "Misère Play" и "Normal Play" позволяют делать одни и те же ходы, за исключением того, что "Normal Play" также позволяет брать все фишки через верхнюю левую угловую плитку.
Если позиция имеет n + 1 плиток, то при совершении хода создается позиция с не более чем n плитками, к которым мы можем применить гипотезу индукции:
Таким образом, список доступных SG-значений в разделе «Обычная игра» получается из списка доступных SG-значений в разделе «Misère Play», каждое из которых увеличивается на 1 и складывается путем сложения значения 0 через взятие всех плиток.
Таким образом, наименьшее неотрицательное число, которое НЕ может быть получено в режиме "Обычная игра", на 1 больше, чем наименьшее неотрицательное число, которое НЕ может быть получено в режиме "Misère Play". Другими словами, для исходной позиции с n+1 плитками значение SG в поле "Normal Play" на единицу выше, чем значение SG в поле "Misère Play". ∎ (На этом доказательство закончено.)
-
Доказательство (путем индукции (и более подробно)):
Почему мы добавили «1»?
Как играть в iChomp
-
Цель состоит в том, чтобы сделать ход таким образом, чтобы SG-значение результирующей позиции было равно нулю. Какой бы ход ни был сделан, он должен быть в одном из 4 квадрантов. Это означает, что SG-значение позиции, в которой был сделан ход, и SG-значения других 3 неизменных квадрантов, все XOR должны давать ноль. Это имеет место тогда и только тогда, когда другие 3 SG-значения XOR дают точно такое же SG-значение нового квадранта после совершения хода (доказательство этого утверждения см. ниже). Таким образом, процедура заключается в следующем:
- (просто) Пример: Два из 4 квадрантов имеют одинаковое SG-значение. Тогда XOR из этих двух равных значений даст ноль, поэтому оба квадранта следует игнорировать.
- Если два других квадранта также имеют одинаковые SG-значения, то SG-значение всей позиции равно нулю, и позиция является убыточной. Затем уберите всего одну плитку из любого квадранта, чтобы отсрочить поражение и иметь больше шансов у соперника сыграть не оптимально.
- Если два других квадранта имеют неравные SG-значения, то выберите квадрант с большим SG-значением. Сделайте ход туда, кликнув по плитке с вписанным числом, которое равно SG-значению другого квадранта. В результате получаем 2 пары квадрантов с попарно равным SG-значением и общим значением XOR, равным нулю, - убыточная позиция.
- (общие положения) Случай:
- Вычислите 4 iChomp-SG-значения, скажем, w,x,y,z из 4 квадрантов (каждый из которых является Chomp-SG-значениями этого квадранта плюс 1) и преобразуйте их в основание два.
- Затем найдите самую левую позицию так, чтобы нечетное число из этих 4 чисел имело 1 в этой позиции. Например, если 4 числа
w=11011
Тогда самая левая позиция с цифрой 1 — это 5-я позиция (считаем позиции справа). w и y имеют там 1, т.е. два числа (w и y) имеют там 1. Двойка — это четное число, поэтому нам нужно игнорировать эту позицию. Следующая позиция – это 4-я позиция, опять же отсчитываемая справа. Здесь также равномерно много чисел имеют 1 (w и x). Нужно игнорировать и эту позицию. На 3-й позиции есть 3 числа с цифрой 1 (x, y, z). 3 — нечетное число, поэтому мы выбираем любое из этих 3 чисел, например, y=10100.
x= 1101
y=10100
z= 100- Если во всех позициях есть четное число 1, то значение XOR всех 4 чисел равно нулю и это убыточная позиция. Например
w'=11011
Имейте четное количество 1 в каждой позиции. XOR этих 4 чисел равен нулю, это убыточная позиция. В этом случае человек убирает всего одну фишку из любого квадранта, чтобы отсрочить поражение и иметь больше шансов на то, что противник не сыграет оптимально.
x'= 1011
y'=10110
z'= 110 - Если хотя бы в одной позиции есть нечетное количество единиц, то мы нашли число, например, y выше (а не y').
- Мы XOR используем остальные 3 числа, в нашем случае w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. Это значение всегда меньше числа, которое мы выбрали, здесь y = 10100 (доказательства см. ниже).
- В квадранте с выбранным значением, здесь y, мы делаем ход, который приводит к позиции со значением SG, равным XOR из других 3 значений, в нашем примере 10011.
- Чтобы узнать, на какую плитку нажимать, мы либо преобразуем 10011 в основание десять (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) и щелкаем плитку с числом 19, либо вычисляем в двоичном виде 10100 − 10011 = 1 и преобразуем это в основание десять (= 1) и знаем, что плитка, на которую нужно кликнуть, должна иметь значение на 1 меньше, чем y (=20), т.е. нажать на плитку с вписанным числом 19.
Почему это выигрышный ход?
-
Пожалуйста, напомните себе о свойствах XOR, показанных ранее, чтобы ответить на следующие вопросы.
если u = w XOR x XOR y XOR z, то что такое y XOR u ?
-
Используя ранее изученные правила XOR, мы получаем
y XOR u
= y XOR w XOR x XOR y XOR z
= y XOR y XOR w XOR x XOR z
= 0 XOR w XOR x XOR z
= w XOR x XOR z.
Если y заменено на y XOR u, то каково новое XOR всех 4 SG-значений?
-
Новый XOR будет выглядеть следующим образом:
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
из-за m XOR m = 0 для любого числа m.
Это означает, что новое значение SG для всей доски будет равно нулю, так что это будет убыточная позиция, как и предполагалось.
Почему должен существовать ход, который изменяет SG-значение y на более низкое?
- Согласно определению: позиция имеет SG-значение y тогда и только тогда, когда существуют ходы, которые генерируют позиции с SG-значениями 0,1,..,(y-1). Таким образом, если y > (y XOR u), то должен существовать ход, генерирующий SG-значение (y XOR u) < y.
Остается только ответить:
Почему должен существовать квадрант с SG-значением y, удовлетворяющим y > (y XOR u)?
-
Напоминание:
Ранее, когда мы узнали о свойствах XOR, мы увидели: XOR u переворачивает все цифры, для которых соответствующая цифра в u равна 1.
Если вы ≠ 0, то u содержит наивысшую степень 2, скажем,2 P. Эта степень 2 должна встречаться в нечетном числе из 4 SG-значений, то есть по крайней мере в одном, скажем, y.
Это означает, что при вычислении y XOR u, это 1 в y превращается в 0 на соответствующий 1 в u. Могут быть и другие двоичные цифры, перевернутые в y, расположенные справа от этого 1. Наибольшее возможное значение y − (y XOR u) возникает, если цифры в y справа от этого 1 являются нулями, а цифры в u справа от этого 1 являются единицами. В этом случае u = 111..111 изменяется y = *100..00 (где * обозначает любое количество цифр) на y XOR u = *011..11. Их отличие заключается в следующем:
y − (y XOR u)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
Это означает, что y по крайней мере на единицу больше, чем (y XOR u). ∎
-
Используя ранее изученные правила XOR, мы получаем
Попробуйте этот алгоритм, играя и выигрывая у «Сложности: Сложно».
-
Для начала выберите «Сложность: Сложная», что гарантирует оптимальную игру на компьютере. Если вы все равно выиграли, значит, вы оптимально разыграли каждый ход.
SG-значение каждого квадранта показано по основанию 10 и основанию 2. Убедитесь, что это число является наименьшим значением, которое не отображается в квадранте.
Ниже показан XOR всех 4 SG-значений, называемых u. Проверьте свою ценность, просто изменив любую пару из двух 1 в 4 SG-значениях на 0, если две 1 находятся в одной и той же позиции. Затем поместите оставшиеся единицы в одно двоичное число и преобразуйте его в основание 10.
Чтобы сделать ход, действуйте, как описано выше:
- Найдите одно из 4 SG-значений, скажем, y, у которого 1 находится в той же позиции, что и левый самый 1 в u.
- Вычислите y XOR u в двоичной форме, а затем преобразуйте его в основание 10.
- В y-квадранте щелкните по плитке с вычисленным значением y XOR u.
- Играйте свои ходы таким образом, пока не выиграете.
- Играйте снова, но на этот раз начните со случайного хода. Если вам не повезло и вы случайно не сделали выигрышный ход, вы не сможете выиграть в этой игре, даже если затем попытаетесь играть оптимально.
Все приведенные выше инструкции предполагают, что известно SG-значение 4 квадрантов, что означает, что известно SG-значение каждого квадранта после каждого возможного хода.
Можете ли вы найти SG-значения некоторых позиций Chomp (в 'Misère Play')?
-
Для того чтобы вычислить SG-значение позиции, необходимо знать SG-значения всех позиций, которые могут быть достигнуты из нее за один ход. Это рекурсивный процесс. Поэтому нам нужно начать с позиций с наименьшим количеством плиток и двигаться вверх.
Можете ли вы найти SG-значения 1,2,3,... Плитка в один ряд?
-
Наличие только 1 плитки (в верхнем левом углу) является проигрышной позицией с следовательно SG-значением 0.
Имея 2 плитки (в верхнем ряду или в левом столбце), единственный возможный ход - взять одну плитку, получив указанную позицию с SG-значением 0. Таким образом, наименьшее неотрицательное значение SG, которое не может быть достигнуто ходом, равно 1, то есть значение SG позиции с 2 плитками равно 1.
Имея по 3 плитки в верхнем ряду, можно взять либо 1, либо 2 плитки и получить SG-значения 1 и 0, таким образом, SG-значение равно 2.
Аналогично, SG-значение n плиток в верхнем ряду равно n-1.
Рассмотрим 3 плитки, 2 в верхнем ряду и 2 в левом столбце. Мы можем удалить только 1 плитку и получить SG-значение 1, но не 0, поэтому наименьшее SG-значение, которое не может быть получено, равно 0, что, следовательно, является значением SG для этой позиции. Это проигрышная позиция.
Можете ли вы найти SG-значение позиции с m+n−1 плитками, из которых n находятся в верхнем ряду, а m плиток — в левом столбце?
- Удалять плитки можно только из верхнего ряда или из левого столбца. Таким образом, SG-значение аналогично наличию двух квадрантов, один с n плитками в верхнем ряду, а другой с m плитками в левом столбце. Таким образом, SG-значение равно (m-1) XOR (n-1). Это то же самое, что играть в NIM с двумя стопками и правилом «обычной игры», где матчи могут быть удалены только из одной стопки за один ход.
Можно ли найти SG-значение позиции с плитками только в двух верхних рядах?
-
Формулы для этих позиций более сложные. Насколько нам известно, ранее они не публиковались. Вы можете попробовать проверить их для небольшого количества плиток.
Пусть n и m — количество плиток в верхнем и втором ряду.
Если n четно, то
k = (n-2)/2
Если m четно, то
a = m/2
SG-значение = 2*k+a+1
else (m — нечетное)
a = (m-1)/2
если ≤ (k/2), то SG-значение = 2*k-a
else SG-значение = 3*(k-a)
else (n — нечетное)
k = (n-1)/2
Если m четно, то
a = m/2
если ≤ (k/2), то SG-значение = 2*k-a
else SG-значение = 3*(k-a)
else (m — нечетное)
a = (m-1)/2
SG-значение = 2*k+a+1
Проверьте правильность формул с помощью приведенной выше игровой доски.
- Выберите минимальную высоту доски, чтобы были квадранты только с двумя рядами плиток. После применения вышеуказанных формул вы должны получить SG-значение, которое на единицу меньше, чем значение, указанное в разделе «SG Value Base Ten:», потому что формулы предназначены для «Misère Play», в то время как iChomp использует «Normal Play».
-
Наличие только 1 плитки (в верхнем левом углу) является проигрышной позицией с следовательно SG-значением 0.
Как можно достаточно хорошо играть в iChomp, не зная SG-значений?
-
Начнем с наблюдения: правила Чомпа не делают разницы между Востоком и Югом.
Каковы последствия для SG-значений двух зеркально симметричных друг другу положений при зеркальном отражении по диагонали, начинающейся от верхнего левого угла?
- Поскольку восточное и южное направления зеркально отражены друг в друге, это означает, что оба должны иметь одинаковое SG-значение.
Что это значит для iChomp, когда 2 квадранта имеют симметричные положения при вращении квадрантов и/или диагональном зеркальном отражении?
- Оба квадранта можно игнорировать. Почему? Оба квадранта имеют одинаковое значение SG при плохой игре, а после сложения 1 также одинаковое значение SG при обычной игре. XOR из этих двух равных значений дает ноль. Таким образом, оба квадранта не вносят никакого вклада в SG-значение всей позиции на совете директоров.
Какая стратегия игры должна работать?
-
Нужно сделать ход, который создает две пары квадрантов так, что квадранты в каждой паре имеют симметричные позиции с равными SG-значениями, скажем, A и A, а также B и B. Тогда SG-значение комбинации всех 4 квадрантов равно A XOR A XOR B XOR B = 0 XOR 0 = 0 или (A XOR B) XOR (A XOR B) = 0, поэтому всегда 0. Один создал убыточную позицию.
Точно так же не следует делать ход, который оставляет два симметричных квадранта и два других, один из которых может быть превращен противником в другой за один ход. Это позволит сопернику создать проигрышную позицию.
Некоторые тестовые вопросы
-
Вот несколько вопросов, с помощью которых вы можете проверить свое понимание Chomp, iChomp и SG-теории.
Достаточно ли знания SG-ценностей, чтобы идеально играть в Chomp?
- Да. Если SG-значение позиции равно нулю, то это убыточная позиция (потому что не существует хода, чтобы сделать ее нулевой, поэтому нет выигрышного хода, поэтому это убыточная позиция). Если SG-значение больше нуля, то это означает, что есть ход, чтобы сделать SG-значение полученной позиции нулевым, поэтому есть выигрышный ход.
Нужно ли знать SG-значения позиций Chomp, чтобы играть в Chomp в совершенстве?
- Нет. Чтобы играть в Chomp, нам нужно найти ход, который генерирует проигрышную позицию. Если такого хода нет, то это проигрышная позиция, и любой ход может быть сыгран. Но, если такой ход найден, можно прекратить поиски. SG-значение не требуется.
Для чего тогда хороши SG-значения?
- Они нужны только для того, чтобы играть в несколько игр Chomp параллельно в качестве новой игры, как в iChomp.
Насколько сложнее в Chomp вычислить SG-значение позиции, чем выигрышный ход?
-
Чтобы играть в Chomp, нам нужно найти ход, который генерирует проигрышную позицию. Если такого хода нет, то это проигрышная позиция, и любой ход может быть сыгран. Но, если такой ход найден, можно прекратить поиски.
Усилия по нахождению SG-значения позиции обычно выше. Для нахождения SG-значения всегда приходится искать ВСЕ ходы, чтобы найти все SG-значения результирующих позиций и найти наименьшее неотрицательное значение, которое не может быть достигнуто в ходе. Это значение является SG-значением позиции.
Например, в наших расчетах (Caribou) мы смогли определить все убыточные позиции (и, следовательно, выигрышные позиции) с количеством плиток до 93. Приложив сопоставимые вычислительные усилия, мы смогли вычислить SG-значение для всех позиций Chomp, состоящих из 82 плиток.
В этом смысле определение SG-значений является более затратным с точки зрения вычислений, чем определение выигрышного хода.
Если играть в Nim с 4 стопками сложнее, чем в NIM с 1 стопкой, то в iChomp с 4 квадрантами играть намного сложнее, чем в Chomp с 1 квадрантом?
-
В Nim SG-значение одной стопки — это просто количество совпадений в этой стопке. (Пожалуйста, подтвердите это, применив приведенные выше комментарии о том, как вычислить SG-значения к одному стеку в Nim.) Единственная сложность игры с несколькими стопками в Nim заключается в том, чтобы использовать XOR различные SG-значения этих стопок, чтобы получить SG-значение всех стопок вместе взятых.
В Chomp получение SG-значения позиции (которая находится в одном квадранте) требует больших вычислительных затрат. В iChomp, как только SG-значения 4 квадрантов известны, эти значения также должны быть XOR, но это гораздо проще, чем найти SG-значение одного квадранта.
Чтобы играть оптимально, не нужно знать SG-значение позиции, достаточно знать выигрышный ход, но, как показано выше, разница не так уж и велика.
Так что ответ НЕТ, играть в iChomp оптимально не намного сложнее, чем в Chomp.
Может ли ход в Chomp создать позицию с более высоким значением SG?
- Да. SG-значение позиции — это наименьшее значение, которое не может быть сгенерировано ходом.
Могут ли в Chomp быть разные ходы, которые создают позицию с одинаковым значением SG?
-
Да. Вы можете посмотреть примеры, увеличив размер доски и нажав кнопку "Показать значения SG ходов". Например, позиция
###
##
#
имеет 3 выигрышных хода, каждый из которых создает позицию с SG-значением 0. Мы даже нашли позицию с 7 выигрышными ходами:
+ 10 6 15 2 20 21 14 22 11 0 23 7 26 13 7 11 9 14 0 19 5 17 11 14 18 0 24 23 8 3 19 2 0 20 11 4 0 5 1 8 0 0 4 23 25 24
Следите за обновлениями или подписывайтесь на них: