Dedicado a mis proyectos en Gambas ,un lenguaje de programación parecido al Visual Basic + Java pero ampliamente mejorado y...¡¡para gnu/linux!!.La potencia del gnu/linux sumada a la facilidad del Basic



Consultas, Desarrollo de programas y petición de presupuestos:



lunes, 31 de enero de 2011

Aplicación Algoritmo MiniMax: Juego 3 en raya con sonido

           Aquí os dejo mi primer juego de Inteligencia Artificial (I.A.)... no tiene mucho merito porque gracias al videotutorial de Jorge Rubira, de la revista Solo Programadores, donde explicaba como hacer el algoritmo del MiniMax para un juego de 3 en raya en Java, "solo" he tenido que traducir de Java a Gambas2.
          Pero bueno, creo que el resultado obtenido y lo que he aprendido (me he visto el vídeo a cámara lenta por lo menos 5 veces)...pues merece la pena haberlo hecho (y también bastante parte del  código es reutilizable para otros juegos de I.A.).


 Aqui os dejo el código fuente

Nota:
El archivo es de 2.1 mb, ya que le he incluido algunos sonidos.

Saludos

¿no encuntras blog sobre gnu/linux? Respuesta: Estamos en....

Una de las cosas más interesante que me he encontrado en el blog:
http://acercadeubuntu.blogspot.com/

Es que tiene unos cuantos enlaces a sitios donde te añaden a listas de blog, (y páginas web), donde hacen una calificación "un top" de tu blog.

La verdad es que me parece buena idea, para encontrar y ver otros blogs dedicados al gnu/linux, de otras partes del mundo, sin tener que buscar en google.

http://www.rankinglinux.com/

 http://www.freesoftwaretop.com/
http://bitacoras.com/top/bitacoras/geo/uy

http://www.wikio.es/blogs/top/Linux
http://planeta.gleducar.org.ar/


Saludos

domingo, 30 de enero de 2011

Inteligencia Artificial: Algoritmos MiniMax y Poda Beta

Siempre me pregunte como se programaban los juegos tales como el ajedrez, damas, etc... ¿tenían las jugadas "preprogramadas"? ¿sabían todas las posibles mejores soluciones?...pues no.

El programa realmente "piensa" o mejor dicho tiene:
 - Una parte dedicada a "valorar" la "posición" (situación de las piezas en el tablero, nº de piezas, dominio del centro del tablero, protección del rey, protección del rey contrario, etc... ), y le da un valor a dicha situación. Ha habido hasta ajedrecista de primera categoría, que han ayudado a los programadores en esta fase.


 - Crea un árbol de posibles jugadas y respuestas a esas jugadas (varios niveles de profundidad). Cuanto mayor profundidad mejor juega. Esta fase es muy importante el ordenador que tengamos. (no es lo mismo un anticuado 8086 a un superordenador que realiza billones de cálculos por segundos)

 - Y finalmente, mediante un algoritmo llamado Poda Alfa Beta (variante del algoritmo MiniMax), elige la jugada que más le convenga...

Por supuesto este algoritmo se puede aplicar a todos los juegos de tablero por turnos (en principio de 2 jugadores), solamente hace falta cambiar la forma de "valorar" la "posición" de la partida, dependiendo de las reglas del juego.

Bueno os dejo un artículo que he encontrado en San Google sobre este algoritmo y su aplicación a juegos (3 en raya y al ajedrez).

APLICACIÓN DEL ALGORITMO PODA ALPHA-BETA PARA LA
IMPLEMENTACION DEL JUEGO “AJEDREZ”

Jorge Edilberto Alvarado Valderrama, Lesly Rodríguez Pinillos
jorgealvarado@seccperu.org, leslyrp@hotmail.com
Universidad Nacional de Trujillo
Facultad de Ciencias Físicas y Matemáticas
Escuela Académico Profesional de Informática
Resumen: 
El siguiente trabajo de investigación, tiene como propósito mostrar la implementación de juegos basados en computadoras, aplicando el campo de la Inteligencia Artificial, mediante la implementación del algoritmo Poda Apha-Beta. Para mostrar la aplicación de un juego de dos adversarios, hemos seleccionado el juego del “Ajedrez”, que tiene un alto grado de complejidad
computacional, el cual describiremos las técnicas usadas para implementarlo.
Palabras Claves: Inteligencia Artificial, Teoría de Juegos, MiniMax, Poda Alpha-Beta, Ajedrez.

 1. Introducción
La inteligencia Artificial, es una campo de que ha tomado gran interés en los últimos tiempos debido a su capacidad de poder resolver soluciones imitando el razonamiento lógico de las personas y hasta el mecanismo de cómo ellas la resuelven.
Un tema interesante a tratar a lo que concierne a la IA son los juegos. Así por ejemplo, el juego del ajedrez es un juego de mesa para dos contrincantes y es uno de los juegos mas mencionados dentro de la teoría de juegos de la
Inteligencia Artificial, por lo que tiene bien definida su meta (el Mate) y sus acciones (conjunto de movimientos de cada una de las piezas que la conforman), las cuales, por cierto, hacen del juego algo complicado de
programarlo, pero no imposible. Este juego fue estudiado por Claude Shanon y hasta el mismo Alan Turing, los cuales sugirieron algunas formas de representarlos en un ordenador.
Existen, pues, varias técnicas de búsqueda para el desarrollo de este juego. Dentro de las técnicas de búsqueda que hemos estudiado, hemos considerado utilizar la búsqueda de Poda Alfa Beta, la cual es muy eficiente en la búsqueda de una solución en un 30% comparada con la  Búsqueda de MiniMax. Sin embargo la elección de una  heurística apropiada es lo que define mejor la solución del  juego. Para este trabajo consideramos tres heurísticas las  cuales explicaremos mas adelante.
Para este trabajo, empezaremos definiendo algo  de la teoría de juegos; luego antes de entrar el desarrollo  del algoritmo Poda Alpha – Beta, analizaremos la técnica  del Minimax, para luego explicar las heurísticas que hemos  utilizado para obtener la utilidad, elemento necesario para  definir una adecuada jugada.

2. Teoria de Juegos
Los juegos han sido estudiados a lo largo de la historia formulándose incluso modelos matemáticos que permitiesen desarrollarlos.
En un principio, estos juegos fueron estudiados por una rama de la ciencia denominada Investigación Operativa (IO), la cual proporcionaba técnicas que solo podrían ser aplicables si existía un procedimiento finito [1]. Con el surgimiento de la Inteligencia Artificial se crean nuevos algoritmos de búsquedas que permiten
desarrollar soluciones dentro de procedimientos no finitos.
Uno de estos algoritmos es el algoritmo de Poda Alpha-Beta que es muy usado en la teoría de Juegos y que permite encontrar soluciones dentro de un campo de búsquedas infinito. Sin embargo para poder entender mejor esta técnica, es necesario y conveniente primero
entender la técnica de búsqueda Minimax, que es una técnica que se centra en la resolución de problemas de búsquedas, basadas en la alternación de dos entes o agentes a los cuales se les denominan Min y Max[2].


3. Estrategia MiniMax
La estrategia minimax es una estrategia de búsqueda exhaustiva mediante un árbol de búsqueda. Este algoritmo considera el caso de 2 participantes a los que se les denomina Max y Min[1].
El que inicia el juego es Max y existe una alternancia en la participación del juego. Por lo tanto lo que tiene que hacer Max, es determinar la secuencia de jugadas que conduzca a un estado Terminal ganador o favorecedor.
La figura 1 muestra parte del árbol generado para la búsqueda por la técnica de Minimax para el juego del tres en raya [5].
Sin embargo, esta búsqueda muchas veces tiene que evaluar ramas innecesarias que no le traerán beneficio alguno para obtener el mejor resultado. Por lo tanto, es aquí donde se plantea la solución mediante la poda de esas ramas que no beneficiaran en nada a la mejor jugada: La técnica de Poda Alpha-Beta.
El algoritmo 1 muestra la implementación de la técnica de Minimax en forma recursiva [3].
Algoritmo 1: Algoritmo recursivo de la técnica de Minimax
Entrada:
  - Nodo N.
Salida:
  - Valor de utilidad de N
-------------------------------------------------------------------------------------------------------------
Si N es nodo Hoja
     ValorUtilidad<-función de utilidad
De lo contrario
Para cada nodoHijo Hi de
      valorUtilidadi<-MiniMaxR(Hi)
Fin para
Si N es max
       valorUtilidad<- max(H1,H2,...Hn)
De lo contrario
       valorUtilidad<- min(H1,H2,...Hn)

Devolver (valorUtilidad)



4. Poda Alpha-Beta


Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcional utilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información. Es una extensión en particular del algoritmo de Búsqueda Minimax en juegos
de dos contrincantes [2].
Cada vez que se evalúa un nodo u hoja, el algoritmo determina s los nuevos hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así, eso significa que seguir analizando esa rama es desperdiciara
recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.
El algoritmo 2, muestra como es el desarrollo para una búsqueda por medio de la Poda Alpha –Beta.
En el algoritmo 2, se detalla las entradas. Para ingresar al algoritmo, se necesita ingresar el nodo a ser evaluado, del que se obtendrá su utilidad, así como la utilidad del padre para evaluar si es que la nueva utilidad afecta o no al nodo padre. De no ser así, se procederá a podar la rama [6].
Una vez podada la rama, la nueva utilidad será la última en ser registrada o actualizada. Esto se da mediante la variable fNodo, que contiene la función de utilidad del nodo ingresado [7].
Algoritmo 2. Algoritmo Poda Alpha–Beta
Entrada:
- Nodo, fNodoP
Salida:
- fNodo
----------------------------------------------------------------------------------------
Si nodo es MAX
     fNodo <- -inf
De lo contrario
     fNodo <- inf
fin si
Si nodo es hoja
 fNodo <- utilidadNodo(nodo)
de lo contrario
   para cada ficha fi que se pueda mover
      para cada accion aj de fi
          nodoH <- crear nodo con ai
          nodoH <- PodaAb(nodoH,fNodo)
          si nodo es MAX
                si fHijo> fNodo
                            fNodo<- fHijo
                            si fNodo>=fNodoP
                                    eliminar fNodo
                                    retorna null;
                             fin si
                fin si
           fin si
           si nodo es MIN
                    si fHijo < fNodo
                           fNodo<- fHijo
                           si fNodo=<fNodoP
                                 eliminar fNodo
                                 retornar null;
                            fin si
                    fin si
           fin si
      fin para
  fin para
retorna nodo;
fin si

-----------------------------------------------------------------------------------------------------------

5. Juego del Ajedrez.
El juego del ajedrez es un juego adecuado para tratarlo mediante técnicas de IA debido a que tiene claramente definidos el objetivo que se quiere alcanzar
(meta) y los medios para llegar (movimientos permitidos) [1].

En este juego, el programa en todo momento debe conocer la configuración del tablero para la maquina poder tomar la decisión adecuada (jugada), que le permita ganar.  Para ello necesita de gran capacidad de almacenamiento de
información, utilizando estructuras que le permitan llegar a conclusiones coherentes.

El juego se desarrolla sobre un tablero de 8 filas y 8 columnas, sobre las cuales se colocan fichas de 2 colores que simbolizan a los 2 oponentes, estos colores son generalmente: Blanco y Negro. Este juego además posee un sin numero de fichas, de diferente tipo y movimiento.

Así pues tenemos:
• Peón
• Torre
• Alfil
• Caballo
• Reina
• Rey
La Tabla 1 ilustra los movimientos permitidos para las diferentes fichas en un juego de ajedrez. 
        - La primera fila indica el tipo de movimiento, ya sea horizontal, vertical, diagonal o en forma de L.
        - La segunda fila indica la dirección hacia donde puede moverse: 
              Arriba (Arr) o Abajo (Aba). 
        - El resto de filas indican las fichas del ajedrez: Peon (P), Alfil (A), Torre (T), Caballo (C), Dama (D) y Rey (R). 
           -El número indicado en las casillas indican la cantidad de casillas que se pueden mover, así: 1 significa que solo puede moverse una sola posición,
mientras que n significa que puede moverse mas de 1 posición dentro del límite del tablero del ajedrez.

Cada jugador al inicio de cada jugada posee 16 elementos, mostrados en la figura 3. Sin embargo, la configuración de cada movimiento que se pueda generar y las posibles acciones que estas puedan sugerir, hacen de este juego algo interesante, motivo por el cual se ha tomado énfasis en estudiar este juego empezando el uso de búsquedas sistemáticas para diseñar programas por ordenador.

Las complicaciones que presenta diseñar una búsqueda adecuada para este juego son bastantes, dentro de las cuales la mas principal es la complejidad espacial en un ordenador, motivo por el cual muchas veces se utiliza una determinada profundidad hasta donde se puede llegar a evaluar.


6. Estructura de Datos Utilizada.
La estructura del node que se ha utilizado, tiene la siguiente estrucutra:

Id
IdPadre
Tipo
(Max o Min)
Estado
(config. Del tablero)
Funcion de utilidad
Mejor accion
Prof.
Id: El primer campo indica el ident del nodo que se esta generando.
IdPadre: El siguiente dato, corresponde al padre que lo generó.
El tipo hace referencia a que nodo se esta analizando: si es Max o es Min. En caso de ser Max, el algoritmo tratará de obtener la jugada de mayor utilidad,pues genera beneficio para Max; sin embargo cuando es Min, la maquina elegirá la menor utilidad posible, perjudicando al oponente.
El estado, es la configuración del tablero, es decir, corresponde al ambiente que será analizado por la maquina.
La función de utilidad corresponde a la utilidad calculada por la heurística explicada posteriormente [2].
La mejor acción es una variable que me va recolectando el camino que se genera con la mejor jugada posible, para esto debe basarse en la utilidad.
Y finalmente la profundidad, indica, que tan profundo se va a analizar las jugadas, es decir, si se escoge una profundidad de 4, esto indicaría que se va analizar 2 turnos para ambos jugadores y de allí se extraerá el mejor camino.

7. Aplicación
Hemos aplicado una heurística en la que se
considera un peso para cada pieza según el color:
• Piezas Blancas
   - Peón : 1
   - Caballo : 3
  - Alfil : 3
 - Torre : 5
- Reina : 10
- Rey : 50
• Piezas Negras
   - Peón : -1
   - Caballo : -3
  - Alfil : -3
 - Torre : -5
- Reina : -10
- Rey : -50
Las Heurística para la función de Utilidad que  logramos analizar son las siguientes:
1º Capturar Posición del Rey Blanco: xRB, yRB
2º Capturar Posición del Rey Negro: xRN, yRN
3º Sumar N° de piezas Blancas: sumaB
4º Sumar N° de piezas Negras: sumaN
5º Calcular que tan protegido esta el rey blanco de las piezas negras: BRP
6° Calcular que tan Protegido esta el rey Negro de las piezas blancas: NRP
7° Calcular que tan cerca están las piezas negras del rey Blanco: BAR
8° Calcular que tan cerca están las piezas blancas del rey Negro: NAR
Finalmente se obtendrá la Utilidad con la siguiente ecuación:


La primera división, mide que tanta es la diferencia de fichas entre los dos oponentes. Si uno de ellos tiene una cantidad de pesos mayor en fichas,
probablemente pueda tener más ventajas sobre el otro, por lo tanto pueda ganar.
La segunda división, es una probabilidad que hemos considerado y mide que tan protegido esta un rey. Si un rey tiene mas cerca a sus piezas, entonces la
probabilidad que sea comido es menor, por lo tanto menos oportunidad de ser atacado directamente.
La tercera división mide la probabilidad de que un rey sea atacado por el oponente. Si un rey tiene mas fichas enemigas cerca, entonces la probabilidad de ser atacado aumenta, y por lo tanto pueda ejecutarse el mate.

Por lo tanto, la ecuación presentada, mide que  tanta ventaja tiene un oponente sobre el otro.

8. RESULTADOS

Para la aplicación, hemos considerado varias profundidades, que determinaban el nivel de juego:
Profundidad 3 -> Nivel Principiante
Profundidad 4 -> Nivel Intermedio
Profundidad 5 -> Nivel Avanzado

Estas profundidades mostraron tener óptimos resultados, demorando en el último, a lo mas 30 segundos de ejecución, tiempo razonable debido a la gran cantidad de nodos que se tenían que evaluar.
9. CONCLUSIONES
9.1 El algoritmo de Poda Alfa-Beta, es un algoritmo eficaz en cuanto a la búsqueda de una solución, si bien no comparamos en este trabajo la diferencia
con el otro algoritmo estudiado, MiniMax, hemos probado que la poda por cierto camino que no aportara nada a la decisión aumenta en un 30% la
eficiencia de la búsqueda.
9.2. Las limitaciones que encontramos para este trabajo es trabajar con respecto a la profundidad. Esto se debe a que trabajamos con una profundidad no tan alta, como 5 en el trabajo presentado, teniendo una respuesta de menos de 1 minuto en la búsqueda de la solución.
9.3. En el trabajo presentado, hemos considerado dos heurísticas que hemos creído conveniente considerar: una basada en el ataque a un rey y otra basada en la defensa de un rey. Estas dos técnicas nos han permitido tener un mejor resultado en la toma de una decisión, mejorando la búsqueda sin  llegar a una profundidad muy alta.

10. Referencia Bibliográfica

[1] Francisco Astudillo Pacheco, Daniel Borrajo Millan, Carmen Tarta Alcalde y Irma Trueba Valle, “Informática Aplicada: Juegos Inteligentes en
Microordenadores”, Ediciones Siglo Cultural, España, 1986.
[2] Stuart Russell and Peter Norvig, “Inteligencia Artificial: Un Enfoque Moderno”, Edición Prentice Hall, ISBN 0-13-10385-2, 1996.
[3] Francisco Jose Ribadas Pena, “Busqueda en Espacio
de Estados”
[4] “Juegos y MiniMax: Poda Alpha Beta”, [en linea], Formato PDF,
2006,Disponible en: http://arantxa.ii.uam.es/~ia/p4/p4.pdf
[5] José Ignacio Nuñez Varela, “Introducción a la Inteligencia Artificial”, [en línea], Universidad Autónoma de Juan Luis Potosí, Formato PPT, 2007,
Disponible en: www.itnuevolaredo.edu.mx
[6] “Inteligencia Artificial: Algoritmo Poda Alpha- Beta”
[7] “Definición de una Poda Alpha-Beta”, [en línea], Disponible en: http://www.lania.mx/~asanchez/IA/minimax3.html
-------------------------------------------------------------------------------------------------------------------------
Documento:http://www.lania.mx/~asanchez/IA/minimax3.htmlDefinición de una Poda Alpha Beta

Queda claro que el arbol empieza a crecer, y en un juego de ajedrez el nivel de expertez del juego se mide por que tantas jugadas adelante vel el minimax, normalmente de va desde 1 ply hasta 6 plys completos. por esto es necesario podar un tanto el arbol, para esto se tiene varios métodos entre ellos la poda Alfaa Beta y la poda de Crash Cut

PODA Alfa Beta Asumiendo que un jugador Alfa tiene que maximizar lo que el otro jugador Beta tiene que minimizar, podemos almacenar la información que van obteniendo los dos y retroalimentarla.
Veamos esto en un ejemplo, en el algoritmo basico de MINIMAX a dos niveles se tiene que
  • 1. Abrir el arbol
    • 1.1 Todas mis jugadas
    • 1.2 Todas sus jugadas
  • 2. Aplicar la evaluación en todos sus hijos
  • 3. Minimizar por nodo en sus jugadas ( beta )
  • 4. Maximizar en todo mis jugadas
  • 5. Seleccionar la mejor  ( alpha )
Asi por ejemplo vemos la apliacación en la figura
Sin embargo el numero de tiradas puede crecer, con la poda alfa beta podemos eliminar con el conocimiento que se va procesando si dejamos hasta el final la evaluación de los  nodos, veamos la figura siguiente:

 

  • En la figura observamos que una vez que minizo el primer nodo el valor beta = 3 indica al jugador alfa que cuando menos ya podra obtener un valor >=3 por lo que no tiene caso evaluar jugadas menores a 3 para el nodo siguiente, asi vemos que cuando el jugador beta minimiza el segundo nodo, se nota que una vez encontrado el valor 1 como su trabajo es minimizar el nodo que subira sera unicamente <=1 y por ende el jugador alpha no va a usarlo, por lo que en algoritmo minimax resulta posible no evaluar  las jugadas marcadas con x, con el correspondiente ahorro de tiempo ( el ahorro se puede dar en tres modos : la creacion de la jugadas, el recorrido del arbol y la evaluación ) . Sin embargo para el caso del tercer nodo el jugador beta tendra despues de encontrar el tablero con valor 8 tiene que continuar evaluado, ya que 8 es mayor 3 y el jugador alfa si lo tomaria, por lo que el beta debe buscar una tirada menor, la cual encuentra con la jugada de valor 2.  Quedando el algoritmo como sigue:

    • 1. Abrir la siguiente jugada mia generando un nodo para el con alfa = valor pequeño
      • 1.1 Si ya no hay mas jugadas :  me voy a 4.
    • 2. Abrir la siguiente jugada de él con  beta = valor grande
      • 2.1 Si ya no hay mas jugadas y Si  beta > alfa :  alfa = beta y salto al paso 1
    • 3. Evaluo su jugada
      • 3.1. Si la jugada de él es mayor que beta me salto al paso 1
      • 3.2. Si la jugada de él es menor que beta :   beta = evaluacion y me salto al paso 2
    • 4. Tomo la jugada que me dio el último alfa y termino
    Este ahorro permite generar mas hijos en jugadas posteriores para esto es necesario modificar el algoritmo para hacerlo recursivo, lo que se logra con modificar el paso 3
    • 0.  numtiradas = profundidad
    • 1. Abrir la siguiente jugada mia generando un nodo para el con alfa = valor pequeño
      • 1.1 Si ya no hay mas jugadas :  me voy a 4.
    • 2. Abrir la siguiente jugada de él con  beta = valor grande ;
      • 2.1 Si ya no hay mas jugadas y Si beta > alfa :  alfa = beta y salto al paso 1
    • 3  Evaluación
      • 3.1.1 Si numerotiradas = profundidad :  Evaluo la jugada
      • 3.1.2 Si numerotiradas < produndidad :  numerotiradas = numerotiradas + 1 ;voy( recursivamente ) a paso 1
      • 3.2.1 Si la jugada de él es mayor que beta me salto al paso 1
      • 3.2.2 Si la jugada de él es menor que beta :   beta = evaluacion y me salto al paso 2
    • 4. Tomo como valor la jugada que me dio el último alpha y regreso a quien me llamo ( recursivamente )



    Pseudo Código para una poda Alfa Beta en Minimax 
    import java.awt.*; 
    import java.applet.Applet; 
    
    public class alfabeta extends Applet 
     // Inicializa variables
    
    int[] TIRADA = new TIRADA[2]  // TIRADA[1]  es el tablero TIRADA[2] es el valor del tablero
    int[] POSIBLE = new POSIBLE[2] ; int[] MinTirada = new MinTirada[2] ;
    int[] MaxTirada = new MaxTirada[2] ;
    int Jugada, numtir, procrece ; // variables que defiene el numero de tablero y la profundidad deseada
     
    //  Procedimiento maximizacion y minimizacion recursivamente 
    
    public void init() 
      {  numtir =  profundidad ;   
         Juego = "en Proceso"; Jugada = 0; tiro= 0;    
         while (Juego <> "en Proceso")   
             {   procrece = 1;   
                 TIRADA =  Maximiza(Jugada, alfa, beta, procrece); 
                 Grafica(TIRADA[1]);  Jugada = TIRADA[1] ;     
                 Juego = EvaluaTerminacion(TIRADA);  } ;   
           };  
    
    // Procedimiento para la Maximizacion   
         int  Maximiza(Jugada,alfa,beta,procrece)      
            {  alfa = -infinito;
               for ( j= 1;  j <= Njugadas ;  j=j+1 )   
                 {   MaxTirada[1] = SiguienteTab(j,Jugada); POSIBLE = Minimiza(MaxTirada[1],alfa,beta,procrece); 
                     if ( beta > alfa ) alfa = beta; 
                     if alfa >= POSIBLE[2]  then TIRADA = POSIBLE   };          
             return TIRADA ;   }  
    
    
    // Procedimiento para la Minimizacion 
         int  Minimiza(Jugada,alfa,beta,procrece)      
            {  procrece = procrece +1;  Poda = "enproceso" ; beta = + infinito ;
               for ( j = 1;  j <= Njugadas AND poda = "enproceso" ;  j=j+1 )   
                 {  MinTirada[1] = SiguienteTab(j, Jugada);
                    if ( procrece = numtir ) POSIBLEMIN[2] = Evalua(MinTirada[1])   
                         else POSIBLEMIN =  Maximiza(MinTirada[1], alfa, beta, procrece); }
                    if ( MinTirada[2] <= beta  )
                             { TIRADA = POSIBLEMIN ;  beta = MinTirada[2] ;
                    if (beta <= alfa)   Poda = "hecha" ; }
                  }
                Return TIRADA }
       
    // Procedimiento para la Evaluacion
         int  Evalua(Jugada)     
    
    // Procedimiento para la Graficacion 
         int Grafica(Jugada)   
    
    // Procedimiento para la determinacion de la siguiente jugada
         int  SiguienteTab(j, Jugada)       
    
    } // end class Alfabeta

    Este ahorro permite generar mas hijos hacia adelante sin un crecimiento exponencial como se muestra en la gráfica

     


    La Figura muestra adicionalmente una poda denomida de corte agresivo, la cual tiene como objetivo eliminar completamente de la evaluacion toda una zona de un arbol en caso de que se considere que dicha zona contiene una jugada que de antemando se perdibe mala, aunque al final se pudiera  ganar por esa ruta, este es el caso para el caso del ajedrez, de decidir no evaluar tableros que asuma la perdida de una pieza clave como la reina, que aunque resulte factible, el programa no quiere considerarlas. A esta poda se le denomina  Corte agresivo o Crash Cut. El pseudocódigo para dicha poda se ve reflejado en el metodo de maximizacion

     

    // Procedimiento para la Maximizacion
         int  Maximiza(Jugada,alfa,beta,procrece)
            {    alfa = -infinito;
                   for ( j= 1;  j <= Njugadas  ;  j=j+1 )
                  {   MaxTirada[1] = SiguienteTab(j,Jugada);
                        If (NotCut(MaxTirada[1])   // la funcion NotCut regresa verdad si no hay un corte agresivo en la jugada considerada
                             {   POSIBLE = Minimiza(MaxTirada[1],alfa,beta,procrece);
                                   if ( beta > alfa ) alfa = beta;
                                   if alfa >= POSIBLE[2]  then TIRADA = POSIBLE   }
                 };
       return TIRADA ;   }

    jueves, 27 de enero de 2011

    Saber si un punto está dentro o fuera de polígono





    He encontrado este algoritmo, muy interesante, para determinar si un punto esta dentro o fuera de un poligono irregular.

    Método 1:  El algoritmo basado en Jordan

    nota: la explicacion lo he encontrado en este foro: http://foro.gabrielortiz.com/index.asp?Topic_ID=24147, gracias a Gabriel)

    Transcribo literalmente:
    Hay varios algoritmos para la determinación de si un punto está dentro de un polígono. La función más fácil de implementar es la del "trazado de rayos", que consiste en trazar una línea con origen en el punto designado por el usuario paralela a alguno de los ejes (X ó Y, da igual). Analíticamente, cuentas el número de intersecciones que se producen con cada una de las líneas del polígono. Si el número de intersecciones es impar, entonces está dentro. Si el número de intersecciones es par, entonces está fuera. El principio se puede ver en esta imagen:





    La geometría analítica que necesitas es bastante sencilla de programar. No hay matemáticas muy complicadas como puedes ver en el código que te paso para C que fácilmente puedes adaptar a PHP o al lenguaje con el que estés desarrollando. La función devuelve los valores Fuera o Dentro.

    #define MIN(x,y) (x < y ? x : y)
    #define MAX(x,y) (x > y ? x : y)
    #define INSIDE 0
    #define OUTSIDE 1

    typedef struct {
    double x,y;
    } Point;

    int InsidePolygon(Point *polygon,int N,Point p)
    {
    int counter = 0;
    int i;
    double xinters;
    Point p1,p2;

    p1 = polygon[0];
    for (i=1;i<=N;i++) {
       p2 = polygon[i % N];
       if (p.y > MIN(p1.y,p2.y)) {
       if (p.y <= MAX(p1.y,p2.y)) {
          if (p.x <= MAX(p1.x,p2.x)) {
              if (p1.y != p2.y) {
                  xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
                  if (p1.x == p2.x || p.x <= xinters)
                    counter++;
                  }
               }
           } 
        }
       p1 = p2;
    }

    if (counter % 2 == 0)
    return(Fuera);
    else
    return(Dentro);
    }



    Otra formula de comprobar si un punto esta fuera o dentro de un poligono:
    El algoritmo –Radial-
    Existe una alternativa fiable y precisa al método de jordan: se trata de un algoritmo al que hemos llamado "radial", por su peculiar manera de abordar el problema. Es un proceso extremadamente simple, que responde al análisis de la siguiente expresión: , donde cada término equivale a la diferencia de ángulos entre dos radios consecutivos (grafico 5).

    Gráfico 5
    El procedimiento consiste en recorrer ordenadamente todos los lados del polígono, calculando el ángulo formado por sus extremos y las rectas que los unen al punto P (por supuesto, siempre se tomarán los ángulos menores o iguales a radianes). El signo a considerar será: positivo, si el sentido de crecimiento del ángulo es antihorario, y negativo en caso contrario, o viceversa.
    En el ejemplo, llamaremos (1) al ángulo comprendido entre V1 y V2, (2) al comprendido entre V2 y V3, y así sucesivamente. El último término es (9), y corresponde al ángulo medido entre V9 y V1. Obsérvese que los ángulos (2) y (4) son negativos.
    Pues bien, si sumamos todos los términos, tan solo podremos obtener dos posibles resultados: 0 o 2. En el primer caso, significará que el punto P está fuera del polígono, y en el segundo que está forzosamente dentro. Así de simple.
    Obsérvese que, en el ejemplo:
    1+ 2+ 3+ 4+5+ 6+ 7+ 8+ 9 igual a 2
    , luego P es interior al polígono
    No existen casos especiales ni situaciones ambiguas, e incluso, para aplicaciones especiales, es posible dejar al criterio del programador el considerar si un punto coincidente con un lado o vértice del polígono, se debe considerar interior o exterior al mismo. Para ello basta con decidir si el signo de los ángulos que sean iguales a radianes debe ser positivo o negativo. Normalmente, lo coherente es interpretarlos como negativos, de modo que el punto sea considerado externo al polígono, ya que en caso contrario y, si tuviéramos dos polígonos adyacentes, estaríamos asumiendo que el punto P se encuentra dentro de ambos polígonos simultáneamente.
    Consideraciones adicionales
    Tal y como se ha podido constatar, el procedimiento es muy simple, fiable, rápido, y preciso.
    Con respecto a la sencillez, no caben muchos más comentarios; todo el proceso se reduce a medir ángulos y sumarlos. En todos los casos, el procedimiento es idéntico. No existen posiciones especiales del punto P o de los vértices del polígono que obliguen a tener en cuenta casos particulares.
    La fiabilidad viene dada por su sencillez. Cualquier resultado diferente de 0 o 2 , implica necesariamente una anomalía en el polígono (polígono abierto, o lados entrecruzados). Pero incluso se soportan algunas "impurezas" en el trazado del polígono, tal como vértices duplicados, sean estos consecutivos o no.
    En cuanto a la velocidad de proceso, cabe resaltar que, frente al elevado grado de crecimiento del tiempo de proceso de algunos algoritmos en función del número de vértices del polígono, el algoritmo radial tiene un crecimiento absolutamente lineal, ya que no requiere ningún preprocesado para identificar el tipo de polígono (convexo o cóncavo), o para detectar a priori algunas situaciones anómalas.
    Por último, la precisión viene dada por la exactitud en el cálculo de los ángulos, y depende, claro está, de la máquina sobre la que se ejecute el programa. Si el número de vértices es muy elevado, podríamos llegar a obtener valores distintos de 0 o 2 , aunque siempre muy próximos a ellos. Por lo tanto, es conveniente establecer un pequeño margen para el resultado de la sumatoria final: De todos modos, en el peor de los casos, disponemos de un margen de error admisible, siempre que E menor que radianes. Es decir, todos aquellos valores de la por debajo de pi deberán corisiderarse 0, y aquellos que estén por encima de ese valor, deberán tomarse como 2.
    Sin embargo, esta última consideración es poco realista. Veamos: aún considerando que nuestra máquina pueda cometer un error de una millonésima de grado en cada medida de ángulo, lo cual ya es un error considerable, y teniendo en cuenta que nuestro margen de error está situado por debajo de los 180 grados, estaríamos hablando de "posibles errores" en el momento de enfrentarnos a un polígono de más de ciento ochenta millones de vértices, algo infrecuente en una cartografía convencional.

    Nota:
    Fuente: http://www.mappinginteractivo.com/plantilla-ante.asp?id_articulo=611 

    FPO: PROGRAMADOR DE SISTEMAS

    Como sabreis (o no), estoy en desempleo, y me acaban de llamar para realizar un curso sobre Programador de Sistemas (estamos aprendiendo a programar desde cero, Pseudocódigo, C, Gnu/linux, etc)

    Comentaros que estoy pasando los apuntes a una nueva pagina web, para que todo el mundo que le interese el tema los pueda consultar.

    La dirección es la siguiente:
    https://sites.google.com/site/fpoprogramadorsistemas/



    Espero que os sea útil.

    Saludos

    Julio Sánchez

    miércoles, 26 de enero de 2011

    Paginas de comandos de gnu/linux:

    He encontrado esta pagina muy interesane que comentan un montón de comandos de linux.
    http://linuxcomandos.blogspot.com/2008/04/comando-file.html

    Uno muy interesante es: file, que te da información del tipo de archivo que es.


    Por ejemplo: el tipico correo que te mandan y que no viene extensión, pues con file
    puedes ver el tipo de archivo
    $file nombre_archivo

    domingo, 23 de enero de 2011

    sábado, 22 de enero de 2011

    Instalar y enjaular Apache2 en Ubuntu 10.10

    He encontrado en: http://www.javcasta.com/2010/12/18/instalar-y-enjaular-apache2-en-ubuntu-10-10/, esta interesante entrada de como instalar y enjaular Apache2 en ubuntu 10.10.

    ¿que es enjaular Apache2?
    (https://lists.ubuntu.com/archives/ubuntu-es/2010-February/041895.html)





    "Consiste en crear una especie de jaula para el usuario que ejecuta apache (
    ej, www-data ), de forma que ese usuario en lugar de "ver" el sistema de
    ficheros normal, tiene la raíz en un directorio y no puede ejecutar, ni ver
    nada que se encuentre fuera de esa "jaula"
    
    Ejemplo:
    Real
    /home
    /bin
    ...
    /var
    /usr/bin/www-data/ ( de aquí partiría la raíz para el usuario www-data )
    /usr/bin/www-data/  /home
    /usr/bin/www-data/  /bin
    ...
    
    Es solo un ejemplo, el chroot, puede hacerse en el lugar que consideres más
    adecuado.
    En cuanto a para que sirve, es por motivos de seguridad"


    Interesante para todos aquellos que quieran empezar a usar Apache para crearte tu propio "servidor web". Os trascribo literalmente el artículo:

    Url de referencias:

    Actualizar paquetes y sistema

    sudo apt-get update
    sudo apt-get upgrade

    Instalar Apache2

    sudo apt-get install apache2 apache2-doc apache2-utils

    Instalar soporte para scripting con Python

    sudo apt-get install libapache2-mod-python
    si necesitas que python se entienda con MySQL
    sudo apt-get install python-mysqldb
    Buscar dependencias de PhP disponibles
    sudo apt-cache search php

    Instalar paquetes de PhP

    sudo apt-get install libapache2-mod-php5 php5 php-pear php5-xcache

    Instalar paquete PhP5-suhosin (proporciona mayor seguridad a PhP)

    sudo apt-get install php5-suhosin
    Si necesitas que PhP se entienda con MySQL
    sudo apt-get install php5-mysql
    Hasta aquí la instalación de Apache2 con soporte para Python, PhP y MySQL.

    Test

    Para comprobar si apache2 esta corriendo en tu máquina:
    • * Navega a http://127.0.0.1
    • * O desde consola haz un wget a http://127.0.0.1
    dice que ¡Trabaja! (el servidor Apache, no tu ni yo … :-) )

    Enjaulando Apache2:

    Instalar módulo mod_chroot

    sudo apt-get install libapache2-mod-chroot

    Habilitamos el módulo mod_chroot

    con el comando aen2mod (a2enmod, a2dismod – enable or disable an apache2 module)
    sudo a2enmod mod_chroot
    usuario@maquina:~$ sudo a2enmod mod_chroot
    Enabling module mod_chroot.
    Run ‘/etc/init.d/apache2 restart‘ to activate new configuration!

    Y reiniciamos Apache2

    usuario@maquina:~$ sudo /etc/init.d/apache2 restart
    * Restarting web server apache2  …
    waiting                          [ OK ]

    Configuramos la jaula

    Creamos el directorio “jaula” de Apache
    mkdir -p /var/www/var/run
    Hacemos a root el propietario de la “jaula”
    chown -R root:root /var/www/run
    Configuramos Apache para que use la “jaula”. Editamos /etc/apache2/apache2.conf
    sudo gedit /etc/apache2/apache2.conf
    PidFile ${APACHE_PID_FILE}
    ChrootDir /var/www
    Se asume que se tiene un vhost con DocumentRoot /var/www. Queda cambiar el camino a DocumentRoot de cada vhost cambiando “/var/www” a “/”
    Por ejemplo si DocumentRoot de un vhost es /var/www/web1/web –> /web1/web
    Y voila. Consultar las urls de referencia si hay dudas.