Таблица транспозиций в игровых программах

Введение

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

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

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

Программы для игры работают, анализируя миллионы позиций, которые могут возникнуть в следующих нескольких ходах игры. Как правило, эти программы используют стратегии, напоминающие поиск в глубину, что означает, что они не отслеживают все проанализированные до сих пор позиции. Во многих играх можно достичь заданной позиции несколькими способами. Это называется транспозициями. В шахматах, например, последовательность ходов 1. d4 Nf6 2. c4 g6 (см. алгебраическую шахматную нотацию) имеет 4 возможных транспозиции, поскольку любой игрок может изменить порядок ходов. В общем случае, после n ходов верхняя граница возможных транспозиций равна (n!)². Хотя многие из них являются незаконными последовательностями ходов, вполне вероятно, что программа в конечном итоге будет анализировать одну и ту же позицию несколько раз. Чтобы избежать этой проблемы, используются таблицы транспозиций. Такая таблица представляет собой хэш-таблицу, содержащую информацию о каждой из проанализированных позиций до определенной глубины. При обнаружении новой позиции программа проверяет таблицу, чтобы узнать, была ли эта позиция уже проанализирована; это можно сделать быстро, в амортизированном постоянном времени. Если да, то в таблице содержится значение, которое ранее было присвоено этой позиции; это значение используется напрямую. Если нет, то значение вычисляется, и новая позиция добавляется в хэш-таблицу. Количество позиций, которые просматривает компьютер, часто значительно превышает ограничения памяти системы, на которой он работает; таким образом, не все позиции могут быть сохранены. Когда таблица заполняется, менее используемые позиции удаляются, чтобы освободить место для новых; это делает таблицу транспозиций своего рода кэшем. Экономия вычислений при поиске в таблице транспозиций заключается не только в оценке одной позиции. Вместо этого избегается оценка целого поддерева. Таким образом, записи таблицы транспозиций для узлов на меньшей глубине в игровом дереве более ценны (поскольку размер поддерева, укорененного в таком узле, больше), и поэтому им придается большее значение при заполнении таблицы и необходимости отбрасывания некоторых записей. Хэш-таблица, реализующая таблицу транспозиций, может использоваться не только для поиска транспозиций. При альфа-бета отсечении поиск выполняется быстрее всего (фактически, оптимально), когда первым рассматривается дочерний узел, соответствующий наилучшему ходу. Конечно, заранее узнать наилучший ход невозможно, но при использовании итеративного углубления ход, который был признан наилучшим при более мелком поиске, является хорошим приближением. Поэтому этот ход пробуется первым. Для хранения наилучшего дочернего узла используется запись, соответствующая этому узлу в таблице транспозиций. Использование таблицы транспозиций может привести к неверным результатам, если не избегать проблемы взаимодействия истории графов. Эта проблема возникает в некоторых играх, поскольку история позиции может быть важна. Например, в шахматах игрок не может сделать рокировку, если король или ладья, с которой он делает рокировку, переместились в ходе игры. Распространенным решением этой проблемы является добавление права на рокировку в качестве части хеш-ключа Цобериста. Другой пример – ничья повторением: для заданной позиции может быть невозможно определить, встречалась ли она уже ранее. Решением общей проблемы является хранение исторической информации в каждом узле таблицы транспозиций, но это неэффективно и редко делается на практике.

Game playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling depth first search, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called transpositions. In chess, for example, the sequence of moves 1. d4 Nf6 2. c4 g6 (see algebraic chess notation) has 4 possible transpositions, since either player may swap their move order. In general, after n moves, an upper limit on the possible transpositions is (n!)2. Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times. To avoid this problem, transposition tables are used. Such a table is a hash table of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see whether the position has already been analyzed; this can be done quickly, in amortized constant time. If so, the table contains the value that was previously assigned to this position; this value is used directly. If not, the value is computed, and the new position is entered into the hash table. The number of positions searched by a computer often greatly exceeds the memory constraints of the system it runs on; thus not all positions can be stored. When the table fills up, less used positions are removed to make room for new ones; this makes the transposition table a kind of cache. The computation saved by a transposition table lookup is not just the evaluation of a single position. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a shallower depth in the game tree are more valuable (since the size of the subtree rooted at such a node is larger) and are therefore given more importance when the table fills up and some entries must be discarded. The hash table implementing the transposition table can have other uses than finding transpositions. In alpha–beta pruning, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first. Of course, there is no way of knowing the best move beforehand, but when iterative deepening is used, the move that was found to be the best in a shallower search is a good approximation. Therefore this move is tried first. For storing the best child of a node, the entry corresponding to that node in the transposition table is used. Use of a transposition table can lead to incorrect results if the graph history interaction problem is not studiously avoided. This problem arises in certain games because the history of a position may be important. For example, in chess a player may not castle if the king or the rook to be castled with has moved during the course of the game. A common solution to this problem is to add the castling rights as part of the Zobrist hashing key. Another example is draw by repetition: given a position, it may not be possible to determine whether it has already occurred. A solution to the general problem is to store history information in each node of the transposition table, but this is inefficient and rarely done in practice.

Стратегии замещения

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

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

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

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

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