Papper sustentacion final

El siguiente enlace direcciona al papper de la sustentación final, este esta guardado en dropbox:

https://www.dropbox.com/sh/gtlyqru8zhaarja/AABlbCQ1CQni9r9aATUk8gh6a?dl=0

Reconocimiento de numeros en matriz 3*5 con una red nueronal

import math
import random
import string

class NN:
  def __init__(self, NI, NH, NO):
    # number of nodes in layers
    self.ni = NI + 1 # +1 for bias
    self.nh = NH
    self.no = NO
 
    # initialize node-activations
    self.ai, self.ah, self.ao = [],[], []
    self.ai = [1.0]*self.ni
    self.ah = [1.0]*self.nh
    self.ao = [1.0]*self.no

    # create node weight matrices
    self.wi = makeMatrix (self.ni, self.nh)
    self.wo = makeMatrix (self.nh, self.no)
    # initialize node weights to random vals
    randomizeMatrix ( self.wi, -0.2, 0.2 )
    randomizeMatrix ( self.wo, -2.0, 2.0 )
    # create last change in weights matrices for momentum
    self.ci = makeMatrix (self.ni, self.nh)
    self.co = makeMatrix (self.nh, self.no)
 
  def runNN (self, inputs):
    if len(inputs) != self.ni-1:
      print 'incorrect number of inputs'
 
    for i in range(self.ni-1):
      self.ai[i] = inputs[i]
   
    for j in range(self.nh):
      sum = 0.0
      for i in range(self.ni):
        sum +=( self.ai[i] * self.wi[i][j] )
      self.ah[j] = sigmoid (sum)
 
    for k in range(self.no):
      sum = 0.0
      for j in range(self.nh):      
        sum +=( self.ah[j] * self.wo[j][k] )
      self.ao[k] = sigmoid (sum)
   
    return self.ao
   
   

  def backPropagate (self, targets, N, M):
    # dE/dw[j][k] = (t[k] - ao[k]) * s'( SUM( w[j][k]*ah[j] ) ) * ah[j]
    output_deltas = [0.0] * self.no
    for k in range(self.no):
      error = targets[k] - self.ao[k]
      output_deltas[k] =  error * dsigmoid(self.ao[k])
 
    # update output weights
    for j in range(self.nh):
      for k in range(self.no):
        # output_deltas[k] * self.ah[j] is the full derivative of dError/dweight[j][k]
        change = output_deltas[k] * self.ah[j]
        self.wo[j][k] += N*change + M*self.co[j][k]
        self.co[j][k] = change

    # calc hidden deltas
    hidden_deltas = [0.0] * self.nh
    for j in range(self.nh):
      error = 0.0
      for k in range(self.no):
        error += output_deltas[k] * self.wo[j][k]
      hidden_deltas[j] = error * dsigmoid(self.ah[j])
 
    #update input weights
    for i in range (self.ni):
      for j in range (self.nh):
        change = hidden_deltas[j] * self.ai[i]
        #print 'activation',self.ai[i],'synapse',i,j,'change',change
        self.wi[i][j] += N*change + M*self.ci[i][j]
        self.ci[i][j] = change
     
    # calc combined error
    # 1/2 for differential convenience & **2 for modulus
    error = 0.0
    for k in range(len(targets)):
      error += 0.5 * (targets[k]-self.ao[k])**2
    return error
     
     
  def weights(self):
    print 'Input weights:'
    for i in range(self.ni):
      print self.wi[i]
    print
    print 'Output weights:'
    for j in range(self.nh):
      print self.wo[j]
    print ''

  def test(self, patterns):
    for p in patterns:
      inputs = p[0]
      print 'Inputs:', p[0], '-->', self.runNN(inputs), '\tTarget', p[1]

  def train (self, patterns, max_iterations = 1000, N=0.5, M=0.1):
    for i in range(max_iterations):
      for p in patterns:
        inputs = p[0]
        targets = p[1]
        self.runNN(inputs)
        error = self.backPropagate(targets, N, M)
      if i % 50 == 0:
        print 'Combined error', error
    self.test(patterns)
 

def sigmoid (x):
  denom = math.pow(math.e, -x)
  return 1 / (1 + denom)

# the derivative of the sigmoid function in terms of output
def dsigmoid (y):
  return y * (1 - y)

def makeMatrix ( I, J, fill=0.0):
  m = []
  for i in range(I):
    m.append([fill]*J)
  return m

def randomizeMatrix ( matrix, a, b):
  for i in range ( len (matrix) ):
    for j in range ( len (matrix[0]) ):
      matrix[i][j] = random.uniform(a,b)

def main ():
  pat = [
      [[0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1], [0, 0, 0, 0]],
      [[0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1]],
      [[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0]],
      [[1, 1, 1, 0, 0, 1, 1, 1, 1, 0 ,0, 1, 1, 1, 1], [0, 0, 1, 1]],
      [[1, 0, 1, 1, 0, 1 ,1 ,1 ,1 ,0 ,0 ,1 ,0 ,0 ,1], [0 ,1 ,0 ,0]],
      [[1 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,1], [0, 1, 0, 1]],
      [[1 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1], [0 ,1 ,1 ,0]],
      [[1 ,1 ,1 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,1], [0 ,1 ,1 ,1]],
      [[1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1], [1 ,0 ,0 ,0]],
      [[1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,1 ,1 ,1 ,1], [1 ,0 ,0 ,1]]    
  ]

  myNN = NN (15, 4, 4)
  myNN.train(pat)







if __name__ == "__main__":
    main()

La propagación hacia atrás de errores o retropropagación (del inglés backpropagation) es un algoritmo de aprendizaje supervisado que se usa para entrenar redes neuronales artificiales. El algoritmo emplea un ciclo propagación – adaptación de dos fases. Una vez que se ha aplicado un patrón a la entrada de la red como estímulo, este se propaga desde la primera capa a través de las capas superiores de la red, hasta generar una salida. La señal de salida se compara con la salida deseada y se calcula una señal de error para cada una de las salidas.

Las salidas de error se propagan hacia atrás, partiendo de la capa de salida, hacia todas las neuronas de la capa oculta que contribuyen directamente a la salida. Sin embargo las neuronas de la capa oculta solo reciben una fracción de la señal total del error, basándose aproximadamente en la contribución relativa que haya aportado cada neurona a la salida original. Este proceso se repite, capa por capa, hasta que todas las neuronas de la red hayan recibido una señal de error que describa su contribución relativa al error total.

La importancia de este proceso consiste en que, a medida que se entrena la red, las neuronas de las capas intermedias se organizan a sí mismas de tal modo que las distintas neuronas aprenden a reconocer distintas características del espacio total de entrada. Después del entrenamiento, cuando se les presente un patrón arbitrario de entrada que contenga ruido o que esté incompleto, las neuronas de la capa oculta de la red responderán con una salida activa si la nueva entrada contiene un patrón que se asemeje a aquella característica que las neuronas individuales hayan aprendido a reconocer durante su entrenamiento.

Gracias a este algoritmo se pudo entrenar esta red, tomando los patrones de la matriz 3*5 como datos de entrada y así poder obtener una salida en binario correspondiente al valor del patrón.

Ej: 

Numero 8

 1 1 1

 1 0 1

 1 1 1

 1 0 1

 1 1 1

Salida: [ 1. 0, 0, 0 ]

Triqui

# coding=UTF8
from Tkinter import Tk, Button
from tkFont import Font
from copy import deepcopy

class Board:

  def __init__(self,other=None):
    self.player = 'X'
    self.opponent = 'O'
    self.empty = '.'
    self.size = 3
    self.fields = {}
    for y in range(self.size):
      for x in range(self.size):
        self.fields[x,y] = self.empty
    # copy constructor
    if other:
      self.__dict__ = deepcopy(other.__dict__)

  def move(self,x,y):
    board = Board(self)
    board.fields[x,y] = board.player
    (board.player,board.opponent) = (board.opponent,board.player)
    return board

  def __minimax(self, player):
    if self.won():
      if player:
        return (-1,None)
      else:
        return (+1,None)
    elif self.tied():
      return (0,None)
    elif player:
      best = (-2,None)
      for x,y in self.fields:
        if self.fields[x,y]==self.empty:
          value = self.move(x,y).__minimax(not player)[0]
          if value>best[0]:
            best = (value,(x,y))
      return best
    else:
      best = (+2,None)
      for x,y in self.fields:
        if self.fields[x,y]==self.empty:
          value = self.move(x,y).__minimax(not player)[0]
          if value<best[0]:
            best = (value,(x,y))
      return best

  def best(self):
    return self.__minimax(True)[1]

  def tied(self):
    for (x,y) in self.fields:
      if self.fields[x,y]==self.empty:
        return False
    return True

  def won(self):
    # horizontal
    for y in range(self.size):
      winning = []
      for x in range(self.size):
        if self.fields[x,y] == self.opponent:
          winning.append((x,y))
      if len(winning) == self.size:
        return winning
    # vertical
    for x in range(self.size):
      winning = []
      for y in range(self.size):
        if self.fields[x,y] == self.opponent:
          winning.append((x,y))
      if len(winning) == self.size:
        return winning
    # diagonal
    winning = []
    for y in range(self.size):
      x = y
      if self.fields[x,y] == self.opponent:
        winning.append((x,y))
    if len(winning) == self.size:
      return winning
    # other diagonal
    winning = []
    for y in range(self.size):
      x = self.size-1-y
      if self.fields[x,y] == self.opponent:
        winning.append((x,y))
    if len(winning) == self.size:
      return winning
    # default
    return None

  def __str__(self):
    string = ''
    for y in range(self.size):
      for x in range(self.size):
        string+=self.fields[x,y]
      string+="\n"
    return string

class GUI:

  def __init__(self):
    self.app = Tk()
    self.app.title('TicTacToe')
    self.app.resizable(width=False, height=False)
    self.board = Board()
    self.font = Font(family="Helvetica", size=32)
    self.buttons = {}
    for x,y in self.board.fields:
      handler = lambda x=x,y=y: self.move(x,y)
      button = Button(self.app, command=handler, font=self.font, width=2, height=1)
      button.grid(row=y, column=x)
      self.buttons[x,y] = button
    handler = lambda: self.reset()
    button = Button(self.app, text='reset', command=handler)
    button.grid(row=self.board.size+1, column=0, columnspan=self.board.size, sticky="WE")
    self.update()

  def reset(self):
    self.board = Board()
    self.update()

  def move(self,x,y):
    self.app.config(cursor="watch")
    self.app.update()
    self.board = self.board.move(x,y)
    self.update()
    move = self.board.best()
    if move:
      self.board = self.board.move(*move)
      self.update()
    self.app.config(cursor="")

  def update(self):
    for (x,y) in self.board.fields:
      text = self.board.fields[x,y]
      self.buttons[x,y]['text'] = text
      self.buttons[x,y]['disabledforeground'] = 'black'
      if text==self.board.empty:
        self.buttons[x,y]['state'] = 'normal'
      else:
        self.buttons[x,y]['state'] = 'disabled'
    winning = self.board.won()
    if winning:
      for x,y in winning:
        self.buttons[x,y]['disabledforeground'] = 'red'
      for x,y in self.buttons:
        self.buttons[x,y]['state'] = 'disabled'
    for (x,y) in self.board.fields:
      self.buttons[x,y].update()

  def mainloop(self):
    self.app.mainloop()

if __name__ == '__main__':
  GUI().mainloop()

En teoría de juegos, 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. Este cálculo se hace de forma recursiva.

El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

La receta del algoritmo Minimax:

1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal o determinando una profundidad concreta.

Vamos aplicando el algoritmo por un número fijo de iteraciones hasta alcanzar una determinada profundidad. En estas aplicaciones la profundidad suele ser el número de movimientos o los incluso el resultado de aplicar diversos pasos de planificación en un juego de estrategia.

2. Cálculo de los valores de la función de utilidad para cada nodo terminal.

Para cada resultado final, cómo de beneficioso me resulta si estamos en MAX o cuanto me perjudicará si estamos en MIN.

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 como se ha comentado, definirá lo buena que es la posición para un jugador cuando la alcanza.

Versiones más avanzadas como el minimax con poda alfa beta hacen que se reduzca considerablemente el número de nodos a visitar por lo que el tiempo de cálculo se reduce ampliamente.

Y para terminar comentar un ejemplo cásico, el tres en raya (juego del gato, tatetí, triqui, tres en gallo, michi, la vieja o tic tac toe). Se trata de hacer una fila de tres para ganar y evitar que el oponente la haga antes que tu.

Entrenamiento red neuronal

#include <stdio.h>
#include <math.h>


int main()
{
    printf("Red neuronal\n");
    const double EULER = 2.71828182845904523536;
int p[4][2] = {(0,0),
 (0,1),
 (1,0),
 (1,1)};

int w[] = {60,40};
double d[4];
int i;
    double suma = 0;
    int s = 0;

for (i=0; i<4; i++)
{
suma = ((-1)*(((p[i+1][1])*w[1])+((p[i+1][2])*w[2])));
s = 1/(1+(pow(EULER, suma)));
printf("suma: %d\n", suma);
printf("Salida: %d\n", s);

}
getchar();
    getchar();
}

Jarras

class Jarra: def __init__(self, inicial = 0, final = 0):
self.inicial = inicial
self.final = final
def acciones(self, estado):
jarra_4 = estado[0]
jarra_3 = estado[1]
l = []
if jarra_4 > 0:
l.append("vaciar jarra 4 litros")
if jarra_3 < 3:
l.append("pasar jarra 4 litros a jarra de 3")
if jarra_4 < 4:
l.append("llenar jarra de 4 litros")
if jarra_3 > 0:
l.append("pasar jarra 3 litros a jarra de 4")
if jarra_3 > 0:
l.append("vaciar jarra 3 litros")
if jarra_3 < 3:
l.append("llenar jarra de 3 litros")
return l
def bombear_agua(self, estado, accion):
jarra4 = estado[0]
jarra3 = estado[1]
if accion == "llenar jarra de 4 litros":
return (4, jarra3)
elif accion == "llenar jarra de 3 litros":
return (jarra4, 3)
elif accion == "vaciar jarra de 4 litros":
return (0, jarra3)
elif accion == "vaciar jarra de 3 litros":
return (jarra4, 0)
elif accion == "pasar jarra 4 litros a jarra de 3":
return (jarra4 - 3 + j3, 3) if jarra3+jarra4 >= 3 else (0, jarra3 + jarra4)
else:
return (jarra3 + jarra4, 0) if jarra3+jarra4 <= 4 else (4, jarra3 - 4 + jarra4)
def solucion(self, estado):
return estado[0] == 2
j = Jarra()
print(j.acciones((0,0))

Minimax

MINIMAX( posición, profundidad, jugador) 
comienzo 
Si SUFICIENTE (posición, profundidad) entonces
    resultado.VALOR = ESTATICA (posición, jugador); 
    resultado.CAMINO = NULO;
    return resultado;
sino
     Sucesores := GENMOV (posición, jugador);
     Si EstaVacia (Sucesores) entonces

    resultado.VALOR = ESTATICA (posición, jugador);
     resultado.CAMINO = NULO; return resultado;
sino
    resultadoMejor.VALOR = MININT; por cada sucesor de Sucesores
    resultadoSucesor := MINIMAX (sucesor, profundidad+1, CONTRARIO (jugador)); 
    Si resultadoMejor.VALOR < - resultadoSucesor.VALOR entonces
    resultadoMejor.VALOR := - resultadoSucesor.VALOR;
     resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO;
                fin si;
            fin por; 
        return resultadoMejor;
     fin sino;
 fin sino;
fin MINIMAX

Codigo solucion 8 puzzle (python)

import random
import Queue as queue

class Tablero():

    def __init__(self,tsolv):
        self.tablero=tsolv
        self.tablerometa=[]
        cont=1
        for i in range(len(tsolv)):
            self.tablerometa.append([])
            for j in range(len(tsolv)):
                self.tablerometa[i].append(cont)
                cont=cont+1
        self.tablerometa[len(tsolv)-1][len(tsolv)-1]=0

    def Size(self):
        return len(self.tablero)

    def EsSolucion(self):
        tmp=[]
        inv=0
        for i in range(self.Size()):
            for j in range (self.Size()):
                if self.tablero[i][j]!=0:
                    tmp.append(self.tablero[i][j])

        for m in range(len(tmp)):
            for i in range (len(tmp)-m):
                if tmp[m]>tmp[i+m]:
                    inv=inv+1
                   
        if (inv%2)==0:
            return True
        else:
            return False
     
    def Copia(self):
        copia = self.tablero[:]
        for i in range(self.Size()):
            copia[i]=self.tablero[i][:]
        return copia
   
    def Hamming(self):
        ham=0
        for i in range(self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]!=self.tablerometa[i][j] and self.tablero[i][j]!=0:
                    ham=ham+1
        return ham

    def Manhattan(self):
        man=0
        for i in range(self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]!=0:
                    x=(self.tablero[i][j]-1)/self.Size()
                    y=(self.tablero[i][j]-1)-self.Size()*x
                    man+=abs(x-i)+abs(y-j)
        return man

    def Print_tab(self):
        for i in self.tablero:
            print i
        print "\n"

    def Vecinos(self):
        vecinos=[]
        for i in range( self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]==0:
                    if i+1<self.Size():
                        vecinos.append((i+1,j))
                    if j+1<self.Size():
                        vecinos.append((i,j+1))
                    if i-1>=0:
                        vecinos.append((i-1,j))
                    if j-1>=0:
                        vecinos.append((i,j-1))
        return vecinos

    def Pos0(self):
        for i in range (self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]==0:
                    posx0,posy0=j,i
        return posx0,posy0
   
    def ModificarPos0(self,b,a):
        posx0,posy0=self.Pos0()
        self.tablero[posy0][posx0]=self.tablero[b][a]
        self.tablero[b][a]= 0
       
    def Solucionado(self):
        if self.Manhattan()+self.Hamming() ==0:
            return True
               
class Resolver():

    def __init__(self,Tableroin):
        self.tablero=Tablero(Tableroin.Copia())
        self.movimientos=0
        self.estadoactual=Tablero(Tableroin.Copia())
        self.estadoanterior=(None,0)
        self.posiblesmov=queue.PriorityQueue()
        self.Repetidos=[]

    def Movimientos(self,vecinos):
        for i in range (len(vecinos)):
            posyv,posxv=vecinos[i]
            self.estadoactual.ModificarPos0(posyv,posxv)
            self.posiblesmov.put((self.estadoactual.Manhattan()+self.estadoactual.Hamming(),self.estadoactual))
            self.estadoactual=Tablero(self.tablero.Copia())
                       
    def Solucion(self):
        cont=0
        vecinos=self.tablero.Vecinos()[:]
        if self.tablero.EsSolucion():
            while(not(self.tablero.Solucionado())):
                self.Movimientos(vecinos)
                pos0x,pos0y=self.tablero.Pos0()
                self.tablero = Tablero(self.posiblesmov.get()[1].Copia())              
                if(self.tablero in self.Repetidos):
                    self.tablero = Tablero(self.posiblesmov.get()[1].Copia())
                else:
                    self.Repetidos.append(Tablero(self.tablero.Copia()))
                self.estadoactual = Tablero(self.tablero.Copia())
                self.posiblesmov=queue.PriorityQueue()
                vecinos=self.tablero.Vecinos()[:]
                vecinos.remove((pos0y,pos0x))
                cont=cont+1
                self.tablero.Print_tab()
            print "Cantidad de Movimientos",cont
        else:
            print "No es solucionable"

               
m=[]
print "Digite el tamanio del tablero (Dimensiones Iguales)"
x=int(raw_input("m*m "))
for i in range(x):
    m.append([])
    for j in range(x):
        print "Digite la posicion",i+1,j+1
        a=int(raw_input())
        m[i].append(a)
       
b= Tablero(m)
b.EsSolucion()
print "Tablero a resolver:"
b.Print_tab()
print "Solucion"
c=Resolver(b)
c.Solucion()