Почему Faile намного быстрее, чем простая шахматная программа (TSCP)? (Оптимизация шахматных движков)

Question

Надеюсь, это не слишком большой вопрос, но я просматриваю исходные коды Faile и TSCP, и я играю их друг против друга. Насколько я вижу, у двигателей много общего, но Faile ищет ~ 1,3 миллиона узлов в секунду, в то время как TSCP ищет только 300 тыс. Узлов в секунду.

Исходный код для faile можно найти здесь: http://faile.sourceforge.net/download.php. Исходный код TSCP можно найти здесь: http://www.tckerrigan.com/Chess/TSCP.

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

Мой вопрос: почему существует 4-кратное различие в скорости этих двух программ? Кроме того, почему Faile последовательно избивает TSCP (я оцениваю примерно 200 ELO разностей, просто наблюдая за их ходами)? Для последнего это, по-видимому, связано с тем, что Фейл ищет несколько слоев глубже.

Answer 1

TSCP не имеет хеш-таблиц (-75 ELO). У TSCP нет ордеров для убийц (-50 ELO). TSCP не имеет нулевого перемещения (-100 ELO). TSCP имеет плохую функцию функции атаки (-25 ELO).

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

Answer 2

Короткий ответ: TSCP очень прост (как вы можете догадаться из его названия). Faile более продвинутый, некоторое время было потрачено разработчиками для его оптимизации. Поэтому для Фейли достаточно разумно быть быстрее, что означает также более глубокий поиск и повышение ELO.

Длинный ответ: Насколько я помню, самая важная часть программы, использующая альфа-бета-поиск (часть, которая больше всего влияет на производительность), является генератором движения. Генератор движений TSCP не генерирует ходы в каком-либо конкретном порядке. Генератор Файла (как вы заметили) использует список штук, который сортируется в порядке уменьшения значения штуки. Это означает, что сначала он генерирует более важные шаги. Это позволяет обрезать альфа-бета, чтобы сократить больше ненужных движений и делает дерево поиска менее разветвленным. И менее разветвленное дерево может быть глубже и все равно иметь такое же количество узлов, что позволяет более глубокий поиск.

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

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