algorithm - examples - artificial intelligence history
Algoritmo AI para el juego "RaceTrack" (8)
Hasta ahora, no creo que nadie haya abordado un punto clave de su pregunta: ¿cómo se le ocurre un buen "valor de calidad"? En AI, el valor de calidad al que se refiere generalmente se denomina "heurístico". Idealmente, su heurística le diría exactamente el número mínimo de movimientos necesarios para alcanzar el final, dada la posición / velocidad actual. En realidad, tenemos que conformarnos con algo que sea más fácil de calcular.
Una guía importante es que una buena heurística debe ser admissable ; es decir, nunca debe sobreestimar el costo de alcanzar la meta (en su caso, la cantidad de movimientos para llegar al final). El algoritmo A * depende de tener una heurística admisible.
Una técnica común para idear una heurística admisible es relajar el problema original. En los juegos, a menudo puede hacer esto cambiando el juego para que sea más fácil (por ejemplo, al descartar reglas). En RaceTrack, por ejemplo, puedes enderezar la pista para que sea un juego más fácil. Con una vía recta, la mejor estrategia es claramente acelerar de forma continua. Por lo tanto, una heurística admisible es calcular la distancia desde la posición actual hasta el final (es decir, la longitud de la pista enderezada) y luego calcular el número de movimientos necesarios para recorrer esa distancia asumiendo una aceleración constante.
Puede idear otras heurísticas relajando diferentes reglas, pero a menudo hay una compensación entre la precisión de la heurística y la cantidad de cómputo requerida.
¿Alguien sabe (o puede sugerir) un buen algoritmo para una IA para el juego de lápiz de papel RaceTrack ?
Ya que tiene 9 opciones posibles en cada paso y necesita mirar por lo menos 6-10 pasos adelante para decidir una buena estrategia, la fuerza bruta se está volviendo muy costosa incluso si puede descartar algunas opciones debido a la intersección con el límite.
Actualmente estoy tratando de asignar un valor de calidad a cada opción para decidir qué opciones descartar, pero aún no conozco buenas reglas sobre cómo asignar ese valor de calidad.
Hay algunos algoritmos conocidos en el ajedrez como la poda alfa-beta, el orden de movimientos, etc. Tal vez tenga mejor suerte si busca en el contexto del ajedrez.
Edición : los algoritmos de búsqueda de ruta solo funcionan si no tiene reglas y condiciones adicionales. Por ejemplo, si también tienes velocidad y fuerzas centrípetas, estás fuera de suerte. Si no tiene esas condiciones avanzadas, está mejor con un algoritmo de búsqueda de ruta simple como se indica en otras respuestas.
He hecho un solucionador de C ++ que es un poco demasiado largo (187 líneas) para que quepa cómodamente aquí, así que lo puse en pastebin: http://pastebin.com/3G4dfTjR . El programa calcula una solución óptima (número mínimo posible de movimientos) o informa que no es posible.
Uso
Ejecute el programa como pista de carreras startX startY goalX goalY [circleX circleY radius] .
El programa asume una cuadrícula de 100x100 que opcionalmente puede contener un único obstáculo circular cuyo centro y radio especifiques. Además, debe especificar la ubicación inicial del automóvil y una ubicación de objetivo único. Aunque estas restricciones son un tanto restrictivas, un vistazo al código debería hacer que sea obvio que no limitan el algoritmo en general; toda la lógica relevante está encapsulada en las isMoveValid() y isGoalState() , así que si alguien puede serlo. se molestó en implementar versiones más generales de estas rutinas (por ejemplo, permitir que el usuario especifique un mapa de bits de las ubicaciones de la cuadrícula y / o permitir múltiples ubicaciones de objetivos), entonces esto se puede incorporar sin dificultad.
La única complicación leve sería que la ubicación del objetivo sea la misma que (o cerca, pero "al otro lado de") la ubicación de inicio, que es lo que necesita si desea que su pista sea un circuito. En este caso, para evitar que el solucionador simplemente gire el automóvil o se detenga de inmediato, deberá especificar una "línea de inicio" invisible, y modificar isMoveValid() para prohibir los movimientos "hacia atrás" a través de esta línea.
Cómo funciona
Debido a que cada movimiento cuesta exactamente 1, es posible usar una primera búsqueda de amplitud a través del espacio de estado 4D para encontrar una solución óptima. Cuando visitamos un estado dado s, que consiste en una tupla de 4 (x, y, dx, dy) donde dx y dy son el vector de velocidad que usamos para llegar a (x, y), consideramos los 9 estados que Puede llegar desde s con un solo movimiento. Para cualquier estado t que no se haya visto ya, se garantiza que esta ruta a t (es decir, a través de s) sea óptima, ya que BFS siempre visita los nodos en orden de su distancia mínima desde la raíz. Cuando determinamos una ruta óptima para un estado, registramos el estado predecesor, lo que permite que se produzca un rastreo de la ruta completa al final.
BFS es más simple y, por lo tanto, probablemente más rápido, que el algoritmo de Dijkstra o la búsqueda A *, que son algoritmos más generales que permiten que los movimientos tengan varios costos, flexibilidad que no necesitamos aquí. A * puede ser más rápido si hay pocos obstáculos para confundir su heurística, pero en cada paso debe buscar el nodo de costo mínimo, que generalmente se realiza utilizando un montón, mientras que para BFS, siempre hay un nodo de costo mínimo disponible en El frente de la cola.
Ejemplos
Cronómetro del cronómetro 30 3 90 10
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.
Cronómetro del cronómetro 30 3 90 10 50 20 25
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.
Observe cómo la solución óptima aquí primero tiene que "doblarse", ir arriba y alrededor y luego nuevamente hacia abajo, ya que el obstáculo circular se extiende hasta el fondo de la cuadrícula.
Pequeño error: el código publicado dará una respuesta corta (¡pero sin longitud cero!) Si establece la ubicación del objetivo igual a la ubicación inicial. Obviamente, esto podría comprobarse como un caso especial, pero ya había puesto el código en pastebin cuando me di cuenta de esto ... :)
Menciona la idea de "asignar a cada opción algún valor de calidad", esto se denomina función heurística. Muchos algoritmos de inteligencia artificial (como la poda A * y alfa-beta, mencionados por otros) son tan buenos como la función heurística que se conecta a ellos.
Sin embargo, si logra crear una buena función heurística, entonces estos algoritmos se desempeñarán automáticamente mucho mejor "gratis", por lo que vale la pena invertir tiempo en desarrollar una buena.
Otro ángulo es tratar de pre-computar toda tu carrera desde el principio. Entonces se trata de minimizar el número de turnos para cruzar la línea de meta. Un útil algoritmo de búsqueda mínima es el recocido simulado .
Aparte de eso, también sería genial ver alguna solución de algoritmo genético para un juego como este. No estoy seguro de si es el ajuste correcto, pero podría imaginarme creando un ''cerebro'' que tome varias entradas (distancia esperada de la pared en unos cuantos giros en el futuro, velocidad, distancia a otros corredores, etc.) y evolucionando la lógica de eso Cerebro con un algoritmo genético. El truco consiste en dividir el problema en partes que puedan mutarse significativamente.
En realidad, incluso podrías combinarlos y usar un gen genético. para desarrollar una función heurística que esté conectada a un algoritmo de búsqueda estándar de AI.
Sin embargo, honestamente, la fuerza bruta probablemente funcionaría bien en una pista restringida, ya que puedes lanzar un subárbol si fallas (y las fallas son comunes en caminos incorrectos).
Otros recomiendan A *, que es probablemente el camino a seguir, pero hay un problema con ese enfoque. Primero, permítame decir que el ''costo'' de ir de un nodo a otro siempre es 1, ya que desea minimizar el número de pasos, simplemente no hay otro costo involucrado.
¡Pero lo importante que quiero hacer es que una ubicación (x, y) no es un nodo único en el gráfico de búsqueda de A *! El nodo se caracteriza por x e y, pero también por las coordenadas x e y del nodo del que proviene el automóvil (o por los componentes de velocidad vx y vy si así lo desea). Por lo tanto, no puede atravesar el algoritmo A * sobre una cuadrícula bidimensional; En realidad, debería ser de 4 dimensiones. Dicho esto, A * probablemente sigue siendo el camino a seguir.
En cuanto a la heurística, podría ser realmente creativo acerca de eso, pero sugiero algo como la distancia para terminar menos la velocidad actual, donde la distancia se calcula previamente para cada punto en la cuadrícula 2D regular (use un algoritmo Dijkstra para eso). Esto hace que el algoritmo A * busque primero hacia la línea de meta y, de preferencia, lo más rápido posible. Creo que tal algoritmo haría muy bien para calcular la ruta completa de inmediato.
Sin embargo, un problema es que A * siempre proporcionará la ruta óptima, por lo que no sería divertido jugar contra una IA que use tal algoritmo, ya que siempre ganaría (suponiendo que las posiciones iniciales sean justas).
Si bien no será inmediatamente aplicable a RaceTrack, es posible que pueda aprender algo del algoritmo de búsqueda de rutas A * . Se usa en muchos juegos para ayudar a la IA a descubrir cómo ir del punto A al punto B lo más rápido posible.
Te propondría que comiences por revertir el problema. Use el análisis retrógrado (como lo hacen en los juegos de ajedrez finales http://en.wikipedia.org/wiki/Retrograde_analysis ) para calcular hacia atrás desde el final, suponiendo que usted es el único jugador, para ver cuántos pasos se necesitan para cruzar la línea de meta. , dada una posición y velocidad. Si mi pensamiento es correcto, el tiempo para calcular esto debería ser lineal en el número de posiciones. Debería ser muy rápido.
No será la verdad absoluta, ya que tiene competidores que perturban su camino, pero le dará una muy buena heurística para su algoritmo de búsqueda.
Este documento puede ayudarte