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

Читателям, желающим заниматься проблемой шахматного программирования более глубоко, можно рекомендовать для ознакомления другие работы на русском языке [62-78, 80, 81].

3. Результаты отладки трехходовой программы

После внесения вышеперечисленных изменений в программу алгоритма 50CJ (в варианте П1) с помощью расширенной таким образом трехходовой программы были сначала повторены решения всех тех задач на мат в два хода, которые )же были приведены Б свидетельстве к алгоритму 50CJ. Среднее время решения десяти задач из газеты «Вечерняя Москва» было 49 с, а шести задач из еженедельника «64» 101 с, т.е. почти не отличалось от среднего времени решения этих задач по дв)хходовой программе. Поскольку размерность массива СПИСОК в программе алгоритма 50CJ вычисляется априорно по формуле (2Xs-f-l)Xl00, то попутно с решением проводилось и определение максимальной длины, которзю принимает массив СПИСОК в процессе исследования однозначности этих задач.

Для вышеуказанных десяти задач из газеты «Вечерняя Москва» максимальная длина списка была в пределах от 188 (для задачи № 5) до 275 (для задачи № 7), а для шести задач типа Валодао-таск из еженедельника «64» она была в пределах от 305 (для задачи № 6) до 471 (для задачи № 4). Таким образом, для исследованных 16 задач длина массива СПИСОК нигде не выходила за пределы размерности [1 :500], определяемой по априорной формуле, хотя для некоторых сложных задач она была близка к этой размерности.

Далее с помощью этой расширенной программы были решены все те 10 задач на мат в три хода, которые были опубликованы (под номерами И-20) в газете «Вечерняя Москва» с декабря 1972 по февраль 1973 года под рубрикой «Конкурс-26». Эти задачи следующие.

11. Белые: Kpd8, ФйЗ, аЗ. Черные: Кра4, Ь6.

12. Белые: Kpd6, Ф!2, Лс5, сЗ. Черные: Kpd3.

13. Белые: Крс5, ФдЗ. Черные: Кра5, Cdl, с6, с7.

14. Белые: Кра8, Oh7, ЛЫ, Ch3. Черные: Kpg3, 14, f5.

15. Белые: Крс7, Л13, Cd6. Черные: Краб, а5, Ь5.

16. Белые: Kpd3, Фе7, СЫ. Черные: Kpfl, Cal, f2.

17. Белые: Kpfl, Фg8, Kf4, Kg4, h4. Черные: Kpf3.

18. Белые: Kpe2, Фа5, Лс2, Jlg2. . . Черные: Креб, а6.

19. Белые: КреЗ, ФЬ7, d7. Черные: Кре7.

20. Белые: Кре2, Феб, Се5. Черные: Кре4, е7.

Время, затраченное на решение каждой из этих задач и на исследование их однозначности, а также длина массива СПИСОК, которую он принимает в процессе исследования однозначности, приведены в табл. 26.

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

7. Белые: Kpel, Ла1, Лсб, Ch4, Ка5, 15, 17, g7. Черные: Kpd7, Ле8, JlfS, d4, е7.

8. Белые: Kpel, ФЬ5, Ла1, ЛЫ, СаЗ, Cg6,

Кс8, Kh5, сЗ, е2, е7, g3. Черные: Креб, Лаб, Лд8, Са2, Се5, Ь6, Ь7, d4, f4, g5, g7.

Время решения задачи 7 было 2 ч 7 мин 25 с, а задачи 8-5 ч 30 мин 56 с. Время исследования задачи 7 было 2 ч 7 мин 56 с, а задачи 8 - 7 ч 5 мин. Максимальная длина массива СПИСОК в процессе исследования задачи 7 была равна 517,



Номер задачи

Ключевой ход

Время

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

Длина списка

Крс8

153"

928"

Kpd7

152"

20И"

253"

936"

Cg4-

1338"

1932"

226"

804"

ШО!"

1907"

18Х)9"

2311"

Фе1 •

4508"

9707"

Kpf4

1340"

1356"

Kpel

1744"

1935"

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

1338"

2329" -

задачи 8 - 846. Таким образом оказалось, что с)ществ)ют задачи, для которых априорная форм)ла А. Белла (2Xs-bl)X100 определения длины массива СПИСОК оказывается нездовлетворительной. Для таких задач н)жно, • по-видимому, определить длину массива СПИСОК по другой формуле, например(2X+1) X130.

Проведенные расчеты показывают также и то, что предложенный А. Беллом алгоритм для решения трехходовых задач (особенно типа Балодао-таск) оказывается, уже медленным. Таким образом, прежде чем переходить к дальнейшему усложнению программы для решения задач в четыре и более ходов, целесообразно, по-видимому, усовершенствовать алгоритм с целью зскорения его работы. Предварительный обзор алгоритма 50CJ показывает, что в алгоритме А. Белла для повышения быстродействия имеются еще большие неиспользованные резервы.

4. Результаты отладки четырехходовой программы

Для проверки операторов, приведенных выше в указаниях 1-6, эти операторы были вставлены в программу, и с помощью полученной таким образом четырехходовой программы были решены четыре простейшие задачи из «Альбома ФИДЕ» [58] с номерами 839-842 на мат в четыре хода. Эти задачи следующие:

839. Белые: Kpg3, Ch4, Ch5. . . ...

Черные: Kphl, 15. . ,

840. Белые: КрЬЗ, Ле8, Kd2, Ке2.

Черные: Kpdl, е5. - " . .

841. Белые: Крс5, СЫ, Сс7, КЬ8, Кс8.

Черные: КрЬ7. ; . .

842. Белые: Крс7, Фе4, "ЛсЗ..... . . .. .. .....

Черные: Kph5, d3, g6, h7. .

Результаты решения этих задач приведены в табл. 27.

... Таблица 27

Номер задачи

Ключевой ход

Бремя

Длига списка

решения

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

Kpf2

704"

1200"

4ч 5024"

5ч 5828"

4700"

2ч 3656"

Kpd6

4ч 2250"

Решение всех вышеприведенных задач проводилось на машине БЭСМ-6 в системе БЭСМ-АЛГОЛ [51] (вариант от 10.11.71). Бо всех сл)чаях исходная позиция вводилась Б машину Б порядке возрастания номеров полей, занимаемых фигурами одного цвета. (Последнее не относится к фигурам, участвующим в рокировке: для них предусмотрен специальный порядок ввода.)



5. Некоторые простейшие способы ускорения решения задач

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

Так, если решающий задачу может расположить фиг)фы белых в порядке возрастания вероятности того, что первый ход этими фиг)фамп является ключевым, то он может воспользоваться тем свойством алгоритма 50CJ, что фигуры, вводимые в память машины позже, рассматриваются программой для поиска ключевого хода раньше. Поэтому целесообразно в информации, вводимой в память машины, располагать фигуры Б порядке возрастания вероятности принадлежности им первого ключевого хода. (Это не относится к фигурам, участвующи.м в рокировке. Для них предусмотрен особый порядок ввода.)

Если же решающий задачу желает опробовать на машине не все возможные первые ходы белых, а только определенный набор этих ходов, то он может провести решение с заданным списком первых ходов следующим образом.

1. Обращение к процедуре

ОБЗОР ХОДОВ (ПОЛЯ БЕЛЫХ,ДОСКА БЕЛЫХ.ДОСКА ЧЕРНЫХ, РУБЕЖ ХОДОВ[1], ОШИБКА);

следующее за строкой с меткой «НАЧАЛО;», нужно заменить операторами

input (п); РУБЕЖ Х0Д0В[1]: = n-f 1; for i: = l step 1 until n do

begin input(j); CnHCOK[i]:=j end;

2. После информации об исходной позиции, вводимой обычно в машину для решения данной задачи, н)жно подготовить к вводу список тех первых ходов белыми, которые решающий задачу считает ключевыми. Этот список вводимых ходов должен быть составлен в порядке, заказанном в пояснительном тексте к алгоритму 50CJ (см. табл. 26 [24]), а перед этим списком должно по.мещаться число элементов этого вводимого списка. Например, если в первой из дв)х задач, приведенных А. Беллом Б алгоритме 50, нужно исследовать только ходы слоном, расположенным иа поле а8, то вводимая информация должна и.меть вид -6; .10;3; 57;50;43;36-57;

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

Решать задачу по частям можно и другим, еще более простым способом, используя опять же свойство алгоритма, что поиск ключевого хода в нем всегда начинается с белой фигуры, введенной в память машины последней. Следовательно, задачу можно решать отдельными попытками, меняя в каждой попытке порядок ввода так, чтобы последней вводилась каждый раз новая белая фиг)фа, и заканчивая решение, как только программа закончит рассмотрение ходов вышеуказанной фигурой. Для этого достаточно в программу перед обращением (ниже метки «НАЧАЛО:»)

ВЫПОЛНЕНИЕ ХОДА (Б 1, ДОСКА БЕЛЫХ, ДОСКА ЧЕРНЫХ, ПОЛЯ БЕЛЫХ, ПОЛЯ ЧЕРНЫХ, Б1 ПРОДОЛЖЕНИЕ);

вставить оператор

if СПИСОК[Б1 + 1]<0 then begin output(/,Т,РАССМОТРЬНЫ ХОДЫ ФИГУРОЙ,

Z-DB,q[l],T,C - П0ЛЯ,2 - DDB,OBP.ATHO К[1],/");

go to КОНЕЦ end;

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





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

0.0018