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

Следующий оператор в процедуре ОБЗОР ХОДОВ является критическим. Идентификатор К ХОДАМ описан как название переключателя, и результатом оператора

go to К ХОДАМ [СВОЯ ДОСКА [ПОЛЕ]]

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

В данном примере сначала рассматривается одиннадцатая фигура (при такой записи цикл работает быстрее). Она занимает в массиве ДОСКА БЕЛЫХ поле 62, содержащее число 2, т. е. коня. Поэтому выполняются операторы

СПИСОК {с]: = 11, СПИСОК [с-М]: =2 и СПИСОК [c-f-2]:=62.

Затем в процедуре делается переход к метке КОНЕМ, выполняется обращение к процедуре ХОДЫ КОНЯ И КОРОЛЯ, и генерируются ходы для коня, занимающего поле 62, т. е. последовательность 56, 47, 45 и 52. Далее делается переход к метке ДАЛЕЕ, где проверяется, был ли генерирован хотя бы какой-нибудь ход (если фигура не может сделать ни одного хода, то информация о ней затирается информацией о новой фигуре). Если ходы были генерированы, то процедура записывает в массив СПИСОК значение -ПОЛЕ (т. е. в данном примере -62), чтобы отметить окончание перечня ходов данной фигуры, и затем переходит к рассмотрению еовой фигуры в массиве СВОИ ПОЛЯ- Так продолжается до исчерпания этого массива. Получающийся в результате список чисел в массиве СПИСОК приведен в табл. 26. Заметим, что две пешки (р=5 и р=2) не имеют ходов и поэтому в таблице пропущены.

Таблица 26

Содержание массива СПИСОК

Название фигуры

Фигура

Исходно? поле

Поля возможных ходов

Признаки конца

Конь

56, 47. 45, 52

Слон

50, 43. 36

Слон

60. 42, 58, 44, 37

Пешка

47. 46

Ладья

34, 35, 36. 41, 49. 25. 17, 9, 1

Пешка

Конь

35, 28. 3. 1

Ферзь

15. 16, 13. 6, 23. 5. 21, 28. 7

Король

1. 2. 3. 9. 11, 17. 19

После генерации ходов всех фигур индекс последней записи (в массиве СПИСОК- Прим. ред.) запоминается в переменной РУБЕЖ. Это значение используется тогда, когда ходы выполняются фактически. Незаконность некоторых ходов (король не может ходить иа поля 11 или 19) обнаружится после того, как ходы будут фактически сделаны и окажется, что противнщ может взять короля (см. следующий раздел).

Выполнение ходов

Процедура ВЫПОЛНЕНИЕ ХОДА оперирует со списком, генерируемым процедурой ОБЗОР ХОДОВ, и выполняет следующие функции.

1. Изменение содержимого четырех массивов: ДОСКА БЕЛЫХ, ДОСКА ЧЕРНЫХ, ПОЛЯ БЕЛЫХ и ПОЛЯ ЧЕРНЫХ в зависимости от того, какая из сторон должна ходить (если переменная УРОВЕНЬ нечетная, то ходят белые, в противном случае - черные). Для этого необходимо знать следующее:



а) поля, с которых и на которые может пойти фигура (эта информация отыскивается в массиве СПИСОК по значению индекса р; в данном примере для первого хода конем р=3, поэтому ОТ=62 и НА=56);

б) номер позиции рассматриваемой фигуры в массиве ПОЛЯ СВОИХ (в данном примере конь находится в позиции И); эта информация хранится в переменной НОМЕР [УРОВЕНЬ];

в) начальное значение фигуры иа случай превращения пешки в фигуру; эта информация запоминается в q {УРОВЕНЬ] *. Для вьшолнения хода требуются шесть операций, обозначенных в программе метками от aal до аа&.

аа\: Значение данной фигуры (из [УРОВЕНЬ]) присваивается переменной ДОСКА СВОИХ [НА] (кроме случая превращения пешки в фигуру, когда вместо пешки присваивается значение ферзя, ладьи, слона или коня соответственно).

CU&: Поле ДОСКА СВОИХ [ОТ] очищается.

ааЗ: Любая фигура, возможно взятая при опробовании предыдущего хода данной фигуры (когда проверялся ход на поле ОТ), возвраг ается на доску противника.

аа4: Любая фигура, возможно взятая новым ходом данной фигуры, записывается в с УРОВЕНЬ] **. Чаще всего туда записывается нуль, но это не важно.

аа5: Поле НА доски противника очищается от любой фигуры, которая возможно на нем находилась.

аа&: Список позиций фигур на доске корректируется. В данном примере коиь в позиции И занимал поле 62, теперь это поле заменяется на 56; тем самым подготавливается возможность генерации списка белых фигур иа второ.м ходе.

2. После выполнения хода УРОВЕНЬ увеличивается и для нового расположения фигур яа доске генерируются ответные ходы противника. При этом проверяется, является ли сделанный ход законным? Если нет, то из процедуры ОБЗОР ХОДОВ осуществляется выход к метке НЕЗАКОННЫЙ ХОД, что является, по существу, отклонением только что сделанного хода.

3. Если ход законный, то все готово к выполнению списка ответных ходов противника. Запоминается номер позиции *** первой фигуры противника и ее значение ****, и процедура заканчивается (назначение переменной ОБРАТНО К [УРОВЕНЬ], в которой запоминается исходное поле фигуры, только что сделавшей ход, разъясняется в следующем разде.пе).

Назначение процедуры ВЫПОЛНЕНИЕ ХОДА, оперирующей с массивом СПИСОК, состоит в том, чтобы просмотреть ***** все поля, на которые может пойти данная фигура, пока ие встретится поле с отрицательным значением НА. Это будет означать, что ходы данной фигуры кончились. Поэтому фигура и доска восстанавливаются в исходное состояние (пять операций с метками 661-665; нам известно, что в данном случае ДОСКА ЧУЖИХ {-НА] имеет нулевое значение, в остальном эти операции идентичны операциям аа\-actio). Подготавливаются ходы следующей фигуры, и делается выход из процедуры через метку ПРОДОЛЖЕНИЕ, за которой проверяется, не исчерпан ли список ходов, и обычно сразу же вызывается процедура ВЫПОЛНЕНИЕ ХОДА и начинает свои ходы новая фигура.

Решение задачи на мат в два хода

Для проверки правильности и быстродействия процедур ОБЗОР ХОДОВ и ВЫПОЛНЕНИЕ ХОДА они используются здесь в законченной программе, решающей

ред.)

* q - начальная буква слова queening - превращение пешки в фигуру. {Прим.

** с - начальная буква слова capture-взятие. {Прим. ред.)

*** В переменной НОМЕР [УРОВЕНЬ]. {Прим. ред.)

**** В переменной q [УРОВЕНЬ]. {Прим. ред.)

*****В результате последовательных к ней обращений. {Прим. ред.)



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

Для ускорения работы программы необходимо иногда брать ход назад. Например, белые делают первый ход (Б1), а черные - ответный (41) такой, что белые не могут шаховать черного короля на втором ходу. Тогда прежде чем пытаться сделать другой

11\\б 7

8 !/-.5 15 1б\гъ 24

45 47

1111 гУ 29 57

39\4б\53 55

¥4

Рис. 4 Позпция форсированного мата в два хода. Белые могут сделать только один ход, черные имеют тоже только один ответ, а белые еще только один ход:

а - позиция Белпа - простейшая из известных задач на мат в два хода: 6 -массив ПОЛЯ БЕЛЫХ; в -массив ПОЛЯ ЧЕРНЫХ.

ХОД белыми нужно взять назад ответный ход черных (41). Это осуществляется процедурой ВОЗВРАТ ХОДА при условии задания поля, занимаемого черной фигурой 8 данный момент, и ее исходного поля. Исходное поле любой фигуры перед выполнением ее ходов всегда запоминается в переменной ОБРАТНО К [УРОВЕНЬ].

Для иллюстрации процесса решения задачи рассмотрим позицию, приведенную ва рис. 4,а.

В массивах ПОЛЯ БЕЛЫХ и ПОЛЯ ЧЕРНЫХ (рис. 4,6 и в) содержится И белых я 11 черных фигур соответственно.

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

Блок-схе.ма программы приведена на рис. Б, а фактическое содержание массива СПИСОК, отображающее ходы, генерированные на пяти уровнях, в табл. 27.

Таблица 27

УРОВЕНЬ

Номер фигуры

Значение

Исходное поле

Далее

41 t

-64. 5. 1. 39, 31. -39

(незаконный)

Перечисление хсдсв за-

кончено





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