¿Cómo implementar AI para damas / borradores?

Vi este juego de damas y me pregunté cómo se implementó la IA.

¿Cómo debo implementar una IA para las damas (borradores, dama, dama)? ¿Hay algún algoritmo conocido?

Muy gracias a todos. Me sorprende mucho ver esta publicación del blog tutorial del juego Tic Tac Toe .

Entonces, quiero el código de código abierto del algoritmo de juego de dama y la publicación de blog ... ¿Hay algún enlace útil o algún archivo de documento ...? Por favor hagamelo saber..

¡Oh, me encantan estos juegos!

Entonces, lo primero es lo primero, para que una computadora juegue un juego, necesita:

1. una estructura para trabajar
2. reglas para jugar
3. una condición de victoria para trabajar hacia

Abordemos esta pieza a la vez.

Estructura

Dado que el tablero es una cuadrícula de 8x8 (pero podría escalarse fácilmente), y cada espacio de cuadrícula puede existir solo en uno de los cinco estados, definamos esos estados:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Resumiblemente ENUM'd para:

[0, 1, 2, 3, 4]

Ahora que sabemos qué puede ser cada espacio, necesitamos alguna forma de representar todos los espacios, o el tablero si lo desea. Casi todos los lenguajes fuertes admitirán una matriz multidimensional (una matriz donde cada elemento es una matriz que contiene datos). Así que tome el siguiente código de holgura para definir nuestra matriz:

BOARD_ARRAY = array(8, 8)

Esto nos dará una matriz de 8 x 8 en la que podemos almacenar enteros (nuestras enumeraciones de antes):

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

¡Ahora ya puedes ver cómo esto empieza a parecer un tablero! Nunca he jugado la variante mencionada en el video de youtube, pero parece comenzar con 2 filas de piezas blancas una fila desde la parte inferior y 2 filas de piezas negras una fila desde la parte superior. Lo que significaría que cuando comenzamos un juego, nuestra matriz debería verse así:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(Recuerde que 2 representa 'BLACK_PIECE' y 1 representa 'WHITE_PIECE')

Así que ahora la computadora tiene una estructura para trabajar. Paso 1 completo!

Reglas

Imaginemos que tienes un tablero real configurado frente a ti, jugando contra un jugador maestro. Si trataras de mover una de sus piezas, recibirías una bofetada. Si intentaras mover una pieza de una manera que no podrías, recibirías una bofetada. Si trataste de hacer trampa bien ... tienes la idea. Pero el problema es que las computadoras no. Por lo tanto, nuestro trabajo es proporcionar reglas estrictas para jugar dentro.

Necesitamos crear una forma de verificar si un movimiento dado es 'legal'. Lo que significa que primero necesitamos alguna forma de representar un 'movimiento'. Una forma sería usar posiciones de matriz; Por ejemplo, para mover una pieza de [0, 0] a [0, 1], podríamos crear una función que actualizará el tablero dado ese movimiento. Así que de vuelta a la holgura:

MY_MOVE = array( [0, 0], [0, 1] )

Lo anterior representa una pieza, moviéndose un espacio hacia abajo desde la esquina superior del tablero (asumiendo que 0, 0 es la esquina superior izquierda). También puede notar que elegí usar una matriz multidimensional para el movimiento. Esto se debe a que las piezas teóricamente pueden moverse una gran cantidad de veces en un turno (para "saltar" otras piezas). Supongamos que en 0, 1 había una pieza de oponentes, lo que significa que aterrizaríamos en 0, 2:

MY_MOVE = array( [0, 0], [0, 2] )

Bastante simple eh. El programa debe comprender que si omitimos un espacio, estamos saltando otra pieza (o de lo contrario, es un movimiento ilegal y debería arrojar un error). Ahora saltemos dos piezas:

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Esto nos da una manera de describir cualquier movimiento en el tablero. ¡Hurra! Ahora, dado que no entiendo completamente las reglas del juego exacto en cuestión (aunque he jugado un poco de damas canadienses en mi día), la legalidad exacta del movimiento deberá ser definida por usted. Un buen flujo hasta este punto se vería así:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

Lo anterior supone que puede recorrer cada pieza para encontrar todos sus movimientos legales, luego, dada una colección de todos los movimientos legales, elija de alguna manera la mejor (estrategia aquí). El movimiento se aplica al tablero o arroja un error. Entonces el siguiente jugador toma su turno. ¡Entonces tenemos una IA que sabe cómo jugar! ¡Alegría! Siguiendo adelante.

Victorioso

Los juegos simples son maravillosos, porque ganar se define por un estado muy simple. ¿No hay piezas blancas en el tablero? Bueno, supongo que has ganado! Esto se implementa en el paso 2 cuando elegimos el mejor movimiento para acercarnos a la condición ganadora.

Para hacer una IA muy inteligente, podría mantener una base de datos que almacenara todos los tableros posibles como un estado, con cada movimiento posible de cada estado posible, para encontrar cadenas para ganar.

También puede crear estrategias, como: si hay una pieza que se SALTARÁ, guarde esa pieza o si una pieza puede saltar más de otra pieza, haga ese salto.

Eso debería darte un buen punto de partida, es solo un método de posibilidades literalmente ilimitadas. Teóricamente, podrías construir un robot gigante para dibujar con lápices de colores y luego realizar un análisis espectral en el dibujo para elegir movimientos ... pero no funcionaría muy bien o rápido. Esta manera ha funcionado en el pasado, y funcionó bien (: ¡Espero que ayude!

Algunas palabras sobre la implementación

Damas es lo que se conoce como un juego "resuelto", en el que podemos calcular cada movimiento sin incógnitas. Pero eso es todo un golpe de movimientos! Así que no hay forma de hacerlo todo manualmente ... si solo hubiera algunos ... oh, claro, somos programadores. bomba de puño

SQL es una herramienta maravillosa para almacenar todos estos movimientos aparentemente interminables. Para aquellos sin experiencia con SQL, mySQL es un servidor SQL gratuito (bastante fácil de usar) y de código abierto. SQL se usa para administrar bases de datos, como una hoja de cálculo con esteroides. También es capaz de almacenar grandes cantidades de datos y trabajar con ellos muy rápidamente.

Entonces, ¿cómo podemos usar esto? Como sabemos que si el tablero está en un estado exacto (cada pieza en una posición determinada) podemos calcular todos los movimientos disponibles y guardarlos. Por ejemplo:

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

Entonces, cuando la computadora necesita hacer un movimiento, simplemente busca el estado del tablero (almacenado como la clave principal) en la base de datos, y puede elegir el mejor movimiento (debería ser inmejorable) o uno de los otros movimientos para hacer un movimiento más amigable AI.

Genial, ahora construyamos esta base de datos. Primero necesitamos calcular cada estado del tablero. Lo que se puede hacer con un gran bucle desagradable, si alguien quiere pasar un tiempo y resolverlo, sería increíble. Mire la matriz como un número grande, luego cuente hacia arriba, excepto en la base 5 (0, 1, 2, 3, 4), y condicione que cada jugador solo pueda tener 16 piezas.

En este punto, deberíamos tener almacenados todos los estados del tablero y podemos calcular todos los movimientos posibles.

Una vez que se calculan todos los movimientos posibles, viene la parte divertida de encontrar los mejores movimientos posibles. Aquí es donde mi conocimiento comienza a fallar, y cosas como Minimax o A * comienzan a entrar en juego. Lo siento, no puedo ser de más ayuda en eso: /

En cualquier momento del juego, la cantidad de movimientos posibles para un jugador es bastante baja * (alrededor de 5), esto significa que pensar en algunos movimientos por delante, evaluar cada movimiento posible y seleccionar el mejor movimiento es factible.

Este enfoque se llama minimax (wikipedia) .

Para implementar minimax, necesitará una función de evaluación que devuelva una puntuación para un diseño de tablero y jugador determinados. Para los borradores, una implementación ingenua sería una función que devuelve un punto por cada pieza que el jugador tenga vivo.

Una visualización de un árbol de decisión minimax (del artículo de Wikipedia). En el lado izquierdo está el número de turno. Los nodos de las hojas tienen una puntuación evaluada que se retroalimenta en el árbol para tomar una decisión.

*Sin embargo, Drafts es el juego con el factor de ramificación más alto que se ha resuelto por completo .

La poda alfa-beta es un algoritmo de búsqueda que busca disminuir el número de nodos que evalúa el algoritmo minimax en su árbol de búsqueda. Es un algoritmo de búsqueda de adversarios que se usa comúnmente para jugar en máquinas de juegos de dos jugadores (Tic-tac-toe, Chess, Go, etc.). Se detiene completamente la evaluación de un movimiento cuando se ha encontrado al menos una posibilidad que demuestra que el movimiento es peor que un movimiento examinado previamente. Tales movimientos no necesitan ser evaluados más a fondo. Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que minimax, pero elimina las ramas que no pueden influir en la decisión final.