Игра Ним
Функция CHECKFIELD и процедуры PLAYERVICTORY и OWNVICTORY достаточно просты и их текст помещается без каких-либо пояснений в окончательный вариант программы (см. прил. 5.3). Отмечу лишь, что в случае победы игрока нет смысла повторять партию заново с той же самой раскладкой фишек. Поэтому игра усложняется: в исходную раскладку добавляется еще по одной фишке в каждый ряд.
В процедуре CHOOSEMOVE анализируется позиция и выбирается очередной ход программы. Описание оптимальной стратегии уже приводилось выше. Действия программы заключаются в поиске первого слева (старшего) двоичного разряда, для которого сумма чисел нечетная. Если такой разряд не обнаружен, то текущая позиция безопасна для игрока, а значит любой ход программы сделает ее опасной. В этом случае для программы не существует оптимального выбора и она лишь убирает одну фишку из любого непустого ряда. Такая тактика означает пассивное ожидание ошибки игрока.
Если обнаружен разряд i с нечетной суммой, программа приступает к реализации оптимальной стратегии и тогда игрок обречен на поражение. Для выбора ряда, из которого следует взять фишки, программа просматривает последовательно все ряды и отыскивает тот ряд j, количество фишек в котором (в двоичном представлении) дает единицу в разряде i. Значение этого разряда для количества фишек в ряду j заменяется нулем. Затем программа продолжает подсчет суммы для оставшихся младших разрядов. Если в каком-либо из них вновь обнаружена нечетность, значение этого разряда для количества фишек в ряду j инвертируется, т.е. 0 заменяется на 1, а 1 на 0.
Например, если двоичные представления числа фишек и четности сумм таковы:
число фишек в ряду j: 01001 четность сумм: 01011
(Единицей указаны разряды с нечетными суммами), то в результате этой операции получим:
число фишек в ряду j: 00010 четность сумм: 00000
Таким образом, в исходном состоянии в ряду j было 1001 =9 фишек, безопасная позиция требует, чтобы в ряду осталось 0010 = 2 фишки, следовательно, из него нужно забрать 9-2 = 7 фишек.
Окончательный вариант программы представлен в прил.5.3. Попробуйте разобраться в ее деталях самостоятельно.
В программной реализации алгоритма широко используется то обстоятельство, что Ваш компьютер, как и все остальные вычислительные машины, работает с числами, представленными в двоичной системе счисления. Поэтому для получения двоичного представления числа в процедуре BITFORM оно проверяется на четность с помощью стандартной функции ODD, затем сдвигается вправо на один двоичный разряд (операция SHR), вновь осуществляется проверка на четность и т.д. до тех пор, пока не будут проверены все разряды. Максимальное число двоичных разрядов, достаточное для двоичного представления количества фишек в ряду MAXCOL=63, задается константой ВIТ=6.
Для получения суммы двоичных разрядов в процедуре CHOOSEMOVE используется суммирование разрядов по модулю 2 с помощью операции XOR. Такое суммирование дает 0, если количество единиц четное или равно нулю, и 1 – если нечетное. В этой же процедуре для инверсии двоичного разряда применяется оператор:
if nbit[i] = 1 then
ncbit[j,i]: = ord(ncbit[j,i]=0); {Инверсия разрядов},
В котором используется соглашение о внутреннем представлении логических величин в Турбо Паскале: 0 соответствует FALSE, а 1 – TRUE.