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

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

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.

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.

Introducción - EstadosIntroducción - Estados

Estado Inicial:Estado Inicial:

Estado Objetivo:Estado Objetivo:

Aleatorio: Aleatorio:

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.

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:

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.

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

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.

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.

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.

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.

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*.

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.

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.

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

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

ResultadosResultados

ResultadosResultados

ResultadosResultados

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.

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.

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

¿Preguntas?¿Preguntas?