Таблица транспонирования

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

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

Функциональность

Игровые программы работают, анализируя миллионы позиций, которые могут возникнуть в следующие несколько ходов игры. Обычно эти программы используют стратегии, напоминающие поиск в глубину , что означает, что они не отслеживают все проанализированные на данный момент позиции. Во многих играх можно достичь заданной позиции несколькими способами. Это так называемые транспозиции . В шахматах , например, последовательность ходов 1. d4 Nf6 2. c4 g6 (см. обозначение алгебраических шахмат ) имеет 4 возможных транспозиции, поскольку любой игрок может поменять порядок своих ходов. В общем, после n ходов верхний предел возможных транспозиций равен ( n !) ² . Хотя многие из этих последовательностей ходов являются недопустимыми, вполне вероятно, что программа в конечном итоге будет анализировать одну и ту же позицию несколько раз.

Чтобы избежать этой проблемы, используются таблицы транспонирования. Такая таблица представляет собой хеш-таблицу каждой из проанализированных на данный момент позиций до определенной глубины. При обнаружении новой позиции программа проверяет таблицу, чтобы убедиться, что позиция уже проанализирована; это можно сделать быстро, за амортизированное постоянное время. Если да, то таблица содержит значение, которое ранее было присвоено этой позиции; это значение используется напрямую. Если нет, значение вычисляется, и новая позиция вводится в хеш-таблицу.

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

Вычисления, сохраненные при поиске в таблице транспонирования, — это не просто оценка одной позиции. Вместо этого избегается оценка всего поддерева. Таким образом, записи таблицы транспонирования для узлов на меньшей глубине в дереве игры более ценны (поскольку размер поддерева, основанного на таком узле, больше) и поэтому им придается большее значение, когда таблица заполняется и некоторые записи необходимо отбросить. .

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

Использование таблицы транспонирования может привести к неверным результатам, если тщательно не избежать проблемы взаимодействия графа и истории. Эта проблема возникает в некоторых играх, поскольку история позиции может иметь важное значение. Например, в шахматах игрок не может рокироваться, если король или ладья, с которой должна быть сделана рокировка, переместились в ходе игры. Распространенным решением этой проблемы является добавление прав рокировки как части хеш-ключа Zobrist . Другой пример — рисование путем повторения : учитывая позицию, может быть невозможно определить, произошло ли это уже. Решение общей проблемы — хранить историческую информацию в каждом узле таблицы транспонирования, но это неэффективно и на практике делается редко.

Стратегии замены

Таблица транспонирования — это кэш, максимальный размер которого ограничен доступной системной памятью, и он может переполниться в любой момент. На самом деле ожидается переполнение, и количество позиций, кэшируемых в любой момент времени, может составлять лишь небольшую часть (даже на порядки меньше), чем количество узлов в дереве игры. Подавляющее большинство узлов не являются узлами транспозиции, то есть позициями, которые будут повторяться, поэтому эффективные стратегии замены, которые сохраняют потенциальные узлы транспозиции и заменяют другие узлы, могут привести к значительному уменьшению размера дерева. Замена обычно основана на глубине и старении дерева: предпочтение отдается узлам выше в дереве (ближе к корню), поскольку поддеревья ниже них крупнее и приводят к большей экономии; Предпочтение отдается более поздним узлам, поскольку более старые узлы больше не похожи на текущую позицию, поэтому транспозиции в них менее вероятны.

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

Размер и производительность

Хотя доля узлов, которые будут транспонированы, невелика, дерево игры представляет собой экспоненциальную структуру, поэтому кэширование очень небольшого количества таких узлов может иметь существенное значение. В шахматах сообщалось о сокращении времени поиска на 0–50% в сложных позициях в середине игры и до 5 раз в конце игры.

Связанные методы

• Подобные методы можно использовать для кэширования оценок определенных характеристик позиции. Например, хэш-таблица пешек может использоваться для хранения оценки пешечных структур в позиции. Поскольку количество проверенных пешек обычно намного меньше, чем общее количество искомых позиций, хеш-таблица пешек имеет очень высокую вероятность попадания , что позволяет программе тратить больше времени на сложные оценки пешек, поскольку они используются повторно много раз.
• Таблицу опровержений можно использовать для хранения последовательностей ходов от корневого узла к листовым узлам. Сюда входят основные вариации и реакции на другие линии, показывающие, что они хуже. Таблицы опровержений иногда использовались вместо таблиц транспонирования в первые годы компьютерных шахмат, когда память была более ограниченной. Некоторые современные шахматные программы используют таблицы опровержений в дополнение к таблицам транспонирования для упорядочивания ходов.
• Статические растровые изображения возможных ходов каждого типа фигуры на каждом поле доски могут быть кэшированы при инициализации программы, так что допустимые ходы фигуры (или вместе все допустимые ходы для генерации ходов) можно извлечь из одной памяти. load вместо последовательного перечисления. Они обычно используются в реализациях растровых панелей.

См. также

• Минимаксный алгоритм
• Альфа-бета обрезка
• Зобристское хеширование

Внешние ссылки

• Таблицы транспонирования Sigmachess.com
• Техническая Основная таблица транспонирования (информация о структуре данных и реализации)
• Анатомия шахматных программ Т. А. Марсланд, Университет Альберты
• Таблица транспонирования The Chess Programming Wiki