Un enfoque de puntuación para los oponentes de la computadora que necesita equilibrio

Esta pregunta trata sobre un enfoque para los oponentes informáticos que he creado y que actualmente se está utilizando o se planea utilizar en varios juegos de computadora.

Antecedentes

El año pasado, cuando traté de mejorar a un oponente de la computadora para un juego llamado "Buscaminas" (descripción breve: una versión multijugador por turnos de Minesweeper donde tienes que tomar más minas que tu oponente) , cambié fuertemente la forma en que funcionaban mis algoritmos . En lugar de usar un enfoque como if-else-if-else, estoy usando un conjunto de "anotadores" con pesos específicos para determinar cuál es el mejor movimiento.

Puedes pensar que para un juego como Minesweeper Flags, solo se trata de hacer movimientos que te den la mayor probabilidad de tomar una mina, pero no es tan simple. El movimiento que hará la computadora generalmente depende de varias características para ese movimiento específico en el estado actual del juego. Ejemplos de características:

• ¿Cuál es la probabilidad de que este movimiento marque una mina?
• ¿Cuál es la probabilidad de revelar algo a mi oponente aquí?

Descripción del sistema.

El sistema básicamente funciona así:

1. "Pre-goleadores": se realiza un preanálisis para el estado actual del juego (en términos de Banderas del Buscaminas, esto generalmente es: Calcular todas las probabilidades)
2. "Goleadores": se les pide a un conjunto de goleadores normales que determinen el puntaje para cada posible movimiento, cada anotador aplica los puntajes de acuerdo con sus propios criterios. Los anotadores pueden verificar los resultados del preanálisis realizado.
3. Las puntuaciones calculadas en el paso anterior se suman y se configura como la puntuación de un movimiento.
4. Los movimientos se ordenan de acuerdo con su puntaje y se clasifican para que todos los movimientos con el mismo puntaje obtengan el mismo rango.
5. "Post-anotadores": el resultado de lo anterior se puede enviar a "Post-anotadores" que tienen la posibilidad de modificar los puntajes de cualquier campo de la forma que deseen, de acuerdo con las propias reglas del post anotador.

Al combinar un grupo de pre-anotadores, anotadores (con sus pesos) y post-anotadores, se convierte en lo que yo llamo una configuración de puntaje .

Resultado de ejemplo

Este es un ejemplo de puntajes que se han aplicado a las banderas de Buscaminas. Este es el mapa que se calificó:

Y esta es la salida de una configuración de puntuación real. Muestra el rango de los movimientos posibles, donde 1 es el mejor rango y se ha resaltado en blanco:

Gracias a haber escrito un código altamente flexible, este enfoque de IA también se puede insertar en otros juegos.

Ventajas y desventajas

A continuación se presentan algunas ventajas y desventajas de este sistema que puedo pensar en mí mismo.

Ventajas

• Es muy fácil crear muchas configuraciones diferentes para las IA.
• Es posible usarlo con algoritmos genéticos: cada anotador tiene un peso asociado, el peso puede convertirse en el gen.
• Usando algunas herramientas, es posible verificar por qué se realizó un movimiento específico y qué anotadores fueron los principales responsables de ese movimiento
• Usando herramientas, es posible crear un mapa del puntaje general / rango de movimientos posibles (como la captura de pantalla anterior)
• Al aplicar puntajes a la forma en que juega el humano, es posible crear un "#AI_Mirror" que intenta hacer movimientos que cree que el humano haría

Desventajas

• Puede ser extremadamente difícil ajustar una configuración de puntuación "correctamente", para que la IA juegue lo mejor posible.

Preguntas

• ¿El sistema que he construido aquí es ampliamente conocido en el mundo de la IA? ¿Cómo se llamaría en términos reales de IA?

• ¿Tiene sentido este enfoque o hay un enfoque diferente que recomendaría?

• ¿Qué formas hay que podrían facilitar el proceso de ajustar una configuración de puntaje?

Con respecto a la última pregunta, soy consciente de la posibilidad de usar algoritmos genéticos, también soy ligeramente consciente de SARSA (y creo que mis anotadores se parecen a la descripción de las características de ese sitio con pesos, pero desde mi entendimiento, eso no es exactamente lo que he creado aquí). Creo que un problema con SARSA es que no conoces la recompensa hasta que el juego termina, el mejor movimiento es a menudo un movimiento que no da una recompensa (una mina) en absoluto. Sus posibilidades actuales de ganar dependen tanto del puntaje actual (cuántas minas han tomado usted y su oponente) como del aspecto del mapa actual.

_{Esta pregunta se publicó originalmente en un sitio de Inteligencia Artificial ya desaparecido .
El código (Java) utilizado para este enfoque ahora se ha publicado en Code Review .}

En un tramo es un sistema experto (como la lógica difusa). Como no está ejecutando un algoritmo para realizar comentarios sobre los parámetros de decisión basados ​​en la salida, en realidad no está aprendiendo. Sin embargo, realizar comentarios no es el único indicador de si un alogirthm es AI. Se podría argumentar que si actúa de una manera que parece inteligente, eso es todo lo que importa, especialmente cuando el juego es jugado por un oponente humano.

El tipo de algoritmo que ha especificado es realmente una ecuación parametrizada, el tipo que encontrará en los cálculos de seguros. Después de cada movimiento, el espacio de entrada cambia pero el algoritmo no necesita memoria del estado anterior, por lo que trata cada movimiento como una nueva placa separada.

Usando Algoritmos Genéticos

Hay dos opciones claras para los algoritmos genéticos:

• Use los parámetros para el genoma (como sugirió). Optimizará las reglas que tiene, pero aún le queda un sistema experto.
• Use el Sistema de clasificación de aprendizaje (LCS) para elegir las reglas por usted. Un LCS es un tipo de algoritmo genético en el que codifica las reglas y los parámetros. Tardan más en converger y son sensibles a la función de estado físico. Creo que la forma de juego resultante podría ser más interesante.

Recocido simulado

Otra forma de resolver el problema es utilizar el recocido simulado (SA). Su problema es un espacio de entrada limitado y puede escribir analíticamente una función que encuentre el mejor cuadrado para elegir en cualquier escenario dado. El uso de recocido simulado encontrará un óptimo global para sus parámetros.

Al hacerlo demasiado bueno

Sé que quieres que el algoritmo sea lo mejor posible, pero no olvides que un humano está jugando contra él. Hay una forma tácticamente perfecta de jugar este tipo de juegos deterministas y si el jugador de IA lo toma, solo sería pura suerte que eso significara que el jugador gana.

Sí, la técnica de asignación de puntajes basada en ciertos aspectos de la posición es estándar para escribir IA para jugar. Por ejemplo, casi todos los programas de ajedrez funcionan puntuando posiciones basadas más significativamente en las piezas disponibles, con bonificaciones más pequeñas según sus posiciones (por ejemplo, los peones que se protegen entre sí). Luego intentan calcular el mejor movimiento disponible mediante el uso de un algoritmo de búsqueda contradictorio como alfa-beta.

La búsqueda adversaria puede ser difícil aquí debido al gran factor de ramificación: en cualquier posición, los movimientos legales son para marcar o revelar cualquier casilla desconocida. Por otro lado, es posible que pueda reducir mucho el factor de ramificación por heurística. Por ejemplo, marcar o revelar una casilla de la que no sabes nada rara vez será la mejor jugada. Por el contrario, si conoce la ubicación de algunas minas sin marcar, marcar una de ellas probablemente será la mejor jugada, la mayoría de las veces. Mantener una tabla de transposición también probablemente ayudaría.