Todas las entradas por iautp

Sistema Experto Diagnosticador 2

En esta entrada se incorpora el anterior sistema experto realizado en SWI-PROLOG así como también su respectiva representación en PHP, además de su transformación equivalente a un sistema experto probabilistico.

Recordar el sistema experto en PHP fue realizado para probar bajo servidor local, en este caso, se utilizó WAMP como host para ejecutar los archivos utilizando PHP 5.3.10, leer las instrucciones de uso dentro de los archivos .rar que se encuentran en el siguiente enlace junto con los respectivos códigos fuente:

Enlace -> * Link de Descarga *

Imagen relacionada

Algoritmo de Búsqueda en Anchura y Profundidad

A continuación se comparte el link para descarga y uso de forma libre de un algoritmo de búsqueda tanto en anchura como en profundidad de un grafo realizado en Java con el entorno de desarrollo NetBeans IDE 8.0.2.

También contiene Paper en formato de revista científica sobre el tema de algoritmos de búsqueda y de su implementación:

link: https://www.dropbox.com/sh/sp6linga7mjlz6n/AADxs5t9rRaW3rVmSyAO5xA-a?dl=0

 

 

 

Poda Alpha-Beta

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald W. Moore.

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

Desarrollo del Algoritmo:

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.

La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino.

  • α es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, esto implicará por lo tanto la elección del valor más alto
  • β es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, esto implicará por lo tanto la elección del valor más bajo.

Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

función alfabeta(nodo //en nuestro caso el tablero, profundidad, α, β, jugador)
    si nodo es un nodo terminal o profundidad = 8
        devolver el valor heurístico del nodo
    si jugador
        para cada hijo de nodo
            α := max(α, alfabeta(hijo, profundidad+1, α, β, jugador))
            si β≤α
                break (* poda β *)
        devolver α
    si no
        para cada hijo de nodo
            β := min(β, alfabeta(hijo, profundidad+1, α, β, jugador))
            si β≤α
                break (* poda α *)
        devolver β
(* Llamada inicial *)
alfabeta(origen, profundidad, -infinito, +infinito, jugador_deseado)
Ejemplo del Algoritmo:

La figura muestra un ejemplo de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que tendrán que definir un valor α o β respectivamente.

A continuación se presenta un ejemplo de aplicación del algoritmo para el árbol de la figura. En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris.

Comenzamos con la búsqueda de primero en profundidad. El padre de los nodos hoja más a la izquierda, etiquetados con 5 y 6 respectivamente, deberá escoger un valor β al tratarse de un nivel MIN, esto implica que deberá escoger el valor mínimo entre dichos nodos, es decir 5.

Siguiendo el desarrollo, se expandirán el resto de sucesores del padre. En este caso se expande el camino que conduce a los nodos hoja 7 y, buscando un valor β menor, el nodo etiquetado con 4. En este momento el valor momentáneo de β en ese nivel es 4 (el mínimo entre 7 y 4). Esto implica que en este momento en el nivel superior, el padre del nodo que etiquetamos anteriormente con β igual a 5, y de este β igual a 4 momentáneo, debe decidir el mejor valor, el más alto al encontrarse en un nivel MAX), si siguiéramos expandiendo hijos del nodo MIN padre de 7 y 4, sólo podríamos conseguir valores menores a 4, lo que seguiría implicando una elección de la jugada izquierda en el nivel MAX, por lo tanto, podemos podar el resto de hijos, tal y como se muestra en la figura.

El resto del desarrollo del árbol se seguiría utilizando los criterios mencionados con anterioridad.

Algoritmo Minimax

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. Minimax es un algoritmo recursivo. El funcionamiento de minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

Historia:

Aunque existen evidencias de que Charles Babbage ya había trabajado antes sobre una idea similar, fue el matemático francés Émile Borel el primero en ofrecer en 1921 un tratamiento riguroso a los juegos competitivos y en estudiar las estrategias aplicables a los juegos de suma cero. Sin embargo suele atribuirse a John von Neumann el principal mérito de la concepción del principio minimax, ya que fue él quien, en su artículo de 1928 «Zur Theorie der Gesellschaftsspiele» («Sobre la teoría de los juegos de sociedad») publicado en la revista Mathematische Annalen, puso las bases de la moderna teoría de juegos y probó el teorema fundamental del minimax, por el que se demuestra que para juegos de suma cero con información perfecta entre dos competidores existe una única solución óptima.

Teorema Minimax:

John von Neumann es el creador del teorema minimax, quien dio la siguiente noción de lo que era un juego:

Un juego es una situación conflictiva en la que uno debe tomar una decisión sabiendo que los demás también toman decisiones, y que el resultado del conflicto se determina, de algún modo, a partir de todas las decisiones realizadas.

También afirmó que:

Siempre existe una forma racional de actuar en juegos de dos participantes, si los intereses que los gobiernan son completamente opuestos.

La demostración a esa afirmación se llama teoría minimax y surge en 1928.

Este teorema establece que en los juegos bipersonales de suma cero, donde cada jugador conoce de antemano la estrategia de su oponente y sus consecuencias, existe una estrategia que permite a ambos jugadores minimizar la pérdida máxima esperada. En particular, cuando se examina cada posible estrategia, un jugador debe considerar todas las respuestas posibles del jugador adversario y la pérdida máxima que puede acarrear. El jugador juega, entonces, con la estrategia que resulta en la minimización de su máxima pérdida. Tal estrategia es llamada óptima para ambos jugadores sólo en caso de que sus minimaxes sean iguales (en valor absoluto) y contrarios (en signo). Si el valor común es cero el juego se convierte en un sinsentido.

En los juegos de suma no nula, existe tanto la estrategia minimax como la maximin. La primera intenta minimizar la ganancia el rival, o sea busca que el rival tenga el peor resultado. La segunda intenta maximizar la ganancia propia, o sea busca que el jugador obtenga el mejor resultado.

Algoritmo Minimax con movimientos alternativos:

Pasos del algoritmo minimax:

  1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.
  2. Cálculo de los valores de la función de utilidad para cada nodo terminal.
  3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Según nivel si es MAX o MIN 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 evaluación, empezando por los nodos terminales y subiendo hacia la raíz. La función de utilidad definirá lo buena que es la posición para un jugador cuando la alcanza. En el caso del ajedrez los posibles valores son (+1,0,-1) que se corresponden con ganar, empatar y perder respectivamente. En el caso del backgammon los posibles valores tendrán un rango de [+192,-192], correspondiéndose con el valor de las fichas. Para cada juego pueden ser diferentes.

Si minimax se enfrenta con el dilema del prisionero escogerá siempre la opción con la cual maximiza su resultado suponiendo que el contrincante intenta minimizarlo y hacernos perder.

Ejemplo del Algoritmo:

En el siguiente ejemplo puede verse el funcionamiento de minimax en un árbol generado para un juego imaginario. Los posibles valores de la función de utilidad tienen un rango de [1-9]. En los movimientos del contrincante suponemos que escogerá los movimientos que minimicen nuestra utilidad, en nuestros movimientos suponemos que escogeremos los movimientos que maximizan nuestra utilidad.

El primer paso será calcular los nodos terminales, en verde. Posteriormente calcularemos el cuarto nivel, movimiento min, minimizando lo elegido (5, 2 y 1). Después podremos calcular el tercer nivel, movimiento max, maximizando la utilidad (5, 9). El segundo nivel es un movimiento min (5, 3 y 1). Finalmente llegamos al primer nivel, el movimiento actual, elegiremos el nodo que maximice nuestra utilidad (5).

Estándares Universales del Pensamiento

Los Estándares son aplicaciones que se emplean al pensamiento cada vez que se quiera evaluar la calidad del razonamiento sobre un problema, un tema o una situación. Pensar críticamente implica dominar estos estándares.

Al exponer sobre los Estándares Intelectuales Universales tomamos como punto de partida al Pensamiento Crítico, el cual es el proceso de analizar y evaluar el pensamiento con el propósito de mejorarlo. Presupone el conocimiento de las estructuras y los estándares intelectuales básicos, por esta razón la clave para desencadenar el lado creativo del pensamiento crítico está en reestructurar el pensamiento como resultado de analizarlo y evaluarlo de manera efectiva.

A continuación presentamos los siete Estándares Intelectuales Universales que deben aplicarse al pensamiento cada vez que se quiera evaluar la calidad del razonamiento sobre un problema, un tema o una situación. Pensar críticamente implica dominar estos estándares.

El objetivo final es que estas preguntas se graben en el pensamiento de los estudiantes y se conviertan así en parte de su voz interior, que los conduzca a un razonamiento cada vez mejor. Aunque existen un gran número de estándares universales, los siguientes son los más significativos:

claridad

CLARIDAD:

La claridad es el primer estándar. Con él se debe comenzar. Si una proposición no es clara, no podemos determinar si es cierta o si es relevante. En efecto, no podemos decir nada sobre ella porque no sabemos aún que pretende expresar.

EXACTITUD:

¿Es eso cierto? ¿Cómo podríamos verificarlo? ¿Cómo podríamos asegurarnos de que es verdad?. Una proposición puede ser clara pero no veraz, como por ejemplo;  “La mayoría de los perros pesan más de 150 kilos”.

PRECISIÓN:

¿Podría dar más detalles? ¿Podría ser más específico?. Una proposición puede ser clara y veraz pero no precisa, como por ejemplo; “Juan tiene exceso de peso” (No sabemos si el sobrepeso es de 1 kilogramo o de 100 kilogramos).

PERTINENCIA:

¿Cómo se conecta esto con la pregunta? ¿Qué tiene que ver con el tema?. Una proposición puede ser clara, veraz y precisa, pero no pertinente a la pregunta o tema. Por ejemplo: los estudiantes piensan con frecuencia que la cantidad de esfuerzo que realizan en un curso o materia, debe tenerse en cuenta para mejorarles la evaluación o calificación de estos. Con frecuencia, sin embargo, el “esfuerzo” no mide la calidad del aprendizaje del estudiante y cuando lo hace, el esfuerzo es irrelevante a la calificación adecuada.

PROFUNDIDAD:

¿Cómo enfoca o maneja la respuesta las complejidades de la pregunta? ¿Cómo se tienen en cuenta los problemas que involucra la pregunta? ¿Está atendiendo la pregunta los factores más significativos?. Una proposición puede ser clara, veraz, precisa y pertinente, pero superficial (esto es, poco profunda). Por ejemplo: la proposición “Simplemente diga No” que se utiliza con frecuencia para disuadir a los niños y adolescentes para que no utilicen drogas es clara, precisa y relevante. Sin embargo, le falta profundidad porque trata un problema extremadamente complejo, el grave problema del uso de las drogas entre niños y jóvenes, en forma superficial. Falla en atender las complejidades del tema.

LÓGICA:

¿Es esto verdaderamente lógico? ¿Esto se desprende de lo que se dijo? ¿De qué manera lo hace? ¿Por qué antes la implicación era una y ahora parece ser otra; cómo pueden las dos ser ciertas?. Cuando pensamos, ponemos una diversidad de pensamientos en cierto orden. Cuando la combinación de pensamientos se apoyan mutuamente y su combinación hace sentido, el pensamiento es “lógico”. Cuando la combinación de pensamientos no se respalda mutuamente, de alguna forma es contradictoria, o no “hace sentido”, la combinación no es lógica.