Программирование игр и головоломок

Выигрывающее положение — 31 декабря. Возьмите листок бумаги в клетку. Расположите по абсциссе месяцы, а по ординате дни. Так как 31 декабря выигрывает, то вы обозначаете эту точку числом Спрага-Грюнди 0. Из каждого дня декабря можно получить 31, но также и любой другой последующий день. Поэтому вы приписываете значение 1 дате 30 декабря, значение 2 дате 29 декабря, и т, д. То же для любого 31 числа; из него можно получить 31 число всех последующих месяцев. Поэтому 31 октября получает 1, 31 августа 2 и т. д.

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

Закон заполнения таблицы достаточно сложен; и я не пытаюсь вам его сформулировать. Как только октябрь заполнен, появляется простая закономерность, которая дает соотношение между номером дня и номером месяца для выигрывающих положений.

Даже если вы мало знаете современную математику, вы слышали разговоры об отношении эквивалентности. Все выигрывающие положения эквивалентны. Игровое положение задается парой д, м, где д — номер дня, а м — номер месяца. Следовательно, вы должны найти такое отношение эквивалентности для пар натуральных чисел, чтобы

д, м' было не эквивалентно д, м при м /= м', и

д', м было не эквивалентно д, м при д /= д'.

Наконец, для выигрывающей позиции д, м должно быть эквивалентно 31, 12. Что-то похожее на это можно видеть в программах лицеев…

Я прекрасно понимаю, что календарь осложняет все, поскольку длина месяца не постоянна и зависит от м, причем к тому же с непростым законом изменения. Но, к счастью, оказывается, что это никак не сказывается на этом замечательном отношении эквивалентности.

После всего сказанного вы должны выпутаться из этой задачи…

Игра 18.

Эта игра — производная от средневековой игры. Сначала попытайтесь достичь 50 с точностью до кратного 7. Но как только все четыре карты, имеющие одинаковое значение, оказываются использованными, так ситуация сразу меняется. Вот пример начала партии,

Я беру туза, компьютер тоже. Сумма 2.

Чтобы получить 8, я беру 6. Компьютер берет туза. Сумма 9.

Чтобы получить 15, я снова беру 6.

Компьютер берет последнего туза. Сумма 16,

Теперь остаются следующие карты:

2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6

Так как тузов больше нет, то числа Спрага-Грюнди изменились[20]. Теперь из 49 больше нельзя получить 50.

SG(50) = 0, SG(49) = 0.

Из (48) можно получить 50. Поэтому SG(48) = 1.

Из 47 можно получить 49 и 50, но не 48. Поэтому SG(47) = 1.

Теперь положения, имеющие нулевое SG, — это

42 41 34 33 26 25 18 17

Поэтому я могу взять 2, чтобы достичь 18.

Стратегия усложняется, поскольку числа Спрага-Грюнди полностью меняются при удалении каждой карты. Но это как раз и благоприятствует компьютеру. Если он не может достичь выигрывающего положения, он берет карту, оставшуюся в наименьшем количестве экземпляров. Каждый раз, когда тот или иной тип карт исчерпывается, компьютер пересчитывает заново числа Спрага-Грюнди.

Мне придется переписать мою программу в соответствии с этой стратегией.

Игра 19. Ним-сумма.

Для меня эта игра — своего рода педагогический вызов. Я чрезвычайно раздражен тем, что все, кто излагает эту игру, ведут себя одинаково: известно, что выигрывающей стратегией является следующая… Почему она выигрывает? Откуда она вообще взялась эта стратегия?

Выписать числа Спрага-Грюнди очень трудно.

Попытаемся найти несколько выигрывающих положений.

Если к моменту своего хода я обнаруживаю только одну спичку, то я выигрываю.

Если я обнаруживаю единственную кучку, то я тоже выигрываю.

Если, кроме одной кучки, ничего больше нет, то можно положить SG(0) = 0 (я выигрываю, я взял последнюю спичку), вследствие чего SG(n) = n.

Предположим теперь, что у нас две кучки. Если я оставляю две кучки, в каждой из которых по одной спичке, то я обязательно выигрываю: мой противник должен взять столько спичек, сколько он хочет, но — только из одной кучки. У него нет выбора, он может только взять одну из спичек, после чего я возьму последнюю спичку и выиграю.

Если я оставляю две одинаковые кучки по n спичек в каждой, то у моего противника две возможности:

— взять целиком одну из кучек, я возьму другую и выиграю;

— взять часть одной из кучек и оставить в ней n' спичек. Я возьму столько же из другой, оставляя ситуацию n', n'. По индукции — я на пути к победе.