Laboratorio 10

Aplicación Adaline: Detección Enfermedades Aceitunas

La presente aplicación se baso del trabajo: http://seccperu.org/?q=node/372 , el cual consiste en determinar la enfermedad “Fish Eye” en aceitunas. Para lo cuál empleaban los siguientes pasos:

1. Binarizar la imagen
2. Aplicar un detector de bordes
3. Extraer las aceitunas en la imagen
4. Para cada aceituna calcular el porcentaje de infección=Área Infectada/Área Aceituna.

El área infectada es determinada por la cantidad de píxeles que contiene el detector de bordes en el interior de la aceituna.

Dado el porcentaje de infección este nos ayudara a clasificar la aceituna en uno de los siguientes clases: Infectada, a supervisión humana y sana.

En el presente trabajo dado que la red adaline solo permite clasificar en 2 clases, tendremos como entradas de patrones los respectivos porcentajes de aceitunas y como patrones de Salida un 1: aceituna sana y -1: aceituna infectada.

Al entrenar a la red el error Global queda en 3.056 y clasifica los nuevos porcentajes de infección de una manera correcta.

PERCEPTRON EN SU FORMA DUAL

En este caso la función de decisión va estar dada por:

Y la regla de actualización puede ser escrita de la siguiente forma:

A continuación se muestra el algoritmo (donde a es el alfa):

• Responder Cuales son los valores de alfa b y k para el perceptron en su forma dual (usar la funcion AND).

Nota: los patrones de entrenamiento son las mismas utilizadas para el algoritmo primal, y la matriz de alfas se inicializan en 0.

DUAL AND

 Factor de Aprendizaje: 0.15

• Matriz de Alfas:
   alfa [0]=2.0
   alfa [1]=2.0
   alfa [2]=1.0
   alfa [3]=0.0
• Valor de b: -2.0000000000000004
• Valor de k: 5
• Numero de Iteraciones: 3

 Factor de Aprendizaje: 0.2

• Matriz de Alfas:
   alfa [0]=2.0
   alfa [1]=2.0
   alfa [2]=1.0
   alfa [3]=0.0
• Valor de b: -2.0000000000000004
• Valor de k: 5
• Numero de Iteraciones: 3

 Factor de Aprendizaje: 0.25

• Matriz de Alfas:
   alfa [0]=2.0
   alfa [1]=2.0
   alfa [2]=1.0
   alfa [3]=0.0
• Valor de b: -2.0000000000000004
• Valor de k: 5
• Numero de Iteraciones: 3

A continuación una visualización de como se entrenó,

y luego como predijo para cada patron de entrada:

Laboratorio9

             RED NEURONAL PERCEPTRON (Clasificador Lineal)

Antecedentes. La primera red neuronal conocida, fue desarrollada en 1943 por Warren McCulloch y Walter Pitts; ésta consistía en una suma de las señales de entrada, multiplicadas por unos valores de pesos escogidos aleatoriamente. La entrada es comparada con un patrón preestablecido para determinar la salida de la red. Si en la comparación, la suma de las entradas multiplicadas por los pesos es mayor o igual que el patrón preestablecido la salida de la red es uno (1), en caso contrario la salida es cero (0). Al inicio del desarrollo de los sistemas de inteligencia artificial, se encontró gran similitud entre su comportamiento y el de los sistemas biológicos y en principio se creyó que este modelo podía computar cualquier función aritmética o lógica.

La red tipo Perceptrón fue inventada por el psicólogo Frank Rosenblatt en el año 1957. Su intención era ilustrar algunas propiedades fundamentales de los sistemas inteligentes en general, sin entrar en mayores detalles con respecto a condiciones específicas y desconocidas para organismos biológicos concretos.

El Perceptrón era inicialmente un dispositivo de aprendizaje, en su configuración inicial no estaba en capacidad de distinguir patrones de entrada muy complejos, sin embargo mediante un proceso de aprendizaje era capaz de adquirir esta capacidad.

Estructura de la red.

La estructura de un Perceptrón sencillo; en la que se observa la adición de una condición umbral en la salida. Si la entrada neta, a esta condición es mayor que el valor umbral, la salida de la red es 1, en caso contrario es 0 (ó -1).

Veamos mediante el siguiente gráfico la estructura de la perceptron:

Regla de aprendizaje.
El Perceptrón es un tipo de red de aprendizaje supervisado, es decir necesita conocer los valores esperados para cada una de las entradas presentadas; su comportamiento está definido por pares de esta forma:
        {p1, t1 },{p2 , t2 }, . . . ,{pQ , tQ }

Cuando p es aplicado a la red, la salida de la red es comparada con el valor esperado t, y la salida de la red esta determinada por una función de salida, como las que se muestran a continuación:

Perceptron para Clasificar Nueces, utilizando el Algoritmo de Aprendizaje para el Perceptron y

Perceptron para la funcion AND, en su forma Primal

Bueno en aquí hemos implementado el Algoritmo Perceptrón con su Algoritmo de Aprendizaje y el algoritmo Perceptrón en su forma primal.

Para el Algoritmo Perceptrón con su Algoritmo de Aprendizaje (como para el Adeline), se utilizaron los siguiente patrones de entrada y de salida deseada, tanto para el AND como para las nueces:

• Patrones entrenamiento para AND
  

          Patrones de Entrada:
                      X1= [1.0 , 1.0 , 1.0]
                      X2= [1.0 , 1.0 , -1.0]
                      X3= [1.0 , -1.0 , 1.0]
                      X4= [1.0 , -1.0 , -1.0]
         Patrones de Salida:
                      D1= 1.0
                      D2= -1.0
                      D3= -1.0
                      D4= -1.0
 

                

• Patrones entrenamiento para Nueces
  

                  
     Es decir:
    
          Patrones de Entrada:
                    X1= [1.0 , 2.2 , 1.4]
                    X2= [1.0 , 1.5 , 1.0]
                    X3= [1.0 , 0.6 , 0.5]
                    X4= [1.0 , 2.3 , 2.0]
                    X5= [1.0 , 1.3 , 1.5]
                    X6= [1.0 , 0.3 , 1.0]
          Patrones de Salida:
                    D1= 1.0
                    D2= 1.0
                    D3= 1.0
                    D4= -1.0
                    D5= -1.0
                    D6= -1.0

   

Para el Algoritmo Perceptrón Primal (como para el Dual), se utilizaron los siguiente patrones de entrada y de salida deseada, tanto para el AND como para las nueces:

• Patrones entrenamiento para AND
  

          Patrones de Entrada:
                      X1= [1.0 , 1.0]
                      X2= [1.0 , -1.0]
                      X3= [-1.0 , 1.0]
                      X4= [-1.0 , -1.0]
         Patrones de Salida:
                      D1= 1.0
                      D2= -1.0
                      D3= -1.0
                      D4= -1.0

• Patrones entrenamiento para Nueces
  

          Patrones de Entrada:
                    X1= [2.2 , 1.4]
                    X2= [1.5 , 1.0]
                    X3= [0.6 , 0.5]
                    X4= [2.3 , 2.0]
                    X5= [1.3 , 1.5]
                    X6= [0.3 , 1.0]
          Patrones de Salida:
                    D1= 1.0
                    D2= 1.0
                    D3= 1.0
                    D4= -1.0
                    D5= -1.0
                    D6= -1.0
 
                   

A continuación algunos experimentos realizados:

PERCEPTRÓN NUECES

 Factor de Aprendizaje: 0.15

• Matriz de Pesos Inicial:
peso [0]= 0.12589034468012628
peso [1]= 0.7903058923898821
peso [2]= 0.9984030903113681

• Matriz de Pesos:
peso [0]= 0.12589034468012628
peso [1]= 0.3703058923898827
peso [2]= -0.5615969096886317

• Numero de Iteraciones:9

 Factor de Aprendizaje: 0.2

• Matriz de Pesos Inicial:
peso [0]= 0.5211053777949533
peso [1]= 0.2648711912609053
peso [2]= 0.9012579714386163

• Matriz de Pesos:
peso [0]= 0.5211053777949533
peso [1]= 0.4248711912609069
peso [2]= -1.0187420285613844

• Numero de Iteraciones: 10

 Factor de Aprendizaje: 0.25

• Matriz de Pesos Inicial:
peso [0]= 0.4635237244427848
peso [1]= 0.811524746560602
peso [2]= 0.6304562017839236

• Matriz de Pesos:
peso [0]= 0.9635237244427848
peso [1]= 1.3115247465606044
peso [2]= -2.269543798216076

• Numero de Iteraciones: 15


PERCEPTRÓN AND

 Factor de Aprendizaje: 0.15

• Matriz de Pesos Inicial:
peso [0]= 0.49061731276640874
peso [1]= 0.006799938954024531
peso [2]= 0.3200514432209699

• Matriz de Pesos:
peso [0]= -0.4093826872335912
peso [1]= 0.3067999389540245
peso [2]= 0.6200514432209698

• Numero de Iteraciones: 4

 Factor de Aprendizaje: 0.2

• Matriz de Pesos Inicial:
peso [0]= 0.3492676171883031
peso [1]= 0.5332770227376556
peso [2]= 0.44576721981941836

• Matriz de Pesos:
peso [0]= -0.4507323828116969
peso [1]= 0.5332770227376556
peso [2]= 0.44576721981941836

• Numero de Iteraciones: 2

 Factor de Aprendizaje: 0.25

• Matriz de Pesos Inicial:
peso [0]= 0.6058080756193948
peso [1]= 0.6177095431809719
peso [2]= 0.8570807155227276

• Matriz de Pesos:
peso [0]= -0.39419192438060524
peso [1]= 0.6177095431809719
peso [2]= 0.8570807155227276

• Numero de Iteraciones: 2

PRIMAL AND

 Factor de Aprendizaje: 0.15

• Matriz de Pesos Inicial:
peso [0]=0.04337321278786277
peso [1]=0.8707094307946116
peso [2]=0.8313040363776814

• Matriz de Pesos:
peso [0]=-0.10662678721213723
peso [1]=0.7207094307946116
peso [2]=0.9813040363776814

• Valor de b: -0.4499999999999999
• Valor de k: 1
• Numero de Iteraciones: 2

 Factor de Aprendizaje: 0.2

• Matriz de Pesos Inicial:
peso [0]=0.18526642378180813
peso [1]=0.8435329132210375
peso [2]=0.2543760126900195

• Matriz de Pesos:
peso [0]=-0.01473357621819188
peso [1]=0.6435329132210375
peso [2]=0.45437601269001954

• Valor de b: -0.6
• Valor de k:1
• Numero de Iteraciones: 2

 Factor de Aprendizaje: 0.25

• Matriz de Pesos Inicial:
peso [0]=0.906910074177728
peso [1]=0.2607305274667093
peso [2]=0.7652212917544058

• Matriz de Pesos:
peso [0]=0.40691007417772795
peso [1]=0.7607305274667093
peso [2]=0.7652212917544059

• Valor de b: -1.4999999999999998
• Valor de k: 4
• Numero de Iteraciones: 3

Ejecutándolo el algoritmo Perceptrón Primal, para el primer caso, cuando el factor de aprendizaje = 0.1, tenemos:

 De los 4 patrones de entrada se escoge el de max(R) = 1.7320508075688772
 Para i = 0
 entrada = [1.0 , 1.0 , 1.0]
 Si ( 1.6260213167230448 < = 0 ) -> falso
 Matriz de Pesos:
    • peso [0]= 0.6179109054594774
    • peso [1]= 0.5502077938601178
    • peso [2]= 0.4579026174034496
 Valor de b = 0.0
 Valor de k = 0

Para i = 1
 entrada = [1.0 , 1.0 , -1.0 ]
 Si ( -0.7102160819161455 < = 0 ) entonces
 Matriz de Pesos:
    • peso [0]= 0.5179109054594774  
    • peso [1]= 0.4502077938601178
    • peso [2]= 0.5579026174034496
 Valor de b = -0.3
 Valor de k = 1

 Para i = 2
 entrada = [ 1.0 , -1.0 , 1.0 ]
 Si ( -0.3256057290028092 < = 0) entonces
 Matriz de Pesos :  
   • peso [0]= 0.4179109054594774  
   • peso [1]= 0.5502077938601178  
   • peso [2]= 0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2
 Para i = 3
 entrada = [ 1.0 , -1.0 , -1.0 ]
 Si ( 1.19019950580409 < = 0 ) -> falso
 Matriz de Pesos:
     • peso [0]= 0.4179109054594774
     • peso [1]= 0.5502077938601178
     • peso [2]= 0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2

Otra iteración
 Para i = 0
 entrada = [ 1.0 , 1.0 , 1.0 ]
 Si ( 0.8260213167230447 < = 0 ) -> falso
 Matriz de Pesos:
    • peso [0]= 0.4179109054594774
    • peso [1]= 0.5502077938601178
    • peso [2]=0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2

 Para i = 1
 entrada = [ 1.0 , 1.0 , -1.0 ]
 Si ( 0.08978391808385444 < = 0 ) -> falso
 Matriz de Pesos
     • peso [0]= 0.4179109054594774
     • peso [1]= 0.5502077938601178
     • peso [2]= 0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2

Para i = 2
 entrada = [ 1.0 , -1.0 , 1.0 ]
 Si ( 0.2743942709971907 < = 0 ) -> falso
 Matriz de Pesos
     • peso [0]= 0.4179109054594774
     • peso [1]= 0.5502077938601178
     • peso [2]= 0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2

Para i = 3
 entrada = [ 1.0 , -1.0 , -1.0 ]
 Si ( 1.19019950580409 < = 0 ) -> falso
 Matriz de Pesos
    • peso [0]= 0.4179109054594774
    • peso [1]= 0.5502077938601178
    • peso [2]= 0.4579026174034496
 Valor de b = -0.6
 Valor de k = 2

 Entonces el numero de iteraciones del primal es:2

Laboratorio8

Clasificador de SPAM y NO SPAM

Antes de comentar la aplicación en si veamos algo de teoría. Un clasificador Bayesiano "naïve" es una clasificador probabilístico que se basa en aplicar el Teorema de Bayes. Este tipo de clasificadores es frecuentemente empleado para detectar mensajes de correo basura (spam).

En abstracto, el modelo de probabilidad para un clasificador es

sobre una variable dependiente C, con un pequeño número de resultados (o clases). Esta variable está condicionada por varias variables independientes desde F₁ a F_n. El problema es que si el número n de variables independientes es grande (o cuando éstas pueden tomar muchos valores), entonces basar este modelo en tablas de probabilidad se vuelve imposible. Por lo tanto el modelo se reformula para hacerlo más manejable:

Usando el teorema de Bayes se escribe:

Lo anterior podría reescribirse en lenguaje común como:

En la práctica sólo importa el numerador, ya que el denominador no depende de C y los valores de F_i son datos, por lo que el denominador es, en la práctica, constante.

El numerador es equivalente a una probabilidad compuesta:

que puede ser reescrita como sigue, aplicando repetidamente la definición de probabilidad condicional:

... y así sucesivamente. Ahora es cuando la asunción "naïve" de independencia condicional entra en juego: se asume que cada F_i es independiente de cualquier otra F_j para . Esto significa que

por lo que la probabilidad compuesta puede expresarse como

Esto significa que haciendo estas asunciones, la distribución condicional sobre la variable clasificaroria C puede expresarse de la siguiente manera:

donde Z es un factor que depende sólo de , es decir, constante si los valores de F_i son conocidos

Ahora con el conocimiento previo comentemos la aplicación


El presente programa usa el algoritmo de Naive Bayes para clasificar mensajes de correo y determinar si estos son SPAM o NO SPAM.

Para construir el programa, hemos empleado una cierta cantidad de mensajes de prueba los cuales hemos clasificado manualmente en SPAM o NO SPAM. Para cada mensaje de prueba son eliminadas las palabras, por ejemplo:”la, lo, del, sobre, encima, y, o, etc” y así asociaremos ciertas palabras al hecho que el mensaje sea SPAM o NO SPAM. Se recomienda también transformar los verbos infinitivos y las plurales a singular.

Los mensajes de prueba son la base del algoritmo empleado y ayudaran a determinar si un nuevo mensaje pertenece a la clase SPAM o NO SPAM, teniendo en cuenta la clase que tenga mayor probabilidad de pertenencia.

El grado de pertenencia se determinara de acuerdo a la mayor cantidad de palabras que concuerden con el texto nuevo ya sean de clase SPAM o NO SPAM.

En el presente envió se adjuntan los archivos de entrenamiento y los de prueba, descargar aquí.

Laboratorio7

Red Bayesiana e Inferencia utilizando el Algoritmo de Eliminación de Variables

A continuación se presenta el algoritmo implementado para la resolución.

 Algoritmo de Eliminación de Variables
Entrada: una v.a. X de consulta, un conjunto de valores observados e para las variables de evidencia y una red bayesiana. Salida: P(X|e)

FUNCION INFERENCIA_ELIMINACION_VARIABLES(X,e,RED)
1. Sea RED_E el resultado de eliminar de RED las variables irrelevantes para la consulta realizada
2. Sea FACTORES igual a vacío
3. Sea VARIABLES el conjunto de variables de RED_E
4. Sea VAR_ORD el conjunto de VARIABLES ordenado según un orden de eliminación
5. PARA cada VAR en VAR_ORD HACER
      5.1 Sea FACTOR el factor correspondiente a VAR (respecto de e)
      5.2 Añadir FACTOR a FACTORES
      5.3 Si VAR es una variable oculta hacer FACTORES igual
                a. AGRUPA(VAR,FACTORES)
6. Devolver NORMALIZA(MULTIPLICA(FACTORES))

 En el paso nro 5 se detalla una mejor manera de implementarlo aquí. Para el desarrollo de nuestro laboratorio, hemos considerado las siguientes variables aleatorias:

• D: práctica deportiva habitual
  
• A: alimentación equilibrada
  
• S: presión sanguínea alta
  
• F: fumador
  
• I: ha sufrido un infarto de miocardio
  

Las relaciones causales y el conocimiento probabilístico asociado están reflejadas en la siguiente red bayesiana:

 Podemos usar la red bayesiana para calcular la probabilidad de fumador si se ha sufrido un infarto y no se hace deporte, P(F|i, ¬d), para ello:

• Seguiremos el siguiente orden de variables, inspirado en la topología de la red (de abajo a arriba): I, F, S,A,D.
  
• Aunque igual otro orden sería más eficiente, pero eso no lo sabemos a priori
  
• Entonces finalmente luego de los cálculos nos queda
  
• P(F|i, ¬d) = <0,48,>

Laboratorio 6

Tabla de Distribución Conjunta Completa

El caso que hemos desarrollado es : “Tráfico en la ciudad de Trujillo”(aquí puede descargar el documento), considerando las siguientes variables Aleatorias:
a. TraficoMayor

     i. true
     ii. false

b. HoraPunta
     i. true
     ii. false
c. Temporada
     i. verano
     ii. otoño-invierno
     iii. primavera
d. Semana
     i. lunes-viernes
     ii. finSemana
e. HuelgaUNT
     i. true
     ii. false
f. Feriado
     i. true
     ii. false
g. Pasaje Sube
     i. true
     ii. false
h. GasolinaSube
     i. true
     ii. false

Las mismas que para su utilización fueron abreviadas como se muestra en la siguiente tabla:

GasolinaSube	GS	lunes-viernes	l-v
HuelgaUNT	HUNT	finSemana	fs
Feriado	F	verano	v
HoraPunta	HP	otoño-invierno	o-i
Temporada	T	primavera	p
Semana	S

Y la distribución de la tabla (en fila y columnas ) fue la siguiente:

                             TraficoMayor
                             PasajeSube
                             GasolinaSube

HoraPunta Temporada Semana Feriado HuelgaUNT


A continuación veamos algunos de los valores asignados dentro de la tabla de Distribución Conjunta Completa de este caso:

A continuación algunos Ejemplos y resultados obtenidos de nuestro programa:

Probabilidad Conjunta

• P(HuelgaUniversitaria y PasajeSube)= 0.0120001

• P(HoraPunta y Feriado)= 0.011007600000000001

• P(Temporada=Verano y PasajeSube)= 0.0108004

• P(Temporada=Verano y HuelgaUNT y PasajeSube )=0.00216

• P(Traficoy y Temporada=Verano y Feriado)=0.0033078
  
  

Probabilidad Disjunta

• P(HuelgaUniversitaria v PasajeSube)=0.2480005999

• P(HoraPunta v Feriado)=0.31799350000000004

• P(Temporada=Verano v PasajeSube)=0.2292005999

• P(HuelgaUNT v EsFeriado)=0.23024059999

• P(Tráfico v Semana=finSemana)=0.51250069999

Probabilidad Condicional

• P(HoraPunta|PasajeSube)= 0.291204239964667

• P(HoraPunta|HuelgaUNT, Feriado)= 0.2912169312169311

• P(PasajeSube|GasolinaSube)= 0.06000110399823361

• P(Tráfico|HoraPunta, PasajeSube)= 0.3500206039239028

• P(Tráfico|EsFeriado)=0.34999365086083745
  

Laboratorio 5

Problema de Satisfaccion de Restricciones

• Implementar un algoritmo para PSR que utilice heurística de Grado, heurística MVR y Forward Checking para el Problema de Coloracion de Mapas

Implementamos el Problema de Satisfacción de Restricciones, para el Problema de Coloración de Mapas, mediante los siguientes algoritmos:

• Algoritmo con Heurística MVR
  
• Algoritmo con Heurística de Grado
• Algoritmo con Forward Checking
• Algoritmo con Heurística MVR y Forward Checking

Tenemos a continuación el caso visto en clase:

• Ciudades: WA, NT, SA, Q, NSW, V, T
  
• Grafo de Adyacencia:

• Colores: rojo, azul, verde

Y los respectivos resultados obtenidos luego de utilizar cada uno de los algoritmos ya mencionados:

Luego tambien lo hemos aplicado para el siguiente caso:

• Ciudades: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z

• Grafo de Adyacencia:

• Colores: rojo, azul, verde, amarillo

Y donde los resultados fueron, para el caso del:

• MVR: (A . rojo) (B . azul) (C . verde) (G . rojo) (F . azul) (K . verde) (J . rojo) (L . amarillo) (E . verde) (D . rojo) (I . azul) (M . amarillo) (H . verde) (N . azul) (O . rojo) (P . verde) (Q . amarillo) (R . azul) (S . rojo) (T . verde) (U . rojo) (W . azul) (V . verde) (X . azul) (Y . rojo)
  (Z . verde)

• Grado: (B . rojo) (I . rojo) (J . azul) (M . verde) (E . amarillo) (K . verde) (N . rojo) (O . azul) (P . amarillo) (Q . verde) (R . rojo) (S . azul) (T . verde) (C . azul) (D . azul) (F . rojo)
  (G . amarillo) (L . amarillo) (U . azul) (X . rojo) (Y . azul) (H . amarillo) (W . rojo) (A . verde)
  (V . verde) (Z . verde)

• Forward Checking: (A . rojo) (B . azul) (C . verde) (D . rojo) (E . verde) (F . rojo) (G . amarillo) (H . azul) (I . amarillo) (J . rojo) (K . verde) (L . azul) (M . azul) (N . verde) (O . rojo) (P . amarillo) (Q . verde) (R . azul) (S . rojo) (T . verde) (U . rojo) (V . azul) (W . amarillo) (X . azul) (Y . rojo)(Z . verde)
  

• MVR + FC: (A . rojo) (B . azul) (C . verde) (G . rojo) (F . azul) (K . verde) (J . rojo) (L . amarillo) (E . verde) (D . rojo) (I . azul) (M . amarillo) (H . verde) (N . azul) (O . rojo)
  (P . verde) (Q . amarillo) (R . azul) (S . rojo) (T . verde) (U . rojo) (W . azul) (V . verde)
  (X . azul) (Y . rojo) (Z . verde)
  

Veamos la implementación:

Escogemos por ejemplo la opción MVR y tenemos en la parte superior izquierda la conexión, parte inferior resultado luego de colorear, y lado derecho respuesta de las asignaciones hechas:

Escogemos la opción Grado:

Adjuntamos nuestras prueba aquí.

Proyecto 1º Unidad: "Juego Mancala"

MANCALA

A continuación veamos las características del juego en sí que implementamos, es decir algo de su historia, sus reglas del juego; luego continuaremos mencionando los algoritmos empleados.

Historia Mancala. Mancala es el nombre de una familia de juegos de tablero muy extendidos por toda África. Este juego se practicaba ya en el antiguo Egipto, pues se han encontrado tableros en la pirámide de Keops, y de allí debió extenderse a otros países de África y Asia.
Forma parte desde tiempos muy remotos de la tradición cultural de muchos pueblos y tribus, principalmente de África, y su práctica ha estado ligada a diferentes hechos, como a ritos funerarios, con motivo de mantener entretenido al espíritu del difunto; a ceremonias nupciales, para asegurar la fertilidad de la unión; y además, en casi todos los pueblos ha sido objeto de adivinación. Hoy, sin embargo, se juega sobre todo por placer y se ha convertido en el juego nacional de muchos países africanos, donde es conocido bajo diversas denominaciones, conociéndose casi doscientas variantes del juego, aunque todas ellas poseen características comunes.

Las versiones de Mancala más comunes en Europa, son el Awale (también llamado Wari), el Kakua, el Mweso o Hus (que se juega con 64 fichas en un tablero de 32 huecos), el Oware, que es una de las variantes más sencilla, y el Kalah, Kalaha o conocido simplemente como Mancala, que es la variante egipcia, la más extendida y conocida en Occidente, y es la implementada en este proyecto.

Reglas de Juego. Bueno como ya mencionamos, El Mancala se juega en un tablero que contiene dos filas de seis huecos o hoyos en cada una, y dos huecos especiales o Mancalas situados en ambos lados del tablero. Al comienzo del juego, todos los hoyos han de tener el mismo número de fichas, y los Mancalas de ambos jugadores han de estar vacíos.
Para comenzar a jugar, los jugadores se sitúan uno frente al otro, dominando el lado del tablero que se encuentra más próximo y el Mancala que se encuentra situado a su derecha, véase Figura 1.

El objetivo del juego es introducir el mayor número de fichas en el propio Mancala. Ganará el jugador que, al término del juego, tenga más de la mitad de las fichas en su Mancala (nuestro caso seria 25 el minimo mayor de la mitad ya que tenemos 48 fichas en total).

Las reglas para los movimientos a realizar son:

• Un movimiento consiste en coger todas las fichas del hoyo en el lado del jugador, e ir en contra de las agujas del reloj poniendo una ficha en cada hoyo hasta q no haya nada. Se puede dar el caso q el jugador ponga una ficha en su mancala pero no se puede dar el caso q la ponga en la mancala de su oponente, en este caso saltara al siguiente hoyo, véase Figura 2. Así mismo si fuese a dar más de una vuelta al tablero, no deberá depositar una ficha en el hoyo donde inició.

• Cuando en un movimiento, la última ficha se deposita en el Mancala del jugador al que pertenece el turno de juego, este jugador tendrá un turno extra. Pero si la última ficha de un movimiento cae en cualquier hoyo, tanto propio como del adversario, el siguiente turno será del jugador contrario, véase Figura 3.

• Cuando en un movimiento, la última ficha se deposita en un hoyo vacío del jugador que mueve, se produce una captura. El jugador tomará las fichas que se encuentren en el hoyo de su adversario situado justo enfrente y las colocará, junto a la suya, en su Mancala, véase Figura 4. El turno tras la captura será del jugador contrario.

• En el momento en que todos los hoyos de un jugador estén vacíos se llega a la situación de fin de juego. El jugador contrario, depositará en su Mancala todas las fichas almacenadas en sus hoyos, véase Figura 5. Ganará el juego el jugador que haya almacenado más fichas en su Mancala.

Algoritmos Utilizados

A continuación describimos el Algoritmo Minimax con Poda Alfa-Beta desarrollado y la función evaluación utilizada con la Heurística y Programación Genética.

Algoritmo Minimax con Poda Alfa-Beta. En el desarrollo de los juegos de dos jugadores, a uno se le denominará MAX y al otro MIN, cada uno con su turno correspondiente
Esta búsqueda realizada se puede definir en base a: un Estado Inicial, Movimientos Posible o Legales (Sucesores, luego de aplicar la Función Sucesor), un Estado Final, Valor o Función de Utilidad; los mismos que a su vez vienen a definir un árbol de juego y donde se desarrollará primero una búsqueda en profundidad, para nuestro caso profundidad limitada.

Usualmente se puede decir en una Búsqueda cualquiera, la estrategia óptima se logra alcanzar cuando tras un conjunto de movimientos posibles se llega a la meta u objetivo que viene a ser el estado ganador; sin embargo, la estrategia óptima que aquí hablamos no va por ese camino, sino mas bien consideramos que tras la realización de una jugada MAX, viene una jugada MIN y tras la misma viene otra MAX y puede ser vista en el árbol de juego (generado dado una cierta profundidad), evaluando la función del Valor Mínimax en cada nodo.

Existe un problema en el Algoritmo Minimax, el cual tiene que ver con la complejidad del mismo, ya que el número de estados a examinar o evaluar es exponencial en el número de movimientos. Sin embargo aunque este exponente no se pueda eliminar, existe una posibilidad de reducirlo a la mitad, y esto mediante la realización de una Poda al árbol Minimax, en nuestro caso: Poda Alfa-Beta, donde Alfa y Beta representan, respectivamente, las cotas inferior y superior de los valores que se van a ir buscando en la parte del subárbol que queda por explorar. Si Alfa llega a superar o igualar a Beta, entonces no será necesario seguir analizando las ramas del subárbol.

Entonces nuestro algoritmo del Minimax con poda Alfa Beta aplicado a nuestro juego Mancala (considerando el doble turno), queda:

Algoritmo MINIMAX-A-B
Entrada: nodoJuego (Mancala), Profundidad, turnoPC, Alfa (inicialmente -inf), Beta (inicialmente +inf)
Salida: el nodo (Mancala) a Jugar

1. Si el estado del nodoJuego es un final (Juego Terminado) o la profundidad de análisis restante es cero,
    1.1. Devolver nodoJuego cuyo valor sea el valor calculado mediante la función de Evaluación respectiva.
    1.2. En caso contrario, hacer
          1.2.1 Calcular los SUCESORES del nodoJuego
          1.2.2 Si la lista de SUCESORES es vacía
                1.2.2.1 Devolver nodoJuego cuyo valor sea el valor calculado mediante la función de Evaluación respectiva.
               1.2.2.2 En caso contrario, si el jugador del nodoJuego es MAX
                      1.2.2.2.1 Devolver el nodo de la lista de SUCESORES obtenido con la función MAXIMIZADOR-A-B
                      1.2.2.2.2 Sino Devolver el nodo de la lista de SUCESORES obtenido con la función MINIMIZADOR-A-B

Veamos sólo la función MAXIMIZADOR-A-B, ya que el otro es similar, solo que para los casos donde se consideran a Alfa, en el otro se consideran a Beta.

Algoritmo MAXIMIZADOR-A-B
Entrada: Sucesores a evaluar, Profundidad, Alfa, Beta
Salida: el nodo (Mancala) a Jugar Máximo

1. Crear las siguientes variables locales
     1.1. MEJOR-SUCESOR (para almacenar el mejor sucesor encontrado hasta el momento o el sucesor por defecto en caso de no encontrar ninguno que mejore la cota ALFA), cuyo valor es el primer elemento de la lista de SUCESORES
     1.2. VALOR (para almacenar el mejor valor encontrado hasta el momento), cuyo valor inicial es 0.
2. Para todo SUCESOR de la lista de SUCESORES hacer
     2.1. Calcular el VALOR minimax-a-b de SUCESOR, disminuyendo en 1 la profundidad de análisis y utilizando los valores de ALFA y BETA.
     2.2. Cuando el VALOR calculado sea mayor que ALFA, hacer
             2.2.1 Actualizar ALFA, que pasa a ser VALOR
             2.2.2 Actualizar el MEJOR-SUCESOR, que pasa a ser SUCESOR
     2.3. Cuando el valor de ALFA supere o iguale al de BETA, terminar el bucle: se ha producido un corte alfa.
3. Poner ALFA como valor del MEJOR-SUCESOR.
4. Devolver el MEJOR-SUCESOR.

Función de Evaluación. Tenemos para la función de evaluación dos formas de hallarla:

• F1: Ser Ganador del Juego = 500 puntos.
  
• F2: Puntos a Favor
  
• Heurística=F1+10*F2
  
• Heurística Total= Heurística a favor – Heurística del oponente
  

Programación Genética
La Programación Genética es parecida a los algoritmos genéticos con algunas variaciones como por ejemplo:

1. Los cromosomas ya no son cadenas de 1’s y 0’s en este caso son árboles que representan programas, ver figura 6.
   

1. El operador de mutación viene dado de la siguiente manera, seleccionar un subárbol, borrarlo y crear un subárbol aleatorio.
2. El operador de cruzamiento consiste dado 2 árboles, seleccionar 2 subárboles aleatoriamente e intercambiarlos.
   

En el caso de nuestro programa hemos usado las siguientes funciones:

• Si _ <>
• Resta
  
• Adición
  
• valorDe _: Calcula el valor de un depósito dada una posición.
  
• Nuestro conjunto de terminales esta compuesto de números entre 0 y 13.
• 
  

Implementación

Implementamos el juego Mancala, para un jugador (jugador 1 ó A y PC jugador 2 ó B) como para 2 Jugadores, y bajo la siguiente estructura de Juego:

Bueno el de 2 jugadores no tiene nada de interesante ya que ahí interactúan sólo dos personas, sin embargo, para el caso de 1 jugador, éste tendrá a la “máquina” como contrincante, siendo la persona el que inicie la jugada (jugador 1). Bueno aquí tenemos luego opciones de jugar por niveles, es decir nivel Principiante, Intermedio, Avanzado, y tenemos la opción de Programa Genético.

Para el caso de escoger cualquiera de los 3 niveles, se enfrentarán a la máquina, la misma que utilizará el algoritmo Minimax con Poda Alfa-Beta (donde el factor de ramificación máximo es 6), a profundidades: 2 (para Principiantes), 4 (para Intermedio), 6 (para Avanzado), y utilizará como función de evaluación la heurística ya definida por nosotros (que fue ya mencionada con anterioridad).

Para el caso de escoger Programa Genético, la máquina utilizará un programa genético creado luego de ejecutar Programación Genética vs Poda Alfa-Beta, donde tenemos a la probabilidad de mutación de 0.01, probabilidad de cruzamiento de 0.9, tamaño de población igual a 10, y para el caso de Poda Alfa-Beta profundidad 6.

A continuamos veamos como se ejecuta el juego: Para ellos empieza el jugador 1, es decir nosotros,

Entonces escogemos mover las fichas de la posición 2 (según nuestra estructura de juego ya mostrada),

Vemos que nos toca realizar otra jugada dada por la regla del turno extra, entonces escogemos mover las fichas de la posición 1, y vemos como inmediatamente la máquina también ejecuta su jugada y nos toca ya otra vez jugar a nosotros:

Bien finalmente luego de unas cuantas jugadas se termina el juego, donde según la siguiente figura, la máquina nos ganó 35 a 13 fichas :(

Descargue aquí el informe del trabajo.

Poster

Is There an Intelligent Agent in Your Future?

El poster desarrollado lleva como título: Is There an Intelligent Agent in Your Future?, al cual puede tener acceso a través de la siguiente dirección: http://www.nature.com/nature/webmatters/agents/agents.html

Imagínese usted que un día desea salir de viaje, pero no ha decidido a donde y desea asesoramiento de alguien...¿Qué haría?... Lo más normal es que vaya hacia una agencia de viaje y solicite información a una persona (un guía turistico) ... pero que tal UN AGENTE !!!

mmm daría que pensar en la forma como puede ser capaz de interactuar con un agente... Bueno es necesario saber que eso es posible, pero para ello éste debe cumplir ciertos requisitos para lograr ser "UN BUEN AGENTE".

Los requisitos que debe cumplir son:

1. Comunicativo: El agente deber tener conocimiento del tema de interes, por ejemplo un agente para venta de libros, tiene que tener el conocimiento adecuado para responder a nuestras inquietudes y estar acorde con nuestras expectativas. Actualmente este conocimiento se representa mediante ontologías, aquí un ejemplo.
   
2. Capaz: El agente debe ser capaz de realizar acciones. Principalmente la diferencia entre un agente y un asesor, es que el primero no solo te da consejos sino tambien ofrece el servicio de hacer el trabajo por ti :D. Que el agente sea capaz involucra ciertos items dependiendo del contexto por ejemplo, si a mi agente le digo que me busque papers de IA y encontro uno muy bueno pero es pagado, el agente necesitaria mi nº de tarjeta de credito, el monto a pagar y realizar la transacción bancaria.
   
3. Autónomo: Un agente debe tener un nivel intermedio de autonomía, ya que por ejemplo en el caso que tuviera poco nivel de autonomía ya no cumpliria su rol de agente porque por cada item que necesite nos lo consultaria y más bien cumpliria un rol de asesor mas no de agente. Por el otro lado si tiene mucho nivel de autonomía pudiera realizar muchas cosas sin nuestra autorización, por ejemplo compra cosas con nuestro dinero sin autorización, vender cosas, etc.
   
4. Adaptativo: El agente debe ser capaz de adaptarse ya que funcionara para diferentes usuarios (con diferentes maneras de pensar y actuar), diferentes ambientes, etc logrando asi de una mejor manera cumplir con los requerimientos del usuario. Este objetivo se puede lograr de diversas maneras por ejemplo cada vez que un nuevo usuario se registre se le pida cierta información para clasificarlo en un grupo (cluster) de usuarios que ya tenemos logrando asi tener un patron de comportamiento inicial, luego este patron se ira amoldando a las preferencias especificas del usuario.
   

A continuación algunas fotos del dia de la presentación de nuestro poster desarrollado sobre el tema en mención:

Poster Realizado

Renzo, Rulber, Leissi y Nils exponiendo