¿Por qué Faile es mucho más rápido que el Simple Chess Program (TSCP)? (Optimización del motor de ajedrez)

Question

Espero que esto no sea una pregunta demasiado arbitraria, pero he estado revisando los códigos fuente de Faile y TSCP y los he jugado uno contra el otro. Por lo que puedo ver, los motores tienen mucho en común, pero Faile busca ~ 1.3 millones de nodos por segundo mientras que TSCP busca solo 300k nodos por segundo.

El código fuente para faile se puede encontrar aquí: http://faile.sourceforge.net/download.php. El código fuente de TSCP se puede encontrar aquí: http://www.tckerrigan.com/Chess/TSCP.

Después de mirar a través de ellos veo algunas similitudes: ambos usan una representación de matriz (aunque Faile usa una placa de tamaño 144), ambos usan una búsqueda alpha beta con algún tipo de tabla de transposición, ambos tienen funciones de evaluación muy similares. La principal diferencia que puedo encontrar es que Faile usa una representación redundante del tablero al tener también matrices de las ubicaciones de las piezas. Esto significa que cuando se generan movimientos (por funciones muy similares para ambos programas), Faile tiene que pasar por un ciclo de menos piezas malas, mientras que mantener esta matriz cuesta considerablemente menos recursos.

Mi pregunta es: ¿por qué hay una diferencia 4x en la velocidad de estos dos programas? Además, ¿por qué Faile constantemente vence al TSCP (estimo una diferencia de ~ 200 ELO simplemente observando sus movimientos)? Para el último, parece ser porque Faile está buscando varias capas más profundas.

Answer 1

TSCP no tiene tablas hash (-75 ELO). TSCP no tiene movimientos de asesinos para ordenar (-50 ELO). TSCP no tiene movimiento nulo (-100 ELO). TSCP tiene un diseño de función de ataque incorrecto (-25 ELO).

En estas 4 cosas tienes una diferencia de 250 puntos ELO. Esto aumentará la cantidad de nodos por segundo, pero no puede comparar los nodos por segundo en diferentes motores, ya que los programadores pueden usar una interpretación diferente de lo que es un nodo.

Answer 2

Respuesta corta: TSCP es muy simple (como se puede adivinar por su nombre). Faile es más avanzado, algunos desarrolladores pasaron algún tiempo para optimizarlo. Por lo tanto, es razonable que Faile sea más rápido, lo que significa también una búsqueda más profunda y mayor ELO.

Respuesta larga: Por lo que recuerdo, la parte más importante del programa, utilizando alfa beta search (parte que más influye en el rendimiento), es el generador de movimientos. El generador de movimiento de TSCP no genera movimientos en ningún orden en particular. El generador de Faile (como habrás notado) usa una lista de piezas, que se ordena en orden de valor de pieza decreciente. Esto significa que genera movimientos más importantes primero. Esto permite que la poda alfa-beta corte más movimientos innecesarios y hace que el árbol de búsqueda sea menos ramificado. Y menos árbol ramificado puede ser más profundo y aún tener el mismo número de nodos, lo que permite una búsqueda más profunda.

Aquí hay un ejemplo muy simplificado de cómo el orden de los movimientos permite una búsqueda más rápida. Supongamos que el último movimiento del blanco fue una tontería: movieron una pieza a una posición desprotegida. Si encontramos algún movimiento de negro que elimina esta pieza, podemos ignorar todos los movimientos que aún no se hayan calculado y regresar a la lista de movimientos del blanco de procesamiento. Queen controla mucho más espacio que un peón, por lo que tiene más posibilidades de eliminar esta pieza, por lo que si miramos primero los movimientos de la reina, es más probable que saltemos más movimientos innecesarios.

No comparé otras partes de estos programas. Pero lo más probable es que Faile los optimice también mejor. Cosas como el algoritmo alfa-beta en sí mismo, profundidad variable del árbol de búsqueda, análisis de posición estática también pueden optimizarse.