Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Шахматный компьютер

Это список терминов, используемых в компьютерных шахматах .

A – M [ править ]

алгоритм
Точно определенная пошаговая процедура выполнения задачи. См. Алгоритм .
альфа
В алгоритме минимаксного поиска - минимальное значение, которого может достичь сторона, которую нужно переместить, в соответствии с изменениями, которые были оценены до сих пор.
альфа – бета обрезка
Алгоритм, уменьшающий количество узлов, просматриваемых минимаксным алгоритмом. Это уточнение необходимо для того, чтобы сделать возможным поиск в больших деревьях игр, например, в шахматах. См. Альфа – бета обрезка .
множество
Список, хранящийся в памяти компьютера, элементы которого можно быстро найти с помощью числового индекса.
искусственный интеллект
AI
Раздел информатики, занимающийся воспроизведением или имитацией мышления человеческого уровня в компьютерах. Игра в игры была ранней областью исследований ИИ. См. Искусственный интеллект .
Уточнение альфа-бета-отсечения, которое еще больше ускоряет поиск за счет рассмотрения только узкого окна, как правило, на основе опыта. Поиск с нулевым окном, поиск с нулевым окном и поиск с разведкой - это названия для крайнего случая, в котором альфа и бета установлены на одно и то же значение.
бета
В алгоритме минимаксного поиска максимальное значение, которого может достичь перемещаемая сторона, основано на вариациях, которые были оценены на данный момент.
кусочек
Двоичная цифра, 0 или 1. Наименьшая часть информации, которая может быть сохранена или обработана компьютером.
битовая доска
Массив из 64 бит, каждый бит представляет квадрат шахматной доски. Используются несколько битных досок, каждая из которых записывает определенную характеристику, например, все клетки, занятые фигурой определенного типа, или все клетки, находящиеся под атакой.
фактор ветвления
Количество возможностей, которые необходимо учитывать на каждом уровне дерева поиска.
грубая сила
Подход к решению проблем, основанный на быстром компьютерном оборудовании, а не на элегантных алгоритмах.
кандидат двигаться
Ход, выбранный при первоначальном наблюдении за позицией как заслуживающий дальнейшего анализа. Алгоритм альфа-бета может быть более эффективным, если список ходов кандидатов правильно упорядочен так, чтобы в первую очередь рассматривались лучшие ходы. См. Ход кандидата .
Расширение алгоритма поиска, которое продолжается с конечного узла, учитывая только захваты, которые могут быть сделаны каждой стороной.
отрезать
Удаление ветви дерева поиска без необходимости поиска в ней. Это сокращающее действие алгоритма альфа-бета.
функция оценки
Алгоритм, используемый для оценки благоприятности позиции. Поскольку большинству шахматных позиций не может быть присвоено точное значение (выиграна, проиграна или ничья), это эвристика, основанная на таких факторах, как материальный баланс, преимущество в пространстве, подвижность фигур, пешечная структура, безопасность короля и т. Д. Большинство функций оценки возвращают числовое значение в пешках и долях пешки, представляющее преимущество, которое, как считается, имеют белые в данной позиции. Ноль означает, что позиция уравновешена, а отрицательные значения указывают на то, что черный считается впереди. См. Оценочную функцию .
Поиск, в котором исследуются все ветви дерева игры. Из-за высокого коэффициента разветвления в шахматах поиск по всей ширине обычно нецелесообразен, за исключением случаев, когда на доске остается немного фигур, поэтому возможные позиции значительно сокращаются.
игровое дерево
Все возможные позиции, которые могут возникнуть в результате всех разрешенных ходов из данной позиции.
эвристический
Метод, используемый для решения проблемы, оптимальность или правильность которой не гарантируется, когда метод точного решения проблемы неизвестен или непрактичен. Эвристика может использоваться в компьютерных шахматах для оценки позиций и управления алгоритмом поиска.
эффект горизонта
Следствием этого является то, что для алгоритма поиска в большинстве случаев нецелесообразно выполнять поиск вплоть до завершения игры. Компьютер может сделать плохой ход, потому что он не может увидеть последствия даже на один слой сверх максимальной глубины поиска. Эффект горизонта был серьезной проблемой в первые годы компьютерных шахмат, но сегодня это не так важно, поскольку современные шахматные движки могут искать много ходов вглубь даже в сложных позициях. Смотрите эффект горизонта .
итеративное углубление
Алгоритм поиска, который сначала ищет на глубине N слоев, а затем, используя результаты этого поиска, переупорядочивает ходы кандидата, чтобы провести поиск на N + 1 слоях. См. Итеративный поиск с углублением в глубину .
убийственная эвристика
Предположение, что ход ( убойный ход ), который вызвал прекращение поиска в другой ветви игрового дерева на той же глубине, может вызвать отсечение в текущей позиции. Это может сделать обрезку альфа-бета более эффективной. См. Убийственную эвристику .
минимаксный алгоритм
Основной алгоритм, используемый для поиска в деревьях игр. На каждом уровне в дереве игры игрок, который должен двигаться, выбирает возможность, которая максимизирует минимальное преимущество, полученное в результате любого из возможных ответов оппонента. См. Алгоритм минимакса .
переместить генератор
Модуль, формирующий список ходов, которые следует учитывать с определенной позиции. Обычно это часть программного обеспечения шахматного движка, но некоторые шахматные компьютеры генерируют ходы аппаратно.

N – Z [ править ]

открытая книга
База данных ходов, которые нужно сыграть в шахматном дебюте с начала игры. Эти ходы можно выбрать прямо из памяти компьютера, поэтому поиск по ним не требуется.
слой
Ход белых или черных, следовательно, полуход. Полный ход - это два слоя. См. Слой .
основная вариация
Лучшая или правильная линия игры; вариант, наиболее выгодный для текущего игрока при условии, что каждый игрок выбирает лучшие ходы.
обрезка
Устранение веток в дереве игры без их поиска.
Обозначение ходов, которые являются законными на основе всех критериев, кроме подверженности проверке. Генераторы ходов оборудования, такие как у Belle , производят псевдозаконные ходы. Их необходимо проверить, чтобы убедиться, что они не мешают движущейся стороне. [1]
Расширение алгоритма поиска, которое будет продолжать поиск ветви за пределами того, что обычно было бы самой глубокой частью поиска (конечный узел), до тех пор, пока не будет достигнуто положение покоя, в котором захват невозможен и ни один король не находится под шахом. Этот прием можно использовать для минимизации опасности эффекта горизонта.
опровержение
Ход, демонстрирующий, что предыдущий рассматриваемый ход был бы плохим.
глубина поиска
Количество слоев, на которых выполняется поиск в дереве игры.
Поиск, при котором на каждом уровне дерева игры исследуются только некоторые возможности; контрастирует с полноширинным поиском.
Число Шеннона
Оценка снизу сложности дерева игр в шахматы. В 1950 году Клод Шеннон подсчитал, что в шахматах существует примерно 10 120 вариантов стартовой позиции.
конечный узел
конечная позиция
Самая глубокая часть поиска в определенной ветви дерева игры. Функция оценки применяется к оконечным узлам, чтобы присвоить значение этой ветви.
таблица транспонирования
Запись позиций и их оценок, найденных в предыдущей части поиска. Таблица транспонирования экономит вычисления, позволяя искать значение позиции, когда она снова достигается с помощью другого порядка ходов, вместо того, чтобы требовать повторного вычисления. См. Таблицу транспонирования .
стратегия типа А
Грубая сила, поиск по всей ширине с учетом всех возможных разрешенных ходов на каждом уровне дерева поиска. Придумано Клод Шеннон в 1949 году контрастировать с стратегией типа B .
стратегия типа B
Выборочный поиск , рассматривая одни строки более глубоко, чем другие. Придумано Клод Шеннон в 1949 году Contrast с стратегией типа A .
вариация
Определенная последовательность ходов, часто используемая для описания будущих возможностей в игре, а не ходов, которые были сыграны для достижения текущей позиции. Смотрите вариации .
окно
Разница между альфа и бета в алгоритме поиска альфа-бета. По мере поиска окно становится меньше. При поиске стремлений окно устанавливается на узкое значение. Самый крайний случай, поиск с нулевым окном , также называется поиском с нулевым окном или поисковым поиском .

Ссылки [ править ]

  1. ↑ Фрей, 1983, с. 203.