Таблица транспозиции является кэшем ранее просмотренных позиций, и связанными с ними оценками, в дереве игры , порожденном компьютерная игра игровой программой. Если позиция повторяется через другую последовательность ходов, значение позиции извлекается из таблицы, что позволяет избежать повторного поиска в дереве игры под этой позицией. Таблицы транспонирования в первую очередь полезны в играх с точной информацией (где полное состояние игры всегда известно всем игрокам). Использование таблиц транспонирования по сути является мемоизацией, применяемой к поиску по дереву, и представляет собой форму динамического программирования .
Таблицы транспозиции обычно реализуются как хеш-таблицы, кодирующие текущую позицию платы как хеш-индекс. Количество возможных позиций, которые могут появиться в дереве игры, является экспоненциальной функцией глубины поиска и может составлять от тысяч до миллионов или даже больше. Таким образом, таблицы транспонирования могут потреблять большую часть доступной системной памяти и обычно занимают большую часть объема памяти игровых программ.
Функциональность
Игровые программы работают, анализируя миллионы позиций, которые могут возникнуть в следующие несколько ходов игры. Как правило, эти программы используют стратегии, напоминающие поиск в глубину , что означает, что они не отслеживают все позиции, проанализированные на данный момент. Во многих играх можно достичь определенной позиции более чем одним способом. Это называется транспонированием . [1] В шахматах , например, последовательность ходов 1. d4 Nf6 2. c4 g6 (см. Алгебраическую шахматную нотацию ) имеет 4 возможных перестановки, так как любой игрок может поменять порядок ходов . В общем, после n ходов верхний предел возможных перестановок равен ( n !) 2 . Хотя многие из них являются недопустимыми последовательностями ходов, все же вероятно, что программа в конечном итоге проанализирует одну и ту же позицию несколько раз.
Чтобы избежать этой проблемы, используются таблицы транспонирования. Такая таблица представляет собой хеш-таблицу каждой позиции, проанализированной на данный момент до определенной глубины. При обнаружении новой позиции программа проверяет таблицу, чтобы увидеть, была ли позиция уже проанализирована; это можно сделать быстро, с постоянной амортизацией. Если это так, таблица содержит значение, которое ранее было присвоено этой позиции; это значение используется напрямую. Если нет, значение вычисляется, и новая позиция вводится в хеш-таблицу.
Количество позиций, которые ищет компьютер, часто значительно превышает ограничения памяти системы, в которой он работает; таким образом, не все позиции могут быть сохранены. Когда таблица заполняется, менее используемые позиции удаляются, чтобы освободить место для новых; это делает таблицу транспонирования своего рода кешем .
Вычисление, сохраненное при поиске в таблице транспонирования, - это не просто оценка отдельной позиции. Вместо этого избегается оценка всего поддерева. Таким образом, записи таблицы транспонирования для узлов на меньшей глубине в дереве игры более ценны (поскольку размер поддерева, имеющего корень в таком узле, больше), и поэтому им придается большее значение, когда таблица заполняется и некоторые записи должны быть отброшены. .
Хеш-таблица, реализующая таблицу транспонирования, может использоваться не только для поиска транспозиций. При альфа-бета-отсечении поиск является самым быстрым (фактически, оптимальным), когда дочерний узел, соответствующий лучшему ходу, всегда рассматривается первым. Конечно, невозможно заранее узнать лучший ход, но когда используется итеративное углубление , ход, который был признан лучшим при более мелком поиске, является хорошим приближением. Поэтому сначала пробуем этот ход. Для сохранения лучшего потомка узла используется запись, соответствующая этому узлу в таблице транспонирования.
Использование таблицы транспонирования может привести к неверным результатам, если старательно не избежать проблемы взаимодействия графа с историей. Эта проблема возникает в некоторых играх, потому что история позиции может быть важной. Например, в шахматах игрок не может рокироваться, если король или ладья, с которой должна производиться рокировка, переместились во время игры. Обычное решение этой проблемы - добавить права на рокировку как часть хэш- ключа Zobrist . Другой пример - розыгрыш путем повторения : учитывая позицию, может быть невозможно определить, произошло ли это уже. Решение общей проблемы состоит в том, чтобы хранить историческую информацию в каждом узле таблицы транспонирования, но это неэффективно и редко делается на практике.
Стратегии замены
Таблица транспонирования - это кэш, максимальный размер которого ограничен доступной системной памятью, и он может переполниться в любой момент. Фактически, ожидается переполнение, и количество позиций, кэшируемых в любой момент, может быть лишь небольшой частью (даже на несколько порядков меньше), чем количество узлов в дереве игры. Подавляющее большинство узлов не являются узлами транспозиции, то есть позициями, которые будут повторяться, поэтому эффективные стратегии замены, которые сохраняют потенциальные узлы транспозиции и заменяют другие узлы, могут привести к значительному уменьшению размера дерева. Замена обычно основана на глубине дерева и старении: узлы выше в дереве (ближе к корню) предпочтительнее, потому что поддеревья под ними больше и приводят к большей экономии; предпочтение отдается более новым узлам, поскольку более старые узлы больше не похожи на текущее положение, поэтому транспозиции к ним менее вероятны.
Другие стратегии состоят в том, чтобы сохранить узлы в основном варианте, узлы с более крупными поддеревьями независимо от глубины дерева и узлы, вызвавшие отсечки.
Размер и производительность
Хотя доля узлов, которые будут транспонированы, мала, дерево игры представляет собой экспоненциальную структуру, поэтому кэширование очень небольшого количества таких узлов может иметь существенное значение. В шахматах сообщалось о сокращении времени поиска на 0-50% в сложных позициях в середине игры и до 5 раз в конце игры. [2]
Связанные методы
- Подобные методы могут использоваться для кэширования оценок определенных характеристик позиции. Например, пешечная хеш-таблица может использоваться для хранения оценки пешечных структур в позиции. Поскольку количество исследуемых пешечных позиций обычно намного меньше, чем общее количество найденных позиций, хеш-таблица пешек имеет очень высокий процент совпадений , что позволяет программе тратить больше времени на сложные оценки пешек, поскольку они многократно используются повторно.
- Таблица опровержения может быть использована для хранения последовательности переходит от корневого узла до листовых узлов. Это включает в себя основные вариации и ответы на другие строки, показывающие, что они хуже. Таблицы опровержения иногда использовались вместо таблиц транспонирования в первые годы компьютерных шахмат, когда память была более ограниченной. Некоторые современные шахматные программы используют таблицы опровержения в дополнение к таблицам транспонирования для упорядочивания ходов.
- Статические растровые изображения возможных ходов каждого типа фигуры на каждом участке доски могут быть кэшированы при инициализации программы, так что допустимые ходы фигуры (или вместе, все допустимые ходы для генерации ходов) могут быть извлечены из одной памяти. load вместо последовательного перечисления. Они обычно используются в реализациях битовой доски.
Смотрите также
Примечания и ссылки
- ^ Таблицы транспозиции , Gamedev.net, Франсуа-Доминик Ларами.
- ↑ Аткин, Л. и Слейт, Д., 1977, «Шахматы 4.5, шахматная программа Северо-Западного университета», в «Шахматные навыки человека и машины», Питер В. Фрей, изд. Спрингер-Верлаг, Нью-Йорк, Нью-Йорк
Внешние ссылки
- Таблицы транспонирования Sigmachess.com
- Технические данные The Main Transposition Table (информация о структуре данных и реализации)
- Анатомия шахматных программ TA Marsland, Университет Альберты
- Таблица транспонирования The Chess Programming Wiki