Según tengo entendido, los motores se pueden dividir en cuatro grupos en este momento: aquellos que usan Alpha-beta (AB) + aquellos que usan Monte Carlo Tree Search (MCTS) para la búsqueda, y aquellos que usan funciones escritas a mano + aquellos que usan redes neuronales para eval. Los dos motores más fuertes son Leela y Stockfish. Leela usa MCTS + NN, mientras que Stockfish usa AB + escrito a mano.
¿Por qué estas dos combinaciones? ¿Por qué no NN + AB o MCTS + escrito a mano? Si MCTS es mejor que AB, ¿por qué Komodo MCTS no es más fuerte que Komodo AB? Si AB es mejor que MCTS, ¿por qué Leela no usa AB en su lugar?
Respuestas:
Velocidad
Las redes neuronales operan mucho más lentamente que las funciones de evaluación artesanales. En el TCEC Superfinal , Leela Chess Zero, que se ejecuta en dos GPU cada una con núcleos de tensor dedicados, puede buscar alrededor de 60 mil posiciones por segundo. Por el contrario, Stockfish, en un solo núcleo en mi PC, busca más de 2 millones de posiciones por segundo.
Si bien los motores modernos tienen una gran selección de técnicas para cortar ramas innecesarias , la búsqueda de árboles alfa-beta sigue siendo una técnica de fuerza bruta, que requiere un gran número de posiciones para buscar buenos movimientos.
MCTS, por el contrario, es mucho más selectivo y solo expande su árbol de búsqueda hacia los movimientos más prometedores, lo que le permite aprovechar al máximo el número más limitado de nodos que se pueden buscar.
Comportamiento en el peor de los casos
Uno de los requisitos clave de la función de evaluación para un motor basado en la búsqueda alfa-beta es que debe tener un buen comportamiento en el peor de los casos . Esto se debe a que cualquier error importante en la evaluación, por raro que sea, puede propagarse fácilmente a la raíz y provocar un movimiento terriblemente incorrecto.
Por la naturaleza de su complejidad, las redes neuronales son propensas al sobreajuste y solo pueden ser tan buenas como los datos utilizados para entrenarlas. Por ejemplo, en el partido 80 de la Superfinal de la Temporada 14 de TCEC , en el movimiento 47 Lc0 aparentemente no se inmutó por la reina extra de Stockfish, evaluando la posición como un cool +0.77, mientras que Stockfish (y la mayoría de los otros motores) tenían una evaluación de +8.31. Una explicación popular para esto es que Lc0 puede no haber tenido un número significativo de juegos con múltiples reinas en el tablero en su conjunto de entrenamiento.
Las redes neuronales, por lo tanto, tienen un comportamiento pobre en el peor de los casos y, por lo tanto, es probable que funcionen mal con la búsqueda alfa beta. MCTS, por el contrario, permite compensar un puntaje incorrecto asignado a una posición al promediarlo con puntajes razonables asignados a las posiciones cercanas en la búsqueda.
Quietud
Todos los motores alfa-beta fuertes utilizan una técnica llamada búsqueda de reposo , una forma restringida de búsqueda alfa-beta aplicada en los nodos hoja, en reconocimiento de que sus funciones de evaluación artesanales solo funcionan bien en posiciones "silenciosas", donde no hay capturas o controles pendientes .
Por ejemplo, inmediatamente después de la primera mitad de un intercambio de reina, una función de evaluación artesanal podría decirle que el lado que acaba de tomar su reina está completamente perdido, mientras que una red neuronal puede comprender que la reina será recapturada pronto.
Esto hace que las funciones de evaluación artesanales sean igualmente inadecuadas para MCTS debido a la ausencia de búsqueda de inactividad, lo que da como resultado que las funciones artesanales funcionen mal la mayor parte del tiempo (aunque Komodo 12 MCTS supera esta restricción al usar búsquedas alfa-beta cortas de todos modos , para obtener posiciones inactivas y por lo tanto, permita que su evaluación artesanal devuelva un puntaje razonable)
fuente
AB y MCTS no son necesariamente mejores entre sí por sus propios méritos. Es solo que son diferentes algoritmos de búsqueda que funcionan mejor con diferentes fundamentos. Para el NN, MCTS funciona bien, ya que permite que el motor explore ramas que lo están haciendo mejor. Esto le da al motor más libertad para ver lo que "quiere".
Mientras tanto, con AB, todas las ramas en principio tienen que ser observadas. Esto se debe a que incluso con la profundización iterativa, el motor solo mira hasta ahora en cada rama en cada iteración. Por lo tanto, no sabe si una rama realmente está ganando para un lado, incluso si parece perder a una profundidad limitada.
fuente