machine learning - tic - ¿Cómo crear una buena función de evaluación para un juego?

minimax algorithm (8)

Escribo programas para jugar variantes de juegos de mesa a veces. La estrategia básica es la poda estándar alfa-beta o búsquedas similares, a veces aumentadas por los enfoques habituales de los juegos finales o aperturas. He jugado principalmente con variantes de ajedrez, así que cuando llega el momento de elegir mi función de evaluación, uso una función de evaluación de ajedrez básica.

Sin embargo, ahora estoy escribiendo un programa para jugar un juego de mesa completamente nuevo. ¿Cómo elijo una función de evaluación buena o incluso decente?

Los principales desafíos son que las mismas piezas están siempre en el tablero, por lo que una función material habitual no cambiará según la posición, y el juego se ha jugado menos de mil veces, por lo que los humanos no necesariamente lo hacen lo suficiente. bien aún para dar una visión. (PS. Consideré un enfoque de MoGo, pero no es probable que terminen los juegos al azar).

Detalles del juego : El juego se juega en un tablero de 10 por 10 con seis piezas fijas por lado. Las piezas tienen ciertas reglas de movimiento e interactúan de cierta manera, pero ninguna pieza es capturada. El objetivo del juego es tener suficientes piezas en ciertos cuadrados especiales en el tablero. El objetivo del programa de computadora es proporcionar un jugador que sea competitivo o mejor que los jugadores humanos actuales.

Comenzaré con algunos conceptos básicos y luego pasaré a las cosas más difíciles.

Agente básico y un framework de pruebas.

No importa qué enfoque adopte, debe comenzar con algo realmente simple y tonto. El mejor enfoque para un agente tonto es aleatorio (generar todos los movimientos posibles, seleccionar uno al azar). Esto servirá como punto de partida para comparar a todos sus otros agentes. Necesitas un marco fuerte para la comparación. Algo que toma varios agentes, permite jugar una cantidad de juegos entre ellos y devuelve la matriz de la performance. Con base en los resultados, usted calcula la aptitud para cada agente. Por ejemplo, su función de tournament(agent1, agent2, agent3, 500) jugará 500 juegos entre cada par de agentes (jugando el primero / segundo) y le devolverá algo como:

x -0.01 -1.484 | -1.485 0.01 x -1.29 | -1.483 1.484 1.29 x | 2.774

Aquí, por ejemplo, uso 2 puntos para ganar, 1 punto para la función de puntuación del sorteo, y al final solo tengo que sumar todo para encontrar la condición física. Esta tabla me dice inmediatamente que agent3 es el mejor, y agent1 no es realmente diferente de agent2 .

Entonces, una vez que estas dos cosas importantes estén configuradas, estará listo para experimentar con sus funciones de evaluación.

Empecemos con la selección de características.

En primer lugar, no necesita crear not a terrible función de evaluación not a terrible . Con esto quiero decir que esta función debe identificar correctamente 3 aspectos importantes (ganar / empate / perder). Esto suena obvio, pero he visto una cantidad significativa de bots, donde los creadores no pudieron configurar correctamente estos 3 aspectos.
Luego usas tu ingenio humano para encontrar algunas características del estado del juego. Lo primero que debes hacer es hablar con un experto en juegos y preguntarle cómo acceder a la posición.
Si no tiene el experto, o si acaba de crear las reglas de su juego hace 5 minutos, no subestime la capacidad del ser humano para buscar patrones. Incluso después de jugar un par de juegos, una persona inteligente puede darte ideas sobre cómo debería haber jugado (no significa que pueda implementar las ideas). Utilice estas ideas como características.
En este punto, no es necesario saber cómo afectan estas características al juego. Ejemplo de características: valor de las piezas, movilidad de las piezas, control de posiciones importantes, seguridad, número total de movimientos posibles, cercanía a un acabado.
Después de codificar estas funciones y usarlas por separado para ver qué funciona mejor (no se apresure a descartar las funciones que no tienen un rendimiento razonable por sí mismo, podrían ser útiles en conjunto con otras personas), está listo para experimentar con combinaciones.

Construyendo mejores evaluaciones combinando y ponderando características simples. Hay un par de enfoques estándar.

Crea una función uber basada en varias combinaciones de tus características. Puede ser lineal eval = f_1 * a_1 + ... f_n * a_n (funciones f_i , coeficientes a_i ), pero puede ser cualquier cosa. Luego, cree una instancia de muchos agentes con pesos absolutamente aleatorios para esta función de evaluación y utilice un algoritmo genético para reproducirlos entre sí. Compare los resultados utilizando el marco de prueba, descarte un par de perdedores claros y mute a un par de ganadores. Continuar el mismo proceso. (Este es un esquema aproximado, lea más acerca de GA)
Usa la idea de propagación hacia atrás de una red neuronal para propagar el error desde el final del juego para actualizar los pesos de tu red. Puedes leer más sobre cómo se hizo con el backgammon (no he escrito nada similar, por lo que lamento la falta).

¡Puedes trabajar sin función de evaluación! Esto puede parecer una locura para una persona que solo escuchó hablar de minimax / alpha-beta, pero hay métodos que no requieren una evaluación en absoluto. Uno de ellos se llama Monte Carlo Tree Search y como Monte Carlo en un nombre sugiere que utiliza una gran cantidad de juegos aleatorios (no debe ser aleatorio, puede usar tus buenos agentes anteriores) para generar un árbol. Este es un gran tema por sí mismo, por lo que les daré una explicación de muy alto nivel. Comienzas con una raíz, creas tu frontera, la cual tratas de expandir. Una vez que expandes algo, solo vas al azar a la hoja. Al obtener el resultado de la hoja, se vuelve a propagar el resultado. Haga esto muchas veces y reúna las estadísticas sobre cada niño de la frontera actual. Selecciona el mejor. Existe una teoría importante que se relaciona con la forma en que se equilibra entre la exploración y la explotación y una buena cosa para leer allí es UCT (algoritmo de límite superior de confianza)

Como lo entiendo, quieres una buena función de evaluación estática para usar en las hojas de tu árbol mínimo-máximo. Si es así, es mejor recordar que el propósito de esta función de evaluación estática es proporcionar una calificación sobre qué tan bueno es ese tablero para el jugador de la computadora. Asi es

f (tablero1)> f (tablero2)

entonces debe ser cierto que board1 es mejor para la computadora (es más probable que eventualmente gane) que en board2. Por supuesto, ninguna función estática es completamente correcta para todas las tablas.

Entonces, usted dice que "el objetivo del juego es tener suficientes piezas en ciertos cuadros especiales en el tablero", por lo que una primera puñalada en f (tablero) sería simplemente contar el número de piezas que tiene la computadora en esos Plazas especiales. A continuación, puede refinarlo más.

Sin conocer los detalles del juego es imposible dar mejores conjeturas. Si nos diera las reglas del juego, estoy seguro de que los usuarios de podrían venir con toneladas de ideas originales para tales funciones.

Encuentre algunos candidatos para su función de evaluación, como movilidad (número de movimientos posibles) menos la movilidad del oponente, luego intente encontrar el peso óptimo para cada métrica. Los algoritmos genéticos parecen funcionar bastante bien para optimizar los pesos en una función de evaluación.

Cree una población con pesos aleatorios, lúcelos entre sí con una profundidad y giros limitados, reemplace los perdedores con combinaciones aleatorias de los ganadores, mezcle y repita, imprimiendo el promedio de la población después de cada generación. Deje que se ejecute hasta que esté satisfecho con el resultado, o hasta que vea la necesidad de ajustar el rango para algunas de las métricas y vuelva a intentarlo, si parece que el valor óptimo para una métrica podría estar fuera de su rango inicial.

Edición tardía: un enfoque más aceptado, estudiado y comprendido que no sabía en ese momento es algo que se llama "Evolución diferencial". Los descendientes se crean a partir de 3 padres en lugar de 2, de tal manera que evita el problema de la convergencia prematura hacia el promedio.

Me gustaría ver un algoritmo de aprendizaje automático supervisado, como el aprendizaje por refuerzo. Echa un vistazo a aprendizaje de refuerzo en juegos de mesa . Creo que eso te dará algunas buenas direcciones para mirar.

Además, echa un vistazo a la Estrategia de Adquisición para el Juego de Otel Basado en el Aprendizaje de Refuerzos (enlace PDF) donde, dadas las reglas del juego, se puede aprender una buena "función de pago". Esto está estrechamente relacionado con TD-Gammon ...

Durante el entrenamiento, la red neuronal en sí misma se utiliza para seleccionar movimientos para ambos lados ... El hallazgo bastante sorprendente fue que realmente se llevó a cabo una gran cantidad de aprendizaje, incluso en los experimentos de conocimiento inicial cero utilizando una codificación de tabla sin procesar.

Si bien puede usar varios métodos de aprendizaje automático para crear una función de evaluación (TD-Learning, utilizado en proyectos como gnubackgammon, es uno de esos ejemplos), los resultados dependen definitivamente del juego en sí. Para el backgammon, funciona realmente bien, porque la naturaleza estocástica del juego (dados rodantes) obliga al alumno a explorar el territorio que tal vez no quiera hacer. Sin un componente tan importante, probablemente terminará con una función de evaluación que es buena contra sí misma, pero no contra otras.

Dado que la diferencia de materiales puede no ser aplicable, ¿es importante el concepto de movilidad, es decir, cuántos movimientos posibles tiene disponibles? ¿El control de un área determinada del tablero suele ser mejor que no? Habla con las personas que juegan el juego para descubrir algunas pistas.

Si bien es preferible tener una función de evaluación tan buena como sea posible, también debe ajustar su algoritmo de búsqueda para que pueda buscar lo más profundamente posible. A veces, esto es realmente una preocupación, ya que un buscador profundo con una función de evaluación mediocre puede superar a las búsquedas superficiales con una buena función de evaluación. Todo depende del dominio. (Gnubackgammon juega un juego experto con una búsqueda de 1 capa, por ejemplo)

Existen otras técnicas que puede utilizar para mejorar la calidad de su búsqueda, y lo más importante, tener una tabla de transposición para almacenar en caché los resultados de la búsqueda para tener una poda avanzada.

Recomiendo encarecidamente mirar estas diapositivas .

Si nadie entiende el juego todavía, no hay forma de que puedas obtener una función de evaluación decente. No me digas que el estándar alfa-beta con recuento de material es bueno o incluso decente para el ajedrez o sus variantes (tal vez el ajedrez de los perdedores sea una excepción).

Puede probar redes neuronales con retroalimentación o algoritmos de aprendizaje automático similares pero, por lo general, apestan hasta tener un montón de entrenamiento, que en este caso probablemente no esté disponible. Y aun así, si no apestan, no puedes obtener conocimiento de ellos.

Creo que no hay manera de entender el juego lo mejor que puedas y, para empezar, dejar las incógnitas como aleatorias en la función de evaluación (o simplemente fuera de la imagen hasta que las incógnitas se hagan más conocidas).

Por supuesto, si compartiera más información sobre el juego, podría obtener mejores ideas de la comunidad.

También debe tener cuidado en su elección. Si su algoritmo no tiene una relación conocida con el valor real, las funciones AI estándar no funcionarán correctamente. Para ser válido, su función de evaluación o heurística debe ser igual o inferior al valor real de manera consistente o guiará sus decisiones de manera extraña (lo que podría argumentar para el ajedrez, aunque creo que los puntos estándar son correctos). ).

Lo que normalmente hago es averiguar qué es capaz y qué se requiere. Para algunos juegos, como sokoban, he usado el número mínimo de movimientos de caja necesarios para obtener una caja (de forma aislada) desde su ubicación actual a cualquiera de las ubicaciones de los objetivos. Esta no es una respuesta precisa para el número de movimientos requeridos, pero creo que es una heurística bastante buena, ya que nunca se puede sobreestimar y se puede calcular previamente para todo el tablero. Al sumar la puntuación de un tablero, es solo la suma de los valores para cada ubicación de cuadro actual.

En una simulación de vida artificial que escribí para evolucionar la búsqueda de paquetes y la defensa de paquetes, el sistema de puntuación que utilicé fue solo para guiar la evolución y no para realizar ninguna poda. Le di a cada criatura un punto por nacer. Por cada punto de energía que consumieron en su vida, les di un punto adicional. Luego utilicé la suma de los puntos de su generación para determinar la probabilidad de reproducción de cada uno. En mi caso, simplemente usé la proporción del total de puntos de su generación que habían adquirido. Si hubiera querido evolucionar a criaturas que eran geniales para evadir, habría anotado para obtener puntos devorados por ellas.

También debe tener cuidado de que su función no sea un objetivo difícil de alcanzar. Si está tratando de evolucionar algo, quiere asegurarse de que el espacio de la solución tenga una pendiente decente. Desea guiar la evolución en una dirección, no solo declarar una victoria si sucede para golpear aleatoriamente.

Sin saber más sobre tu juego, sería difícil decirte cómo construir una función. ¿Existen valores claros de algo que indiquen una ganancia o una pérdida? ¿Tiene una forma de estimar un costo mínimo para cerrar la brecha?

Si proporciona más información, estaré encantado de intentar ofrecerle más información. También hay muchos libros excelentes sobre el tema.

Jacob

Tenga en cuenta que no es necesariamente cierto que incluso exista una función de evaluación decente. Para esta afirmación, asumo que una función de evaluación debe ser de baja complejidad (P).