jueves, 9 de junio de 2016

4 EN RAYA



Mas conocido como conecta 4 es un juego para dos jugadores, en el que se introducen fichas en un tablero vertical con el objetivo de alinear cuatro consecutivas de un mismo color. Fue creado en 1974 por Ned Strongin y Howard Wexler para Milton Bradley Company

El juego fue desarrollado en lenguaje Java y para su implementación fueron requeridas 3 clases:

  • clase Board: la cual es la encargada de crear el tablero en el que se desarrolla el juego y cuenta con métodos relacionados a este como mostrar el tablero, determinar si puedo o no ingresar una ficha en determinada columna además determina el momento en el que el juego haya terminado gracias a que se ha llenado el tablero.
  • La Clase MiniMax: Es la clase que contiene el algoritmo con el cual se obtienen los movimientos del adversario. Este es un algoritmo recursivo el cual busca obtener el mejor movimiento para el adversario y el peor movimiento para el oponente. En este caso este algoritmo nos ayudara a obtener el mejor movimiento para nuestro adversario que sera la maquina.
  • Clase Main: Esta es la clase principal en la cual creamos los objetos de las otras dos clases y la ejecución del programa.


Reconocimiento de patrones numéricos con red neuronal


Recognition of numerical patterns with neural network


Jhon Edinson Acevedo Rojas, Mauricio Marín Orozco, Juan Sebastian Herrera Giraldo
Risaralda, Universidad Tecnológica de Pereira, Pereira, Colombia
Correo-e: juseherrera@utp.edu.co


Resumen— Mediante los algoritmos de “redes neuronales, redes neuronales backpropagation, perceptron”, se logra crear un programa capaz de reconocer números del cero al nueve (0-9). Este entrenamiento da como resultado que tan parecido es el patrón de entrada con el patrón de salida.


Palabras clave—Red Neuronal, Backpropagation, perceptron, capas ocultas, capas de entrada, capas de salida.


Abstract— through algorithms “neural network, backpropagation neural network, perceptron”, is able to create a program that can recognize numbers from zero to nine (0-9). This training result in so similar is the input pattern to the output pattern.


Key Word Neural Network, Backpropagation, hidden layers, input layers, output layers, perceptron


  1. INTRODUCCIÓN


Las redes neuronales fueron una simulación abstracta de los sistemas nerviosos biológicos. Ya que estos tienen dendritas, axón y el cuerpo de la neurona. Las redes neuronales artificiales tienen las siguientes características:


  • Auto-Organización y adaptabilidad: utilizan algoritmos de aprendizaje y auto-organización, por lo que ofrecen mejores posibilidades de procesado robusto y adaptativo.


  • Procesado no Lineal: Aumenta la capacidad de la red para aproximar funciones, clasificar patrones y aumentar su inmunidad frente al ruido.


  • Procesado paralelo: Normalmente se usa un gran número de nodos con alto nivel de interconectividad.

  1. CONTENIDO


Como se ha dicho nuestro objetivo es entrenar una red que reconozca patrones numéricos con y sin ruido.

  1. Algoritmo de entrenamiento Red Neuronal Backpropagation.


El lenguaje utilizado para la creación de esta red neuronal es Python 3.x.


Figura 1.


Basados en la figura 1 se debe tener bien claro cuáles van a ser las entradas de nuestra red.


Una vez hecho esto se calcula todas las entradas para las capas ocultas, lo cual debe hacerse teniendo en cuenta los pesos y todas las entradas. Visto de una manera formal se puede ver:


Donde (tetha j) es el umbral de la neurona que se considera como un peso asociado ficticio a la salida de 1


Wji son los pesos.
Xi son las entradas.

El valor de la salida de la neurona de las capas ocultas se le aplica una función F(t). Visto formalmente


Una vez realizado este paso, se repite el cálculo de pesos, esta vez entre la capa oculta y la capa de salida, e incluimos la función  F(t), la manera formal es la siguiente.


Y otra vez se debe calcular una función F(t)  para la salida de la red.


.


  1. Minimizar Errores de la Red Backpropagation

En el tema pasado se vio una parte importante del algoritmo de entrenamiento, una vez entendido esto se debe minimizar el error. Para ello se tiene en cuenta la salida deseada de la neurona ante la presentación del patrón.




Para calcular el error hacemos uso del vector director gradiente el cual es la derivada respecto a los pesos, como el vector gradiente toma la dirección más rápida al error y este se busca es minimizar, entonces se le da dirección negativa.


.
Para calcular los errores de manera iterativa se aplica regla de la cadena al gradiente y añadir una taza de aprendizaje n.


Para mayor información visitar la siguiente página web [1] Introducción a las redes neuronales.

  1. Reconocimiento de patrones numéricos.


Visto el algoritmo de backpropagation sabemos que lo que hace es encontrar el mínimo error y reducir el ruido. En la  figura 2. Se explica un tipo de ruido
Figura 2.


El ruido se puede definir como aquello que interfiere con la forma original.


Un claro ejemplo puede ser el número nueve (9), como se observa en la figura 2. El nueve está conformado por las siguientes entradas [a, b, c, d, e, f, g], donde 1 significa encendido y 0 significa apagado.


El número nueve representado en forma de entrada es [1, 1, 1, 0, 0, 1, 1], pero si se añade ruido a la imagen se puede decir que el nueve también es [1, 1, 1, 1, 0, 1, 1] esto también debe generar como salida un nueve (9), y no solo para el número nueve, si nuestra entrada es de mayor cantidad pueden existir cientos de ruidos que hagan un poco complicado el aprendizaje.

  1. CONCLUSIONES


El aprendizaje de una red neuronal puede tener tantas entradas como capas ocultas y salidas, aunque es un buen método de aprendizaje, este tiene cierto nivel de errores.


Este aprendizaje sirve tiene muchas aplicaciones, una de ellas es el famoso juego triki (tic tac toe), donde usted cada vez que juegue con la maquina ella va entrenado, hasta el punto de que piensa por ella misma.


A diferencia de la red neuronal con el algoritmo minimax en el triki, es evidente que tarda más con el algoritmo minimax debido a que ella genera un árbol con muchos nodos sobre la siguiente jugada, en cambio con la red neuronal es cuestión de entrenarla.


REFERENCIAS

  1. http://halweb.uc3m.es/esp/Personal/personas/jmmarin/esp/DM/tema3dm.pdf





martes, 17 de mayo de 2016



N-PUZZLE


Es un puzzle el cual consta de un marco de azulejos cuadrados numerados en orden aleatorio, con una ficha que falta. El objetivo del rompecabezas es colocar todas las fichas en orden por movimientos deslizantes que utilizan el espacio vacío.

Para la solución de este problema se hace uso de python como lenguaje de programación y ademas se utiliza la librería graphics que junto con la clase Animate realiza la parte grfica de nuestro programa. 

Para la parte de la lógica se implementan una pila en la cual va a quedar cada uno de los tableros solución y una cola de prioridad que basándose en las distancias hamming manhattan del puzzle decide cual sera el siguiente movimiento.

En la siguiente imagen se muestra como funcionan estas distancias mencionadas:


A continuación vemos el resultado del programa para el proximo puzzle propuesto:

blocks = [  [2 , 3   ,  4  ,  8  ],
                  [1 , 6   ,  0  , 12 ],
                  [5 , 10 ,  7  , 11 ],
                  [9 , 13 , 14 , 15 ]
                ] 




















lunes, 15 de febrero de 2016

Búsqueda en anchura (BFS)


Búsqueda en anchura

 (BFS - Breadth First Search)



En la búsqueda en espacios de estado para la solución de problemas de inteligencia artificial lo podemos hacer mediante una búsqueda a ciegas en la cual no se utiliza información sobre el problema y normalmente se realiza una búsqueda exhaustiva a diferencia de la búsqueda heurística en la cual se hace uso de información sobre el problema. 

Este método va construyendo un grafo de estados explícito mediante la aplicación de los operadores disponibles al nodo inicial después aplica los operadores disponibles a los nodos sucesores directos del nodo inicial, y así sucesivamente.






A continuación se expone una posible implementación del algoritmo en Pseudocódigo en la cual se hace uso de una cola, la cual es una estructura de datos tipo FIFO (first in, firs out)de la cual solo se disponen dos operaciones: insertar al final de la cola o extraer del principio de la cola.

Se establece el nodo origen insertándolo en la cola.
Mientras la cola no este vacía
sacamos el primer elemento y es evaluado
Si lo es entonces terminamos y salimos
Si no lo es, obtenemos todos los hijos de dicho nodo y los insertamos en la cola. Repetimos hasta que hayamos encontrado el elemento o la cola sea vacía.





miércoles, 3 de febrero de 2016




MARVIN MINSKY


Fue un matemático estadounidense e informático, cofundador del laboratorio de inteligencia artificial del instituto tecnologico de Massachusetts (MIT) y uno de los más famosos practicantes de la ciencia de la inteligencia artificial (IA).Es considerado uno de los padres de las ciencias de la computación.

Recibió la licenciatura y doctorado en matemáticas en la Universidad de Harvard (1950) y Princeton (1954). En 1951  construyó  SNARC, el primer simulador de redes neuronales. Sus otras invenciones incluyen brazos mecánicos, manos y otros dispositivos robóticos, el confocal de barrido microscopio, el sintetizador "muse" de variaciones musicales (con E. Fredkin) y uno de los primeros logotipos "turtles".

Minsky ha hecho muchas contribuciones a la IA, la psicología cognitiva, matemáticas, lingüística computacional, robótica, y la óptica. En los últimos años ha trabajado principalmente en impartir a las máquinas de la capacidad humana para el razonamiento de sentido común. Su concepción de la estructura y la función intelectual humana se presenta en dos libros: The Emotion Machine y The Society of Mind  (que es también el título del curso que enseña en el MIT).

De entre sus libros mas destacados podemos encontrar:


  • Redes neuronales y el problema del modelo de cerebro”. Título original en inglés “Neural Nets and the Brain Model Problem”. Ph.D. disertación, Universidad de Princeton, 1954.
  • Computación: máquinas finitas e infinitas”. Título original en inglés “Computation: Finite and Infinite Machines”, Prentice-Hall, 1967.
  • Procesamiento de información semántica”. Título original en inglés “Semantic Information Processing”. MIT Press, 1968.
  • Perceptrones”. Título original en inglés “Perceptrons” (con Seymour Papert). MIT Press, 1969.
  • Inteligencia artificial”. Título original en inglés “Artificial Intelligence” (con Seymour Papert). Prensa de la Universidad de Oregón, 1972.
  • Robótica”. Título original en inglés "Robotics" Doubleday, 1986.
  • La sociedad de la mente”. Título original en inglés “The Society of Mind”. Simon and Schuster, 1987.
  • La opción de Turing”. Título original en inglés “The Turing Option” (con Harry Harrison). Warner Books, New York, 1992.
  • La máquina con emociones”. Título original en inglés “The Emotion Machine”. ISBN / ASIN: 0743276639.