Home

Descargar PDF con la memoria de la practica

1. No se encuentra el archivo d e configuracion lt lt endl fgets cadaux MAXLINEA fich sscanf amp cadaux 0 PROFUNDIDAD d amp profundidad actual fgets cadaux MAXLINEA fich sscanf amp cadaux 0 SLEEP d amp do sleep fgets cadaux MAXLINEA fich sscanf amp cadaux 0 TIME d amp sleep time fclose fich bool jugando true srand time 0 tablero partida obtenerMapa dni tiempo max tablero tiempo delta t idUsuario tablero idUsuario 1 0 i lt ncasillas 1 if tablero casillas i BANDERA for 22 banderas_numero push_back i nbanderas cout lt lt Soy el jugador lt lt idUsuario lt lt endl creamos el nodo raiz njugadores int8 tablero jugadores size 2 ncasillas int16 tablero dimx tablero dimy vector lt Jugadores gt jugadores vector lt Casilla gt casillas setear jugadores if idUsuario 1 for i 0 i lt njugadores 2 i jugadores push_back new Jugadores i 1 tablero jugadores i casilla tablero jugadores i energia 0 0 0 else for i 0 i lt njugadores i jugadores push back new Jugadores i 1 tablero jugadores itnjugadores casilla tablero jugadores i njugadores energia 0 0 0 for i njugadores i lt njugadores 2 itt jugadores push_back new Jugadores it 1 tablero jugadores i njugadores casilla tablero jugadores i njugadores energia 0 0 0 crear estado inicial Estado estad
2. UNIVERSIDAD DE CASTILLA LA MANCHA ESCUELA SUPERIOR DE INFORM TICA INTELIGENCIA ARTIFICIAL E INGENIERIA DEL CONOCIMIENTO PRACTICA 2 EL JUEGO DE LA BANDERA CON ADVERSARIO FINAL Alumno Miguel Garcia Corchero 27 de Mayo de 2009 ndice de contenido 1 IntroduCcci ia a Nae Geass 4 1 1 Definici n del problema data sincera enana barrena crios 4 1 2 Decisiones de di i 5 13 Bstructuras p ra TESOlUCI N a s teas SSS SASS a ia 6 A SO lUCIONESAC LI CAS A s s POEM T 2 1 Breve explicaci n de los algoritmos utilizados poda Alfa Beta 7 RR NI 8 3 Pruebas o E M Q 9 A Conclusiones OA 12 gt Manual de WSU ANI O ooo 13 A ods tunt ka fa diat qb zu aN as Wu Sui aq aku o obe 13 5 2 Ejecuciomde la pr ctica iodo 13 6 C digo Fuentes Sosa u unun a O 14 A E aa ode oka a Qa tade Sessoms Aad sn thle EN 14 GL Banderas Sh pom ma wa mt Sua ask acho te seu eens maaa oo ooo eo tees edel 14 0 3 Clases Lie re a eis sau P Tc 15 GACT AS SS 26 BP case sss AA saa ka uss abt hioa tacts uu ma a uku le Gasset cadens 16 6 5 Cheto ere AA Add nudn Rea ee ee as 22 0 0 CHEM Cp DE 23 FM Problema h L n EE 26 6 8 Problema CPP aa eni t A sappnecesnasbasdch Ee RENE SERE VER EA GEOES aiae 27 0 9 Colores usina 32 6 10 Colores PDA 32 1 Introducci n 1 1 Definici n del problema a tratar Re
3. c new Casilla numero tipo casillas push back c catch std bad_alloc cout lt lt endl lt lt No hay disponible memoria para crear mas instancias de Casilla exit 1 sint8 Estado Movimiento int8 jugador int8 mov Jugadores jugador_copia try jugador copia new Jugadores jugadores jugador gt id jugadores jugador gt casilla jugadores jugador gt energia jugadores jugador gt hacha jugadores jugador gt barca jugadores jugador gt pala catch std bad_alloc cout lt lt endl lt lt No hay disponible memoria para crear m s instancias de Jugador exit 1 std vector lt Jugadores gt iterator posicion jugadores begin jugador posicion punteros 1 17 jugadores erase posicion jugadores insert posicion jugador_copia intl6 nueva_casilla SiguienteCasilla jugadores jugador gt casilla mov i sint8 resultado 0 sint8 tipo_casilla 0 if EstaLibreCasilla nueva_casilla obtenemos el valor de las casillas actualizadas for i 0 i lt int16 casillas size 1 if casillas i numero nueva casilla 1 tipo_casilla casillas il gt tipo si no ha sido actua if tipo_casilla 0 switch tipo_casilla case HIERBA case AGUA 3 jugadores jugador gt barca case BARRO case HOYO case ZANJA case BANDERA case BARCA gt barcat 20 break case HACHA gt hacha 20 break case ZUMO gt energia 20 break
4. break case 6 if casilla 1 siguiente casilla mapa dimx mapa dimy else if columna 1 siguiente casilla casilla 1 else if fila 1 siguiente casilla mapa dimx mapa dimy mapa dimx casilla 1 else siguiente casilla casilla mapa dimx 1 break else casillas pares empezando por el 2 switch mov case 1 if fila 1 siguiente casilla mapa dimx mapa dimy mapa dimx casilla else siguiente casilla casilla mapa dimx break case 2 if columna mapa dimx siguiente casilla casilla mapa dimx 1 else siguiente_casilla casilla 1 break case 3 if casilla mapa dimx mapa dimy siguiente_casilla 1 else if columna mapa dimx siguiente casilla casilla l else if fila mapa dimy siguiente casilla mapa dimx mapa dimx mapa dimy casilla 1 else siguiente casilla casilla mapa dimx 1 break case 4 mapa dimx mapa dimy casilla 30 fila mapa dimy siguiente casilla mapa dimx case 5 mapa dimx mapa dimy casilla 1 break case 6 return siguiente_casilla else Se esta cavando intl6 i mapa casillas casilla A i HIERBA else return ERROR 6 9 Colores h ifndef __COLORES_H_ define __COLORES_H_ include lt stdio h gt void void void void void void void void void void void void void void void void col col col col col col col col col col
5. case PALA gt pala 10 break case BOSQUE 4 jugadores jugador gt hacha case MURAYA if jugadores jugador jugadores jugador gt c else resultado ERROR return resultado lizada obtenemos el tipo de casilla del mapa original tipo_casilla mapa casillas nueva_casilla 1 jugadores jugador gt energia break if jugadores jugador gt barca gt 0 jugadores jugador gt energia else jugadores jugador gt energia 6 break jugadores jugador gt energia 2 break jugadores jugador gt energia 4 break jugadores jugador gt energia 6 break resultado 1 ActualizarCasilla nueva casilla 1 HIERBA break ActualizarCasilla nueva casilla 1 HIERBA jugadores jugador ActualizarCasilla nueva casilla 1 HIERBA jugadores jugador ActualizarCasilla nueva casilla 1 HIERBA jugadores jugador ActualizarCasilla nueva casilla 1 HIERBA jugadores jugador if jugadores jugador gt hacha gt 0 jugadores jugador energia else jugadores jugador energia 8 break resultado ERROR break gt energia lt 0 resultado ERROR asilla nueva casilla bool Estado operator Estado e if banderas e gt banderas return false if casillas size e gt casillas size return false else for int16 i 0 i lt int16 casillas size i if casillas i e gt casillas i return false if jugadores size e
6. a ado las banderas if nodo gt estado gt EstaCogidaBandera banderas_numero i b gt push_back banderas numero i while b gt size gt 0 distancia_minima INFINITO bandera_eliminar 0 for unsigned int i 0 i lt j gt size it for unsigned int k 0 k lt b gt size k distancia distancia casillas j i b k true if distancia lt distancia_minima distancia minima distancia bandera eliminar k jugador cambiar i 3 jugador_cambiar b bandera eliminar b gt erase b gt begin bandera eliminar valuel distancia minima preferencia por estados con casillas de jugador de menos costo for int i 0 i lt njugadores it a ado los jugadores switch nodo estado jugadores i casilla case HIERBA value2 1 10 break case AGUA if nodo estado jugadores i barca 0 value2 3 10 else value2 6 10 break case BARRO value2 2 10 break case HOYO value2 4 10 break case ZANJA value2 6 10 break case BOSQUE if nodo estado jugadores i hacha 0 value2 4 10 else value2 8 10 break 29 b clear j gt clear value3 1 float nodo gt estado gt banderas 1 float nbanderas 1 value4 nodo profundidad 0 1 nodo gt v valuel value2 value3 value4 delete b delete j return nodo gt v BORK KKK k K k K K k K k K K K K K K K K K kkk kkk kk kkk k k kk k k k
7. int banderas for int8 i 0 i lt int8 jugadores size 2 i jugadores i gt Print for int16 i 0 i intl6 casillas size i casillas i gt Print color_azul cout lt lt endl lt lt UANCZ NNSZ7 NNHS7 NN27 NN 7 NN27 NNC7 NAN97 NN2 7 NN27 7NNH7 ANG IAAI Nayak Sasa 7 color normal int16 Estado Size return sizeof int8 sizeof jugadores sizeof casillas sizeof Estado bool Estado EstaCogidaBandera int16 num for int16 i 0 i lt int16 casillas size i if casillas i gt numero num return true return false bool Estado EstaLibreCasilla int16 num bool resultado true for int16 i 0 i lt int16 jugadores size 2 i if jugadores i gt casilla num resultado false break return resultado void Estado ActualizarCasilla int16 numero int8 tipo int16 i bool actualizado false for i 0 i lt int16 casillas size i tt if casillas i gt numero numero if casillas i gt tipo tipo Casilla casilla_copia try casilla copia new Casilla numero tipo catch std bad alloc cout endl No hay disponible memoria para crear m s instancias de Casilla exit 1 std vector lt Casilla gt iterator posicion casillas begin i posicion punteros 1 casillas erase posicion casillas insert posicion casilla copia actualizado true break if actualizado Casilla c try
8. jugadores size return false else for int8 i 0 i lt int8 jugadores size i if jugadores i e gt jugadores i return false return true bool Estado operator lt Estado e int16 energia_this 0 energia_e 0 bool resultado false for int8 i 0 i lt int8 jugadores size i energia_this jugadores i gt energia for int8 i 0 i lt int8 e gt jugadores size i energia_et e gt jugadores i gt energia if energia_this gt energia_e return resultado bool Estado operator gt Estado e resultado true else resultado false intl6 energia_this 0 energia_e 0 bool resultado false for int8 i 0 i lt int8 jugadores size i energia_this jugadores i gt energia for int8 i 0 i lt int8 e gt jugadores size i energia_et e gt jugadores i gt energia if energia_this lt energia_e return resultado bool Estado operator lt Estado e resultado true else resultado false intl6 energia_this 0 energia_e 0 bool resultado false for int8 i 0 i lt int8 jugadores size i energia_this jugadores i gt energia for int8 i 0 i lt int8 e gt jugadores size i energia e e gt jugadores i gt energia if energia this gt energia e resultado true else resultado false 18 return resultado bool Estado operator gt Estado e int16 energia_this 0
9. b squeda mediante el algoritmo MiniMax con poda Alfa Beta se ha optado por implementar una mejora que es la siguiente Dada una decisi n a tomar en el ltimo nivel si tenemos queremos quedarnos con el nodo que tenga el m ximo valor MiniMax pero hay varios con dicho valor entonces de entre todos esos nodos nos quedaremos con el que mejor resultado de para la funci n heur stica Es decir para valores iguales como el valor que han elevado los nodos inferiores es el mismo para todos ellos calcularemos cual es la valoraci n de ese nodo y entonces tomaremos la decisi n en base a eso En cierto modo es como aplicar una b squeda mediante ascensi n a colinas cuando tenemos empate de valores en nodos y no sabemos cual elegir 1 3 Estructuras para su resoluci n Se ha dispuesto el siguiente diagrama de clases UML para la resoluci n del problema estado Estado costo int16 Romea 7 res movimiento int8 modo int8 sre jugador int8 cola std degue lt Nodo gt f float Size uint32 nodo padre Nodo Print void pop Nodo push nodo Nodo void Size int16 Print void operator n Nodo bool operator lt n Nodo bool operator gt n Nodo bool operator n Nodo bool operator gt n Nodo bool banderas int8 jugadores std vector Jugador casillas std vector Casillas Size int16 Print void Movimiento jugador i
10. ck ck ck ck ck ck ck ck ck ok ck ck ck ok ke e k Estado Estado int8 banderas vector lt Jugadores gt jugadores vector lt Casilla gt casillas this jugadores reserve jugadores size this gt casillas reserve casillas gt size this gt banderas banderas for int8 k 0 k lt int8 jugadores gt size k jugadores k gt punteros this jugadores push back jugadores k for int16 k 0 k lt int16 casillas gt size k casillas k gt punteros this gt casillas push back casillas k Estado Estado for int8 i 0 i lt int8 jugadores size i try std vector lt Jugadores gt iterator p for p jugadores begin p lt jugadores end pt t jugadores erase p k catch char str 4 cout lt lt endl lt lt Exception de borrado de Jugador lt lt str lt lt endl for intl6 i 0 i lt int16 casillas size i try 1 std vector lt Casilla gt iterator p for p casillas begin p lt casillas end ptt casillas erase p catch char str cout lt lt endl lt lt Exception de borrado de Casilla lt lt str lt lt endl 16 jugadores clear casillas clear void Estado Print color_azul cout lt lt endl lt lt NN NN NN NN NN NN AN NN NN NN NN NN NN NN7 7NNP j cout endl ESTADO cout endl banderas
11. col col col col col col endif 6 10 Colores cpp include void void void void void void void void void void void void void void void void col col col col col col col col col col col col col col col col or normal or negro or cyan or cyan claro or rojo or rojo claro or verde or amarillo or marron or gris claro or azul or azul claro or purpura Colores h or normal or negro or cyan or cyan claro or rojo or rojo claro or verde or verde claro or amarillo or marron or gris oscuro or gris claro or azul or azul claro or purpura or verde claro or gris oscuro or purpura claro or purpura claro putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout putc 27 stdout i BARRO else siguiente_casilla casillatmapa dimx break if fila mapa dimy siguiente casilla mapa dimx else siguiente casilla casilla mapa dimx 1 Siguiente casilla casilla 1 i HOYO fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout
12. else if nodo lt medio inicio inicio fin medio medio inicio fin inicio 2 igual que medio else i medio break i medio c insert i 1 nodo else c gt push_back nodo break void Frontera Print for std deque lt Nodo gt iterator i c gt begin i lt c gt end i i gt Print unsigned int Frontera size return c gt size 20 6 5 Client h de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de de fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine fine include Ice Ice h include list include iostream include queue include deque ERROR 1 SI 1 NO 0 HIERBA 1 AGUA 2 RRO 3 RAYA 4 BOSQUE 12 LINEAS CLEAR MAX JUGADORES COLA FIFO 1 COLA LIFO 2 COLA ORDENADA INFINITO 1000 MAX REPETIR C ifndef CLIENTE H define CLIENTE H 40 16 3 ASILLA 2 MAXMEM DEFAULT 262144 MAXLINEA 255 MAX COSTO 1000 CAMBIO ALGOR CAMBIO ALGOR FACTOR CORREC NFINITO 1000 NACCIONES 6 PESO MAX EVAL unsigned char 8 bits char short int 16 bits unsigned int 32 bits int 8 bits 32 bits unsigned long 32 bits enum long float
13. energia_e 0 bool resultado false for int8 i 0 i lt int8 jugadores size i energia this jugadores i gt energia for int8 i 0 i lt int8 e gt jugadores size i energia_et t e gt jugadores i gt energia if energia this energia e resultado true else resultado false return resultado J BRR k k k k k K k kk K K k K K K K K K K K K K KOK KOK KOK K KOK ck kkk kk kk kkk kk kk kkk kk kkk kk kk k kk kk k kk kk kkk kk kk k kk k k k ck ck ck ck k k k JUGADORES J RRR RK kk Ck kk kk kk kk kk kkk kkk kkk kkk kkk kkk kkk KH kk kkk k kc k kc k k k k k kk k k ck ck k k k k k k k k k k ck ck ck ck ck ck ck ck ck ck ck ck ck ok ck ok ck k k k k Jugadores Jugadores int8 id int16 casilla int16 energia intl16 hacha intl16 barca int16 pala this id id this gt casilla casilla this gt energia energia this gt hacha hacha this gt barca barca this gt pala pala punteros 1 Jugadores Jugadores void Jugadores Print color cyan cout lt lt endl lt lt cout lt lt endl lt lt JUGADOR lt lt int id lt lt cout lt lt endl lt lt casilla lt lt int casilla lt lt energia lt lt int energia lt lt pala lt lt int pala lt lt hacha lt lt int hacha lt lt barca lt lt int barca cout lt lt endl lt lt 4 4 4 4 4 4 4 4 4 4
14. fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout fprintf stdout 31 return casilla break
15. mapa dimx columna c1 columna c2 1 if columna_cl lt columna_c2 if columna cl mapa dimx columna c2 1 dif x dif y columna cl mapa dimx columna c2 1 float hip sqrt dif_x dif_x dif_y dif_y return round hip BRR k k KK k K k K k kkk kk k k kkk k k k k K KOK k K KOK ck Ck Ck KOK k k k k k k k k k k k k k k k k AS CALCULO DE SUCESORES KARA RA kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kok kkk kkk kkk kkk kkk kkk kkk kkk kkk kkk kkk kkk kkk vector lt Nodo gt Sucesores Nodo nodo vector lt Nodo gt s new vector lt Nodo gt int8 i j veces accion NACCIONES jugador MAX JUGADORES k swap pl p2 sint8 resultado 0 nodos internos 0 int16 energia antes energia despues delta energia sintl6 costo aleatoriedad a la hora de cual meter primero en la frontera for i 0 i lt NACCIONES i accion i itl for i 0 i lt njugadores i jugador i i for i 0 i lt NACCIONES i pl rand SNACCIONES p2 rand sNACCIONES swap accion pl accion p1 accion p2 accion p2 swap for i 0 i lt njugadores i pl rand njugadores p2 rand snjugadores swap Jugador p1 jugador p1 jugador p21 jugador p2 swap for i 0 i lt NACCIONES i n aciones aciones njugadores for j 0 j lt njugadores j no permitir acciones contrarias al padre if jugador j nodo gt jugador amp amp accion i nod
16. nodos utilizan el par metro b n que va a ser en cada momento el m nimo de los valores encontrados de los nodos sucesores de ese nodo Existen dos formas de podar dependiendo del nodo en el que se est estudiando En los nodos MAX la condici n de poda es a p gt b p 1 es decir si el a de un nodo MAX de profundidad p es mayor o igual que el b del nodo MIN padre profundidad p 1 se pueden podar los sucesores del nodo MAX no estudiados todav a Esto es debido a que como valor inferior el nodo MAX va a 7 devolver ese valor de a a p Ya que el nodo superior trata de minimizar va a calcular Ppl Sl amp p gt B pa La po SIA SB ps con lo que siempre va a elegir el b pl Por lo tanto los nodos no estudiados todav a en el nodo MAX no es necesario estudiarlos porque no cambian el valor b del nodo padre Sim tricamente la condici n de poda en los nodos MIN es b ys dy La explicaci n es an loga al caso anterior El algoritmo recursivo del Alfa Beta podr a especificarse de la forma expresada en la tabla adjunta donde la llamada inicial es de la forma Alfa Beta Situaci n Inicial Menor N mero Mayor N mero 0 2 2 Heur sticas dise adas La heur stica dise ada es una funci n de la forma Eval s w1f1 s w2f2 s w3f3 s w4f4 s Donde wl peso del factor 1 0 7 w1 peso del factor 2 0 1 w1 peso del factor 3 0 1 w1 peso del factor 4 0 1 fl s suma de las distancias a las banderas
17. un movimiento no valido Introduzca de nuevo el movimiento lt lt endl nodo_actual gt Print vector lt Nodo gt sucesores Sucesores nodo actual nodo_actual sucesores rand sucesores gt size cout lt lt Introduzca de nuevo el movimiento para salir del paso lt lt endl bool devuelto partida gt jugada tablero idUsuario nodo actual jugador nodo_actual gt movimiento info token cout lt lt Movimiento realizado lt lt devuelto lt lt endl moviendo false for unsigned int i 0 i lt sucesores gt size i delete sucesores i delete sucesores virtual int run int argc char argv string dni 5698168 string password blacksun if argc 1 argc gt 2 printHelp elsel Ice ObjectPrx base communicator gt stringToProxy AutenticacionObject Practica AutenticacionPrx autenticacion Practica AutenticacionPrx checkedCast base if autenticacion cout lt lt Error obteniendo el proxy de autenticacion lt lt endl return 1 Practica PartidaPrx partida NULL 24 try partida autenticacion gt login dni password catch Practica PasswordIncorrectaError e cout lt lt e reason lt lt endl catch Practica UsuarioIncorrectoError e cout lt lt e reason lt lt endl catch Practica NoExisteContrincanteError e cout lt lt e reason lt lt endl catch Practica NoExistePart
18. 4 4 4 4 4 4 4 4 4 4 4 color normal int16 Jugadores Size return sizeof int16 6 sizeof int8 sizeof Jugadores bool Jugadores operator Jugadores if casilla j gt casilla amp amp pala j gt pala 44 hacha j gt barca return true else return false bool Jugadores operator Jugadores j if id j id return true else return false bool Jugadores operator lt Jugadores j if id gt j gt id return false else return true bool Jugadores operator gt Jugadores j if id gt j gt id return true else return false bool Jugadores operator gt Jugadores j if id lt j gt id return false else return true J BRK k k kkk kkk kkk kkk kkk K K K kk YK K K K K k kk ck ck ck Ck kkk kkk kk kk kkk kk kk kkk kk kkk kk kk kkk kk kkk kk kkk kk kk kkk k k kk k FRONTERA J BRK RK KK Ck kk RI RARA RARA RARA k kk kk kk kk k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k kok k k k k k k k Frontera Frontera int8 modo try c new deque lt Nodo gt this gt modo modo catch std bad_alloc cout lt lt endl lt lt No hay disponible memoria para crear mas instancias de Frontera exit 1 Frontera Frontera for std deque lt Nodo gt iterator i c begin i c end i delete i delete c Nodo Fron
19. XFLAGS Clases o Clases cpp Clases h COMPILADOR OPTIMIZACIONES DEBUG c Clases cpp o Clases o CXXFLAGS Colores o Colores cpp Colores h COMPILADOR OPTIMIZACIONES DEBUG c Colores cpp o Colores o CXXFLAGS cleano RM o clean S RM S PROGRAMNAME o Practica cpp Practica h clear S RM S PROGRAMNAME o Practica cpp Practica h edit S EDITOR Client cpp Client h Problema cpp Problema h Clases cpp Clases h Colores cpp Colores h Banderas Makefile Configuracion amp config S EDITOR Configuracion amp 6 2 Banderas sh bin sh Client 1 Ice Config config client 13 6 3 Clases h ifndef _ CLASES_H_ define _ CLASES_H_ include include include include Client h Colores h lt memory gt lt math h gt using namespace std class Casilla public y int16 numero punteros int8 tipo Casilla int16 numero int8 tipo Casi void int16 bool bool bool bool bool class Jugadores public y int8 lla Print Size operator operator operator operator operator id Casilla c lt Casilla c lt Casilla c gt Casilla c gt Casilla c intl6 casilla hacha barca pala punteros sintl6 energia Jugadores int8 id intl6 casilla intl6 energia intl16 hacha int16 Juga void int16 bool bool bool bool bool class Estado public y int8 band
20. ador 1 Movimiento 6 gt Movimiento realizado 1 x JUGADA gt Jugador 2 Movimiento 5 gt Movimiento realizado 1 B m p JUGADA Jugador 2 Movimiento 2 gt Movimiento realizado 1 JUGADA Jugador 2 Movimiento l gt Movimiento realizado 1 ls JUGADA gt Jugador 2 Movimiento 3 Movimiento realizado 1 o JUGADA gt Jugador 2 Movimiento 3 Movimiento realizado 1 zi JUGADA gt Jugador 2 Movimiento 5 Movimiento realizado 1 r d JUGADA Jugador 1 Movimiento 1 Movimiento realizado 1 a T JUGADA gt Jugador 1 Movimiento 1 gt Movimiento realizado 1 e JUGADA gt Jugador 1 Movimiento 1 gt Energia insuficiente para rea lizar el movimiento Ha introducido un movimiento no valido Introduzca de nuevo el m Greenbite greenbite desktop Escritono Practica2 TA zs Lies 1 a Archivo Editar Ver Terminal Solapas Ayuda S JUGADA gt Jugador 3 Movimiento 5 gt Movimiento realizado 1 Has GANADO S AAA asseeeeeeeeseeeseeeseesssssss c NODO Size 183 Bytes jugador 3 movimiento 5 costo 52 profundidad 33 v 2 3 o BAENSP N 7 N 7 N 7 f N T 1 1 ESTADO banderas 1 A ok 4 4 4 4 4 4 4 4 JUGADOR 1 w casilla 36 energia 6 pala 0 hacha 0 barca 0 l ee 4 4 4 4 4 4 4 4 RR RA A PESECECECEOEH a a a RU ERR RR RR RR b BUGADOR 2 o Casilla 86 energia 2
21. alizar un bot agente racional que pueda jugar de forma aut noma contra un adversario permitiendo la posibilidad de realizar una peque a competici n La estrategia de Juego ser dirigida por un algoritmo Mini Max con poda alfa beta El juego se desarrolla con las reglas establecidas en el anexo Servidor del Juego de la Bandera El flujo de control aproximado se muestra en la figura siguiente inicio ME a Identificarse A yY fue Ma r Crear Partida Agea Sale j ta E Partida Y PrineraPartdae True MS NUES Recibir Mapa eid mal Y pee B Turno al o Y rir AA Anotar rosultado Temporizador on Y j movement Adversaro EJ Y L e p Estrategia MiniMax pow gt a 1 2 Decisiones de dise o El lenguaje elegido para implementar la soluci n es C por su paradigma orientado a objetos y por que genera un ejecutable m s r pido y robusto que en otros lenguajes A grandes rasgos se han dispuesto los siguientes mecanismos Se crea un hilo donde se lanza la b squeda mediante algoritmo MiniMax con poda Alfa Beta usando una b squeda en profundidad iterativa Cuando se acaba el tiempo abortamos la ejecuci n de dicho hilo alternativo y lo que tenemos es la ltima soluci n buena calculada que al haber hecho una b squeda en profundidad iterativa habremos llegado a la m xima profundidad para ese tiempo dado sin correr riesgos En cuanto a la
22. double long double 80 bits A typede typede typede typede typede typede typede typede typede 16 bits 32 bits 32 bits 64 bits signed char signed char signed char signed short signed short signed short signed int signed int signed int PESO ENERGIA PESO DISTANCIA COLINAS 0 3 PESO NBANDERAS COLINAS 0 6 FACTOR CORRECCION DISTANCIA 1 25 LIMITE LATERAL COLINAS 100 COLINAS 0 1 TMO1 999 TMO2 9999 ION_DISTANCIA_AGUA 6 PARA BANDERAS 0 5 fine PESO MAX EVAL PARA ENERGIA 0 1 fine PESO MAX EVAL PARA BARCA 0 05 fine PESO MAX EVAL PARA PALA 0 02 fine PESO MAX EVAL PARA PROFUNDIDAD 0 2 fine PESO MAX EVAL PARA HACHA 0 03 fine PESO MAX EVAL CONTRARIO 0 1 0 a 255 128 a 127 32 768 a 32 767 0 a 4 294 967 295 2 147 483 648 a 2 147 483 647 0 a 4 294 967 295 2 147 483 648 a 2 147 483 647 2 147 483 648 a 2 147 483 647 3 4 10 38 a 3 4 10 38 6 dec 1 7 10 308 a 1 7 10 308 15 dec 3 4 10 4932 a 1 1 10 4932 sint8 int8 uint8 sint16 int16 uintl6 sint32 int32 uint32 21 typedef typedef typedef signed long signed long signed long int sint64 int int64 int uint64 define define define define define int8_size 1 intl6_size 2 int32_size 4 int64_size 8 obj_ptr_size 8 endif 6 6 Client cpp lt Ice Ice h gt Client h Clases h Practica h Colores h Problema h lt math h gt lt sys time h gt lt pthread h gt lt semaphore h gt lt sys
23. e return true bool Casilla operator gt Casilla c if this gt numero gt c gt numero return true else return false bool Casilla operator gt Casilla c if this gt numero lt c gt numero return false else return true 15 J J K k k k K k k k k K k K K K YK k K kkk K K ck K ck K k K K kkk KOK Ck ck Ck K KOK kkk kkk kk kkk ck Ck kkk kk kk kk kk k KOK k k k kkk kk kkk kk k k k ck ck ck k k k k NODO J BRK RK kkk kkk kok kkk kkk kkk kkk kk RA kk kk k ck k k kk k kk ck k I k k k k k k k ck ck ck ck k k ckck ckck ck ck ck k ck ck ckck ck k ck ck ck ck k k ck ck kk ke e k Nodo Nodo Estado estado Nodo nodo padre int8 jugador int8 movimiento int16 costo intl6 profundidad float v this estado estado this gt nodo padre nodo padre this gt jugador jugador this gt v v this gt costo costo this gt profundidad profundidad this gt movimiento movimiento Nodo Nodo nodo_padre NULL delete estado void Nodo Print color_rojo cout lt lt endl lt lt WAAR e We eoe ha b a Sao AE kuk b ha ca SNE kosa h aa ALAR kash bo E esie Mes cout lt lt endl lt lt NODO Size lt lt int Size lt lt Bytes cout lt lt endl lt lt jugador lt lt int jugador lt lt movimiento lt lt int movimiento lt lt costo lt lt int costo lt lt profundidad lt lt int profundidad lt lt v lt lt float v estado gt Prin
24. eras dores Print Size operator operator operator operator operator Jugadores j lt Jugadores j gt Jugadores j lt Jugadores j gt Jugadores j vector lt Jugadores gt jugadores vector lt Jugadores gt contrarios vector Casilla casillas barca intl6 pala Estado int8 banderas vector Jugadores jugadores vector Casilla casillas Esta void int16 do Print Size bool EstaCogidaBandera int16 num bool EstaLibreCasilla int1l6 num sint8 Movimiento int8 jugador int8 mov void ActualizarCasilla intl6 numero int8 tipo bool bool bool bool bool class Nodo public operator operator operator operator operator Estado e lt Estado e gt Estado e lt Estado e gt Estado e Estado estado int16 costo profundidad 14 int8 movimiento jugador Nodo nodo_padre float v valor de utilidad Nodo Estado estado Nodo nodo_padre int8 jugador int8 movimiento int16 costo int16 profundidad float v Nodo void Print void Copiar Nodo nodo int16 Size bool operator Nodo n bool operator Nodo n bool operator lt Nodo n bool operator lt Nodo n bool operator gt Nodo n bool operator gt Nodo n y class Frontera private deque lt Nodo gt c int8 modo public Frontera int8 modo Frontera Nodo pop void push Nod
25. estado terminal 2 C lculo de los valores de la funci n de utilidad para cada nodo terminal 3 Calcular el valor de los nodos superiores a partir del valor de los inferiores Alternativamente se elegir n los valores m nimos y m ximos representando los movimientos del jugador y del oponente de ah el nombre de Minimax 4 Elegir la jugada valorando los valores que han llegado al nivel superior El algoritmo explorar los nodos del rbol asign ndoles un valor num rico mediante una funci n de utilidad empezando por los nodos terminales y subiendo hacia la ra z La funci n de utilidad definir lo buena que es la posici n para un jugador cuando la alcanza En el caso del ajedrez los posibles valores son 1 0 1 que se corresponden con ganar empatar y perder respectivamente En el caso del backgammon los posibles valores tendr n un rango de 192 192 correspondi ndose con el valor de las fichas Para cada juego pueden ser diferentes Poda Alfa Beta La poda Alfa Beta se basa en la idea de disponer de dos valores que conforman una ventana a la cual deben pertenecer los valores de la funci n eval n para que sean considerados En los nodos n MAX seg n el algoritmo minimax se debe maximizar el valor de los nodos sucesores En estos nodos se utiliza el par metro a n que determina el m ximo de los valores de los nodos sucesores encontrado hasta el momento As mismo como los nodos n MIN tratan de minimizar el valor de los
26. f2 s preferencia por estados con casillas de jugador de menos costo f3 s numero de banderas conseguidas f4 s profundidad de ese nodo 3 Pruebas El equipo sobre el que se han realizado las pruebas es el siguiente Software SO Ubuntu Gnu Linux 8 10 Kernel 2 6 27 7 Version 64 Bits Lenguaje de programaci n C amp STL amp ICE Runtime Hardware Procesador Intel Quad Core 2 4 Ghz Memoria 4 Gb 800 Mhz En una partida con un mapa normal se ha encontrado que llega a profundidad 8 A continuaci n una captura del juego mientras se esta Jugando B practica2lA final OpenOffice org Writer ej x JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador 1 Movimiento 1 Movimiento 2 Movimiento 2 Movimiento 1 Movimiento 1 Movimiento 2 Movimiento 2 Movimiento 1 Movimiento 1 Movimiento 6 gt Movimiento 5 gt Movimiento 6 gt Movimiento 3 gt Movimiento 5 gt Movimiento 6 gt Movimiento 5 gt Movimiento 1 gt Movimiento 3 gt Movimiento 3 gt Movimiento greenbite greenbite desktop Escritorio Practica2 IA o x Archivo Editar Ver Terminal Solapas Ayuda BanderasP2 ldesktop Escritorio Practica2 IA FINAL Exec Soy el jugador 1 realizado realizado realizado realizado reali
27. fundidad actual vector Nodo sucesores ector lt Nodo gt Sucesores Nodo nodo loat alphabeta Nodo nodo int depth float alfa float beta endif Fh lt Hh h Z ih F h O h h 25 6 8 Problema cpp include Problema h include Clases h include lt math h gt BOR KK KK RI SK SK SK SK SK SK SK SK RARA SK SK SK SK RARA RARA SK SK SK SK RARA kk Sk SK RARA RARA RARA K K K K K k k K KOK k k k k k k k k k k k k k k k k k kk ke K K VARIABLES GLOBALES oko CK kok kok kok A SK kok kok kok SK SK kok A SK A Mapa mapa Frontera frontera extern int8 njugadores nbanderas extern int16 ncasillas int nodos_creados 0 extern double tiempo_max extern vector lt int16 gt banderas numero int painprimir 0 int maxbanderas 0 extern int idUsuario BRR k k k KK k K k K k RK KK K K K k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k kk k k k k k MACROS Y ALGUNAS FUNCIONES TR RK K ck k K K K K K K K K K K ck K K K KOK K K KOK KOK KOK KOK ck ck Ck ck K KOK KOK KOK KOK KOR KOK k Ck ck ck KOK KOR OK KOK KOR OK KOK k k K ck ck KO KOK R KOR R KOR K RO R OR K RO k f define round x x lt 0 ceil x 0 5 floor x 0 5 float MIN float a float b if a lt b return a else return b float MAX float a float b if a gt b return a else return b double medicion tiempo struct timeval x struct timezone y getti
28. idaError e cout lt lt e reason lt lt endl if stremp argv 1 1 amp amp partida NULL jugarPartida dni partida autenticacion gt finalizarPartida dni password else if strcmp argv 1 2 ss partida NULL jugarPartida dni partida cout lt lt RECUPERANDO SEGUNDA PARTIDA lt lt endl sleep 5 jugarPartida dni partida autenticacion gt finalizarPartida dni password else if partida NULL cout lt lt ERROR El argumento introducido no es valido lt lt endl printHelp return 0 y int main int argc char argv Client c c main argc argv 6 7 Problema h ifndef PROBLEMA H define _ PROBLEMA H include Clases h include Client h include Ice Ice h include lt Practica h gt include list include iostream include queue include deque include vector include Colores h include time h include memory using namespace Practica using namespace std loat MIN float a float b loat MAX float a float b ouble medicion tiempo loat distancia casillas int16 cl int16 c2 bool tile nt16 SiguienteCasilla intl16 casilla int8 mov loat Eval Nodo nodo odo Busqueda Alfa Beta Mapa map Nodo nodo int profundidad max loat Max ValorAB Nodo nodo float alfa float beta int profundidad actual vector Nodo sucesores loat Min ValorAB Nodo nodo float alfa float beta int pro
29. int nodo_actual gt movimiento lt lt gt cout lt lt a profundidad lt lt int profundidad_actual bool devuelto partida jugada tablero idUsuario nodo actual gt jugador nodo_actual gt movimiento info token cout lt lt Movimiento realizado lt lt devuelto lt lt endl moviendo false else cout lt lt endl lt lt Nos hemos quedado sin sucesores fflush stdout cout lt lt endl lt lt A la desesperada nodo_actual nodo_de_reserva nodo actual Print for int i 0 i lt njugadores it t Estado e nodo actual gt estado e gt jugadores i gt energia 20 vector lt Nodo gt sucesores Sucesores nodo actual nodo_actual sucesores rand sucesores gt size cout lt lt Introduzca de nuevo el movimiento para salir del paso lt lt endl bool devuelto partida gt jugada tablero idUsuario nodo actual gt jugador nodo actual gt movimiento info token cout lt lt Movimiento realizado lt lt devuelto lt lt endl moviendo false for unsigned int i 0 i lt sucesores gt size i delete sucesores i delete sucesores catch Practica TokenIncorrectoError e cout lt lt e reason lt lt endl cout lt lt El temporizador ha expirado Has PERDIDO la partida lt lt endl jugando false moviendo false catch Practica MovimientoIncorrectoError e cout lt lt e reason lt lt endl cout lt lt Ha introducido
30. k k k k AS CALCULA LA SIGUIENTE CASILLA DADA LA ACTUAL Y UN MOVIMIENTO CK k lt k k k Kk k k K k K K K K k K K K Ck K K K KOK K K KOK KOK KOK KOK ck Ck ck ck kckckckckckck k k k KOK k k Ck ck Ck KOK KOK KOK KOK OR k k KOK KOK ck ck KO KOK R K R KOR R k ck ck KOR K RO k int16 SiguienteCasilla intl6 casilla int8 mov if mov 7 Se esta haciendo un desplazamiento int16 siguiente_casilla fila columna fila casilla mapa dimx if casilla mapa dimx 0 fila if casilla gt mapa dimx columna casilla fila 1 mapa dimx if columna 0 columna mapa dimx else columna casilla if casilla 2 1 casillas impares empezando por el 1 switch mov case 1 if fila 1 siguiente casilla mapa dimx mapa dimy mapa dimx casilla else siguiente casilla casilla mapa dimx break case 2 if casilla mapa dimx siguiente casilla mapa dimx mapa dimy mapa dimx else if fila 1 siguiente casilla mapa dimx mapa dimy mapa dimx casilla 1 else siguiente casilla casilla mapa dimx 1 break case 3 Siguiente casilla casilla 1 break case 4 if fila mapa dimy siguiente casilla mapa dimx mapa dimx mapa dimy casilla else siguiente casilla casilla mapa dimx break case 5 if casilla mapa dimx mapa dimy mapa dimx 1 siguiente casilla mapa dimx mapa dimy if columna 1 siguiente casilla casilla mapa dimx 1 else siguiente casilla casilla 1
31. mejor valoracion propia tenga es como si aplicamos colinas a los estados con el mismo valor minimax minV INFINITO for unsigned int i 0 i lt candidatos gt size i Eval candidatos i if candidatos i gt v lt minv accion candidatos i no_borrar i for unsigned int i 0 i lt candidatos gt size i if i no borrar delete candidatos i delete candidatos return accion float Max_ValorAB Nodo nodo float alfa float beta int profundidad_actual vector lt Nodo gt sucesores nodo gt v INFINITO vector lt Nodo gt sucesores next bool clear false if profundidad_actual 1 sucesores NULL Eval nodo else for unsigned int i 0 i lt sucesores gt size i sucesores_next Sucesores sucesores i if sucesores_next NULL nodo gt v MAX nodo gt v Min_ValorAB sucesores i alfa beta profundidad actual 1 sucesores next if nodo gt v gt beta clear true break alfa MAX alfa nodo v for unsigned int i 0 i lt sucesores next gt size i delete sucesores_next i delete sucesores_next if clear 28 for unsigned int i 0 i lt sucesores next gt size i delete sucesores_next i delete sucesores_next return nodo gt v float Min_ValorAB Nodo nodo float alfa float beta int profundidad_actual vector lt Nodo gt sucesores nodo gt v INFINITO vector lt Nodo gt suceso
32. meofday amp x amp y return x tv_sectx tv_usec 1000000 0 BRK RK kk kkk K K k k k k k k k k k KKK k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k ck k k k k k k k k K k k k k k k ck ck K k k k k k k ck k k ck k ck ck ck ck k k FUNCIONES HEURISTICAS DE A Y ASCENSI N COLINAS KK kok kok kok kok kok kok kok kok kok kok kok kok kok kok k k k k kok k k kok kok k k k k k k k k k k k k k k k k k k kkk kk kk kk kk kk kk kk kk kk kkk kkk float distancia_casillas int16 cl int16 c2 bool tile if cl c2 return 0 else if abs cl c2 1 return 1 else int16 fila_cl columna_cl fila_c2 columna_c2 dif_x dif_y fila_cl cl mapa dimx if cl mapa dimx 0 fila cl if cl gt mapa dimx columna_cl cl fila_cl 1 mapa dimx if columna_cl 0 columna_cl mapa dimx else columna_cl c1 fila_c2 c2 mapa dimx if c2 mapa dimx 0 fila_c2 if c2 gt mapa dimx columna_c2 c2 fila_c2 1 mapa dimx if columna_c2 0 columna_c2 mapa dimx else columna_c2 c2 dif x abs fila cl fila c2 if tile if fila cl gt fila c2 if mapa dimy fila_cl fila_c2 1 dif x dif x mapa dimy fila cltfila c2 1 if fila_cl lt fila_c2 if fila_cl mapa dimy fila_c2 1 lt dif_x dif_x fila_cl mapa dimy fila_c2 1 dif_y abs columna cl columna c2 if tile if columna cl columna c2 26 if mapa dimx columna_cl columna_c2 1 dif x dif y
33. nt8 mov int8 int8 EstaCogidaBandera num int16 bool EstaLibreCasilla num int16 bool ActualizarCasilla numero int16 tipo int8 void operator e Estado bool operator lt e Estado bool operator gt e Estado bool operator e Estado bool operator gt e Estado bool id int8 casilla int16 hacha int16 i i tipo inte si punteros int16 pala int16 energia int16 Sizel int16 punteros int16 Print void Size int16 operator c Casilla bool Moss nd operator lt c Casilla bool c i gt operator j Jugador bool operator gt c Casilla boo 4 operator lt c Casilla bool operator lt j Jugador bool hla uersa xag aale Dsi operator gt c Casilla bool operator j Jugador bool operator gt j Jugador bool numero int16 2 Soluciones te ricas 2 1 Breve explicaci n de los algoritmos utilizados poda Alfa Beta Minimax Es un m todo de decisi n para minimizar la p rdida m xima esperada en juegos con adversario y con informaci n perfecta Minimax es un algoritmo recursivo El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escoger el peor para ti Pasos del algoritmo Minimax 1 Generaci n del rbol de juego Se generar n todos los nodos hasta llegar a un
34. o 5 2 Ejecuci n de la pr ctica Para jugar una partida individual debemos hacerlo de la siguiente forma Debemos abrir 2 terminales diferentes donde tenemos el ejecutable y ejecutar en cada uno de ellos la siguiente orden BanderasP2 1 Para jugar una partida contra contrincante lo haremos de la siguiente forma Abrimos un nico termina donde tenemos el ejecutable y cuando la partida est creada en el servidor ejecutamos la orden BanderasP2 2 12 6 C digo Fuente 6 1 Makefile CXXFLAGS 1 I usr lib lm lpthread SLICOMPILER slice2cpp fcuando no queramos modo debug dejamos vac o el valor de esta variable DEBUG Wall OPTIMIZACIONES 03 mmmx msse msse2 msse3 SLICEFLAGS I usr share slice output dir PROGRAMNAME Client EDITOR gedit COMP ILADOR g all S PROGRAMNAME PROGRAMNAME Practica cpp Practica o Problema o Clases o Client o Colores o S COMPILADOR OPTIMIZACIONES S DEBUG Practica o Problema o Clases o Client o Colores o o S PROGRAMNAME lIce CXXFLAGS Practica cpp Practica ice S SLICOMPILER Practica ice SLICEFLAGS Client o Client cpp Client h COMPILADOR OPTIMIZACIONES DEBUG c Client cpp o Client o CXXFLAGS Practica o Practica cpp Practica h COMPILADOR OPTIMIZACIONES DEBUG c Practica cpp o Practica o CXXFLAGS Problema o Problema cpp Problema h COMPILADOR OPTIMIZACIONES DEBUG c Problema cpp o Problema o CX
35. o gt movimientot3 6 amp amp accion i 7 continue copiar el estado del padre y modificarlo a partir de la copia Estado e try e new Estado nodo estado banderas amp nodo estado jugadores amp nodo gt estado gt casillas catch std bad_alloc cout lt lt endl lt lt No hay disponible memoria para crear m s instancias de Estado exit 1 energia antes e gt jugadores jugador j gt energia resultado de hacer que el jugador j haga el movimiento i resultado e Movimiento jugador jl accion i energia despues e jugadores jugador j l energia Calculo del costo basado en la energia del jugador delta energia energia antes energia despues if delta energia lt 0 costo nodo costo else costo nodo costo delta energia comprobaci n de que no hemos pasado ya por esa casilla Nodo puntero padre nodo k nodo gt profundidad veces 0 while k gt 0 hasta que nos encontremos con la raiz subimos comprobando if puntero padre gt jugador j 1 if puntero padre gt estado gt jugadores j gt casilla e gt jugadores jugador j gt casilla veces if veces gt MAX REPETIR CASILLA resultado ERROR break puntero_padre nodo gt nodo_padre 27 si es un movimiento que se puede hacer entonces es un nodo hijo y se agrega a sucesores if resultado ERROR nodos_creados nodos_internos e gt banderas e gt bande
36. o nodo unsigned int size void Print J endif 6 4 Clases cpp include Clases h include Problema h extern Mapa mapa extern int8 njugadores define round x x 0 ceil x 0 5 floor x 40 5 J BRK k k K k k k k K kkk kkk K K K K K ck ck ck ck K K K KOK K kk ck ck Ck Ck ck k k k KOK K k k kk kk ck ck ck Ck ck k k KOK K k k k kk k k k k k ck ck k k KK K KOK ck k k k ck ck ck ck ck kk CASILLA S BRK RK Ck k k k k k k kk k k RARA RARA kk kk k k kk kk kk ck kk ke kk Ck RR kc k kc RA TK SK K K ck ck ckck ckck ckck ck ck ck ck ck ck ck ck ck ck ck ck ck ck ck ck ck ok ke e K Casilla Casilla int16 numero int8 tipo this numero numero this gt tipo tipo punteros 1 Casilla Casilla void Casilla Print color verde Gout e endl lt lt D StS m P 7 Pa o S ITI TP cout lt lt endl lt lt CASILLA T cout lt lt endl lt lt numero lt lt int numero 1 lt lt tipo lt lt int tipo Contras seri S Mi A A color normal int16 Casilla Size return sizeof int8 sizeof int16 2 sizeof Casilla bool Casilla operator Casilla c if numero c gt numero ss tipo c gt tipo return true else return false bool Casilla operator lt Casilla c if this gt numero lt c gt numero return true else return false bool Casilla operator lt Casilla c if this gt numero lt c gt numero return false els
37. o actual Jugadores Jugador 1 Posicion Ficha 107 Energia 18 P H B 000 Jugador 2 Posicion Ficha 63 Energia 24 P H B 000 Jugador 3 Posicion Ficha 41 Energia 26 P H B 000 Jugador 4 Posicion Ficha 88 Energia 20 P H B 0019 Estad General Energia 88 Banderas J1 1 9 Y la conclusi n del mismo con un ganador a2lA final OpenOffice org Writer Ver Inteligencia Artificial Panel de Administracion Mozilla Firefox Historial Marcadores Herramientas Ayuda 6 http obi wan inf cr uclm es 44080 parte2 index php u 56981688p bENUdAowTwKc FENBITEblog Administracion FeedBurner EjFeedw Analytics W StatCounter G Adwords AdSense Pwebmas Bienvenido a Nick Yo GREENBITE y cliente HAL9000 Des Inteligencia Artificial e Ingenier a del Conocimiento urso 200 Juego de la Bandera conectar de Inform tica Univ Castilla La Manch Partida Ranking Mis Datos artida Activa Partida finalizada desde el cliente ICE ar M Esperando ejecuci n del cliente No se ha detectado conexi n de cliente ICE Escuela Superior de Inform tica Universidad de Castilla La Mancha 3 greenbite greenbite desktop Escritorio Practica2 IA 0 x Arc Archivo Editar Ver Terminal Solapas Ayuda JUGADA Jugador 1 Movimiento 1 Movimiento realizado 1 Al JUGADA gt Jug
38. o inicial new Estado 0 6 jugadores amp casillas crear nodo inicial Nodo raiz new Nodo estado inicial NULL 0 0 0 0 INFINITO nodo_actual raiz while jugando bool moviendo true Practica InfoJugada info partida pedirTurno tablero idUsuario if info resultado 0 if info resultado 1 cout lt lt Has GANADO lt lt endl nodo_actual gt Print jugando false moviendo false elsel cout lt lt Has PERDIDO lt lt endl nodo actual Print jugando false moviendo false actualizar la informaci n del contrario if info mov idJugador 1 if idUsuario 1 Estado e nodo_actual gt estado e gt Movimiento info mov idJugador 1l info mov mov else Estado e nodo actual gt estado e gt Movimiento info mov idJugador 1 njugadores info mov mov break while moviendo if a_la_desesperada profundidad_actual 2 crear hilo pthread create amp hilo NULL void amp ejecucion hilo void NULL dormir sleep tablero tiempo sleep_time destruir hilo pthread_destroy amp hilo coger ultima solucion 23 nodo_de_reserva nodo_actual pthread mutex lock amp mutex nodo actual nodo solucion pthread mutex unlock amp mutex else nodo_actual NULL try if nodo actual NULL cout lt lt endl lt lt JUGADA gt Jugador lt lt int nodo actual jugador lt lt Movimiento lt lt
39. pala 0 hacha 0 barca 18 N REDE RED R RA RA Ne a N CASTELA numero 70 tipo 1 CASILLA numero 86 tip ANN ENS ENS ENS CNANANANANANANANA RN 222 MURS lt P gina 8 29 Predeterminado E gt Espa ol Espa a 100 INSERT STD 10 4 Conclusiones Podemos quedarnos con la idea de que tomar decisiones ptimas en juegos que est n limitados en tiempo es una tarea bastante complicada El algoritmo MiniMax nos permite trabajar con este tipo de problemas y si adem s utilizamos poda Alfa Beta podremos bajar mucho m s en el rbol de b squeda lo que significa calcular movimientos m s inteligentes Por otro lado el dise o de una heur stica acertada y que permita una ejecuci n r pida nos permitir tambi n bajar mas a n en el rbol de b squeda y que nuestro bot inteligente pueda mirar m s lejos a la hora de planificar un movimiento Como conclusi n decir que para la resoluci n correcta de este tipo de problemas es importante elegir un lenguaje que permita un nivel de optimizaci n alto pero el punto cr tico sin duda es el dise o de una heur stica que sea buena 11 5 Manual de usuario 5 1 Configuraci n Primero debemos compilar el programa lo cual es bastante sencillo entramos en el directorio donde est el c digo fuente y compilamos de la siguiente forma make Esto generara un ejecutable y adem s tenemos un script de shell BanderasP2 para hacer m s sencillo su us
40. ras resultado Nodo hijo try if idUsuario 1 hijo new Nodo e nodo jugador 3 1 accion il sint16 costo nodo gt profundidad 1 INFINITO else hijo new Nodo e nodo Jugador 3j 1 njugadores accion i sint16 costo nodo gt profundidad 1 INFINITO catch std bad_alloc cout lt lt endl lt lt No hay disponible memoria para crear mas instancias de Nodo exit 1 Eval hijo S push back hijo else delete e if s gt size gt 0 return s else delete s return NULL S EKK k k k KK k k k k k k k k RK k k k k k k k k k k k k k k k k k KOK K K K k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k ck k ck ck ck k k k BUSQUEDA ALFA BETA ok kok kok kok kok kok K K kok kok kok kok kok kok kok kok kok kok kok kkk A Nodo Busqueda Alfa Beta Mapa map Nodo nodo int profundidad max Nodo accion NULL mapa map unsigned int no borrar 0 float minV vector Nodo sucesores Sucesores nodo vector lt Nodo gt candidatos new vector lt Nodo gt if sucesores NULL float v Max_ValorAB nodo INFINITO INFINITO profundidad max sucesores for unsigned int i 0 i lt sucesores gt size i if v sucesores i gt v candidatos gt push_back sucesores i else delete sucesores i delete sucesores de los nodos que tenemos con el mismo valor minimax elegiremos el que
41. res next bool clear false if profundidad_actual 1 sucesores NULL Eval nodo else for unsigned int i 0 i lt sucesores gt size i sucesores_next Sucesores sucesores i if sucesores_next NULL nodo gt v MIN nodo v Max ValorAB sucesores i alfa beta profundidad actual 1 sucesores next if nodo gt v lt alfa clear true break beta MIN beta nodo gt v for unsigned int i 0 i lt sucesores next gt size i delete sucesores_next i delete sucesores_next if clear for unsigned int 1 0 i lt sucesores_next gt size 1 delete sucesores_next i delete sucesores_next return nodo gt v BRR k k KK k K k K k K k k RR K KOK k k K k k K k k k ck ck Ck Ck KOK kckckckckckck k k k k k k k k k k KK k k k k k k k k k k k k k k k k k k k k k k k k k kk k k k k k FUNCI N DE EVALUACI N KKK kok kok kok kk kok kok kok k k kok k k kok kok kok k k kok kok kok kok kok kok k k k k kk k k k kk kkk kok kok kkk kkk kkk kkk kkk kkk kkk kkk kkk float Eval Nodo nodo float valuel 0 value2 0 value3 0 value4 0 distancia minima distancia unsigned int bandera_eliminar 0 jugador_cambiar 0 vector lt int16 gt b new vector lt intl6 gt vector lt intl6 gt j new vector lt intl6 gt for int i 0 i lt njugadores it afiado los jugadores j push back nodo gt estado gt jugadores i gt casilla for int i 0 i lt nbanderas it
42. signal h gt include include include include include include include include include include include bool devuelto int val i idUsuario profundidad actual 2 sleep time 1 do sleep 0 int8 njugadores 0 nbanderas 0 int16 ncasillas 0 pthread_t hilo pthread_mutex_t mutex vector lt int16 gt banderas_numero int tiempo_max 0 delta_t 2000 using namespace std using namespace Practica Nodo nodo_solucion NULL nodo actual nodo de reserva Practica Mapa tablero bool a la desesperada false void ejecucion hilo void p Nodo n while 1 n Busqueda Alfa Beta tablero nodo_actual profundidad_actual pthread mutex lock amp mutex nodo solucion n pthread mutex unlock amp mutex class Client virtual public Ice Application void printHelp cout lt lt AnEjecucion del cliente para las practicas de IA lt lt endl cout lt lt Para jugar una partida individual ejecutar dos instancias del programa con la linea Client 1 Ice Config Ruta Archivo config n lt lt endl cout lt lt Para jugar una competicion ejecutar una instancia del programa con la linea Client 2 Ice Config Ruta Archivo config n endl Esperar a que el oponente se una a la partida n n lt lt void jugarPartida string dni Practica PartidaPrx partida FILE fich if fich char cadaux MAXLINEA fopen Configuracion r cout lt lt endl lt lt
43. t color_rojo cout lt lt endl lt lt color normal int16 Nodo Size return estado gt Size sizeof int16 2 sizeof int8 2 sizeof Nodo sizeof Nodo sizeof Estado Mk ee k esee eee e RARA I ARR RR AAR ARR CCAR eee e sese sek eek eoe EE Mis bool Nodo operator Nodo n if this gt profundidad n gt profundidad return false else if this costo n costo return false else if this movimiento n movimiento return false else if this jugador n jugador return false else if this estado n gt estado return false else return true Cuidado usados para ordenar A bool Nodo operator Nodo n return this gt v n gt v bool Nodo operator lt Nodo n if this gt v lt n gt v return true else return false bool Nodo operator gt Nodo n if this gt v gt n gt v return true else return false bool Nodo operator gt Nodo n if this gt v gt n gt v return true else return false bool Nodo operator lt Nodo n if this gt v lt n gt v return true else return false J BRK k k k KKK k kk RR K K K K K K KOK RK KKK KOK kkk kkk kk kkk kkk kkk kkk kkk kkk kkk kk kkk kk kkk kkk kkk k ESTADO J BRK RK KK Ck kk kk kk kkk kkk kkk kkk kkk kkk kkk kkk k kk k k k k k k k k k k k k k k k k k k k k k k k k k ck ck ckck ckck ck ck
44. tera pop Nodo nodo switch modo case COLA_FIFO nodo c gt front c gt pop front break case COLA LIFO nodo c back c pop back break case COLA ORDENADA nodo c gt front c gt pop front break 19 y return nodo void Frontera push Nodo nodo switch modo case COLA_FIFO c gt push back nodo break case COLA LIFO c push back nodo break case COLA ORDENADA unsigned int size c gt size if size gt 0 primer elemento if nodo lt c gt front c gt push_front nodo ultimo elemento else if nodo gt c gt back c gt push_back nodo else en medio if size lt CAMBIO_ALGORITMO1 Algoritmo para n pequefio std deque lt Nodo gt iterator i float fup fdown fup c gt back gt v nodo gt v fdown nodo v c gt front gt v if fdown lt fup i c gt begin int j c gt size while nodo gt 1 amp amp 3 gt 0 i c insert i nodo else i c end 1 int j c gt size while nodo lt i ss 350 i p od c insert i 1 nodo else Algoritmo para n grande std deque lt Nodo gt iterator inicio fin medio i inicio c gt begin fin c gt end 1 medio inicio fin inicio 2 i medio while medio fin amp amp medio inicio amp amp nodo zu ET if nodo gt medio inicio medio fin fin medio inicio fin inicio 2
45. zado realizado realizado realizado realizado realizado Hitar Ver Historial Marcadores Herramientas Ayuda Inteligencia Artificial Panel de Administracion Mozilla Firefox k g D http obi wan inf cr uclm es 44080 parte2 index php u 56981688 p bENUdAowTwKc v G v GREENBITEblog Administracion FeedBurner EjFeedw Analytics StatCounter Inteligencia Artificial e Ingenieria del Conocimiento ja Bandera La Mancha J JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador JUGADA gt Jugador 4 Movimiento 3 Movimiento 4 Movimiento 3 Movimiento 4 Movimiento 4 Movimiento 3 Movimiento 4 Movimiento 4 Movimiento Archivo Editar Ver Terminal Solapas Ayuda greenbite greenbite desktop Escritorio Practica2 IA FINAL Exec BanderasP2 1 Soy el jugador 2 3 gt Movimiento 4 gt Movimiento 6 gt Movimiento 6 gt Movimiento 2 gt Movimiento 6 gt Movimiento 3 gt Movimiento 3 gt Movimiento 4 gt Movimiento realizado realizado realizado realizado realizado realizado realizado realizado realizado zi desde obi wan inf cr uclm es GJAdwords AdSense Webmas Bienvenido a Nick Yo GREENBITE y cliente HAL9000 Desconectar Ranking Mis Datos Partida Estad

Descargar PDF con la memoria de la practica

Contents

Download Pdf Manuals

Related Search

Related Contents