machine learning - jugar - ¿Qué tan difícil es implementar un motor de ajedrez?
alphazero vs stockfish (13)
Me pregunto qué tan difícil sería implementar un motor de ajedrez . ¿Ya hay implementaciones de código abierto?
Parece que necesitarías una función de puntuación para una constelación de tablero dada, y una manera muy rápida de explorar varias constelaciones probables de tablero en el futuro. Explorar todos los movimientos futuros posibles es, por supuesto, imposible, por lo que uno podría seguir con entusiasmo los movimientos más prometedores, o utilizar técnicas aproximadas como el recocido simulado para seguir probables movimientos de forma probabilística.
¿Cree que está dentro del alcance de un proyecto de estudiante de posgrado de aprendizaje automático ? ¿Suponiendo que hubiera una implementación de código abierto que los estudiantes pudieran usar, que hace las cosas básicas como devolver los próximos movimientos posibles para una figura determinada? ¿Probablemente demasiado duro?
Sería un proyecto divertido tener diferentes equipos trabajando en los motores de ajedrez y luego dejarlos jugar unos contra otros ...
¡Todos dependen del objetivo que arregles sobre la IA del juego! si es un juego de 2 jugadores ... ¡fácil! Pero la IA es bastante difícil ... ¡Bien, la fuente abierta bien conocida es GNU Chess!
Algunos algoritmos: http://www.vclcomponents.com/s/0__/source_code_genetic_algorithm_chess
¡Aquí hay una wiki de programación de ajedrez !
Cada año en mi universidad, el curso de Introducción a la IA (3er curso) requiere que los estudiantes creen un programa de ajedrez desde cero junto con un documento, y cubrimos un capítulo sobre búsqueda adversarial en una conferencia para que los estudiantes tengan suficiente conocimiento para hacerlo. Para nosotros, el proyecto se puede hacer solo o con otro (obviamente esperando un mejor programa si se hace con un socio, como capas más profundas, etc.). Debido a que el curso de Computer Graphics es también un curso de tercer año, los estudiantes pueden combinar el proyecto final de eso con el proyecto final del curso de AI.
Como estoy en mi tercer año y tomo ambos cursos (que ahora terminaron en el primer semestre), me uní a un amigo que también está en ambos cursos y hemos estado trabajando en el programa desde el final de nuestro curso. exámenes (que fue alrededor del 21 de diciembre) y vence el 11 de enero.
Es completamente factible dentro de un mes (especialmente como un proyecto de posgrado). Estamos haciendo un programa de ajedrez 3D por lo que requiere más trabajo que solo un motor de ajedrez, por supuesto. Las partes más difíciles serán decidir sobre una representación de la junta, implementar todas las reglas (en passant, enroque, promoción, etc.), crear una función heurística, y el árbol del juego (que generalmente se realiza con poda alfa-beta).
Aquí está el sitio que estamos usando para documentar el progreso, y luego alojar el código y el documento una vez que hayamos terminado (está un poco vacío en este momento). http://sites.google.com/site/chessatbrock/
Depende del nivel de fortaleza que tengas como objetivo y tus habilidades de programación. Asumiendo que usted sea un programador experimentado , esta es mi opinión (conozco muchos motores, pero nunca he codificado uno):
* Un motor muy simple, que puede vencer a un principiante / aficionado (ELO 1200-1600): un montón de código, pero fácil.
* Un motor que puede vencer a un ''jugador de club'' (ELO 1800-2000): comienza a ser difícil, necesitará abrir libros, optimizaciones y una inteligencia artificial sólida.
* Un motor que puede vencer a un maestro: difícil, necesitarás algunos años de experiencia previa
* Un motor superior (como Rybka, Houdini, Stockfish, Hiarcs), que puede vencer a cualquier ser humano en la tierra el 99% del tiempo: este es un gran esfuerzo, necesitarás MUCHA paciencia y años de experiencia.
¡Así es como lo veo!
En mi curso de AI de pregrado, pasamos medio semestre creando varios motores de ajedrez y probándolos usando XBoard o WinBoard. Luego, al final del semestre, tuvimos un torneo en el que los motores de ajedrez de los estudiantes competían entre sí en XBoard. En general, funcionó bastante bien.
La interfaz con XBoard es bastante fácil si no recuerdo mal. Aquí hay algunos enlaces.
http://www.gnu.org/software/xboard/
interfaz para XBoard
http://www.tim-mann.org/xboard/engine-intf.html
No estoy seguro de si esto te da todo lo que deseas, creo que nuestros motores de ajedrez tuvieron que crear sus propias representaciones de tablero y crear movimientos por su cuenta, pero al menos te da un tablero gráfico que conoce las reglas y tiene una GUI.
Esto es probablemente demasiado simple, pero aún así, hay lecciones interesantes que aprender: te presento el juego de ajedrez ZX81
Hacer una buena es difícil, pero probablemente esté en el nivel adecuado para un proyecto de posgrado (cuando tomé mi licenciatura en Ciencias de la Computación, un amigo mío escribió un motor de ajedrez para su disertación final).
Y sí, hay Open Source, el principal contendiente es GNU Chess , que es muy respetado.
Hicimos una IA de mancala seguida por una IA de ajedrez en Algoritmos y Estructuras de datos (CS de segundo año).
Sin embargo, el profesor proporcionó grandes partes del motor de ajedrez, y tuvimos que hacer cosas como mejorar la función de decisión, implementar el jaque mate y otras cosas.
Necesitas generar todos los movimientos de vaild para el estado dado. Luego, para cada posibilidad, deberías verificar los movimientos posibles de los oponentes. Si hay al menos uno de ellos que empeora su posición, entonces no debe seguir esa rama. Para hacer esto, necesitas algún tipo de puntuación para determinar qué tan bien estás. El ajedrez ya tiene algunas reglas sobre qué unidad vale la cantidad de puntos. Es suficiente mirar hacia adelante solo unos pocos pasos como este. Vencer al programa seguirá siendo un desafío.
Esto, por supuesto, está lejos de ser perfecto: los jugadores reales pueden sacrificar algunas unidades para lograr objetivos a largo plazo. Este algoritmo no hará eso.
No puedo responder a tu pregunta, pero puedo responder a tu comentario final
"Sería un proyecto divertido tener diferentes equipos trabajando en los motores de ajedrez y luego dejarlos jugar unos contra otros ..."
Esto ya está hecho en el servidor de ajedrez de FICS . Te sugiero que inicies sesión allí (necesita telnet) y también revises la documentación, probablemente puedas ponerte en contacto con personas que puedan darte pistas específicas sobre sus chessbots.
Pasé el último año construyendo mi propio motor de ajedrez en C #. No fue tan difícil. Durante mi trabajo cometí errores. Descubrí que la información en Internet simplemente no se presentaba claramente, y gran parte simplemente se copiaba de otros sitios.
Con el fin de hacer la vida más fácil para otra persona que está pasando por este proceso, he estado documentando el desarrollo de mi motor de ajedrez y publiqué gran parte del código fuente en mi blog:
Incluso he creado un Kit de desarrollo de juegos de ajedrez que lo ayudará a comenzar a desarrollar su propio motor de ajedrez, que contiene:
- Todo el código necesario para representar un tablero de ajedrez y piezas de ajedrez
- Código relacionado con la validación del movimiento de la pieza de ajedrez
- Interfaz gráfica de usuario que muestra la posición del ajedrez y le permite mover las piezas por todo el tablero
Mi sitio está básicamente dedicado a personas como usted; personas que quieren comenzar a construir su propio motor de ajedrez.
Sí, esto está definitivamente dentro del alcance de un proyecto de estudiante. Aquí hay algunos enlaces de mi archivo para que comiences:
- Esta es una wiki de programación de ajedrez útil.
- Esta es una introducción simple a la programación de ajedrez.
- Esta es una introducción más avanzada .
- Este es un buen análisis de MTD , un sofisticado algoritmo de búsqueda.
- Esta es una buena guía para la validación de la generación de movimiento .
- Esto describe la arquitectura básica de un programa de ajedrez .
- Esta es mucha información buena sobre el programa de ajedrez Dark Thought .
- Estas son más notas sobre programación de ajedrez .
- Una introducción razonable a los bitboards rotados .
- Una introducción razonable a los magic bitboards .
- Aquí hay un informe anterior de 2 estudiantes que escribieron un programa de ajedrez .
- Finalmente, aquí está la versión de Wikipedia sobre ajedrez de computadora .
Un motor de ajedrez razonable en las PC modernas es ciertamente factible, especialmente si tienes la edad suficiente para recordar que hubo muchos programas de ajedrez que utilizaron solo unos pocos K de memoria en máquinas de 8 bits de 1 y 2 MHz que podían jugar bastante bien. Puedes usar un motor de ajedrez en un lenguaje interpretado hoy en día y sacarte los pantalones de un programador 6502 o Z80 que codifica sus cosas más rápidas.
Empecé a trabajar con Dan Spracklen, quien hizo el Sargon original en 1978 con su esposa Kathleen. El hermano de Kathleen hizo el puerto a Apple II, y trabajé con él y con su hijo. (En el momento en que trabajé con estos tipos, el negocio de ajedrez por consumidor fue hecho. Recuerdo a un tipo que sacó los juegos de Atari ST y Amiga Chess y realmente no había mucho mercado para ellos en ese momento).
" Computer Gamesmanship " es una excelente introducción a la programación de ajedrez ya que los aficionados lo realizaron en 1983. Todavía es un placer leerlo. Cubre lo bueno: alfa-beta, minimax, etc.
Es un libro lo suficientemente bueno que puede comenzar allí y luego aprender sobre los avances realizados desde entonces.
Crafty es uno de los principales motores de ajedrez y fuente completamente abierta. Sin embargo, le desalentaría a usarlo para un proyecto de estudiante escrito en C, muy complejo y muy difícil de entender porque está muy optimizado.
Con fines educativos, recomendaría echar un vistazo al sitio de Adam Berents, donde describe el proceso por el que pasó cuando implementó un motor de ajedrez en C #. El código fuente está disponible también, por supuesto. Es un excelente punto para comenzar, en mi opinión.