Cómo escribir inteligencia artificial Snake en Python
Prólogo
En los últimos dos días, vi una imagen en Internet que despertó mucho mi interés. La imagen es del juego Snake. Se estima que la mayoría de la gente ha jugado. él. Pero si fuera sólo un juego de Snake, no tendría nada de emocionante. La clave es que la serpiente en la imagen es tan codiciosa XD, se comió toda la comida en el rectángulo y luego llenó todo el rectángulo magníficamente, lo cual es realmente agradable a la vista. Como CSer, lo primero que me viene a la mente es que su programa hace esto (porque la persona promedio no puede hacer esto). La segunda cosa que me viene a la mente es cómo puedo escribir un programa para lograr esto. ¿Y qué algoritmo debo usar? Ahora que comencé a pensar en ello, déjame comenzar a hacerlo porque "las palabras vacías arruinarán el país, pero el trabajo duro hará que el país prospere", muéstrame el código (aprendido del tío). Mouse)
Antes de comenzar, apreciemos nuevamente la codiciosa serpiente con su postura elevada: (Si la imagen dinámica a continuación no es fácil de ver, puede hacer clic derecho para guardar y ver)
p>
Selección de idioma
La vida es corta, usa python. Así que no lo pienses mucho, ve directamente a la versión inicial
¡Inicia y ejecuta tu programa!
Lo primero que debemos hacer No es una pregunta de análisis. Al menos podrías escribir primero un juego de serpientes que funcione, cc tiene solo cien líneas de código (si no recuerdo mal. No). interfaz complicada). Simplemente ejecútelo bajo la consola), Python es más simple, elimine los comentarios y las líneas en blanco, y se hace en 5 o 60 líneas de código. Lo mejor de todo es que está muy bien escrito en la web y no lo hace. Necesitas reinventar la rueda, solo obtén una copia y modifícala a tu gusto.
Versión simple
No creo que sea una buena idea simplemente escribir la versión perfecta allí. Hay muchas cosas a considerar y, por lo general, hay muchos errores al escribir directamente. Entonces, mi objetivo al principio es simplemente dejar que el programa controle el movimiento de la serpiente y que se coma la comida. inicial. Pregunta:
1
2
En un rectángulo, hay un alimento en cada momento, y la serpiente debe encontrar un camino (no necesariamente el mejor). camino) para llegar a la ubicación de la comida sin golpearte, luego corre por el camino hasta la ubicación de la comida
No nos preocupemos por el hecho de que la serpiente se está alargando Básicamente, dado un comienzo. punto (la cabeza de la serpiente) y un punto final (la comida), debes evitar el obstáculo (el cuerpo de la serpiente) y encontrar un camino factible desde el punto inicial hasta el punto final. Los métodos que podemos utilizar son:
BFS
DFS
A*
Siempre que tenga una opción, primero debe elegir la solución más simple. Nuestro objetivo actual es obtener la solución más simple. El programa se ejecuta primero, y la optimización es una idea de último momento. Inicialmente colocamos la posición de la cabeza de la serpiente en la cola y luego, siempre que la cola no esté vacía, sacamos la posición de la cabeza de la cola y luego la colocamos dentro de cuatro puntos. Los cuatro campos se colocan en la cola y la operación del bucle continúa hasta llegar a la posición de la comida. Durante este proceso, debemos prestar atención a varios puntos: 1. Los puntos que han sido visitados no serán visitados nuevamente. 2. Guarde el nodo principal de cada punto (es decir, desde qué posición se llega a cada ubicación para que podamos encontrar el camino factible) 3. Las ubicaciones del cuerpo de la serpiente y las cuatro paredes son inaccesibles.
Después de encontrar comida a través de BFS, lo único que debemos hacer es mover la serpiente por un camino factible. Después de escribir esta versión simple, Pac-Man puede correr felizmente por un tiempo. Echa un vistazo a la siguiente imagen: (La lentitud se debe al programa de grabación @_@)
Para mantener las cosas lo más simples posible, utilicé el módulo curses, que puede dibujar directamente desde la terminal. Como puede ver en el gif de arriba, si simplemente usara BFS cada vez, Gluttony eventualmente sería derribado por este comportamiento imprudente y miope.
Incluso entonces, solo utilizará una estrategia que le haga dejar de progresar en algún momento de su vida porque pierde de vista el objetivo (la comida) y piensa que eso es todo lo que tiene que hacer. (Soy tan filosófico. Es una serpiente estúpida y si no le enseñas más, morirá en minutos. Por lo tanto, escribí una función de "caminar" que, como sugiere el nombre, permite a la pequeña serpiente detener BFS cuando encuentra dificultades y dejarla caminar y pensar en su propia vida. Esto es como ir a trabajar cuando estás aturdido. No sólo no es eficiente, sino que también puede impedirte salir del apuro, por el contrario, si dejas el trabajo que tienes entre manos, para, sal a por un rato; viaje o algo así.
La funcionalidad de deambular se puede programar como quieras, pero ciertamente existen ventajas y desventajas. Escribí dos versiones, una que tomaba pasos aleatorios en direcciones aleatorias dentro de los límites de lo factible. En otras palabras, la dirección en la que se mueve la serpiente cada vez es aleatoria y el número total de pasos en los que se mueve también es aleatorio. Después de Wander, ve a BFS y mira si puedes conseguir algo de comida y, si lo haces, todos estarán contentos. Si no puedes comer, significa que no has tenido tiempo suficiente para pensar en la vida, por lo que empiezas a deambular de nuevo. Etcétera. Pero al igual que el "proceso estocástico de aleatorización", usted "vaga al azar, se estrangula al azar". De hecho, una serpiente errante puede dar muchos más pasos. Pero un día, llegará aleatoriamente a un callejón sin salida. Si te quedas atascado, aún puedes "vagar", pero si llegas a un callejón sin salida, no hay ningún mecanismo de retroceso. Entonces, en la segunda versión de la función de roaming, dejé que "Glotonería" llegara hasta el final. Una vez que el BFS no se haya resuelto, dígale a la serpiente una cantidad de pasos (un número de pasos generado aleatoriamente) y déjela moverse en un paso en forma de S en el área vacía. La dirección del movimiento esta vez no es aleatoria, sino organizada y regular. Primero echemos un vistazo a la imagen y luego hablemos de lo que tiene de malo:
Sí, finalmente murió. Ni siquiera un movimiento en forma de S puede evitar que Xiabuxiabu muera. Con el movimiento S, Gluttony podría haber sobrevivido por un tiempo, pero porque su estrategia es:
1
2
3
4
5
Sin presionar la tecla ESC:
Si hay un camino entre la serpiente y la comida:
Sigue adelante y come la comida
De lo contrario:
Quédate un rato
El problema es que la serpiente se da cuenta de que hay un camino entre ella y la comida, y sin Diciendo una palabra, corrió a comer la comida. No tiene en cuenta que cuando vas a comer, lo que sucede (la disposición del cuerpo de la serpiente) es muy posible que te deje colgado. (Como entrar en un espacio pequeño y cerrado rodeado por el propio cuerpo)
Por lo tanto, para que una serpiente viva más tiempo, debe ser más previsora.
La versión hipermétrope
Ahora tenemos una versión básica del problema y una comprensión ligeramente mejor del mismo. Ahora estamos listos para un análisis más reflexivo y riguroso. Primero, enumeremos algunas preguntas: (Al igual que en una lluvia de ideas, escribe lo que se te ocurra)
No es aconsejable crear un camino directo entre la serpiente y la comida.
Entonces, ¿qué se debe hacer?
Si la serpiente va a buscar comida y el diseño es seguro, ¿va directamente a buscar comida? (¿Es esta la mejor opción?)
¿Cómo definir si un diseño es seguro?
¿Qué pasa si no hay camino entre la serpiente y la comida?
¿Es el camino más corto el camino óptimo? Obviamente, este no es el caso)
Entonces, si el diseño es seguro, ¿el camino más corto es el camino óptimo?
Además del camino más corto, ¿qué más podemos hacer? ¿Forma S? ¿El camino más largo?
¿Cómo solucionar el problema de que las serpientes sean cada vez más largas?
La comida aparece de forma aleatoria. ¿Es posible que haya un diseño irresoluble?
¿Puede la fuerza bruta obtener la secuencia óptima? (Deje que Xiabuxiabu coma tanta comida como sea posible)
Hay muchas preguntas con solo pensarlo. Llegados a este punto, tomemos las preguntas anteriores y pensemos desde una perspectiva orientada al proceso. Inicialmente, la serpiente es corta (inicializada en longitud 1), ve la comida y usa BFS para obtener el camino más corto hacia la comida para cada ubicación en el rectángulo. Sin serpientes en el camino, esa es la distancia de Manhattan. Luego, primero tuve que determinar si era un camino seguro para la serpiente. Entonces necesito una serpiente virtual que explore el camino en todo momento. Si es seguro, dejaré correr a la verdadera serpiente. Por supuesto, la serpiente virtual no será dibujada, solo se encarga de simular la detección. Entonces, ¿cómo se define un diseño como seguro? Si observas cuidadosamente el movimiento extático de la serpiente en la animación al comienzo del artículo, encontrarás que aunque el cuerpo de la serpiente es muy largo al final, aún puede salirse del camino sin problemas. Además, ¡sigue la cola de la serpiente! De hecho, esto no es difícil de explicar. A medida que la serpiente se mueve, su cuerpo seguirá consumiéndose y siempre aparecerá un nuevo espacio detrás de su cola. Cuando la serpiente es corta, esto no importa, pero cuando es larga, se da cuenta de que debe seguir la cola de la serpiente si quiere sobrevivir. Mientras persigues la cola de la serpiente, también debes considerar si puedes comer la comida de manera segura. (La siguiente imagen es el diseño obtenido después de un determinado BFS. 0 representa la comida, el número representa la distancia desde la posición a la comida, el símbolo representa la cabeza de la serpiente, el * representa el cuerpo de la serpiente, el - representa la cola de la serpiente , y el # representa el espacio y el círculo exterior # representa la valla)
1
2
3
4<. /p>
5
6
7
# # # # # # # # #
# 0 1 2 3 4 #
# 1 2 3 # 5 #
# 2 3 4 -6 #
# 3 * * 7 #
# 4 5 6 7 8 #
# # # # # # # # # ##
Después de analizar el contenido anterior, podemos definir si el diseño es seguro o si la serpiente Puede seguir la cola de la serpiente, es decir, después de que la serpiente come la comida, la distancia entre la cabeza de la serpiente y la cola de la serpiente ¿Hay un camino? Si es así, lo considero seguro.
Vale, continúa. Después de que la serpiente real le pidió a la serpiente virtual que explorara el camino, descubrió que el diseño después de comer la comida era seguro. Entonces la verdadera serpiente se dirigió directamente hacia la comida. Espera, ¿es esta una buena estrategia? incierto. Porque cada vez que la serpiente se mueve, el diseño cambia. Y el cambio de diseño significa que puede haber una solución mejor. Por ejemplo, debido al consumo de la cola de la serpiente, la comida que la serpiente tuvo que desviarse para alcanzar aparece repentinamente frente a la serpiente. Por lo tanto, después de que la serpiente real da un paso, un mejor enfoque es volver a realizar el BFS, luego hacer el mismo juicio de seguridad que el anterior y seguir adelante nuevamente.
A continuación, consideremos ¿qué pasa si no hay un camino entre la serpiente y la comida? De hecho, el método que se mencionó anteriormente es seguir la cola de la serpiente. Mientras no haya un camino entre la serpiente y la comida, la serpiente seguirá siguiendo su cola. Del mismo modo, dado que el diseño cambia en cada paso, el BFS se rehace en cada paso para obtener el diseño más reciente.
Vale, aquí viene de nuevo el problema.
¿Qué pasa si no hay un camino entre la serpiente y la comida, ni entre la serpiente y la cola? No hay nada que pueda hacer al respecto, sólo puedo elegir el camino que funcione. Es la misma idea: avance paso a paso, actualice el diseño y determine si hay un camino seguro entre la serpiente y la comida, si no, si hay un camino entre la cabeza y la cola de la serpiente, si no, elija; otro paso factible.
Varios de los problemas enumerados anteriormente involucran la estrategia de caminar de la serpiente. En términos generales, dejaremos que la serpiente tome el camino más corto cada vez. Esto se aplica cuando la serpiente está a punto de comer, pero no cuando se persigue la cola. Queremos que la cabeza de la serpiente persiga la cola de la serpiente lo más lentamente posible. De esta manera, hay más espacio entre la cabeza y la cola de la serpiente, y se necesita más espacio para el desarrollo de la serpiente. Por lo tanto, existen dos estrategias principales para caminar de las serpientes:
1
2
1 Cuando el objetivo es la comida, toma el camino más corto
.2. Cuando el objetivo es la cola, toma el camino más largo
¿Qué pasa con el tercer caso? A falta de un camino hacia la comida o una cola, simplemente elige un paso factible, no importa si es el más corto o el más largo. En cuanto a hacer que las serpientes caminen artificialmente en forma de S, no creo que sea una buena estrategia, y los problemas que plantea ya fueron analizados en la versión original. (A menos, claro, que quieras usar la versión más hermética, que es ignorar la comida por completo y dejar que la serpiente siga caminando en forma de S, dejando un pasillo a lo largo de la pared. De esta manera, la serpiente puede comerse toda la comida. perfectamente y luego ocupa todo el espacio, pero es aburrido, no tiene sentido)
Se mencionó otra pregunta anteriormente: dado que la comida aparece al azar, ¿es posible que haya una situación que no se pueda resolver? La respuesta es: sí. #
# * * # * #
# * * * * * #
# * * * * #
# * * * * #
# * * * * #
# # # # # # # # # # # # # #
Entre ellos, el " " El número es la cabeza de la serpiente, entre los cuales " " representa la cabeza de la serpiente, "-" representa la cola de la serpiente, "*" representa el cuerpo de la serpiente, "0" representa la comida, "#" representa el espacio y el círculo exterior tiene "#" representa la pared. En este diseño, la comida ya está frente a la cabeza de la serpiente, pero ¿puede comerla? ¡No se puede comer!
# * * * * * * #
# * * * * * * * #
# * * * * * * * #
# # # # # # # # # # # # #
En este momento, dado que la longitud de la serpiente se ha sumado a 1, la cola de la serpiente no se ha tocado, y la cabeza de la serpiente está rodeada de sí misma y suspendida. Sin embargo, todavía tenemos una cuadrícula vacía # que aún no se ha llenado. De acuerdo con la estrategia que le enseñamos a la serpiente antes, cuando se encuentre con esta situación, la cabeza de la serpiente seguirá persiguiendo la cola de la serpiente. Siempre que tenga un camino hacia la comida, dejará que la serpiente virtual la atraviese porque está consciente del nuevo diseño. Lo que consiguió no era seguro, por lo que en lugar de comer la comida, decidió seguir persiguiendo la cola de la serpiente. Luego siguió corriendo y corriendo. Este es un bucle sin fin hasta que presionas la tecla ESC.
Dado que la comida aparece de forma aleatoria, es posible tener diseños inseguros como el de arriba. Por supuesto, también puedes conseguir el final perfecto de "la serpiente llena todo el rectángulo".
La última pregunta anterior es si los métodos de fuerza bruta producen una secuencia óptima. Según el análisis anterior, parece posible, pero no hay garantía de que sea posible.
Finalmente, observe cómo lo ejecuta Vision Snake:
El tamaño del rectángulo es 10*20, sin incluir el exterior del borde, que es 8*18. Las imágenes grabadas en Linux y luego convertidas a formato GIF tienen un tamaño de más de 40 MB después de la optimización, lo que realmente no es comparable a Windows.
Al optimizar con el siguiente comando, parece que el sistema se está optimizando con su vida:
Shell
1
convertir salida.gif -fuzz 10 -layers Optimizar optimizado.gif
Finalmente, llegué a Windows y usé AE.
Por último, pero no menos importante
Si está interesado en el código fuente, haga clic en el siguiente enlace: "Code here
Además. El programa Snake. utiliza el módulo curses, que se instala de forma predeterminada en sistemas tipo Unix, pero los usuarios de Windows deben instalarlo aquí: Por favor, llámame si necesitas curses
El código anterior se puede seguir mejorando (ahora). Agregue comentarios de menos de 300 líneas, la optimización puede ser menor), también puede usar la biblioteca pygame o pyglet para hacer la interfaz más hermosa, ¡disfrútelo!