Точно так же материал книги (кроме 3-го раздела IV главы) не требует специальных математических знаний. Хотя некоторые методы решения проблем программирования игры в шахматы связаны с серьезными математическими исследованиями, в книге о них говорится на уровне обычного здравого смысла, с иллюстрацией сказанного шахматными примерами. Читатель также может иметь лишь самые общие сведения о принципах работы современных вычислительных машин. Только в начале I главы рель будет идти о некоторых технических аспектах работы шахматной программы и потребуются несколько большие познания в этой области. Соответствующие места книги можно пропустить или понимать весьма приблизительно - это не помешает каждому заинтересованному читателю извлечь для себя нечто полезное из остального текста.
Игра машины в шахматы состоит в том, что она выбирает ходы из предложенных ей или возникающих в партии позиций. Физическим перемещением фигур на доске машина не занимается. Информация о позиции часто задается набором па перфокартах, описывагощих расположение фигур и очередь хода (а также дополнительные сведения: право па рокировку каждой стороны, возможность взятия па проходе, повторения позиций в партии, возможность применить правило пятидесяти ходов) или последовательность ходов, ведущих в даппую позицию из начальной, изображенной на диаграмме 1. Выбранный ход печатает автоматическое печатающее устройство или машина высвечивает его па дисплее (телевизоре, которым может управлять и машина, оператор). При игре с человеком ходы шахматиста удобно вводить с пульта управления ЭВМ или с дисплея, а позиции, возникающие после мяптинпых ходов, машина определяет сама. При соревнованиях (точнее, программ) «хорошим топом» считается непосредственный обмен выбраппьтми ходами через каналы связи.
Читать полностью »
Занумеруем все поля шахматной доски, как это показано. Такой способ нумерации очень похож па применяемый в шахматной нотации, только вертикали вместо букв латинского алфавита обозначены цифрами и меняются они не от 1 до 8, а от 0 до 7. Пусть каждому полю доски соответствует определенное место в памяти машины и номер поля является его адресом. Место в памяти используется для указания, какая фигура стоит на рассматриваемом поле в позиции, из которой надо сделать ход. Однако программе приходится иметь дело и с другими позициями, описанными таким же способом. Поэтому номер поля является относительным адресом информации о нем. Истинный машинный адрес машина вычисляет сама, прибавляя этот номер к адресу начала информации об интересующей ее в данный момент позиции.
Система кодирования для дальнейшего не имеет значения. Поэтому вместо машинного языка будем пользоваться естественным человеческим языком (русским). В памяти машины указано только, какая фигура стоит на каждом поле или же что данное поле свободно. Найти какое-нибудь свободное поле или, например, поле, занятое черным королем, и т. д. - некоторое занятие для машины. Мы будем предполагать, что такие, а также более сложные задачи (выяснить, что данное поле не свободное, т. е. занято равно какой фигурой; найти «поле превращения данной пешки» и пр.) решаются при помощи стандартных подпрограмм. Проблемы создания такой достаточно удобной системы подпрограмм мы в этой касаться не будем.
Читать полностью »
Отметим некоторые условия, необходимые для допустимости хода: 1) на поле, откуда ход, должна стоять соответствующая фигура; 2) па поле, куда ход, не должна стоять фигура своего цвета; 3) на поле, куда ход, не должен стоять король противника; 4) после хода свой король не должен оказаться под шахом. В основном эти условия являются достаточными. Для допустимости пешечных ходов и рокировок требуются дополнительные условия. Одни из них аналогичны приведенным (поле, куда идет пешка, должно быть свободно, а то, куда пешка бьет, - занято фигурой противника и т. д.), другие связаны с «историей», т. е. предыдущими ходами (неподвижность короля и ладьи до рокировки, правило взятия на проходе). Этими тонкостями мы заниматься не будем.
Забудем пока о 3-м и 4-м условиях допустимости ходов (3-е, имеющееся в шахматном кодексе, вообще излишне). Первый этап работы нашей программы - выписать все ходы, удовлетворяющие остальным условиям допустимости. Последовательно просматриваем поля. Если поле не занято своей фигурой, переходим к просмотру следующего поля, в противном случае сначала «порождаем» все ходы расположенной на нем фигуры, т. е. выписываем их в отведенное для этого место в памяти машины (причем ведем счет количества всех порожденных ходов). Если фигура Дальнобойная, то по очереди порождаем ходы по лучам: Для слона - диагоналям, для ладьи - вертикалям и горизонталям, для ферзя - по всем.
Номер первого из них отличается от номера поля «откуда», а номера следующих - от номеров предыдущих па одну и ту же зависящую только от направления луча величину. Их значения указаны ниже:
Читать полностью »
Если ход есть, т. е. в 3- и 4-м случаях, мы записываем его в память в виде пары чисел - номеров полей «откуда» и «куда». В 1-, 2- и 3-м случаях больше ходов по рассматриваемому лучу пет. Нужно перейти к следующему лучу или следующему полю «откуда» либо, если номер последнего был 77, закончить порождение ходов и перейти к следующему этапу работы программы - выбору хода. В 4-м случае могут быть еще ходы по лучу. Поэтому прибавляем к потенциальному полю «куда» еще раз туже величину и повторяем все сначала.
Легко найти также ходы коней и короля. Разница лишь в том, что каждый луч для них состоит только из одного поля. У этих фигур по 8 лучей, причем лучам короля соответствуют те же величины, что и лучам ферзя, а лучам коня величины. Таким образом, конь с поля 07 (Ь7) может пойти на поля 46, 55 и 75, если па них пет своих фигур, а полей 88, 79, 59, 48 и 86 на доске пет. Не останавливаясь на способах порождения других ходов, заметим лишь, что взятие па проходе можно породить вместе с другими взятиями, для чего после прыжка пешки через поле нужно временно (на один ход) оставить па нем «след» - код, отличающийся как от кодов фигур, так и от кода свободного поля. Порождение рокировок (длинной, короткой или обеих), если они возможны, - это отдельная часть подпрограммы порождения ходов.
Читать полностью »
Теперь проверяем, не стоит ли после хода наш король под шахом (эта часть программы будет описана менее подробно). Можно последовательно, как и в предыдущей части программы, порождать ходы - па этот раз противника - и проверять, не стоит ли на их поле «куда» наш король. Если да, то оп под шахом и соответствующий наш ход не допустим. Переходим к ходу со следующим помором, выполняем его, т. е. создаем соответствующую доску, и т. д. В противном случае шаха нашему королю нет и ход допустим. Мы его выбираем, т. е. переносим созданную после него доску на место исходной доски, чтобы играть дальше. Кроме того, сообщаем о нем: печатаем, показываем его па дисплее, передаем по каналу связи.
Если же мы перебрали все ходы и допустимых среди них не оказалось, то нам либо мат, либо пат. Нужно проверить, не стоит ли наш король под шахом в исходной позиции. Делаем это аналогичным способом и определяем результат игры.
Чтобы можно было играть партию, нужно предусмотреть и другой режим работы программы: выполнение хода, выбранного противником. Не будем его подробно описывать, расскажем только, из каких этапов он состоит. Некоторые из них совпадают с описанными выше этапами выбора хода машиной или близки к ним. Так как современная машина умеет читать не только цифры, двоичные и десятичные, но и буквы, ход вводится в нее обычной шахматной нотацией. Это удобно и для игры с машиной, и для отладки программы. Прежде всего мы переводим сообщение о ходе на понятный машине язык, т. е. определяем номера полей «откуда», «куда» и код идущей фигуры.
Читать полностью »
Наконец, программа должна содержать переключения режимов: перехода от выбора хода к ожиданию, а затем восприятию хода противника и от последнего к выбору хода из повой позиции.
Программа, подобная описанной, будет играть. Правда, она не сдастся пи в какой позиции и не предложит ничыо, но этого не умеют делать и участники Третьего чемпионата мира среди шахматных программ, проходившего в 1980 г. С точки зрения шахматистов ходы нашей программы будут выглядеть совершенно случайными. Однако из позиции на диаграмме 3 она обязательно даст мат.
Пусть дана позиция, изображенная на диаграмме 4. Нас интересует, как может протекать дальнейшая игра. Для ответа на этот вопрос построим так называемое дерево игры из данной позиции. Его по традиции изображают растущим не так, как деревья в лесу, а сверху вниз. Оно состоит из веточек, называемых (почему-то) дугами, и их сочленений - вершин. Каждая вершила - позиция, которая может возникнуть в ходе дальнейшей игры, а дуга ход из верхней смежной с пей вершины, т. е. позиции, в пижмою. Первоначально заданная позиция расположена вверху. Она называется корнем дерева игры, а позиции с определенным по шахматным правилам результатом - концевыми вершинами дерева, или заключительными позициями.
Читать полностью »
При помощи полного перебора можно искать ответ не только на вопрос о достижимости главной цели шахматной игры - мата любой стороне. Если нет возможности осмотреть достаточно большую часть дерева игры, попробуем выяснить, нельзя ли достичь каких-либо промежуточных целей. Рассмотрим, например, позицию па диаграмме 6 и зададим вопрос, какое соотношение материала будет через два хода. Осматривая часть дерева игры с корнем в данной позиции, изображенную мы можем узнать следующее чистого ферзя. Поставим в соответствие этим исходам численные оценки соотношения материала, считая, как обычно, что легкая фигура стоит 3,5 пешки, ладья - 5 пешек, а ферзь - 2 ладьи. Таким образом, существующее соотношение материала с точки зрения белых равно - 0,5 (выигрыш ладьи +4,5; коня +.3; проигрыш ферзя за ладью - 5,5; чистого ферзя - 10,5). Так как мат лучше любого соотношения материала, то позициям, где он достигнут, можно приписать большую оценку, чем при максимально возможном материальном выигрыше, равном 128.
У позиций есть две оценки - за белых и за черных. При нашем способе их определения они отличаются только знаком. Если не указано, за какую сторону дается оценка, это - оценка за сторону, которой принадлежит очередь хода в данной позиции. Будем называть ее оценкой за себя (оценка за другую сторону называется оценкой за противника). Соотношение материала в позиции легко рассчитать, по вычисленное соотношение мы будем приписывать только тем позициям, где пи белые, ни черные не могут быстро изменить его в свою пользу. В других случаях оценкой позиции будет лучшее соотношение материала, какого может добиться одна сторона при наибольшем противодействии другой. Для ее определения некоторые варианты нужно просмотреть на глубину, большую, чем два хода.
Читать полностью »
Правилом Цермело можно пользоваться, не зная оценок всех позиций, максимуму которых равна вычисляемая оценка: позиция после ходов. имеет оценку, ; большую +128, так как можно пойти 2. Фшахматы не бывает.
Численные характеристики оценок позиций можно определять разными способами. При учете успехов шахматистов в турнирах оценку позиций, где мы дали мат противнику, считают равной 1, позиций, где мат объявили нам, - 0, а ничейным позициям приписывают ‘/2- Такая оценка не поощряет машину дать мат, если можно сделать другой ход, не упускающий выигрыша: оценки позиций после обоих ходов одинаковы. Чтобы исправить это, можно ценить мат тем выше, чем раньше он достигнут.
Некоторые позиции все шахматисты оценивают одинаково. В примере на диаграмме 4 белые могут дать мат в три хода, значит позиция выиграна за них. На диаграмме 7 изображена позиция, из которой можно дать вечный Ш6+ и КЬ7 + . Если белые не будут шаховать, то они получат мат. После попыток шаховать по-другому черные уходят от вечного шаха, например. С другой стороны, при попытке черных уклониться от вечного шаха они получают мат.. Значит, рассматриваемая позиция ничейная.
При оценке других позиций единодушия пет. Некоторые даже сомневаются в существовании объективных оценок этих позиций. «Откуда вы знаете, как будет играть противник?» - спрашивают они. Посмотрим, однако, к чему ведет предположение о том, что данная позиция не имеет объективной оценки и ее можно оценивать только субъективно (при этом учитывая, как собирается играть противник). Покажем, что из такой позиции можно сделать ход, ведущий в позицию, также по имеющую объективной оценки, и нельзя сделать хода в позицию, выигранную за нас.
Читать полностью »
Правда, но шахматному кодексу если пи одни из противников не потребует ничьей, то партия будет продолжаться. Однако из исходной позиции каждый противник может добиться ничьей и не может выиграть, если другой противник в какой-то момент не сделает проигрывающего хода, обладая возможностью его избежать. Естественно считать такую позицию имеющей объективную ничейную оценку. Без этого длинного рассуждения не объяснить, почему многие, в том числе и авторы книги, считают объективно существующими никому не известные оценки шахматных позиций.
Так как у каждой позиции есть объективная оценка, по правилу Цермело, из нее можно сделать ход, ведущий в позицию с такой же оценкой (если только данная позиция - не заключительная) и нельзя - в позицию с лучшей для себя оценкой. Такой ход называется лучшим (из позиции может быть не один лучший ход), а ход в позицию с худшей для себя оценкой - ошибкой. Найти шахматную истину - это значит определить оценку интересующей нас позиции или, в крайнем случае, лучший ход из нее ‘(в идеале надо найти оценку начальной позиции, изображенной на диаграмме 1). Если мы в партии не добились результата, равного оценке какой-либо из встретившейся в пей позиции значат ошибались, а если добились большего, то ошибался противник.
Читать полностью »
Отказ от просмотра некоторых ходов из позиций дерева игры мы будем называть отсечением, или сокращением, перебора. В приведенных выше примерах такое сокращение производилось, но не регулярным образом. Машина так не может: если она исправна, то реализует алгоритм, заданный программой, а с неисправной машиной дела иметь нельзя. Значит, нам нужно регулярное правило отсечения. Сформулировать ого поможет изучение примера. На диаграмме 8 белым ничего не грозит, и материальное равенство им обеспечено. Однако можно попробовать выиграть пешку, например ходом Черные отвечают. Если белые попробуют взять пешку то потеряют коня (другие ответы черных можно не рассматривать, так как белые могли не брать пешку проиграли бы ничего). Однако пока неизвестно, какой ход белых плох: 1-й иди 2-й. Поэтому они должны сначала попробовать изменить 2-й ход. Любой отход слона ведет к проигрышу либо этого слона (например, либо коня. Каждый второй ход белых опровергается естественным ответом черных, и остальные ходы черных можно не смотреть.
Итак, мы выяснили, что плох ход и можно отсечь все ответы черных, кроме Это отсечение имеет принципиально другой характер: мы уже знаем, где была сделана ошибка. Разницу между отсечениями па 1-м и 2-м ходах можно выяснить еще отчетливее, если рассмотреть другую попытку выиграть пешку Если теперь то защита коня 2. недостаточна: Здесь опять отсекаются 2-е ходы черных, кроме С:Ь5. Однако плох не 1-й ход белых, а 2-й: после 2 белые сохраняют лишнюю пешку. Конечно, пунше еще убедиться, что у черных пет других возможностей.
Читать полностью »