:namespace prefix = o /> Implementación del Algoritmo Minimax para el juego de Damas Chinas Integrantes José Miguel Jiménez Henry F. Montalván Fernanda M. Soto Ma. Del Cisne Torres Facultad de Ciencias de :namespace prefix = st1 />la Computación Universidad Técnica Particular de Loja Ecuador Febrero, 2007 Implementación del Algoritmo Minimax para eljuego de Damas Chinas Objetivos. Implementar un agente inteligente en el juego. Aplicar la programación paralela con MPI (Message Passing Interface). Desarrollo. Existen varias formas o versiones del juego de damas chinas, en el presenteproyecto trabajamos con el tablero del Ajedrez y con 12 fichas para cadajugador. A continuación describimos las instrucciones del juego y el diagrama deflujo de dichas instrucciones: Instrucciones del juego de damas chinas 1. Una ficha puede moverse y saltarsolo para adelante diagonalmente. 2. Una reina puede moverse y saltarpara ambos lados diagonalmente: adelante y atrás. 3. Una reina puede moversediagonalmente todos los casilleros que pueda. 4. Una ficha que llega arriba, a la filainicial del oponente se convertirá en reina. 5. Si una ficha puede saltar sobrela ficha de su oponente, el salto debe ser hecho. Es necesario realizar el salto doble cuandoel salto es posible. Así la regla es: Una pieza no puede realizar otromovimiento diferente al salto si posee un salto disponible. Diseño del agente inteligente Percepciones: Estados de losmovimientos en el tablero, que representa la situación del tablero de damas conlas fichas y posiciones codificadas. Acciones: Movimiento de unaficha (izquierda adelante, derecha adelante, izquierda atrás, derecha atrás,doble salto comer varias veces). Metas: Estado final,eliminación de la mayor cantidad de fichas del adversario. Para cada eleccióndel mejor movimiento del agente inteligente el estado meta será aquella jugadaque elimine o tenga mas posibilidades de eliminar una ficha de su adversario. Ambiente: Posición de las fichas,representado por el tablero de damas codificado. Tipo de agente: Agente basado en metas,se basa en el uso de la búsqueda y planificación para encontrar la acción atomar de manera que permita alcanzar la meta del agente inteligente que en estecaso es la eliminación de fichas del adversario. Características del medio ambiente: Es accesible, determinista, estático y discreto. Medida de rendimiento Numero de fichas del adversario eliminadas. Número de fichas del agente inteligente eliminadas. Forma de Búsqueda a utilizar Búsqueda heurística con contrincante, para el espacio de estados deltablero generados con la aplicación de los operadores a cada una de las fichasdel agente inteligente. Búsqueda con contrincante Problema: ganar un juego contra un oponente. El juego implica actuación alterna de dos jugadores. Juego de suma cero: la victoria de uno indica la derrota del otro. Se conoce los posibles movimientos de cada jugador. Se conoce el movimiento del contrincante. Se desconoce la estrategia del contrincante. No interviene el azar. Se pueden especificar las situaciones de victoria, derrota y empate. El grafo del juego representa todos los posibles movimientos del juego,para nuestro caso el grafo contiene aproximadamente 1040 nodos. Dentro de los tipos de búsqueda heurística con contrincante se encuentra elalgoritmo Minimax, el mismo que será implementado con DFS. Algoritmo Minimax En el algoritmoMinimax, los dos jugadores se representan como Max y Min, Max intentaramaximizar el resultado del juego, mientras que Min intenta minimizarlo. Funcionamientodel algoritmo Construir el árbol de búsqueda a partir de la posición inicial hasta la profundidad máxima posible. Se utiliza una función de evaluación estática para evaluar cada hoja del árbol construido. Propagar los valores de los nodos desde abajo hacia arriba; en cada nodo si Max juega, el valor del nodo hijo con el máximo valor es tomado y propagado hacia el padre; si Min juega, el nodo hijo con el menor valor es tomado por el padre. Algoritmo DFS Recorrido en profundidad DFS - Depth FirstSearch, es un algoritmo que permite recorrer todos los nodos de un grafo demanera ordenada, pero no uniforme. Su funcionamientose basa en ir expandiendo cada uno de los nodos que va localizando, de manerarecursiva, recorriendo todos los nodos de un camino concreto. Cuando ya no existenmás nodos por visitar en este camino, regresa hacia atrás (backtracking), detal manera que comienza el mismo proceso con cada uno de los hermanos del nodoya procesado. Pseudocódigo DFS DFS(grafo G) for each vertice u ∈ V[G]do estado[u]=NO_VISITADO padre[u]= NULL tiempo=0 for each vertice u ∈V[G]do if estado = NO_VISITADO then DFS-Visitar(u) DFS-Visitar(nodo u) estado[u]=VISITADO tiempo=tiempo+1 d=tiempo foreach v ∈ Vecinos[u] do ifestado[v]=NO_VISITADO then padre[v]=u DFS-Visitar(v) estado[u]=TERMINADO tiempo=tiempo+1 f=tiempo Arcos DF Si en tiempo de u tenemos el arco(u,v): Si v estáNO_VISITADO, entonces (u,v) ∈ DF. Si v estáVISITADO, entonces (u,v) es un arco hacia atrás. Si v estáTERMINADO, entonces (u,v) es un arco de cruce o arco hacia delante. Seráde cruce si d[v]d[v] Programación Paralela con MPI MPI es un estándar de programación en paralelo mediantepaso de mensajes que permite crear programas portables y eficientes. Características deMPI Interfaz genérica quepermite una implementación optimizada en cualquier sistema paralelo. Es una biblioteca queincluye interfaces para FORTRAN, C y C++. Define varias formasde comunicación lo que permite programar de manera natural cualquier algoritmo en paralelo. Esta pensado para crearbibliotecas paralelas. Programación Básica en MPI La programaciónusando MPI es distinta a la programación de un código serial, existen factoresnuevos que debemos tener en cuenta. Estructurade un Programa MPI Se debe incluir lalibrería . Se debe inicializary terminar MPI con las funciones MPI_Init y MPI_Finalize respectivamente. El código entreestas llamadas será ejecutado simultáneamente por todos los procesadores. Comunicadores MPI trabaja con un comunicador básico MPI_COMM_WORLD que contiene a todos los procesos. Un comunicador corresponde a un grupo deprocesos sobre el que se realiza la comunicación. Dentro de un comunicador cada proceso tieneun rango que lo identifica. Existen funciones que nos permiten saber elrango y el número de procesos dentro de un comunicador. FuncionesBásicas de Comunicación La forma de comunicación en MPI es a travésde mensajes que contienen datos. La forma mas simple es la comunicación puntoa punto, donde se envía un mensaje de un proceso a otro. Esto se realiza usandolas funciones MPI_Send y MPI_Recv. CódigoBásico en C #include #include int main(int argc,char **argv){ int rank,size; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&size); MPI_Comm_rank(MPI_COMM_WORLD,&rank); printf("Hola mundo, Este es el rango %d de%d",rank,size); if(rank==1){ double data=3.14; MPI_Send(&data,1,MPI_DOUBLE,0,27,MPI_COMM_WORLD); } if(rank==0){ double data; MPI_Recv(&data,1,MPI_DOUBLE,1,MPI_ANY_TAG, MPI_COMM_WORLD,MPI_STATUS_IGNORE); printf("El rango 0 dice %g",data); } MPI_Finalize(); return 0; } Variables y funciones de MPI utilizadas. Nuestro trabajo se va dividir en dos procesos, uno para elanálisis del movimiento del jugador humano y otro para el análisis delmovimiento del agente inteligente. Dentro de la función principal asignamos las siguientesvariables y las respectivas funciones para el entorno de MPI: int id; /*IDENTIFICADOR DELPROCESO*/ intnumprocs; /*NUMERO DE PROCESOS*/ charnombreproc [MPI_MAX_PROCESSOR_NAME]; /*NOMBRE DELPROCESADOR*/ intlnombreproc; /*LONGITUD DEL NOMBRE DEL PROCESADOR*/ longnumjugadores_total; /*NUMERO DE JUGADORES TOTALES*/ longnumjugadores_local; /*NUMERO DE JUGADORES PORPROCESO*/ doubletmpinic = 0.0; /*TIEMPO INICIAL DE EJECUCIÓN*/ doubletmpfin; /* TIEMPO FINAL DE EJECUCIÓN*/ /*INICIALIZACIÓNDEL ENTORNO DE EJECUCIÓN MPI*/ MPI_Init(&argc, &argv); /*ALMACENA ELIDENTIFICADOR DEL PROCESO*/ MPI_Comm_rank(MPI_COMM_WORLD,id); /*ALMACENA EL NÚMERODE PROCESOS*/ MPI_Comm_size(MPI_COMM_WORLD,numprocs); /*E/S: NOMBRE DEL PROCESADOR*/ MPI_Get_processor_name(nombreproc,lnombreproc); /* DIVISIÓN DELNÚMERO DE JUGADORES PARA EL NÚMERO DE PROCESOS*/ if (id==0) /*PROCESO 0*/ { numjugadores_local=numjugadores_total/numprocs; /*DISTRIBUCIÓN DE DATOS*/ /*ENVIO*/ MPI_Isend(MPI_COMM_WORLD, id , numprocs, numjugadores_local); } else { /*RECEPCIÓN*/ MPI_Irecv(MPI_COMM_WORLD, id, numprocs,numjugadores_local); } Herramienta DeinoMPI Para la implementación de MPI utilizamos la herramienta DeinoMPI. DeinoMPI es una puesta en práctica delestándar MPI-2 para Microsoft Windows derivado originalmente de la distribuciónMPICH2 del Laboratorio Nacional de Argonne. Requisitos de software: Windows 2000 /XP/Server 2003 .NET Framework 2.0 Configuración En la pestaña Credential Store crear una llave o credencial y exportarla a los demás equipos del clúster. En la pestaña Cluster se definen los equipos que pertenecen al clúster. En Domain seleccionar el Grupo de trabajo en el que se encuentran los equipos, luego seleccionar el botón Get host names para que los detecte. En la pestaña Mpiexec se define la aplicación sobre la que se va a trabajar, el número de procesos en la que vamos a dividirla. Para iniciar la ejecución seleccionar el botón Execute. La pantalla del Deino nos presenta el procesamiento paralelo que se esta ejecutando.
