Насколько я понимаю, сейчас движки можно разделить на четыре группы: те, которые используют альфа-бета (AB) + те, которые используют поиск по методу Монте-Карло (MCTS) для поиска, и те, которые используют рукописные функции + те, которые используют нейронные сети для Eval. Два сильнейших двигателя - Лила и Стокфиш. Лила использует MCTS + NN, а Stockfish - AB +, написанный от руки.
Почему эти две комбинации? Почему не NN + AB или MCTS + от руки? Если MCTS лучше, чем AB, почему Komodo MCTS сильнее, чем Komodo AB? Если AB лучше, чем MCTS, почему Лила не использует вместо этого AB?
Ответы:
скорость
Нейронные сети работают намного медленнее, чем функции оценки, созданные вручную. В Суперфинале TCEC Leela Chess Zero, работающая на двух графических процессорах, каждый из которых имеет выделенные тензорные ядра, может искать около 60 тысяч позиций в секунду. В противоположность этому, Stockfish на одном ядре моего компьютера ищет более 2 миллионов позиций в секунду.
В то время как современные движки имеют огромный выбор методов для отсечения ненужных ветвей , поиск по альфа-бета-дереву все еще остается методом грубой силы, требующим поиска огромного количества позиций для определения хороших ходов.
MCTS, напротив, гораздо более избирателен и только расширяет свое дерево поиска в сторону наиболее многообещающих перемещений, что позволяет ему максимально использовать более ограниченное количество узлов, которые можно искать.
Наихудшее поведение
Одним из ключевых требований функции оценки для механизма, основанного на альфа-бета-поиске, является то, что он должен иметь хорошее поведение в худшем случае . Это связано с тем, что любая большая ошибка в оценке, пусть и редкая, может легко распространиться на корень и привести к ужасно неправильному ходу.
По своей сложности нейронные сети склонны к переоснащению и могут быть не хуже данных, используемых для их обучения. Например, в матче 80 Суперфинала 14-го сезона TCEC , на ходу 47 Lc0, по-видимому, не был обеспокоен дополнительной королевой Stockfish, оценивая позицию как крутую +0,77, в то время как Stockfish (и большинство других двигателей) демонстрировали оценку +8,31. Популярным объяснением этого является то, что в Lc0, возможно, не было значительного количества игр с несколькими ферзями на игровом поле.
Поэтому нейронные сети имеют плохое поведение в худшем случае и, следовательно, могут плохо работать с альфа-бета-поиском. MCTS, напротив, позволяет смещать неверную оценку, присвоенную одной позиции, путем ее усреднения с разумными оценками, присваиваемыми позициям, находящимся поблизости в поиске.
неподвижность
Все сильные альфа-бета-движки используют технику, называемую поиском покоя , ограниченной формой альфа-бета-поиска, применяемой в конечных узлах, в подтверждение того, что их функции оценки, созданные вручную, хорошо работают только в «тихих» положениях, где нет ожидающих захватов или проверок ,
Например, сразу после первой половины обмена ферзями функция оценки, созданная вручную, может сообщить вам, что сторона, у которой только что была взята их ферзь, полностью потеряна, тогда как нейронная сеть может понять, что ферзь скоро будет пойман.
Это делает функции оценки, созданные вручную, также непригодными для MCTS из-за отсутствия поиска покоя, что приводит к тому, что функции, выполняемые вручную, выполняют плохо большую часть времени (хотя Komodo 12 MCTS в любом случае обходит это ограничение, используя короткие альфа-бета-поиски , чтобы получить позиции покоя и следовательно, позвольте его ручной оценке вернуть разумную оценку)
источник
AB и MCTS не обязательно лучше друг друга по своим достоинствам. Просто это разные поисковые алгоритмы, которые лучше работают с разными основами. Для NN MCTS работает хорошо, поскольку позволяет движку исследовать ветви, которые работают лучше. Это дает двигателю больше свободы смотреть на то, что он «хочет».
Между тем с AB все ветки в принципе должны быть рассмотрены. Это потому, что даже при итеративном углублении механизм просматривает только каждую ветвь в каждой итерации. Таким образом, он не знает, выигрывает ли одна ветка на одной стороне, даже если кажется, что она проигрывает на ограниченной глубине.
источник