Транспозиционная таблица
Кэш уже проанализированных игровых позиций, чтобы поиск не считал заново ту же позицию лишь потому, что к ней пришли другим порядком ходов.
В шахматах 1.e4 e5 2.Nf3 и 1.Nf3 e5 2.e4 приводят к одной и той же позиции — транспозиции. Без памяти поиск анализирует её дважды, а в глубине дерева дубликаты исчисляются миллионами. Таблица — большая хеш-таблица с ключом-хешем позиции, обычно Зобриста; в ней хранятся глубина поиска, оценка, точная она или лишь граница, и лучший ход.
Последнее поле важно не меньше оценки: при итеративном углублении лучший ход прошлой итерации пробуют первым, и альфа-бета работает заметно эффективнее. Таблицы всегда не хватает, поэтому у движков есть политики замещения, решающие, какие записи можно затирать, — классический компромисс кэша в новом обличье.