200412861_fase#3

ROBOCODE - FASE#3 Carlos Andres Barrios Gonzalez [email protected] Ing. Huber Flores

Guatemala, Guatemala Universidad de San Carlos de Guatemala Facultad de Ingenier´ıa. Escuela de Ciencias y Sistemas. Junio, 2009

1

Resumen

Existen distintos algoritmos y estrategias relacionadas con el campo de la inteligencia artificial que pueden ser utilizadas en la creaci´on y programaci´on de robots en Robocode. Estos permiten seleccionar la mejor estrategia para vencer a los adversarios en una batalla. Entre estos se encuentran: uso de redes neuronales, algoritmos gen´eticos, vecino mas cercano (K-NN), arboles de decisi´on, etc.

2

Abstract

Different algorithms and strategies related with the field of the artificial intelligence can be used in the creation and programming in Robocode. These allow to select the best strategy to conquer the opponents in a battle. Some of these they: use of netral networks, genetic algorithms, k-nearest neighbors (K-NN), decision trees, etc. 1

3

ROBOCODE - Algoritmos y Estrategias

Build the best. Destroy the rest!

3.1

ARBOLES DE DECISION

Un ´ arbol de decisi´ on es un modelo de predicci´on utilizado en el ´ambito de la inteligencia artificial. En base a la informaci´on se construyen diagramas de construcciones l´ ogicas utilizados para categorizar y representar distintas condiciones. Por medio de los distintos sensores que cada robot posee en Robocode, podemos obtener informaci´ on sobre nuestros enemigos, el entorno y nosotros mismos. Entre esta informaci´on se encuentra: • El total de robots participantes. • Nuestra cantidad de energ´ıa y de los enemigos. • Tasa de aciertos. • Frecuencia de disparos. • Patrones de movimiento. Para codificar el ´ arbol de decisiones en Robocode, utilizamos la estructura de control if-else y switch en Java. Toda la informaci´on que obtengamos podemos utilizarla para generar distintas condiciones y decisiones basadas en esta informaci´ on, como por ejemplo: 1 S i ( numeroDeEnemigos > 5 ) { esconderse () 3 } sino { Si ( energiaDelEnemigo > 10) { 5 disparar (1) ; sino { 7 disparar (3) ; } 9 }

2

DIAGRAMA DE UN ARBOL DE DECISION:

3.2

´ CERCANO VECINO MAS

Poder encontrar a los robots enemigos es uno de los aspectos vitales para ganar una batalla en Robocode. Mediante el uso del radar podemos encontrar a nuestros adversarios para poder encontrarlos y dispararles. Este m´etodo clasifica objetos bas´ andoos en la cercan´ıa de un punto en el espacio. El algoritomo K-NN es uno de los mas simples de todos los algoritmos de aprendizaje para las maquinas El radar pude escanear robots a 1200 unidades de distancia, cada vez que se detecta alg´ un robot con el arco del radar es enviado al m´etodo onScannedRobot(). La estrategia consiste en escanear con el radar el enemigo mas cercano y aplicar un ataque. Dependiendo de la distancia, ajustar la potencia del disparo optima para evitar la perdida de energ´ıa innecesaria.

3

Usualmente es utilizada la distancia Euclidiana como medida para calcular la cercan´ıa de los robots respecto al nuestro.

Ejemplo: radar giratorio El radar del robot gira de forma simple, m´etodo bastante simple e inefectivo en luchas uno a uno. 1 public void run ( ) { // . . . 3 do { 5 turnRadarRightRadians ( Double . POSITIVE INFINITY ) ; } while ( true ) ; 7 }

3.3

CLUSTERING

El Clustering din´ amico es una t´ecnica para encontrar entradas en un registro similar a la situaci´ on actual, es b´asicamente un algoritmo K-NN. La idea b´asica es guardar un estado o situaci´on en cada entrada de un registro con informaci´on medible. Por ejemplo si guardamos informaci´on sobre la distancia de un enemigo, podemos usar estos datos para encontrar la distancia del estado actual y de los estados pasados.

3.4

REDES NEURONALES

Las redes de neuronas artificiales (RNA o ANN) son un paradigma de aprendizaje y procesamiento autom´atico inspirado en la forma en que funciona el sistema nervioso de los animales. Esta formado por un conjunto de interconexiones que colaboran para producir una salida.

4

En robocode el uso de redes neuronales permite predecir el movimiento de los enemigos e ir aprendiendo para orientarse de la mejor forma y atacar. La evoluci´ on permite que el robot aprenda, evite objetos y mejore su navegaci´on.

3.5

ALGORITMOS GENETICOS

RobocodeJGAP es un enfoque que permite evolucionar robots en robocode por medio de programaci´ on de algoritmos gen´eticos. Esta es una herramienta open source que provee un framework basado en JGAP.

”http://jgap.sourceforge.net/doc/robocode/robocode.html”. JGAP es tan simple de utilizar y solo requiere que los desarrolladores definan una funci´ on fitness (una funci´on encargada de evaluar a las soluciones y elegir la mejor). Los algoritmos gen´eticos permiten tratar cualquier secuencia de bits como si fuera un genoma. La complicaci´on viene en decidir qu´e significa esa secuencia de 5

bits e interpretar el genoma. La t´ecnica de una programaci´on gen´etica permite obtener mejores robots a trav´es de mecanismos de evoluci´on. Se comienza con una poblaci´ on generada aleatoriamente, se seleccionan los mejores elementos. La mutaci´ on y el cruce son los responsables de que aparezcan nuevos por lo que en cada generaci´ on el comportamiento medio debe mejorar.

4

ESTRATEGIAS

Algunos ejemplos de estrategias en robocode son: • LinearMovement: Movimiento en l´ınea recta, simple y con gran vulnerabilidad al apuntamiento lineal • Oscillators: Movimiento en un conjunto de patrones que se repiten. Es vulnerable al Pattern Matching. • CircleBots: Robots que se mueven en circulos. Son vulnerables a apuntamiento circular. • WallBots: Se mueven a lo largo de los muros, trantando de mantenerse alejados y en movimiento, son vulnerable a LinearTargeting, excepto cerca de las esquinas. • RamBots: Se mueven en direcci´on del enemigo. Vulnerable a la mayor´ıa de los apuntamientos pero consigue bonus extras por ram (arrollar). • StopAndGo: Reacciona ante fuego enemigo. Es efectivo frente a apuntamiento lineal y circular pero es vulnerable ante Pattern Matching y GuessFactorTargeting.

La estrategia seleccionada debe de variar dependiendo de distintas variables del entorno, como: cantidad de enemigos, nuestro nivel de energia, etc. 6

5

DESCRIPCION DE LA ESTRATEGIA SELECCIONADA

Luego de realizar varias batallas de prueba con los robots de ejemplo incluidos en robocode y de algunos mas avanzados descargados de internet, se obtuvieron las siguientes observaciones para el dise˜ no de la estrategia: • Al iniciar una batalla con gran cantidad de enemigos, es mejor alejarse y mantenerse en movimiento, como el robot Walls. Debido a la gran cantidad de robots en la arena, mientras nos mantengamos en movimiento constante, esperamos a que los dem´as robots se eliminen entre ellos. • La estrategia de Walls no es ofensiva, y la energ´ıa de los disparos es constante, por lo que se debe de calcular la distancia al robot que se dispara mientras se encuentra detenido en una esquina. Dependiendo de la distancia al enemigo, aplicar distintas potencias al disparo • Si la cantidad de robots es de alrededor de 3 o en una batalla uno a uno, la estrategia de walls puede ser efectiva si el oponente no posee buenos mecanismos de apuntamiento, por lo que al haber pocos enemigos, escoger una estrategia de b´ usqueda a un enemigo especifico. Dependiendo de la distancia al enemigo, disparar con distintas potencias (mientras mas cerca estamos, mas potencia). • Si alguno de los dem´ as robots de la arena nos ataca y acierta cierto numero de balas, cambiar al enemigo actual, alejarse y atacar de nuevo.

Definicion de una estrategia en base a la cantidad de enemigos al iniciar la batalla

7

5.1

ESTRATEGIA WALLS

Estrategia utilizada cuando existe gran cantidad de enmigos.

La seleccion de la estrategia por medio del arbol de decision seria: 1 3 5

i f ( e s t r a t e g i a W a l l s=true ) // u s a r e s t r e t e g i a w a l l s } else { // u s a r e s t r a t e g i a de b u s q u e d a y a t a q u e }

Agregando el codigo para dirigirse a las paredes y disparar: 1 i f ( e s t r a t e g i a W a l l s=true ) double d i s t a n c i a ; 3 distancia = e . getDistance () ; i f ( d i s t a n c i a <=250){ 5 f i r e (3) ; setBodyColor ( Color . white ) ; 7 } else { f i r e (1) ; 9 setBodyColor ( Color . black ) ; } 11 i f ( peek ) { 13 scan ( ) ; } 15 } e l s e { 17

busqueda ( ) ;

19 } ...

8

Trabajando con netbeans.

”Videotutorial que incluye como integrar robocode con Netbeans”. ... 2 4 i f ( cantEnemigos <3){ 6

busqueda ( ) ; disparo () ; execute () ;

8

} else { modoWalls=true ; peek = true ; ahead ( moveAmount ) ; peek = f a l s e ; turnRight (90) ;

10 12 14 16

} 18 . . .

5.2

ESTRATEGIA BUSQUEDA Y ATAQUE

Estrategia utilizada en batallas uno a uno o con pocos adversarios.

9

2

public void busqueda ( ) { i f ( tengoEnemigo == f a l s e ) {

4

scanAngle = 360; } else {

6 8

s c a n A n g l e = n o r m a l R e l a t i v e A n g l e ( g e t H e a d i n g ( )− getRadarHeading ( )+enemigo . p o i n t s T o B e a r i n g ( getX ( ) , getY ( ) , g e t H e a d i n g ( ) )+d i r e c c i o n ∗ ) ; }

10 setTurnRadarRight ( s c a n A n g l e ) ; 12 }

6

CONCLUSIONES • La estrategia de nuestro robot debe de ser adaptable a ciertas variables y par´ ametros que cambian en el entrono para lograr vencer la batalla. • Cuando existe gran cantidad de enemigos, es mejor esperar que se eliminen entre ellos manteni´endose en constante movimiento y alejado de los dem´as robots. • En combate uno a uno o con un numero reducido de robots, es mejor buscar un blanco especifico y atacarlos con una potencia que dependa de la distancia al enemigo. • En robocode, podemos implementar arboles de decisiones mediante las estructuras de control switch e if-then-else de java. Esto permite categorizar 10

y representar las distintas condiciones y variables del entrono. Utilizar una estrategia de clustering permite predecir una posible situaci´on en base a situaciones similares que han pasado con anterioridad. • El uso de redes neuronales en los robots de robocode permite que estos aprendan y logren decidir la mejor estrategia de ataque. • RobocodeJGAP permite evolucionar robots en robocode por medio de programaci´ on de algoritmos gen´eticos. Esta t´ecnica permite obtener mejores robots a trav´es de mecanismos de evoluci´on.

7

Bibliograf´ıa [1 ]: ”Sistemas Basados en Conocimiento: Robocode”. By Javier Jim´enez, Rub´en G´ omez. [2 ]: ”Arbol de Decisiones” By Wikipedia. [3 ]: ”K-NN Algorithm” By Robowiki. [4 ]: ”Radar” By Robowiki. [5 ]: Dynamic Clustering By Robowiki [6 ]: An Artificial Neural Network for a Tank Targeting System By HansW. Guesgen, Xiao Dong Shi. [7 ]: Red Neuronal By Wikipedia.

11