Программирование шахмат и других логических игр, Корнилов Е.Н., 2005

Программирование шахмат и других логических игр, Корнилов Е.Н., 2005.

  Рассмотрено программирование логических игр методом перебора на примере шахмат. Описываются стандартные методики создания шахматной программы, а также приемы, позволяющие разрабатывать более эффективные компьютерные логические игры. Представлены примеры использования рассмотренных методов при программировании других логических игр ("крестики-нолики", "уголки", шашки). Приведено большое количество исходных кодов программ на языках C++ и Pascal и полезных практических советов. На компакт-диске содержатся наиболее известные открытые коды шахматных программ, а также исходные тексты программ, написанных автором.




История развития шахматных программ.
Когда же в первый раз машина заиграла в шахматы? На этот вопрос трудно ответить, наверное, в 1769 году. Венгерский инженер барон Вольфганг фон Компелен создал машину, способную играть в шахматы (рис. 1.1). Она была предназначена дли развлечения королевы Марии-Терезии. Машина, действительно, неплохо играла — внутри ее сидел сильный шахматист, который и делал ходы. История примечательная и, в некоторой степени, актуальна и в наши дни. Что программист вложит в машину, то она и играет. Гарри Каспаров, например, понимает этот тезис буквально. Он утверждает, что в его втором, решающем матче с DeepBlue (первый он выиграл), начиная со второй партии, в игру машины вмешивался человек и компенсировал неспособность машины понимать позиционную игру. Оставим этот вопрос на совести корпорации IBM и Гарри Каспарова. Я лично нисколько не сомневаюсь, что Каспаров может выиграть еще один матч с DeepBlue (если этот матч возможен), если, конечно, ему повезет.

В 1951 году Алан Тьюринг (рис. 1.2) написал алгоритм, при помощи которого машина могла бы играть в шахматы. Только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — "бумажная машина Тьюринга". Автору требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где "бумажная машина" Тьюринга проиграла одному из его коллег.

Содержание.
Введение.
Глава 1. Общие сведения.
История развития шахматных программ.
Некоторые приемы программирования.
Рекурсия.
Ханойские башни.
Задача о ферзях.
Локальные функции.
Игра "Уголки".
Грубое усилие и избирательность.
Глава 2. Основы программирования.
MiniMax и NegaMax.
Alpha-beta.
Alpha-beta с амортизацией отказов.
Перебор с нулевым окном.
Principal Variation Search.
NegaScout.
Генерация и сортировка перемещений.
Списки фигур.
Сортировка взятий (MVV/LVA).
Сортировка простых перемещений.
Испытанный метод сортировки перемещений.
0 х 88.
Bit Board.
Вращенный BitBoard.
Атака дальнобойных фигур.
Правила игры.
Оценка позиции.
Типичная оценочная функция.
Простая оценочная функция.
Эффект горизонта.
Форсированные варианты.
Выборочные продления.
Краткая характеристика расширений.
Дробный Depth.
Безопасность короля.
Глава 3. Простая шахматная программа.
Силовое решение.
Проше некуда.
Глава 4. Более сложные приемы.
ZObrist-ключи.
Хеш-таблицы.
Повторы позиций.
Детекторы шахов.
Недействительное перемещение.
Эвристика убийцы.
Эвристика истории.
Поиск стремления.
MTD(f).
Futility pruning.
Razoring.
Статический поиск.
Устаревший метод выборочного поиска.
Сокращенное вычисление.
Извлечение строки главного изменения.
Использование строки главного изменения.
Теория выборочного поиска.
Статические понятия .
Просмотр шахов в форсированном поиске.
Сокращения глубины поиска.
Правдоподобная генерация перемещений.
Единственный ответ.
Приложение 1. Пример игры "Крестики-нолики".
Приложение 2. Пример генерации перемещений.
Приложение 3. Замечания по технике программирования.
Стековые переменные.
Операции умножения.
Приложение 4. Описание прилагаемого компакт-диска.
Каталог PROGRAMS.
Каталог SOURCE (наиболее известные открытые исходники шахматных программ).
Каталог Winboard.
Каталог AUTHOR (программы, написанные автором книги).
Описание модуля Tchess.
Предметный указатель.

Купить .





Теги: учебник по программированию :: программирование :: Корнилов :: шахматы