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

Таблица 29 показывает, что после вставления в программу операторов, осуществляющих взятие пещки на проходе, быстродействие программы снижается несущественно (примерно иа 2%). Более существенно (еще примерно на 7%) возрастает время работы программы после вставления в нее операторов, осуществляющих рокировку. Следует заметить, что с операторами рокировки процедура ОБЗОР ХОДОВ превращается в рекурсивную, а следовательно, может использоваться далеко не на каждом из современных трансляторов.

Для проверки работы программы в специальных случаях были решены все шесть .задач на мат в два хода, опубликованные в еженедельнике «64» № 21 (256) от 25-31 мая 1973 г. в статье «Таких три разных хода». Эти задачи, содержащие одновременно превращение пешки, взятие на проходе и рокировку (так называемые задачи типа Валодао-таск), следующие.

1. Белые: Kpel, Ла1, Cd6, Ке2, КеЗ, а7, d3, g2, hi. Черные: Kphl, СЫ, сЗ, g5, h4.

2. Белые: Kpel, ЛЫ, Сс4, Ch8, Kd2, Kd3, a7, Ь2, e5. Черные: Kpal, Kg3, a4, b7, d7, f5, h5.

3. Белые: Kpel, ФеВ, ЛЫ, Ccl, Kg2, Kh6. Черные: Kpf3, Ла4, Саб, e4, g3, h3.

4. Белые: Kpel, Ла1, Ла7, СЫ, Ch2. КсЗ, Kg6, Ь4, d5, d7, f5. . = Черные: Kpd6, Л!4, ЛЬ8, Ca5, а6, Ь6, e7, g5.

5. Белые: Kpel, Лд2, ЛЫ, Ch7, Ch8, f5. Черные: Kpbl, Ccl, a2, e7.

6. Белые: Kpel, Фс2, ЛЫ, ЛЬ8, a5, d2, f2, h7. • . Черные: Kpal, Ch2, b7, f3.

Время, затраченное на решение этих задач и на исследование их однозначности, яриведено в табл. 30.

Таблица 30

Номер задачи

Ключевой ход

Время (с)

решения

исследования

46.72

73.84

70.22

83.64

159.02

180.02

0-0-0

178.64

179.72

99.56

100.34

35.40

77.50

Средние значения

98.26

115.76

В том виде, как она здесь приведена, программа алгоритма 50CJ в качестве результата решения печатает расположение всех фигур на доске после выполнения ключевого хода. Например, для вышеуказанной задачи № 4 из газеты «64» программа напечатала следующее:

РЕШЕНИЕ

-1-п

-1-КР



Во всех вышеуказанных случаях использования алгоритма 50CJ указывается время его работы, которое выдавалось на печать вариантом транслятора БЭСМ - АЛГОЛ от 10.11.71 с диспетчером версии 17.9.71. Сюда включается я время подготовки к печати позиции, которое для решения одиночной задачи равно примерно 1 с.

Замечание к алгоритму 50.

Дж. Берн (Berry J. L. «The Computer Journab, 1971, № 1) *

Черные

В отношении алгоритма 50 (данный журнал, т. 13, с. 208-219) мне хотелось бы указать на то, что авторская «Позиция Белла» (с. 211), представленная в качестве простейшей из известных позиций на мат в два хода, не является фактически законной шахматной позицией, т. е. она не может встретиться в игре за шахматной доской.

Я построил более простую позицию, которая дает форсированный мат в два хода тем же способом, что и позиция Белла, и мой пример может встретиться как результат обычных шахматных ходов. Эта позиция показана на рис. 7, а ниже <табл. 31) приведена примерная партия, приводящая к этой позиции (нет сомнения, что возможны и более короткие партии такого рода). Эта партия дает позицию, в которой у белых нет другого выбора, как только сделать мат черному королю серией трех форсированных полуходов, т. е. использует ту же идею, j3HC. 7).

Белые Рис. 7.

что и позиция Белла (см.

Таблица 31

Номер хода

Белые

Черные

Номер хода

Белые

Черные

Kpf2

Kpgl

Kpf7

Л:аЗ

Kpg6 Kph7

Ke5-f

Ф;Ь6

KphS

* Это замечание было опубликовано в форме письма редактору журнала «The Computer Journal». {Прим. ред.)



Ответ автора алгоритма 50 на замечание Дж. Бери

Данный пример был предназначен для того, чтобы показать некоторые фактические генерируемые числа и пути, выбираемые программой. Позиция была незаконной из-за расположения пешек, которое Бери исправил, удалив две (лишние) средние пешки на королевской вертикали е.

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

В связи с этим, если уж игнорировать незаконные ходы короля и допускать превращение пешки в фигуру, то позиция

! j

дает форсированную последовательность ходов

1) d7 КрЬ8

2) й8{Ф)х

ПРИЛОЖЕНИЕ 2

Подтверждения и замечания к алгоритмам, опубликованным в предыдущих выпусках

Подтверждения к алгоритмам 157а,160а, 170а и 190а

3. А. Шиншинова, Москва, июль 1973

Вышеперечисленные алгоритмы были вновь транслированы на машине БЭСМ-6-в системе БЭСМ-АЛГОЛ с примерами, приведенными в соответствующих свидетельствах, и дали верные результаты. В алгоритм 170а предварительно были внесены поправки, предложенные В. Д. Сычевым и Ю. И. Марковым в их «Замечании к алгоритму 170а» [38].

Подтверждение к алгоритму 160а

Б. Л. Шмульян, Москва, июнь 1972

Алгоритм 160а был модифицирован для получения функции

\С"т при /2<т, [ О при п > т.

f{m, n) = <jj

Для этого был помечен последний оператор процедуры, который принял вид

ml: comb:==r

Первым оператором в теле процедуры был поставлен следующий: if n>m then begin r:=0; go to ml end; Алгоритм был транслирован с языка АЛГОЛ в системе 4-70 и пая правильные результаты при т=3, 4,..., 15 и «= 1, 2,..., 5.





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.0023