Как улучшить производительность, используя Transposition Table в Game Playing?

Question

Я реализовал в своей игре итеративное углубление с альфа-бета-обрезкой, а также добавил таблицу транспозиции для хранения уже оцененных досок.

Сейчас я делаю следующее:

1. При выполнении итеративного углубления на глубине = 0 он оценивает и сохраняет все позиции с их оценками в TT.
2. Теперь, когда он перезапускается с глубиной = 1. Я просто возвращаю значение платы, если оно существует в ТТ. Это останавливает алгоритм на глубине = 0, поскольку все значения уже находятся в ТТ для досок с глубиной = 0.

Если я возвращаю значения из ТТ при достижении предела глубины, например. глубина = MAX_DEPTH, тогда большие поддеревья никогда не будут обрезаны.

Итак, я не понимаю, как мне повторно использовать значения, хранящиеся в ТТ, для ускорения моей игры?

Answer 1

Я просто возвращаю значение доски, если оно существует в ТТ.

Для этого необходимо условие: вернуть / использовать значение, если эта позиция была оценена на глубине больше илиравен вашей текущей глубине поиска. В противном случае оцените снова и замените запись TT.

Это означает, что ваш TT также должен хранить, насколько глубоким был поиск позиции.

Но то, что я также не вижу в вашем алгоритме, - это основное использование TT для итеративного углубления: перед расширением дерева в определенном узле сначала упорядочите ходы с доступными оценками из TT. Потому что альфа / бета работает намного лучше, когда вы сначала оцениваете более сильные движения.

Answer 2

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

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

WKe5Qd6Pg2h3h4 BKa8Qa7

Так что если вы попадаете на позицию, вы проверяете наличие ключа кеша, и еслиИтак, затем повторно использовать его оценку. Всякий раз, когда вы посещаете позицию на глубине = 0, после ее правильной оценки она может быть кэширована. Таким образом, если некоторые шаги сделаны, в подвариантах вы можете более или менее перепрыгнуть через оценку. Например, давайте рассмотрим пример того, что в начальной позиции белые переместились на 1. Nf3, а черные ответили 1 ... Nf6. После того, как результирующие позиции для обоих слоев были кэшированы, позиция 2. Белые Ng1 нуждаются в оценке, поскольку они еще не оценивались и не кэшировались, но возможно, что черные 2 ... Ng8 не нуждаются в оценке, потому что это приводит к старту. position.

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

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

• эффект правила 50 ходов
• 3-кратный повтор повторов
• кто на ходу
• были / есть какие-то особые ходы, такие как рокировка или проход, возможно в прошлом / в настоящем, а не в другом случае

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