В ним выигрывает тот, кто оставляет сопернику позицию с нулевой ним-суммой: разбейте каждую кучку на четвёрки, двойки и единицы, вычеркните одинаковые части парами и ходите так, чтобы без пары не осталось ничего. На этой странице вы ходите первыми, и на двух младших уровнях каждый из 2401 возможного стартового расклада выигран для вас — по формуле выигрываются 100% таких партий. На уровне «формула и старт против вас» все 350 раскладов проиграны, и доля побед там ровно 0%. Уровень «ошибается» упускает свой выигрывающий ход примерно в 38% случаев, так что даже после одного промаха вы выигрываете около трёх партий из четырёх.
В учебнике сказано: запишите кучки в двоичном виде и сложите по XOR. Двоичная запись для этого не нужна. Любое число единственным способом раскладывается в сумму разных степеней двойки, а когда в кучке не больше семи камней, частей всего три: 4, 2 и 1. Так, 7 = 4+2+1, 6 = 4+2, 5 = 4+1, 3 = 2+1.
| Кучки | Разбиение | Четвёрки | Двойки | Единицы | Остаток (ним-сумма) |
|---|---|---|---|---|---|
| 3, 5, 7 | 2+1, 4+1, 4+2+1 | две, пара | две, пара | три, одна лишняя | 1 |
| 7, 6, 4 | 4+2+1, 4+2, 4 | три, одна лишняя | две, пара | одна лишняя | 4+1 = 5 |
| 3, 5, 6 | 2+1, 4+1, 4+2 | две, пара | две, пара | две, пара | 0 |
| 4, 6, 7, 2 | 4, 4+2, 4+2+1, 2 | три, одна лишняя | три, одна лишняя | одна лишняя | 4+2+1 = 7 |
Теорема Бутона говорит именно об этом остатке. Если он нулевой, тот, чей ход, проигрывает при правильной игре соперника; если нет — может сделать его нулевым и выигрывает. Нулевые позиции и нужно оставлять сопернику: любой ход из такой позиции разбивает какую-то пару, а другая сторона всегда может её восстановить.
На практике достаточно считать чётность: в чётном или нечётном числе кучек есть четвёрка? То же для двойки и для единицы. Три взгляда на доску — и никакой арифметики.
Когда лишние части известны, выигрывающий ход находится в три шага:
Пример: в позиции 7, 6, 4 лишние части — 4+1. В кучке 6 = 4+2 четвёрка есть, а единицы нет: убираем 4, добавляем 1, получаем 2+1 = 3. Значит, из кучки в шесть камней берём три: в позиции 7, 3, 4 без пары не остаётся ничего.
| Позиция | Остаток | Выигрывающие ходы |
|---|---|---|
| 3, 5, 7 | 1 | один камень из любой кучки: 3→2, 5→4 или 7→6 |
| 2, 5, 6 | 1 | только 5→4 (единица есть лишь в кучке из пяти) |
| 7, 6, 4 | 4+1 | 7→2, 6→3 или 4→1 |
| 1, 3, 5, 6 | 1 | 1→0, 3→2 или 5→4 |
| 4, 6, 7, 2 | 4+2+1 | 4→3, 6→1 или 7→0 |
| 1, 1, 3 | 2+1 | только 3→0 |
Выигрывающих ходов столько же, сколько кучек содержит самую большую лишнюю часть, поэтому их число всегда нечётно. На этой странице в стартовом раскладе ровно один выигрывающий первый ход в 49,4% партий и ровно три — в 50,6%. В начале у вас в среднем 14 возможных ходов, и выигрывают из них лишь 14,5% — поэтому наугад здесь не сыграешь.
С тремя кучками полезно ещё и знать нулевые позиции в лицо. Если в кучках от одного до семи камней и все три размера разные, таких позиций всего семь: 1-2-3, 1-4-5, 1-6-7, 2-4-6, 2-5-7, 3-4-7 и 3-5-6. Две равные кучки сами по себе — тоже ноль: дальше вы просто повторяете каждый ход соперника в другой кучке.
Вот одна партия из стартового расклада 3, 5, 7 против уровня «играет по формуле». Каждая строка — ваш ход; ответы компьютера — один вариант из многих: из нулевой позиции хорошего хода у него нет, и камни он берёт наугад.
| Перед вашим ходом | Разбиение | Остаток | Ваш ход | Затем компьютер |
|---|---|---|---|---|
| 3, 5, 7 | 2+1, 4+1, 4+2+1 | 1 | один камень из первой кучки: 2, 5, 7 | берёт четыре из третьей кучки: 2, 5, 3 |
| 2, 5, 3 | 2, 4+1, 2+1 | 4 | 5→1, четыре камня: 2, 1, 3 | забирает третью кучку целиком: 2, 1 |
| 2, 1 | 2, 1 | 2+1 | 2→1, один камень: 1, 1 | берёт один из двух камней: 1 |
| 1 | 1 | 1 | последний камень | – |
Третья строка показывает правило в самом малом виде: лишние части — 2+1, в кучке из двух камней двойка есть, а единицы нет, так что двойку убираем, единицу добавляем — остаётся кучка из одного камня. На столе две равные кучки, и что бы ни сделал компьютер, остальное забираете вы.
Тренажёр под игрой отрабатывает именно этот шаг, по одной позиции за раз, с кучками до девяти камней — там среди частей появляется восьмёрка. Он открывается после вашей первой законченной партии.
Вы всегда ходите первыми. Игра выкладывает три или четыре кучки, одинаково часто, от одного до семи камней в каждой, а дальше всё зависит от уровня.
| Уровень | Как получается старт | Возможных раскладов | Выиграно для вас, первого игрока |
|---|---|---|---|
| «ошибается» | случайный; пересдаётся, пока ним-сумма равна нулю | 301 с тремя кучками, 2100 с четырьмя | все 2401 |
| «играет по формуле» | так же | те же 2401 | все 2401 |
| «формула и старт против вас» | последняя кучка заменяется так, чтобы ним-сумма стала нулём | 350 | ни одного |
Расклады считаются с учётом порядка кучек. Без пересдачи случайный расклад был бы проигран для первого игрока в 12,2% партий с тремя кучками и в 12,5% с четырьмя; страница такие расклады отбрасывает, поэтому на двух младших уровнях вы выигрываете ещё до первого хода в каждой партии без исключения. На столе при этом от 3 до 27 камней, в среднем 14.
На уровне «формула и старт против вас» страница убирает последнюю кучку и кладёт вместо неё ровно такую, с которой ним-сумма равна нулю. Каждый из 350 раскладов проигран для того, чей ход, а так как этот уровень не ошибается никогда, доля ваших побед там — ровно ноль. Это демонстрация, а не состязание.
Особенность этого уровня: в 2,2% партий в раскладе оказываются кучки из 8 и из 15 камней (8, 7, 15 либо 8 и 15, а между ними две кучки, в сумме дающие 7), так что там среди частей есть и восьмёрка. Может выпасть и классический расклад 1, 3, 5, 7 — это нулевая позиция: 1, 2+1, 4+1, 4+2+1 сокращаются полностью.
Три уровня отличаются только двумя вещами: упускает ли компьютер свой выигрывающий ход и подстроен ли старт. В нулевой позиции все три делают одно и то же — выбирают случайную кучку и берут из неё случайное число камней, — так что, пока вы выигрываете, ходы компьютера ни о чём вам не говорят.
Вот что дают простые способы игры — это точные вероятности победы, когда вы ходите первыми:
| Как вы играете | «ошибается» | «играет по формуле» | старт против вас |
|---|---|---|---|
| По формуле на каждом ходу | 100% | 100% | 0% |
| Случайный возможный ход | 24,1% | 1,8% | 0% |
| Всегда забирать самую большую кучку целиком | 34,6% | 7,1% | 0% |
| Всегда брать один камень из самой большой кучки | 21,4% | 0,9% | 0% |
| Только концовка: одна кучка — забрать всю, две — уравнять, иначе наугад | 52,7% | 6,3% | 0% |
| Неверный первый ход, дальше по формуле, как только выигрывающий ход появляется | 75,7% | 0% | – |
Последняя строка и отвечает на вопрос, сколько шансов вам дают. Против уровня «ошибается» каждый его ход в выигранной для него позиции — это примерно 38% за то, что он вернёт партию вам, а дальше формула доводит дело до конца. Поэтому в проигранной позиции тяните время: берите по одному камню из самой большой кучки и после каждого ответа заново считайте остаток. Это и есть 75,7% из таблицы; наилучшая возможная игра даёт 77,5%, а если в ожидании ходить наугад — только 66,4%.
Последняя строка — среднее по всем неверным первым ходам, каждый из которых равновероятен, во всех раскладах, где такой ход есть. Единственный расклад без неверного хода — 1, 1, 1.
Здесь играют в обычный ним: выигрывает тот, кто взял последний камень. В ниме мизер (поддавки) взявший последний камень проигрывает. Такого режима на странице нет, но правило стоит знать: эти две игры почти совпадают.
В мизере играйте точно так же, как в обычном ниме, — оставляйте нулевую ним-сумму, — пока ваш ход не оставит на столе одни только кучки по одному камню. В этот момент сделайте наоборот: оставьте нечётное число одиночных камней, а не чётное. В этом вся разница. Мы проверили это правило полным перебором на всех позициях до четырёх кучек, до 15 камней в каждой, — их 3876, и исключений нет.
| Позиция | Обычный ним: ход в | Мизер: ход в |
|---|---|---|
| 1, 1, 3 | 1, 1 (забрать тройку) | 1, 1, 1 (взять два камня из трёх) |
| 2, 2, 3 | 1, 2, 3 или 2, 2 | то же самое — кучки больше одного камня остаются |
| 1, 1, 1, 3 | 1, 1, 1, 1 | 1, 1, 1 |
| 1, 1, 1 | любой камень: вы выигрываете | проиграно: последний камень достанется вам |
Как редко это что-то меняет, нетрудно подсчитать. Из 2401 стартового расклада двух младших уровней по правилам мизера исход изменился бы только в одном: 1, 1, 1 в обычном ниме выигран, а в мизере проигран. Набор выигрывающих первых ходов отличался бы в 3,7% раскладов; во всех остальных первый ход в обеих играх один и тот же.
Вторая игра на странице — ним с одной кучкой и ограничением: 21 камень, за ход берут один, два или три, выигрывает взявший последний. Нулевые позиции здесь — числа, кратные четырём. Если вы оставили 4, 8, 12, 16 или 20 камней, то сколько бы соперник ни взял — пусть k, — вы берёте 4−k и попадаете на следующее кратное четырём.
При 21 камне вы ходите первыми, поэтому возьмите один камень, а дальше всегда отвечайте 4−k: 20, 16, 12, 8, 4, 0. Шесть ходов — и против первых двух уровней это срабатывает каждый раз. На уровне «формула и старт против вас» игра начинается с 20 камней, и перед кратным четырём оказываетесь уже вы: 0%.
| Как вы играете | «ошибается» | «играет по формуле» |
|---|---|---|
| Взять один, дальше отвечать 4−k | 100% | 100% |
| Случайный возможный ход | 26,1% | 0,25% |
| Два или три камня первым ходом, дальше верно | 83,2% | 0% |
В этой игре уровень «ошибается» промахивается мимо кратного четырём в 30% своих ходов, а не в 45%: когда он ходит наугад, один вариант из трёх всё равно верный. После вашего неверного первого хода у него пять ходов, чтобы ошибиться, и все пять он проходит без промаха лишь в 0,75 = 17% случаев.
После каждого своего хода оставляйте сопернику позицию с нулевой ним-суммой. Разбейте каждую кучку на четвёрки, двойки и единицы, вычеркните одинаковые части парами и измените одну кучку так, чтобы без пары не осталось ничего. Если ним-сумма равна нулю уже перед вашим ходом, выигрывающего хода при правильной игре соперника нет.
Разложите каждую кучку на степени двойки — 7 это 4+2+1, 6 это 4+2, 5 это 4+1, 3 это 2+1 — и вычеркните одинаковые части парами. Части, оставшиеся без пары, в сумме и дают ним-сумму. Для 3, 5, 7 четвёрки и двойки сокращаются, остаётся одна единица — ним-сумма равна 1.
Только если ним-сумма в начале не равна нулю. При трёх-четырёх случайных кучках от одного до семи камней так бывает примерно в семи раскладах из восьми. На этой странице на двух младших уровнях нулевые расклады пересдаются, поэтому вы, начиная первыми, выигрываете во всех 2401 возможном раскладе; на уровне «формула и старт против вас» все 350 раскладов проиграны.
На двух младших уровнях здесь — всегда: каждый старт выигран для вас, и по формуле выигрываются 100% партий. Уровень «ошибается» к тому же прощает промах: свой выигрывающий ход он упускает примерно в 38% случаев. Уровень «формула и старт против вас» обыграть нельзя: старт — нулевая позиция, а компьютер не ошибается.
В обычном ниме взявший последний камень выигрывает, в мизере — проигрывает. Стратегия одна и та же, пока ход не оставляет одни кучки по одному камню; тогда в мизере оставляют нечётное их число, а не чётное. На этой странице играют в обычный ним.
Оставляйте число, кратное четырём. При 21 камне, когда берут от одного до трёх, первый игрок берёт один камень, а затем на каждые взятые k отвечает 4−k, оставляя 20, 16, 12, 8, 4 и наконец ничего. Если начинать с 20 камней, первый игрок при правильной игре соперника проигрывает.