¿El mejor enfoque para escribir un motor de ajedrez? [cerrado]

Soy un entusiasta del ajedrez y un programador. Recientemente decidí comenzar a hacer un motor de ajedrez utilizando mi ajedrez y mis conocimientos de programación. Así que aquí está mi pregunta:

¿Qué lenguaje (estoy familiarizado con Java, C ++ y Python) y metodología debería adaptar mientras escribo un motor de ajedrez?

Un poco de orientación sería muy apreciada.

Editar:

Entonces decidí hacerlo en JavaScript. Descargué esta interfaz de usuario de ajedrez desde github y ahora estoy listo. Mi primer paso sería escribir movimientos legales para ello. Entonces, ¿alguien puede señalarme en la dirección correcta? (Soy nuevo en jQuery pero tengo mucha experiencia en programación).

PD: No estoy tratando de hacer un motor muy eficiente (sé que es demasiado difícil), solo quiero familiarizarme con el proceso y aprender algunas técnicas nuevas en el camino.

Jugador de ajedrez con calificación de 2072 aquí. Hice este sitio web en JavaScript puro durante un fin de semana. No es un motor de ajedrez (lo diseñé para crear entretenidas posiciones de apertura como una especie de motor Chess960 perverso), pero es un punto de partida. El código fuente está aquí .

Hay muchas complicaciones involucradas en hacer una placa funcional. Éstos incluyen:

• Primero, descubrir cómo representar los movimientos legales básicos. Tienes que hacer cálculos matemáticos con las coordenadas iniciales y finales. Por ejemplo, con movimientos de torre, una de las coordenadas tiene que ser la misma antes y después. Con movimientos de caballero, la suma del valor absoluto de los cambios de coordenadas debe ser 3, y ambas coordenadas deben cambiar. Con los movimientos del obispo, la suma de las coordenadas permanece igual o ambas aumentan en la misma cantidad. Los peones son más complicados porque no solo tienes que descubrir si pueden mover dos cuadrados o uno (verifica la fila y el color en lugar de almacenar cuántos movimientos han hecho), sino que también tienes que lidiar con toda la captura en diagonal, mover -la cosa delantera.
• La captura es un desafío debido a los peones y cheques. No puedes decir que si una pieza se mueve al cuadrado de otra pieza, entonces es una captura. Después de todo, los peones no pueden moverse a la casilla de otra pieza para capturar: tienen su propia forma especial de capturar.
• Tienes que encontrar una manera eficiente de ver si las piezas enemigas están en el camino del movimiento de una pieza para decidir si es legal o no.
• El cheque es difícil de manejar. Después de cada movimiento, debes verificar todos los cuadrados a los que pueden ir las piezas enemigas y ver si uno de ellos involucra a tu rey y, de ser así, es un movimiento ilegal.
• Castling, en passant, promoción, estancamiento, sorteos forzados, repetición: ninguno de estos es trivial de manejar dada la magnitud del problema.

Todos los motores de ajedrez funcionan observando todos (posiblemente un subconjunto determinado heurísticamente) de los movimientos legales en una posición y evaluando los números para representar sus valores relativos haciendo esos movimientos y haciendo recursivamente lo mismo para las posiciones resultantes. Sus problemas gemelos aquí son

• Cómo almacenar estos datos de manera eficiente
• Cómo proceder con esta búsqueda recursiva: después de todo, no puede dejar que continúe para siempre, por lo que debe poner un límite y luego descubrir cómo diseñar su algoritmo para hacer la búsqueda más óptima y exhaustiva dentro de ese límite. Por ejemplo, desea asegurarse de que al menos presente alguna evaluación para cada posible movimiento inicial, pero también puede querer que pase más tiempo evaluando movimientos más prometedores en lugar de dar la misma cantidad de tiempo a cada movimiento.

Todo esto además de diseñar el algoritmo en primer lugar, sobre el cual hay mucha información disponible.

En cuanto a qué idioma elegir (aunque supongo que ya se decidió por JavaScript), creo que depende más de su objetivo que de cualquier otra cosa. Quería hacer el mío en línea (y mejorar en JavaScript), así que JavaScript fue mi elección. Sin embargo, cualquier lenguaje de programación orientado a objetos funcionará.

Una vez que se sienta cómodo con lo que está haciendo, los siguientes recursos probablemente serán de gran ayuda:

• Wiki de programación de ajedrez
• Foro de programación de ajedrez
• StockFish en Github

¡Buena suerte!

El problema con el "programa de ajedrez" como concepto es que hay muchas piezas que pueden absorber mucho tiempo y no necesariamente te interesan en este momento. Puede pasar años simplemente trabajando en gráficos, o una búsqueda alfa-beta, o una visualización para ayudar a desarrollar para el motor de búsqueda, o ... bueno, hay muchas piezas.

Recomiendo encontrar un programa de ajedrez de código abierto (debe haber muchos) y comenzar a mejorar las partes que más le interesan. Eventualmente puede reemplazar todo el programa, una función a la vez, o puede aprender lo suficiente y estar motivado para tirarlo y diseñar su propio programa desde cero. En cualquier caso, la clave es comenzar "ligero" y aprender las cuerdas antes de intentar diseñar un programa completo.

Si está familiarizado con las reglas del ajedrez, un buen punto de partida sobre las técnicas básicas es http://www.frayn.net/beowulf/theory.html. Una amplia colección de materiales y enlaces que puede encontrar aquí: http: // chessprogramming .wikispaces.com / Y tercero: aprende del código de otros. Echa un vistazo a las fuentes de Crafty . Es el principal motor de código abierto. Es muy importante pensar en casos de prueba, para ver si realiza mejoras: comience, por ejemplo, con algunas posiciones simples y sencillas de final de juego con 3 o 4 cifras.

Como se mencionó, no hay nada terriblemente difícil en construir un motor de ajedrez. Tal vez, debería concentrarse en cómo desea usar y (potencialmente) implementar esta aplicación, ya que esto probablemente determinará su elección de idioma.

Si esto es solo un ejercicio divertido, puede codificarlo en Javascript e implementarlo como una página web. Si nunca quieres convertirlo en un juego de ajedrez experto, al menos otros podrán jugar con él y su código fuente.

Si desea aprender una tecnología en particular al mismo tiempo, diga WPF, entonces esta podría ser una buena manera de matar dos pájaros de un tiro. MVVM podría ser excesivo para esta aplicación, pero al menos lo aprenderías.

Si desea apuntar a dispositivos Android, Java sería una buena opción. Del mismo modo, Objective-C para dispositivos iOS.

Largo y corto, la elección del idioma no existe en el vacío.

Supongo que ya conoce el concepto de Min-Max, árboles y podas, heurística y otros conceptos básicos, y lo que escribo aquí son solo algunos detalles que podrían haberse subestimado.

Yo, junto con un amigo, escribí nuestro propio motor de ajedrez a veces. Comparto algunos problemas e ideas que tuvimos y espero que les sean útiles.

Como ambos éramos programadores de Java, nuestro lenguaje se convirtió en Java y comenzamos con un enfoque orientado a objetos. Las piezas eran objetos, el tablero era objeto, los archivos y las filas (filas y columnas en la literatura de ajedrez) eran objetos. Y esto estaba mal. La sobrecarga era masiva y el programa estaba luchando para ir más allá de 2 movimientos (4 capas) en el árbol de búsqueda.

Entonces, con un poco de búsqueda, terminamos con una idea brillante (¡aunque no la nuestra!): Representar las piezas y el tablero como enteros largos (64 bits). Esto tiene sentido porque un tablero de ajedrez tiene 64 casillas. El resto fueron operaciones poco sabias (ejecutando muy cerca de cpu = extremadamente rápido). Por ejemplo, considere un entero binario de 64 bits en el que los que están presentando los cuadrados en el tablero que su pieza puede atacar. Ahora, si ejecuta un "Y" lógico entre dos números como este, un resultado distinto de cero indica que tiene un cuadrado con atacantes. Hay varias formas de presentar el tablero de ajedrez y las piezas, así que:

1 - Decide sobre la presentación de tu junta

Entonces necesitas y abrir la base de datos. La apertura del ajedrez está resuelta de alguna manera y es muy recomendable tener un libro de apertura. En este caso, tienes mucho tiempo extra en los juegos de blitz.

2 - Búscate un libro de apertura.

Hicimos esto, pero aún estábamos lejos de ser buenos:

3 - Un buen motor de ajedrez debería poder ver 6 movimientos (12 capas) por delante.

Entonces, lo que hicimos entonces fue usar el tiempo muerto (si se trata de un motor humano frente a un ordenador).

4 - Usa el tiempo cuando el oponente está pensando en crear algunos niveles de tu árbol.

Y aún así estábamos muy lejos de 12 capas. ¡Por más estudio, descubrimos algunos trucos! Por ejemplo, se sugirió omitir una capa del árbol y comenzar desde la siguiente capa (como si no hubiera oponente). La idea es que si un movimiento es extremadamente idiota, ¿por qué perder el tiempo y ver cuáles son las respuestas de los oponentes a ese movimiento? Sin embargo, un buen motor debería ser capaz de distinguir entre un movimiento idiota y un sacrificio de reina genio.

5 - Aprende los trucos de programación para este problema específico (ajedrez).

Mi amigo y yo, en este estado, todavía éramos malos: / Lo que pudimos hacer, y lo hicimos parcialmente, fue salvar las posiciones calculadas. Si calcula una posición, ¡guárdela para el futuro! Lo mismo ocurre con los bucles en el árbol de búsqueda. El punto era guardar / recuperar eficientemente:

6 - Guarde los datos que genera ... ¡de manera eficiente!

y finalmente:

7 - Código con la máxima optimización.

Este problema es extremadamente costoso tanto en tiempo de CPU como en memoria. Es muy importante escribir su código de manera muy eficiente. Recuerde que estamos hablando del factor de ramificación de 35. Esto significa que un "si" inútil en algún lugar de su heurística puede convertirse en un 3.3792205e+18"si" inútil en algún lugar de su árbol de búsqueda.

La programación de ajedrez es un desafío muy interesante y es el momento en que puedes poner tus capacidades de programación en una prueba seria. Hay algunos puntos más que puedo sugerir, pero estoy seguro de que los descubrirá usted mismo. ¡Hay muchos más puntos que no sé, pero puedes encontrarlos en Internet!

¡Buena suerte y diviertete!

ps No conozco muy bien javascript, pero algo me dice en base a la dificultad del problema, tal vez, teniendo en cuenta todo lo que C ++ puede ofrecer, sería mejor soltar javascript y hacerlo en C ++.

Según su edición, está en la etapa de definir movimientos 'legales'.

Hay dos formas de describir movimientos en el ajedrez. Notación descriptiva y notación algebraica . Lo que probablemente desee es una función que tome la pieza, la posición inicial y la posición final como parámetros. p.ej. Knight de QN1 a QB2 no es válido, pero Knight de QN1 a Q2 es válido. Pensando en ello, la notación algebraica puede ser más simple debido a la capacidad de calcular fácilmente el posicionamiento 'relativo'.

Para asegurarme de que está escribiendo la cantidad mínima de código requerida, primero comenzaría escribiendo pruebas para esa función . Si está utilizando la notación algebraica, probablemente no necesite una prueba por pieza / inicio / final. Haga que cada prueba funcione y refactorice la duplicación antes de pasar al siguiente 'movimiento'. Su código terminará más limpio.

Una vez que haya cubierto suficientemente los movimientos legales e ilegales para cada pieza, comenzaría a agregar cheques para otras variables (como mover un Rey a las condiciones de 'chequeo' y 'mate').

Recomiendo qunit para pruebas unitarias y jazmín para pruebas de comportamiento en JavaScript.

De hecho, he escrito un motor de ajedrez. Prepárese para un regalo y una pesadilla. Cuando mis amigos y yo lo hicimos, fue en un concurso de programación cronometrado y el lenguaje con el que decidimos ir era Java. Siento que Java o C es su mejor opción, pero veo que ha decidido utilizar Javascript. Realmente no puedo tocarlo porque no estoy familiarizado con él.

El principal problema aquí será que hay tantos escenarios de movimiento / ganar con cada pieza que necesita tener en cuenta, por lo que le recomendaría que escriba todas estas situaciones posibles para cada pieza antes de comenzar a codificar. Simplemente saltar sin planificación convertirá este divertido proyecto en una tarea repetitiva. Pero eso es realmente lo principal. Solo planifique primero fuera del código y asegúrese de obtener cada escenario para una pieza a la vez.

Buena suerte

Para la parte del juego de toma de decisiones de los jugadores de computadora, no puedo recomendar lo suficiente el libro "Inteligencia artificial: un enfoque moderno" (sitio web del libro http://aima.cs.berkeley.edu/ ). Dependiendo de sus antecedentes en matemáticas (la teoría de grafos ayuda) puede ser un poco alto, pero está escrito de manera tan simple como puede ser este material académico y contiene una visión general muy actualizada (y cierta profundidad) de técnicas para hacer que los programas decidan las cosas.

Le indicará cosas como establecer un objetivo (es decir, jaque mate o nulo), evaluar qué tan cerca está un estado particular (diseño de tablero) de ese objetivo, cómo generar los diferentes estados posibles siguientes a partir del actual, y cómo atravesar lo que es un inmenso espacio problemático.

Una cosa que podría ayudar en el diseño de un algoritmo de IA es descubrir cómo decidir qué movimiento jugar después como si tuvieras todo el tiempo del mundo, comenzando desde una situación muy cercana a un juego ganado. Lo optimiza para que encuentre una solución en un período de tiempo razonable (horas), luego encuentra formas de elegir un camino ganador a pesar de que aún no ha explorado todos los resultados, para que realmente pueda interrumpir el "pensamiento" para Un giro de tiempo.

Solo entonces consideraría optimizar la representación de para hacer los cálculos individuales más rápidos, como usar números enteros largos como se sugirió. No importa qué tan rápido pueda hacer una sola comparación, si la forma en que atraviesa el espacio del problema no tiene una buena heurística, tomará años hacerlo.

Puedes ir realmente como quieras, pero estos son mis pensamientos sobre el tema:

Usaría Java, ya que eso le permite ser de muy alto nivel y tener bibliotecas de interfaz de usuario (AWT, Swing) a su disposición directa. Puede utilizar un enfoque orientado a objetos para modelar el tablero de ajedrez y las piezas. Otros objetos podrían representar el historial de movimientos y la puntuación. Incluso los jugadores podrían ser objetos, y luego, en el futuro, podría extender su Playerclase para proporcionar un reproductor de computadora inteligente artificial.

Es posible que desee echar un vistazo a model-view-controller (MVC), ya que es un enfoque muy agradable en este caso para vincular los objetos de su modelo (modelo de dominio) a la interfaz de usuario (view) y permitir que el usuario manipule modelo (a través del controlador).

También es posible que desee aplicar el desarrollo basado en pruebas , que no solo garantiza que todos los métodos se comporten de la manera esperada, sino que también lo obliga a escribir código modular comprobable.

Las reglas del ajedrez en sí son bastante simples. Solo necesita poder crear una matriz (matriz bidimensional) para el tablero, y encontrar una manera de codificar los conceptos de las piezas, las reglas de movimiento para cada pieza, la validación de que un movimiento es legal y las condiciones que indican El final del juego. Nada particularmente difícil sobre nada de eso. Debería usar el idioma con el que esté más familiarizado.

Ahora, si quieres hacer una IA que juegue ajedrez y que tome el papel de uno de los jugadores, ahí es donde las cosas se ponen difíciles. Pero nuevamente, la elección del idioma no es el mayor problema aquí; comprender los principios de IA involucrados es. Ese será un factor mucho más importante.

(Dicho esto, este tipo de toma de decisiones puede ser extremadamente computacionalmente intensivo, y probablemente querrás usar algo que se compile en código nativo en lugar de un lenguaje de scripting. Y C ++ es una muy mala elección, no porque no esté bien adecuado para este problema, pero simplemente porque es un lenguaje muy malo en general, y tratar de implementar cosas complejas en él es una buena forma de codificar todo tipo de dolores de cabeza por ti mismo).