Многопоточная оценка с использованием Negamax + альфа-бета-обрезка с таблицами транспозиции

Question

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

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

Теперь у меня есть два соображения:

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

2. Каждый раз, когда я начинаю новый анализ, я должен очистить таблицы или они безопасны для использования?

Какие-нибудь мысли?

Answer 1

1. Вы ДОЛЖНЫ использовать одну таблицу транспозиции для всех потоков, поскольку основная идея заключается в том, что одна и та же позиция достигается разными путями, а не только дочерними узлами одного потока.

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

Еще одно соображение - очистить позиции, которые больше не могут быть достигнуты в текущей игре (то есть позиции с большим количеством фигур).

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

Таким образом, таблица транспонирования - это не что иное, как кеш, и вы должны определить и применить политику вытеснения. Это может быть комбинация различных факторов, и вам также следует проверить общие политики удаления кеша, такие как "Наименее недавно использованный (LRU)" https://en.wikipedia.org/wiki/Cache_replacement_policies