algorithm - tag - Optimizaciones de ajedrez

title tag html

Question

ok, entonces he estado trabajando en mi programa de ajedrez por un tiempo y estoy empezando a golpear una pared. ¡He hecho todas las optimizaciones estándar (negascout, profundización iterativa, movimientos asesinos, heurística de la historia, búsqueda inactiva, evaluación de la posición del peón, algunas extensiones de búsqueda) y me quedé sin ideas!

Estoy tratando de hacer que sea multiproceso pronto, y eso debería darme un buen impulso en el rendimiento, pero aparte de eso, ¿hay otros trucos ingeniosos que hayan encontrado? He considerado cambiar a MDF (f), pero he oído que es una molestia y realmente no vale la pena.

en lo que estaría más interesado es en algún tipo de algoritmo de aprendizaje, pero no sé si alguien lo ha hecho de manera efectiva con un programa de ajedrez.

Además, ¿sería significativo cambiar a una tabla de bits? Actualmente estoy usando 0x88.

Answer 1

Buen movimiento ordenando!

Una vieja pregunta, pero las mismas técnicas se aplican ahora como hace 5 años. ¿No estamos todos escribiendo nuestros propios motores de ajedrez? Tengo mi propio "Gambito noruego" que espero que eventualmente compita con otros motores de Java en el CCRL. Yo, como muchos otros, utilizo Stockfish para las ideas, ya que está muy bien escrito y abierto. Su marco de prueba Fishtest y su comunidad también dan un montón de buenos consejos. Vale la pena comparar sus puntajes de evaluación con lo que obtiene Stockfish, ya que la evaluación es probablemente la incógnita más desconocida en la programación de ajedrez, y Stockfish se ha alejado de muchas tendencias tradicionales que se han convertido en leyendas urbanas (como el bono de doble alfil). Sin embargo, la mayor diferencia fue después de que implementé las mismas técnicas que mencionas, Negascout, TT, LMR, comencé a usar Stockfish para comparar y noté que para la misma profundidad Stockfish tenía muchos menos movimientos que los que tenía (debido al orden de movimientos). ).

Mueve lo esencial para ordenar

Lo único que se olvida fácilmente es una buena ordenación de movimientos. Para que el corte Alpha Beta sea eficiente es esencial obtener los mejores movimientos primero. Por otro lado, también puede llevar mucho tiempo, por lo que es esencial hacerlo solo cuando sea necesario.

1. Tabla de transposición
2. Ordenar promociones y buenas capturas por su ganancia.
3. Movimientos asesinos
4. Mueve ese resultado en el control del oponente.
5. Historia Heurística
6. Movimientos silenciosos - ordenar por valor de PSQT

La clasificación debe realizarse según sea necesario, por lo general, es suficiente para ordenar las capturas y, a partir de entonces, puede ejecutar la clasificación más costosa de cheques y PSQT solo si es necesario.

Acerca de Java / C # vs C / C ++ / Assembly

Las técnicas de programación son las mismas para Java que en la excelente respuesta de Adam Berent que usó C #. Además de su lista, mencionaría evitar las matrices de objetos, en lugar de usar muchas matrices de primitivas, pero contrariamente a su sugerencia de usar bytes, encuentro que con java de 64 bits hay poco que guardar usando bytes e int en lugar de 64 bits. También he ido por el camino de la reescritura a C / C ++ / Assembly y no tengo ninguna ganancia de rendimiento. Utilicé el código de ensamblaje para las instrucciones de exploración de bits como LZCNT y POPCNT, pero más tarde descubrí que Java 8 también usa esos en lugar de los métodos en el objeto Long. Para mi sorpresa, Java es más rápido, la máquina virtual Java 8 parece hacer un mejor trabajo de optimización que un compilador de C.

Answer 2

Durante el último año de desarrollo de mi motor de ajedrez ( www.chessbin.com ), la mayor parte del tiempo se ha dedicado a optimizar mi código para permitir una mejor y más rápida búsqueda de movimientos. Durante ese tiempo he aprendido algunos trucos que me gustaría compartir con ustedes.

Medición de desempeño

Esencialmente puedes mejorar tu rendimiento de dos maneras:

• Evalúa tus nodos más rápido
• Busca menos nodos para llegar a la misma respuesta.

Tu primer problema en la optimización de código será la medición. ¿Cómo sabes que realmente has hecho una diferencia? Para poder ayudarlo con este problema, deberá asegurarse de poder registrar algunas estadísticas durante la búsqueda de movimiento. Los que capturo en mi motor de ajedrez son:

• Tiempo que tardó la búsqueda en completarse.
• Número de nodos buscados

Esto le permitirá comparar y probar sus cambios. La mejor manera de enfocar las pruebas es crear varias partidas guardadas desde la posición inicial, el juego intermedio y el final. Registre la hora y el número de nodos buscados en blanco y negro. Después de realizar cualquier cambio, generalmente realizo pruebas contra los juegos guardados mencionados anteriormente para ver si he realizado mejoras en las dos matrices anteriores: número de nodos buscados o velocidad.

Para complicar aún más las cosas, después de hacer un cambio de código, puede ejecutar su motor 3 veces y obtener 3 resultados diferentes cada vez. Digamos que su motor de ajedrez encontró el mejor movimiento en 9, 10 y 11 segundos. Eso es una propagación de alrededor del 20%. Entonces, ¿mejoró su motor en un 10% -20% o fue solo una carga variable en su PC? ¿Cómo lo sabes? Para luchar contra esto, he añadido métodos que permitirán que mi motor juegue contra sí mismo, hará movimientos tanto en blanco como en negro. De esta manera puede probar no solo la variación de tiempo en un movimiento, sino una serie de hasta 50 movimientos en el transcurso del juego. Si la última vez que el juego tomó 10 minutos y ahora toma 9, probablemente mejoró su motor en un 10%. Ejecutar la prueba de nuevo debería confirmar esto.

Encontrar ganancias de rendimiento

Ahora que sabemos cómo medir las ganancias de rendimiento, analicemos cómo identificar las posibles ganancias de rendimiento.

Si estás en un entorno .NET, el perfilador de .NET será tu amigo. Si tiene una edición de Visual Studio para desarrolladores, esta viene incorporada de forma gratuita, sin embargo, existen otras herramientas de terceros que puede utilizar. Esta herramienta me ha ahorrado horas de trabajo, ya que le dirá dónde está gastando la mayor parte de su motor y le permitirá concentrarse en sus puntos problemáticos. Si no tiene una herramienta de perfil, es posible que tenga que registrar de alguna manera las marcas de tiempo a medida que su motor pasa por diferentes pasos. No sugiero esto. En este caso un buen perfilador vale su peso en oro. Red Gate ANTS Profiler es caro, pero es el mejor que he probado. Si no puede pagar uno, al menos utilícelo para su prueba de 14 días.

Su perfilador seguramente identificará cosas para usted, sin embargo, aquí hay algunas pequeñas lecciones que aprendí trabajando con C #:

• Hacer que todo sea privado
• Lo que no puedas hacer privado, hazlo sellado.
• Hacer tantos métodos estáticos como sea posible.
• No hagas que tus métodos sean conversadores, un método largo es mejor que 4 más pequeños.
• El tablero de ajedrez almacenado como una matriz [8] [8] es más lento que una matriz de [64]
• Reemplace int con byte cuando sea posible.
• Vuelva de sus métodos lo antes posible.
• Las pilas son mejores que las listas.
• Las matrices son mejores que las pilas y las listas.
• Si puede definir el tamaño de la lista antes de rellenarla.
• Casting, boxeo, un-boxing es el mal.

Más ganancias de rendimiento:

Me parece que la generación de movimiento y el orden es extremadamente importante. Sin embargo aquí está el problema tal como lo veo. Si evalúa la puntuación de cada movimiento antes de ordenar y ejecutar Alpha Beta, podrá optimizar su orden de movimientos de modo que obtenga cortes de Alpha Beta extremadamente rápidos. Esto se debe a que, en su mayoría, podrás probar el mejor movimiento primero. Sin embargo, se perderá el tiempo que ha pasado evaluando cada movimiento. Por ejemplo, puede haber evaluado la puntuación en 20 movimientos, ordene sus movimientos, pruebe los primeros 2 y reciba un corte en el movimiento número 2. En teoría, se perdió el tiempo que dedicó a los otros 18 movimientos.

Por otro lado, si realiza una evaluación más ligera y mucho más rápida, por ejemplo, solo capturas, su clasificación no será tan buena y tendrá que buscar más nodos (hasta un 60% más). Por otro lado, no harías una evaluación pesada en cada movimiento posible. En general, este enfoque suele ser más rápido .

Encontrar este equilibrio perfecto entre tener suficiente información para una buena clasificación y no hacer un trabajo extra en movimientos que no usará, le permitirá encontrar grandes ganancias en su algoritmo de búsqueda. Además, si elige el método de clasificación más pobre, primero deberá hacer una búsqueda más superficial, como decir 3, ordene su movimiento antes de entrar en la búsqueda más profunda (esto a menudo se denomina profundización iterativa). Esto mejorará significativamente tu ordenación y te permitirá buscar muchos menos movimientos.

Answer 3

En cuanto a las sugerencias, sé que se pueden encontrar grandes ganancias en la optimización de las rutinas de generación de movimientos antes que cualquier función eval. Hacer que la función sea lo más ajustada posible le puede dar un 10% o más en la mejora de nodos / seg.

Si te estás mudando a bitboards, investiga un poco en los archivos rec.games.chess.computer para algunas de las publicaciones antiguas del Dr. Robert Hyatts sobre Crafty (bastante seguro de que ya no publicará). O toma la última copia de su FTP y comienza a cavar. Aunque estoy bastante seguro de que sería un cambio significativo para ti.

Answer 4

Es una pregunta bastante antigua, solo estaba buscando preguntas sobre ajedrez y encontré esta sin respuesta. Bueno, puede que no sea de ninguna ayuda para usted ahora, pero puede ser útil para otros usuarios.

No vi podas de movimientos nulos, tablas de transposición ... ¿las estás usando? Te darían un gran impulso ...

Una cosa que me dio un gran impulso fue minimizar la ramificación condicional ... Muchas cosas pueden ser precomputadas. Búsqueda de tales oportunidades.

La mayoría de las PC modernas tienen múltiples núcleos, por lo que sería una buena idea convertirla en multiproceso. No necesariamente tienes que ir MDF (f) para eso.

No sugiero mover tu código a bitboard. Es simplemente demasiado trabajo. A pesar de que los bitboards pueden dar un impulso a las máquinas de 64 bits.

Finalmente, y lo más importante, la literatura de ajedrez domina cualquier optimización que podamos usar. La optimización es demasiado trabajo. Mire los motores de ajedrez de código abierto, particularmente astutos y frutales / toga. La fruta solía ser de código abierto inicialmente.

Answer 5

Ha pasado mucho tiempo desde que hice cualquier programación en cualquier programa de ajedrez, pero en ese momento, los tableros de bits dieron una verdadera mejora. Aparte de eso no puedo darte mucho consejo. ¿Solo evalúas la posición de los peones? Algunas bonificaciones (leves) por la posición o movilidad de algunas piezas clave pueden estar en orden.

No estoy seguro de qué tipo de cosas te gustaría aprender sin embargo ...

Answer 6

Perfil y punto de referencia. Las optimizaciones teóricas son excelentes, pero a menos que esté midiendo el impacto en el rendimiento de cada cambio que realice, no sabrá si su trabajo está mejorando o empeorando la velocidad del código final.

Intenta limitarte el castigo a ti mismo por probar diferentes algoritmos. Facilita la prueba de varias implementaciones de algoritmos entre sí. Por ejemplo, facilite la creación de una versión PVS de su código, así como una versión NegaScout.

Encuentra los puntos calientes. Refactor Reescriba en ensamblaje si es necesario. Repetir.

Answer 7

Respondiendo una vieja pregunta.

Suponiendo que ya tiene una tabla de transposición de trabajo.

Reducción de movimiento tardío. Eso le dio a mi programa unos 100 puntos elo y es muy simple de implementar.

En mi experiencia, a menos que su implementación sea muy ineficiente, entonces la representación real de la placa (0x88, bitboard, etc.) no es tan importante.

Si bien puede dañar su motor de ajedrez con un rendimiento deficiente, un generador de movimientos a la velocidad del rayo en sí mismo no va a hacer que un programa funcione bien.

Los trucos de búsqueda utilizados y la función de evaluación son los factores abrumadores que determinan la fortaleza general.

Y las partes más importantes, de lejos, de la evaluación son Material, Peones pasados, Seguridad de rey y Estructura de peones.

Las partes más importantes de la búsqueda son: poda de movimientos nulos, extensión de verificación y reducción de movimientos tardíos.

Su programa puede recorrer un largo, largo camino, ¡solo con estas simples técnicas!

Answer 8

Sé que una mejora de la que se habló en los cursos de AI en la universidad fue tener una gran base de datos de movimientos finales. Así que tener una base de datos precalculada para juegos con solo un pequeño número de figuras restantes. De modo que si alcanza un posicionamiento cercano al final en su búsqueda, detiene la búsqueda y toma un valor precalculado que mejora sus resultados de búsqueda, como una mayor profundización que puede hacer para movimientos importantes / críticos sin mucho tiempo de cálculo. Creo que también viene con un cambio en la heurística en un estado de juego tardío, pero no soy un jugador de ajedrez, por lo que no conozco la dinámica del final del juego.

Answer 9

Suponiendo que la "historia heurística" implica algún tipo de base de datos de movimientos pasados, un algoritmo de aprendizaje no le dará mucho más a menos que juegue muchos juegos contra el mismo jugador. Probablemente pueda lograr más clasificando a un jugador y ajustando la selección de movimientos de su base de datos histórica.

Answer 10

Tenga cuidado, hacer una búsqueda de juegos en un entorno con hilos puede ser un dolor real ( lo he intentado ). Se puede hacer, pero a partir de algunas búsquedas en la literatura que hice hace un tiempo, es extremadamente difícil obtener un aumento de la velocidad.

Answer 11

Respuesta tardía, pero esto puede ayudar a alguien:

Dadas todas las optimizaciones que mencionó, 1450 ELO es muy bajo. Mi conjetura es que algo está muy mal con su código. Tuviste:

1. ¿Escribió una rutina de perft y la pasó por un conjunto de posiciones? Todas las pruebas deben pasar, para que sepa que su generador de movimientos está libre de errores. Si no tiene esto, no tiene sentido hablar de ELO.

2. ¿Escribió una rutina mirrorBoard y corrió el código de evaluación a través de un conjunto de posiciones? El resultado debe ser el mismo para las posiciones normales y duplicadas, de lo contrario, tiene un error en su evaluación.

3. ¿Tienes una tabla hash (también conocida como tabla de transposición)? Si no, este es un deber. Esto ayudará a la hora de buscar y ordenar movimientos, dando una diferencia brutal en la velocidad.

4. ¿Cómo implementas el orden de mudanzas? Esto enlaza de nuevo al punto 3.

5. ¿Implementaste el protocolo UCI? ¿Su función de move parsing funciona correctamente? Tuve un error como este en mi motor:

     /* Parses a uci move string and return a Board object */
     Board parseUCIMoves(String moves)// e2e4 c7c5 g1f3 ...{
         //...
         if (someMove.equals("e1g1") || someMove.equals("e1c1"))
             //apply proper castle
        //...
    }

A veces, el motor se estrelló mientras jugaba una partida, y pensé que era la falla de la GUI, ya que todas las pruebas de perft estaban bien. Me tomó una semana encontrar el error por suerte. Entonces, prueba todo.

Para (1) puede buscar en cada posición hasta la profundidad 6. Uso un archivo con ~ 1000 posiciones. Consulte aquí https://chessprogramming.wikispaces.com/Perft

Para (2) solo necesita un archivo con millones de posiciones (solo la cadena FEN).

Teniendo en cuenta todo lo anterior y una función de evaluación muy básica (material, mesas de piezas cuadradas, peones pasados, seguridad de rey), debe jugarse en + -2000 ELO.

Answer 12

• Tabla de transposición
• Libro de apertura
• Bases de mesa de juego final
• Evaluación mejorada del tablero estático para nódulos foliares
• Bitboards para Raw Speed