Elena, miembro de este staff, nos ha hecho el favor de crear este artículo porque conoce a la perfección este tema.
Para gomoku, ya se ha encontrado la estrategia ganadora. Vea este artículo: L. Victor Allis, HJ van den Herik, MPH Huntjens. Búsqueda de Go-Moku y Threat-Space. Me ayudó mucho cuando estaba escribiendo mi propio programa. De esta manera podrás escribir un programa que sea muy bueno para atacar al oponente y encontrar combinaciones ganadoras.
La estrategia tradicional y bastante efectiva para escribir IA para tales juegos es la típica estrategia de búsqueda de árboles. Es decir, cada estado del tablero forma un nodo en un gráfico, y se coloca un borde dirigido entre cada nodo y los estados que pueden resultar de un solo movimiento. De esta forma se construye un árbol con la placa raíz como un nodo vacío. Luego, atraviesa el árbol de alguna manera inteligente para encontrar lo que parece un estado “bueno”. Un estado “bueno” generalmente se mide mediante una función de evaluación que utiliza algunas heurísticas inteligentes. Obviamente, no desea visitar todos los nodos del árbol, ¡eso sería mucho trabajo! Solo quieres algo inteligente.
Puede agregar un juego temprano precalculado y un juego final para acelerar esos escenarios y luego confiar en una heurística de recorrido de árbol bien optimizada para la mitad del juego.
El nombre real de tales algoritmos de recorrido de árbol es el algoritmo “Minimax”. Búscalo en Wikipedia y verás mucho material bastante decente. Hay algunas formas de aumentar la eficiencia del algoritmo, la más notable de las cuales es la poda alfa-beta, así que asegúrese de echarle un vistazo. Es posible que desee echar un vistazo a las heurísticas de conectar cuatro y decidir cómo puede aplicarlas a su juego. Por ejemplo, una buena heurística para la evaluación de los estados de la junta sería contar el número de 2, 3 y 4 carreras continuables y ponderarlas en la puntuación. (por ejemplo, cada 2 carreras valdría 1 punto, cada 3 carreras valdría 10 puntos y cada 4 carreras valdría 1000 puntos)
Otra estrategia de optimización es desarrollar una heurística que priorice dónde debe buscar más el algoritmo minimax, generalmente estimando algún tipo de certeza de la función de evaluación de la placa.
Con esta estrategia, debería poder obtener una IA no tan estúpida en la misma cantidad de tiempo. Sin embargo, construir una IA realmente buena requiere mucho esfuerzo, incluso en este tipo de juegos “simples”, y aún puede llevar más de 10 segundos o más eliminar los movimientos inteligentes. Por otro lado, hay algunos trucos de programación inteligentes, como recorridos previos a la computación a través del árbol mientras el oponente humano está ocupado pensando. Oye, los humanos pueden pensar mientras la computadora lo hace. ¡Justo es justo!
He estado intentando crear un algoritmo para el mismo programa durante un tiempo.
Por supuesto, tienes razón en que lo primero que debe hacer tu programa es comprobar si hay una manera de formar un 5 y ganar. Y si no lo hay, lo siguiente debería ser comprobar si Tu oponente puede hacer eso, y si es así, entonces la defensa.
¿Cuánto has jugado a gomoku tú mismo? ¿Qué tan buen conocimiento tienes de los conceptos básicos?
Ok, el siguiente paso es pensar: ¿cómo podemos llegar a las posiciones en las que podemos ganar? Evidentemente, para ganar debemos tener cuatro seguidos. Pero si formamos cuatro seguidos como este:
__________
____XOOOO_
__________
Entonces el oponente puede cerrarlo.
Pero si formamos “cuatro abiertos”, así:
__________
____OOOO__
__________
Entonces el oponente no puede cerrar ambos lados y puedes ganar. Así que formar un cuatro abierto es una forma de ganar. Ahora viene la pregunta: ¿cómo podemos formar un cuatro abierto? Seguramente, si formamos “tres abiertos”, así:
__________
____OOO___
__________
Entonces el oponente puede bloquearnos:
___________
____XOOO___
___________
y estamos de vuelta al principio.
Para ganar, podemos formar dos tres abiertos al mismo tiempo:
____________
____OOO_____
_____O______
____O_______
Ahora, si el oponente bloquea a uno de ellos, podemos usar el otro para formar cuatro abiertos:
____________
_______O____
___XOOO_____
_____O______
____O_______
____________
y gana:
________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________
En términos de gomoku, esto se llama 3×3, si haces dos tres abiertos al mismo tiempo.
Tenga en cuenta que ambos tres deben estar abiertos: ¿puede entender por qué?
También hay otras formas de ganar:
4×3: ¿Ves el movimiento ganador y por qué está ganando?
____________
__XOOO______
__XXXO______
____OX______
____________
4×4: ¿Ves el movimiento ganador?
____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________
Estos son solo los conceptos básicos del juego. Conocer las tácticas te ayuda a pensar en cómo construir la IA, para que puedas codificar los principios.
Naturalmente, esto es solo el comienzo. Le agradecería si pudiera intentar implementar esto y luego enviarme sus comentarios.
He estado intentando escribir el programa en Java. ¿Te gustaría ver el código que he hecho para que puedas probarlo? Todavía no es muy bueno, pero podrías obtener nuevas ideas a partir de ahí. Aunque los comentarios y los nombres de las variables están escritos en estonio, puede ser muy difícil de entender. 🙁
Si guardas algún titubeo y forma de beneficiar nuestro crónica puedes escribir una interpretación y con placer lo observaremos.