Ajedrez optimizaciones

Question

bien, así que 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 historia, búsqueda inactiva, evaluación de posición de peones, algunas extensiones de búsqueda) ¡y me he quedado sin ideas!

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

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

también, ¿sería significativo el cambio a una placa de bit? Actualmente estoy usando 0x88.

Answer 1

Suponiendo que "heurística histórica" ​​involucra 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 puedas lograr más clasificando a un jugador y ajustando la selección de movimientos desde tu base de datos histórica.

Answer 2

Ha pasado mucho tiempo desde que realicé cualquier programación en cualquier programa de ajedrez, pero en ese momento, las tablas de bit sí mejoraban realmente. Aparte de eso, no puedo darte mucho consejo. ¿Solo evalúas la posición de los peones? Algunos (ligeros) bonos por posición o movilidad de algunas piezas clave pueden estar en orden.

No estoy seguro de qué tipo de cosas que le gustaría que para aprender sin embargo ...

Answer 3

Sé que una mejora que se ha hablado en los cursos de AI en la universidad donde tener una enorme 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. De modo que si llega a un posicionamiento cercano en la búsqueda, detiene la búsqueda y toma un valor precalculado que mejora los resultados de búsqueda, como profundización adicional que puede realizar para movimientos importantes/críticos sin mucho gasto de tiempo de cálculo. Creo que también viene con un cambio en la heurística en un estado tardío del juego, pero no soy un jugador de ajedrez, así que no sé la dinámica del acabado del juego.

Answer 4

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

Si se está moviendo a bitboards, investigue en los archivos rec.games.chess.computer algunos de los antiguos comentarios del Dr. Robert Hyatts sobre Crafty (bastante seguro de que ya no publica más). O tome la última copia del his FTP y comience a cavar. Sin embargo, estoy bastante seguro de que sería un cambio significativo para ti.

Answer 5

• tabla de transposición
• Apertura libro
• End bases de mesa Juego
• mejorada estático Evaluation Board para la hoja de Nodos
• Bitboards de velocidad pura

Answer 6

Un aviso, que consiguen la búsqueda juego de la derecha en un entorno enhebrado puede ser un dolor real (I've tried it). Se puede hacer, pero de alguna búsqueda bibliográfica que hice hace un tiempo, es extremadamente difícil obtener ningún impulso de velocidad en absoluto.

Answer 7

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

Medición del rendimiento

Esencialmente se puede mejorar el rendimiento de dos maneras:

• Evaluar sus nodos más rápido
• búsqueda menos nodos para llegar a la misma respuesta

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

• Tiempo que tardó en buscar completo.
• Número de nodos buscó

Esto le permitirá hacer el seguimiento y evaluar los cambios. La mejor manera de abordar las pruebas es crear varios juegos guardados desde la posición de apertura, el medio juego y el final del juego. Registre el tiempo y la cantidad de nodos buscados en blanco y negro. Después de hacer cualquier cambio, generalmente realizo pruebas contra los juegos guardados anteriormente mencionados para ver si he realizado mejoras en las dos matrices anteriores: número de nodos buscados o velocidad.

Para complicar las cosas aún más, 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 un spread de aproximadamente 20%. Entonces, ¿ha mejorado su motor en un 10% -20% o simplemente ha variado la carga en su PC? ¿Cómo lo sabes? Para combatir esto, he agregado métodos que permitirán que mi motor juegue contra sí mismo, hará movimientos tanto para el blanco como para el negro. De esta forma puedes probar no solo la variación de tiempo sobre un movimiento, sino una serie de hasta 50 movimientos en el transcurso del juego. Si la última vez que el juego duró 10 minutos y ahora toma 9, probablemente haya mejorado su motor en un 10%. Ejecutar la prueba nuevamente debe confirmar esto.

Encontrar Rendimiento ganancias

Ahora que sabemos cómo medir mejoras de rendimiento permite discutir cómo identificar posibles mejoras de rendimiento.

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

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

• Hacer todo lo privado
• Lo que no se puede hacer privado, dar selló
• Hacer tantos métodos estáticos como posible.
• No hable de sus métodos, uno método largo es mejor que 4 más pequeños.
• 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.
• posible devolución de sus métodos desde .
• Las pilas son mejores que las listas
• Las matrices son mejores que las listas de pilas y .
• Si puede definir el tamaño de la lista antes de completarla.
• Fundir, boxear, quitar el boxeo es malo.

mayores ganancias de rendimiento:

que encuentran la generación de movimiento y el pedido es extremadamente importante. Sin embargo, aquí está el problema tal como lo veo. Si evalúa el puntaje de cada movimiento antes de ordenar y ejecutar Alpha Beta, podrá optimizar su orden de movimiento de modo que obtenga cortes Alpha Beta extremadamente rápidos. Esto se debe a que en su mayoría podrás probar la mejor jugada primero. Sin embargo, el tiempo que haya dedicado a evaluar cada movimiento se desperdiciará. Por ejemplo, puede haber evaluado el puntaje en 20 movimientos, ordenar los movimientos, probar los primeros 2 y haber recibido un punto de corte en el movimiento número 2. En teoría, el tiempo que ha gastado en los otros 18 movimientos se desperdició.

Por otro lado, si realiza una evaluación más ligera y mucho más rápida, digamos simplemente 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 gran evaluación en cada movimiento posible. En general, este enfoque es generalmente más rápido.

Encontrar este equilibrio perfecto entre tener suficiente información para un buen tipo y no hacer más trabajo en movimientos que no usará, le permitirá obtener grandes ganancias en su algoritmo de búsqueda. Además, si elige el enfoque de clasificación más pobre, primero deberá realizar una búsqueda más superficial, por ejemplo, pasar a la 3, ordenar su movimiento antes de entrar en la búsqueda más profunda (esto a menudo se denomina profundización iterativa). Esto mejorará significativamente su clasificación y le permitirá buscar muchos menos movimientos.

Answer 8

Respondiendo a una vieja pregunta.

Suponiendo que ya tiene una tabla de transposición en funcionamiento.

Reducción de movimiento tardío. Eso le dio a mi programa alrededor de 100 puntos de 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.

Aunque puede hacer que su motor de ajedrez tenga un mal rendimiento, un generador de movimiento rapidísimo en sí mismo no va a hacer que un programa sea bueno.

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

Y las partes más importantes, de lejos, de la evaluación son material, peones pasados, King Safety y Pawn Structure.

Las partes más importantes de la búsqueda son: Reducción de movimiento nulo, Verificación de extensión y Reducción de movimiento tardío.

Su programa puede recorrer un largo camino, en estas sencillas técnicas solamente!

Answer 9

Es una vieja pregunta, solo estaba buscando preguntas sobre el ajedrez y encontré esta sin respuesta. Bueno, puede que ahora no te sirva de nada, pero puede ser útil para otros usuarios.

No vi ninguna poda de movimiento nulo, tablas de transposición ... ¿las estás usando? Te darían un gran impulso ...

Una cosa que me dio un gran impulso fue la minimización de la bifurcación condicional ... Se pueden precalcular muchas cosas. Busque tales oportunidades.

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

No sugiero mover su código a la tabla de bits. Es simplemente demasiado trabajo. A pesar de que las bitboards podrían dar un impulso en las máquinas de 64 bits.

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

Answer 10

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 limitar la penalización a ti mismo por probar diferentes algoritmos. Facilite probar varias implementaciones de algoritmos entre sí. es decir, facilite la compilación de una versión PVS de su código y una versión NegaScout.

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

Answer 11

Good move ordering!

Una vieja pregunta, pero las mismas técnicas se aplican ahora que hace 5 años. ¿No estamos todos escribiendo nuestros propios motores de ajedrez, tengo mi propio llamado "Gambito noruego" que espero compita con otros motores Java en el CCRL. Yo, como muchos otros, utilizo las ideas de Stockfish, ya que está muy bien escrito y abierto. Su marco de prueba Fishtest y su comunidad también dan muchísimos buenos consejos. Vale la pena comparar sus puntajes de evaluación con lo que Stockfish obtiene ya que la evaluación es probablemente la mayor incógnita en la programación de ajedrez y Stockfish se ha alejado de muchas evaluaciones tradicionales que se han convertido en leyendas urbanas (como la bonificación del 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 menos movimientos de búsqueda que yo (debido a la orden de movimiento))

esenciales

La única cosa que se olvida fácilmente Mover un pedido es buen movimiento de pedidos. Para que el límite alfa 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. promociones Ordenar y buenas capturas por su aumento de
3. Killer mueve
4. movimientos que resultan en control sobre oponente
5. heurística historia
6. movimientos silenciosos - ordenar por valor PSQT

La clasificación debe hacerse según sea necesario, generalmente t es suficiente para ordenar las capturas y, a partir de ese momento, puede ejecutar la clasificación más costosa de cheques y PSQT solo si es necesario.

información sobre Java/C# y C/C++/Asamblea

técnicas de programación son los mismos para Java como en la excelente respuesta por Adam Berent que utiliza C#. Además de su lista, mencionaría evitar 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 byte e int en lugar de 64 bits de longitud. También he pasado por el camino de la reescritura a C/C++/Assembly y no tengo ninguna ganancia de rendimiento en absoluto. Utilicé el código de ensamblaje para instrucciones de escaneo de bits como LZCNT y POPCNT, pero luego 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 una optimización del trabajo mejor que la que puede hacer un compilador de C.

Answer 12

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

Teniendo en cuenta todas las optimizaciones que usted ha mencionado, 1450 ELO es muy baja. Supongo que algo está muy mal con tu código. lo hizo:

1. escribió un perft rutina y se lo pasó por un conjunto de posiciones? Todas las pruebas deben pasar, para que sepa que su generador de movimiento está libre de errores. Si no tiene esto, no tiene sentido hablar de ELO.

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

3. ¿Tiene una tabla hash (también conocida como tabla de transposición)? Si no, esto es obligatorio. Ayudará mientras busca y ordena movimientos, dando una diferencia brutal en la velocidad.

4. ¿Cómo se implementa el orden de movimientos? Esto vuelve al punto 3.

5. ¿Implementaste el protocolo UCI? ¿Su función move parsing funciona correctamente?Tenía 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 juega un partido, y pensé que era culpa interfaz gráfica de usuario, ya que todas las pruebas perft estaban bien. Me tomó una semana encontrar el error por suerte. Entonces, prueba todo.

Para (1) puede buscar todas las posiciones a profundidad 6. Utilizo 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).

Dado todo lo anterior y una función de evaluación muy básica (material, tablas cuadradas de pieza, peones pasados, seguridad de rey) debería jugar a + -2000 ELO.