Главная Промышленная автоматика.

- =-il (n=3 - квадратичный невычет),

- =2 (m=12 -четное).

Символ Якоби описывается, например, в работе И. М. Виноградова [6, с. 78-81].

Саидетельство к алгоритму ЮОб [02]

Алгоритм 1006 «Заполнение информацией матрицы связи» не публикуется здесь, потому что с помощью соответствующих алгоритмов 100 (Ki vi а t P. J. «САСМ», 1962, № 6) и 100а [23] авторы выпуска не получили удовлетворительных результатов на машине.



ПРИЛОЖЕНИЕ 1

АЛГОРИТМ 50 CJ

Как программировать игру в шахматы [Z]

Введение *

Миллионы людей интересуются шахматами. Большинство из них проявляет интерес и к реализации шахматной игры на машине. И этот интерес далеко не только спортивный. Исследователи проблем современной кибернетики видят (и не без основании!) в программировании шахматной игры один из возможных путей раскрытия законов человеческого мышления и создания «мыслящих машин».

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

Использование для публикации шахматных программ универсальных алгоритмических язьжов сделало возможным для широкого круга программистов восприятие (ОСНОВНЫХ идей шахматного программирования и дало им возможность принять уча-,стие в разработке шахматных программ. Публикуемый здесь алгоритм 50CJ выполняет .в первую очередь именно эти функции.

Разумеется, шахматная программа иа алгоритмическом языке не может соревноваться по быстродействию с шахматной программой в машинном коде или автокоде. Но она и не предназначена для этого. Ознакомившись с основными идеями этой программы, пользователь может сам усовершенствовать ее, и если наступит момент, когда его АЛГОЛ-программа станет потреблять слишком много машинного времени, то и сможет без особого труда перевести ее на один из низших языков программи-.рования. При этом в его распоряжении будет не только готовая отлаженная АЛГОЛ-программа, но и готовый набор идентификаторов, обозначений и специальных терминов. К тому же приведенная здесь АЛГОЛ-программа для решения двухходовок требует так мало машинного времени (см. ниже «Свидетельство к алгоритму 50CJ»), что вряд ли на этом этапе имеет смысл стремиться к его экономии.

* Введение к алгоритму 50CJ наиисано А,=еевым М. И. Индекс CJ у номера алгоритма указывает на источник, в котором был опубликован исходный вариант этого алгоритма (журнал «The Computer JournaI»). Алгоритм 50CJ публикуется здесь на правах обычного подтверждения исходного варианта 140]. {Прим. ред.)



Кроме алгоритма 50 А. Белла [40], послужившего прототипом алгоритма 50CJ, 3 том же журнале «The computer journal* поздиеее был опубликован и более общий алгоритм 68 Дж. Манинга «Белые начинают и дают мат в п ходов» [42]. Однако этот общий алгоритм основан на использовании рекурсивных процедур, а следовательно, имеет более узкую область применимости и, по признанию самого его автора, работает весьма медленно. Кроме того, алгоритм А. Белла имеет гораздо более обширную •описательную часть (см. ниже перевод пояснительного текста к алгоритму 50) и легко может быть обобщен для решения задач на большее число ходов. Таким образом, публикация на русском языке переработанного варианта алгоритма 50 представ--ляется первоочередной.

Пояснительный текст к алгоритму 50

А. Белл (Bell А. G. «The Computer Journal», 1970, № 5) *

Большинство программ, написанных для игры в шахматы [41], содержат ограни-чеиия. В данной работе излагается метод воспроизведения всех ходов в любой шахматной позиции, включая превращение пешки в фигуру, рокировку и взятие пешек на проходе. Для проверки и демонстрации изложенных методов написана АЛГОЛ-про-•грамма решения любой шахматной задачи на мат в два хода. Полностью эта про-л-рамма и требующиеся для работы с нею таблицы вместе с некоторыми факультативными процедурами приводится в дополнениях 1-4.

Таблицы

Наиболее существенной особенностью данной программы является то, что для работы с нею требуется шесть таблиц (массивов). Чтобы программа была короче, лучше всего, если эти таблицы будут вводиться, а не вычисляться. Потому они пол-ностью приводятся в дополнении 1. Кроме того, так будет проще понять и проконтролировать их работу.

Эти шесть таблиц подразделяются иа три группы; таблицы коня и короля, таблицы слона и ладьи, таблицы белой и черной пешек.

Таблицы коня и короля

Таблица коня (дополнение 1.1а) состоит из 64 строк [каждая строка соответствует одному нолю (одной клетке) шахматной доски, как показано на рис. 2], числа

Черные

Белые

Рис. 2. Нумерация полей шахматной доски.

•в самом левом столбце таблицы являются номерами строк и не входят в состав таблицы.

Рассмотрим строку 1. Она используется тогда, когда конь находится иа поле 1. "Последнее число в строке - это общее число полей, на которые может пойти данный

* См. [40]. Перевод и отладка алгоритма выполнены Агеевым М. И.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [27] 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

0.0017