miércoles, 15 de junio de 2016

Primera IA que juega a "Blokus"

Descarga aquí. (Código incluido y comentado)
Blokus es un juego de mesa que me regalaron cuando era niño :')
El objetivo del juego es conseguir colocar mas cuadraditos en el tablero que tu adversario. Para ello debes colocar las fichas tipo pentomino de forma que tus fichas estén conectadas por las esquinas sin llegar a tocarse nunca.

Acordándome por casualidad decidí buscar en internet algún sitio donde jugar contra el ordenador a este juego, y mi sorpresa fue que no había ninguno. Lo que si que encontré son sitios que hay (o habían) donde se podía jugar online. En la imagen muestro un juego de PS3 para jugar únicamente online a Blokus.

Y entonces pensé... ¿Tan difícil debe ser crear una IA que juegue a este juego?
Así que me puse a crear una versión Javascript del juego para intentarlo :')

Creando la IA:
Al principio tenia en mente crear una función heurística y usar minimax, pero al final viendo que minimax sería bastante impreciso y desperdiciaría bastante tiempo de computación, vi que usando esta misma heurística de forma voraz, la IA podia generar movimientos muy buenos (Sin ser invencible, lo cual creo es bastante importante) y lo mas importante de todo... ¡Sería muy, muy rápido!
¡Y he aquí el resultado! A pesar de estar hecho en javascript, la IA no tarda ni 0.1 segundos en pensar en mi ordenador. Y va rápido incluso en mi antiguo Iphone 4.

La heurística funciona teniendo en cuenta tres parámetros:

-Expansión en el tablero --> x1
-Incrementar el numero de movimientos posibles --> x1
-P*tear al adversario :') --> x10

Esto quiere decir que la IA le da la misma importancia a expandirse en el tablero que a incrementar su numero de movimientos, y ademas tiene especial interés en que perdamos :')
Lo mejor de todo es que estos tres parámetros se pueden redefinir. Ej: podemos modificarlo de forma que el adversario quiera expandirse "Sin hacernos daño" lo cual seria un poco raro en un jugador real. Solo habría que cambiar el valor de los parámetros.
¿Que os ha parecido?

No hay comentarios:

Publicar un comentario