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