Cómo crear una buena función de evaluación para un juego?

https://stackoverflow.com/questions/1291377

18-09-2019
|

Pregunta

escribo programas para jugar variantes del juego de mesa a veces. La estrategia básica es la poda alfa-beta estándar o búsquedas similares, a veces aumentada por los métodos habituales a los finales o aberturas. sobre todo me he jugado un poco con variantes del ajedrez, por lo que cuando llega el momento de recoger a mi función de evaluación, utilizo una función básica de evaluación de ajedrez.

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

Los principales retos son que las mismas piezas están siempre en el tablero, por lo que un material de función habitual no cambiará en función de la posición, y el juego ha sido jugado menos de un millar de veces más o menos, por lo que los seres humanos no necesariamente jugar lo suficientemente bien todavía dar una idea. (PS. Me considera un enfoque MoGo, pero los juegos de azar no es probable que terminar.)

Datos del juego : El juego se juega en un tablero de 10 por 10 con un fijo de seis piezas por cada lado. Las piezas tienen ciertas reglas de movimiento, e interactúan en ciertos aspectos, pero ninguna pieza es cada vez capturados. El objetivo del juego es tener suficiente de sus piezas en ciertas casillas especiales en el tablero. El objetivo del programa de ordenador es proporcionar un jugador que es competitivo con o mejor que los jugadores humanos actuales.

Solución

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

Crea una población con pesos aleatorios, luchar contra ellos uno contra el otro con una profundidad y vueltas limitado, reemplazar los perdedores con combinaciones aleatorias de los ganadores, shuffle, y repetir, la impresión de la media de la población después de cada generación. Se deja correr hasta que esté satisfecho con el resultado, o hasta que vea la necesidad de ajustar el rango de algunas de las métricas e intentarlo de nuevo, si se comprueba que el valor óptimo para una métrica podría estar fuera de su rango inicial.

Late edición: A más aceptada, estudiado, enfoque que no sabía en ese momento es algo que se llama "La evolución diferencial" entendida. Descendencia se crea a partir de 3 padres en lugar de 2, de tal manera que evita el problema de la convergencia prematura hacia la media.

Otros consejos

Voy a empezar con algunos conceptos básicos y pasar a cosas más difíciles más adelante.

agente básico y un marco de pruebas

No importa qué enfoque se toma lo necesario para empezar con algo muy simple y tonta. El mejor enfoque para un agente tonto es al azar (generación de todos los movimientos posibles, seleccionar uno al azar). Esto servirá como punto de partida para comparar todos los otros agentes. Es necesario un marco sólido para la comparación. Algo que lleva varios agentes, permite jugar un poco número de juegos entre ellos y devuelve la matriz de la actuación. Con base en los resultados, se calcula la aptitud para cada agente. Por ejemplo, su función tournament(agent1, agent2, agent3, 500) jugará 500 partidos entre cada par de agente (jugar el primer / segundo) y le devuelve 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, utilizo 2 puntos por victoria, 1 punto por empate función de puntuación, y al final acaba sumando todo para encontrar el gimnasio. Esta tabla me dice inmediatamente que agent3 es el mejor, y agent1 no es realmente diferente de agent2.

Así que una vez que estas dos cosas importantes que se establecen ya está listo para experimentar con sus funciones de evaluación.

Vamos a empezar con la selección de características

En primer lugar es necesario crear función de evaluación not a terrible. Con esto quiero decir que esta función debe identificar correctamente 3 aspectos importantes (/ empate / victorias y derrotas). Esto suena obvio, pero he visto cantidad significativa de los robots, en los que los creadores no eran capaces de configurar correctamente estos 3 aspectos.
A continuación, utiliza su ingenio humano para encontrar algunas de las características del estado del juego. Lo primero que debe hacer es hablar con un experto en juego y preguntarle cómo se accede a la posición.
Si usted no tiene el experto, o incluso se acaba de crear las reglas de su juego hace 5 minutos, no hay que subestimar la capacidad del ser humano para buscar patrones. Incluso después de jugar un par de juegos, una persona inteligente puede darle ideas de cómo debería haber jugado (esto no significa que pueda poner en práctica las ideas). Use estas ideas como características.
En este punto usted realmente no necesita saber cómo estas características afectan el juego. Ejemplo de características:. Valor de la movilidad piezas, piezas, el control de las posiciones importantes, la seguridad, el número total de movimientos posibles, la cercanía a un acabado
Una vez codificado por estas características y los usaron por separado para ver qué funciona mejor (no prisa para descartar características que no realizan razonable por sí mismo, que podrían ser útiles en combinación con otros), ya está listo experimentar con combinaciones.

Construcción de mejores evaluaciones mediante la combinación y la ponderación de características simples. Hay un par de enfoques estándar.

Crea una función súper basado en varias combinaciones de sus características. Puede ser eval = f_1 * a_1 + ... f_n * a_n lineal (características f_i, coeficientes a_i), pero puede ser cualquier cosa. A continuación, crear una instancia de muchos agentes con pesos absolutamente al azar para esta función de evaluación y el uso de algoritmo genético para reproducirlos agains entre sí. Comparar los resultados utilizando el framework de pruebas, se descarta un par de perdedores claros y mutar un par de ganadores. Continuar con el mismo proceso. (Este es un esbozo, leer más sobre GA)
Utilice la idea de propagación hacia atrás desde unos redes neuronales para respaldar propagar el error desde el final del juego para actualizar los pesos de la red. Puede leer más cómo se ha hecho con el backgammon (no he escrito algo similar, así lo siento por la estatura).

Se puede trabajar sin la función de evaluación! Esto puede sonar loco para una persona que sólo se enteró de Minimax / alfa-beta, pero hay métodos que no requieren una evaluación en absoluto. Uno de ellos se llama Monte Carlo Árbol Buscar y como Monte Carlo en un nombre sugiere que utiliza una mucho al azar (que no debe ser al azar, puede utilizar sus buenos agentes anteriores) juego se desarrolla para generar un árbol. Este es un gran tema por sí mismo, por lo que me dará la mina realmente la explicación de alto nivel. Se empieza con una raíz, crear su frontera, que intenta expandir. Una vez que expande algo, que acaba de ir al azar de la hoja. Obtener el resultado de la hoja, que backpropagate el resultado. Haga esto muchas veces, y recoger las estadísticas sobre cada niño de la frontera actual. Seleccionar la más adecuada. Existe la teoría de que hay significativa que se relaciona con la forma en qué equilibrio entre exploración y explotación y una buena cosa para leer hay UCT (algoritmo de confianza superior Bound)

Me gustaría ver un algoritmo de aprendizaje automático supervisado tales como el aprendizaje por refuerzo. Echa un vistazo a aprendizaje por refuerzo en el tablero de juegos . Creo que le dará algunas buenas direcciones a considerar.

Además, echa un vistazo a estrategia de adquisición para el Juego Otelo Sobre la base de aprendizaje por refuerzo (enlace PDF), donde da las reglas del juego, una buena "función de pagos" se puede aprender. Esto está estrechamente relacionado con TD-Gammon ...

Durante el entrenamiento, la red neuronal sí se utiliza para seleccionar movimientos para ambos lados ... La sorprendente hallazgo fue que una cantidad sustancial de aprendizaje que realmente ocurrió, incluso en el conocimiento inicial de cero experimentos que utilizan un tablero en bruto codificación.

Si nadie entiende el juego, sin embargo, no hay manera se puede obtener una función de evaluación decente. No me diga que el alfa-beta estándar con recuento material es bueno o incluso decente para el ajedrez o sus variantes (tal vez el ajedrez perdedores es una excepción).

Usted podría tratar de redes neuronales con retroalimentación de aprendizaje o máquina similar algoritmos pero por lo general chupar hasta que tienen un montón de entrenamiento, que en este caso probablemente no está disponible. E incluso entonces, si no se chupan, no se puede obtener conocimiento de ellos.

Creo que no hay forma corta de entender el juego lo mejor que puede y, para empezar, dejar las incógnitas como al azar sobre la función de evaluación (o simplemente fuera de la imagen hasta que las incógnitas hacen más conocidas).

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

A mi entender, que desea una buena función de evaluación estática para usar en las hojas de su árbol mín-máx. Si es así, lo mejor es recordar que el propósito de esta función de evaluación estática es proporcionar una clasificación en cuanto a lo bien que la junta es para el jugador de la computadora. Así es

f (board1)> f (board2)

entonces debe ser cierto que board1 es mejor para el equipo (que es más probable que gane el tiempo) que en board2. Por supuesto, ninguna función estática es siempre totalmente correcta para todas las tarjetas.

Por lo tanto, se dice que "El objetivo del juego es tener suficiente de sus piezas en ciertas casillas especiales en el tablero", por lo que un primer intento de f (bordo) sería simplemente para contar el número de piezas del ordenador tiene en esas casillas especiales. A continuación, puede que sea más finura.

Sin conocer los detalles del juego que es imposible dar mejores conjeturas. Si usted nos dio las reglas del juego estoy seguro que los usuarios stackoverflow serían capaces de llegar con un montón de ideas originales para tales funciones.

Mientras que usted podría utilizar varios métodos de aprendizaje automático para llegar a una función de evaluación (TD-Learning, que se utiliza en proyectos tales como gnubackgammon, es un ejemplo de ello), los resultados son definitivamente depende del juego en sí. Para backgammon, funciona muy bien, debido a la naturaleza estocástica del juego (tirar los dados) obliga al alumno a explorar un territorio que puede no querer hacerlo. Sin un componente tan crucial, es probable que terminar con una función de evaluación que es bueno contra sí mismo, pero no contra otros.

Desde diferencia material puede no ser aplicable, es el concepto de movilidad importante - es decir, el número de movimientos posibles que tiene disponible? Es el control de un área determinada de la junta general, mejor que no? Hablar con las personas que juegan el juego de descubrir algunas pistas.

Si bien es preferible tener tan buena de una función de evaluación como se puede, también deberá sintonizar el algoritmo de búsqueda para que pueda buscar como profundamente como sea posible. A veces, esto es en realidad más de una preocupación, ya que un buscador de profundidad con una función de evaluación mediocre puede superar a búsquedas de poca profundidad con una buena función de evaluación. Todo depende del dominio. (Gnubackgammon juega un juego de expertos con una búsqueda de 1 cabo, por ejemplo)

Hay otras técnicas que puede utilizar para mejorar la calidad de su búsqueda, lo más importante, tener una tabla de transposición a los resultados de búsqueda de caché para tener sonido poda adelante.

Le recomiendo mirando por encima de estas diapositivas .

También es necesario tener cuidado en su elección. Si el algoritmo no tiene una relación conocida con el valor real, las funciones estándar de IA no funcionarán correctamente. Para ser válida, su función de evaluación, o heurística tiene que ser el mismo que, o por debajo del valor real de manera sistemática o que guiará sus decisiones de una manera extraña (que se podría argumentar para el ajedrez, aunque creo que los puntos estándar están bien ).

Lo que suelen hacer es averiguar lo que es capaz y lo que se requiere. Para algunos juegos, como sokoban, he utilizado el número mínimo de movimientos necesarios de la caja para obtener una caja (de forma aislada) desde su ubicación actual en cualquiera de las ubicaciones de gol. Esto no es una respuesta exacta para el número de movimientos necesarios, pero creo que es una muy buena heurística ya que nunca puede sobrestimar y puede ser pre-calculado para todo el tablero. Cuando la suma de la puntuación de un tablero que es simplemente la suma de los valores de cada cuadro de ubicación actual.

En una simulación de vida artificial que escribí para evolucionar la caza y la defensa paquete de paquete, el sistema de puntuación que he utilizado sólo para guiar la evolución y no realizar ninguna poda. Me di a cada criatura un punto de nacer. Para cada punto de la energía que se consume en su vida, les di un punto adicional. Luego utiliza la suma de los puntos de su generación para determinar la probabilidad de cada uno era reproducir. En mi caso, simplemente utilizó la proporción del total de puntos de su generación que habían adquirido. Si hubiera querido evolucionar criaturas que eran grandes en evadir, habría anotado abajo para obtener puntos comen fuera de ellos.

También debe tener cuidado de que su función no es demasiado difícil de un objetivo para golpear. Si usted está tratando de desarrollar algo, desea asegurarse de que el espacio de la solución tiene una pendiente decente. ¿Quieres guiar la evolución en una dirección, no sólo declarar una victoria si sucede a golpear al azar.

Sin saber más acerca de su juego que sería difícil para decirle cómo construir una función. ¿Hay algo de valores claros que indican una ganancia o una pérdida? ¿Tiene una manera de estimar un costo mínimo para cerrar la brecha?

Si proporciona más información, yo sería feliz para tratar de proporcionar una visión más clara. Hay un montón de excelentes libros sobre el tema también.

Jacob

Tome en cuenta que no es nescessarily cierto que incluso existe una función de evaluación decente. Por esta declaración que suponer que, una función de evaluación tiene que ser de baja complejidad (P).

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow