23
TPE 1 - Sistemas TPE 1 - Sistemas de Producción: de Producción: Rolling Cubes Rolling Cubes Sistemas de Inteligencia Sistemas de Inteligencia Artifcial Artifcial Bergez, Brasca y García Bergez, Brasca y García

TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Embed Size (px)

Citation preview

Page 1: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

TPE 1 - Sistemas de TPE 1 - Sistemas de Producción: Producción:

Rolling CubesRolling Cubes

Sistemas de Inteligencia Sistemas de Inteligencia ArtifcialArtifcial

Bergez, Brasca y GarcíaBergez, Brasca y García

Page 2: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Introducción - RepresentaciónIntroducción - Representación

Tablero 3x3 – Matriz 3x3Tablero 3x3 – Matriz 3x3 Cubos mitad negros mitad blancos y Cubos mitad negros mitad blancos y

vacío en el centro – Distintas fichas.vacío en el centro – Distintas fichas.

Page 3: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Introducción - ReglasIntroducción - Reglas

Rotar los cubos si es posible en las 4 Rotar los cubos si es posible en las 4 direcciones. (8 cubos * 4 direcciones. (8 cubos * 4 movimientos = 32 reglas/estado)movimientos = 32 reglas/estado)

Mover el espacio blanco y cambiar la Mover el espacio blanco y cambiar la ficha por al correspondiente (1 ficha por al correspondiente (1 blanco * 4 movimientos = 4 blanco * 4 movimientos = 4 reglas/turno). Se utiliza tabla de reglas/turno). Se utiliza tabla de transformación de ficha.transformación de ficha.

Page 4: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Introducción - EstadosIntroducción - Estados

Estado Inicial:Estado Inicial:

Estado Objetivo:Estado Objetivo:

Aleatorio: Aleatorio:

Page 5: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Función de CostoFunción de Costo

La función de costo siempre suma 1 La función de costo siempre suma 1 a cada regla aplicada, ya que en este a cada regla aplicada, ya que en este tipo de juegos, todas las reglas tipo de juegos, todas las reglas demandas el mismo costo.demandas el mismo costo.

Page 6: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

SimetríasSimetrías

Simetrías en las 4 direcciones. Se Simetrías en las 4 direcciones. Se implementó en el método implementó en el método equalsequals..

Reduce el factor de ramificación pero Reduce el factor de ramificación pero aumenta el procesamiento.aumenta el procesamiento.

Ejemplo de primeros nodos:Ejemplo de primeros nodos:

Page 7: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

HeurísticasHeurísticas

3 heurísticas desarrolladas:3 heurísticas desarrolladas: - Nula: Caso para no utilizar ninguna.- Nula: Caso para no utilizar ninguna. - Posiciones incorrectas.- Posiciones incorrectas. - Manhattan mejorada.- Manhattan mejorada.

Page 8: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Heurísticas – Posiciones Heurísticas – Posiciones IncorrectasIncorrectas

Cada posición que no está en blanco Cada posición que no está en blanco o si el blanco está en el centro o si el o si el blanco está en el centro o si el vacío no está en el medio suma 1 al vacío no está en el medio suma 1 al costo de la solución.costo de la solución.

Ejemplos: Ejemplos:

H = 6 H = 6 H = 8 H = 8

Page 9: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Heurísticas – Manhattan Heurísticas – Manhattan mejoradamejorada

Cuando una ficha horizontal o Cuando una ficha horizontal o vertical se encuentra en el borde del vertical se encuentra en el borde del tablero y es imposible obtener un tablero y es imposible obtener un blanco con un movimiento se le blanco con un movimiento se le asigna el costo de 5 movimientos.asigna el costo de 5 movimientos.

Cuando hay una negra en el centro Cuando hay una negra en el centro se le asigna el costo de 6 se le asigna el costo de 6 movimientos y en otro lugar del movimientos y en otro lugar del tablero 4.tablero 4.

Page 10: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Heurísticas – Manhattan Heurísticas – Manhattan mejoradamejorada

Cuando hay una blanca en el centro, Cuando hay una blanca en el centro, se le asigna el costo de 6 se le asigna el costo de 6 movimientos ya que debe moverse movimientos ya que debe moverse varias veces para volver a ser blanco varias veces para volver a ser blanco en otra posición.en otra posición.

Al vacío se le asigna 0 y a las blancas Al vacío se le asigna 0 y a las blancas en posición distinta del centro en posición distinta del centro también.también.

Page 11: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

MotorMotor

Motor de inferencia genérico.Motor de inferencia genérico. Entrada: Problema y método de Entrada: Problema y método de

resolución.resolución. Salida: Respuesta según problema Salida: Respuesta según problema

(Solución si es hay alguna).(Solución si es hay alguna). Utiliza el algoritmo de listas de nodos Utiliza el algoritmo de listas de nodos

abiertos y cerrados.abiertos y cerrados.

Page 12: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Motor – Estructura de NodoMotor – Estructura de Nodo

Nodo ancestro: Una referencia al Nodo ancestro: Una referencia al padre, para poder rastrear y padre, para poder rastrear y reconstruir el camino de ser reconstruir el camino de ser necesario.necesario.

Regla: La regla que se utilizó para Regla: La regla que se utilizó para transformar al padre en este nodo.transformar al padre en este nodo.

Estado: El estado del tablero Estado: El estado del tablero generado.generado.

Page 13: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Motor – Estructura de NodoMotor – Estructura de Nodo

Nivel: El nivel de profundidad.Nivel: El nivel de profundidad. Costo: El costo hasta ese nodo.Costo: El costo hasta ese nodo. Heurística: El resultado de la función Heurística: El resultado de la función

heurística de haber una.heurística de haber una. Función f: La suma entre la heurística Función f: La suma entre la heurística

y el costo, utilizada en los métodos y el costo, utilizada en los métodos A*.A*.

Page 14: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Motor - ConfiguraciónMotor - Configuración

El motor se configura mediante un El motor se configura mediante un archivo con los siguientes archivo con los siguientes parámetros:parámetros:

- lookCloseNodes: Para realizar la - lookCloseNodes: Para realizar la búsqueda como si fuese un grafo.búsqueda como si fuese un grafo.

- lookOpenNodes: Para dejar los - lookOpenNodes: Para dejar los nodos de menor costo en la lista de nodos de menor costo en la lista de abiertos.abiertos.

Page 15: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Motor - ConfiguraciónMotor - Configuración

- problem: Se ingresa el problema a - problem: Se ingresa el problema a resolver siempre que esté soportado.resolver siempre que esté soportado.

- method: El método de búsqueda.- method: El método de búsqueda.

Page 16: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

Motor – Métodos de BúsquedaMotor – Métodos de Búsqueda

DFSDFS DFS informadoDFS informado Costo uniformeCosto uniforme A*A* IDA*IDA*

Page 17: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

ResultadosResultados

Page 18: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

ResultadosResultados

Page 19: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

ResultadosResultados

Page 20: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

ResultadosResultados

La solución óptima se encontró con La solución óptima se encontró con el método A* y la heurística el método A* y la heurística manhattan en 68 minutos manhattan en 68 minutos aproximadamente y se utilizaron un aproximadamente y se utilizaron un total de 54410 nodos exploradores.total de 54410 nodos exploradores.

IDA* tardó medio minuto menos y IDA* tardó medio minuto menos y usó la misma cantidad de nodos.usó la misma cantidad de nodos.

Page 21: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

ConclusionesConclusiones

Los métodos más complejos reducen Los métodos más complejos reducen drásticamente el tiempo de drásticamente el tiempo de computación.computación.

De acuerdo a la complejidad del De acuerdo a la complejidad del problema, la heurística incrementa problema, la heurística incrementa su importancia y es determinante en su importancia y es determinante en la búsqueda del camino óptimo.la búsqueda del camino óptimo.

Page 22: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

BibliografíaBibliografía

Juego de Rolling Cubes Juego de Rolling Cubes URL:http://www.minijuegos.com/juegURL:http://www.minijuegos.com/juegos/jugar.php?id=3416os/jugar.php?id=3416

Juego y solución óptima Juego y solución óptima URL:URL:http://www.righto.com/java/rollinhttp://www.righto.com/java/rollingcubes.htmlgcubes.html

Page 23: TPE 1 - Sistemas de Producción: Rolling Cubes Sistemas de Inteligencia Artifcial Bergez, Brasca y García

¿Preguntas?¿Preguntas?