INTRODUCCION A LA PROGRAMACION LOGICA

La Programación Lógica estudia el uso de la lógica para el planteamiento de problemas y el control sobre las reglas de inferencia para alcanzar la solución automática.

La Programación Lógica, junto con la funcional, forma parte de lo que se conoce como Programación Declarativa, es decir la programación consiste en indicar como resolver un problema mediante sentencias, en la Programación Lógica, se trabaja en una forma descriptiva, estableciendo relaciones entre entidades, indicando no como, sino que hacer, entonces se dice que la idea esencial de la Programación Lógica es:

Programa= lógica + control

• Lógica (programador): hechos y reglas para representar conocimiento.
• Control (interprete): deducción lógica para dar respuestas (soluciones)

La programación lógica intenta resolver lo siguiente:

Dado un problema S, saber si la afirmación A es solución o no del problema o en qué casos lo es. Además queremos que los métodos sean implantados en máquinas de forma que la resolución del problema se haga de forma automática

La programación lógica: construye base de conocimientos mediante reglas y hechos.

• Regla: implicación o inferencia lógica que deduce nuevo conocimiento, la regla permite definir nuevas relaciones a partir de otras ya existentes.
• Hecho: declaración, cláusula o proposición cierta o falsa, el hecho establece una relación entre objetos y es la forma más sencilla de sentencia
• Consulta: se especifica el problema, la proposición a demostrar o el objetivo Partiendo de que los humanos son mortales y de que Sócrates es humano, deducimos que

La programación lógica comprende dos Paradigmas de Programación la Programación Declarativa y la Programación funcional.

La programación declarativa gira en torno al concepto de predicado, o relación entre elementos.

Características de la programación lógica

•  Unificación de términos
• Mecanismos de inferencia automática
• Recursión como estructura de control básica
• Visión lógica de la computación

Mecanismos básicos de Prolog

Son predicados predefinidos en PROLOG para las operaciones matemáticas básicas. Su sintaxis depende de la posición que ocupen, pudiendo ser infijos o prefijos. 

Por ejemplo el operador suma ("+"), podemos encontrarlo en forma prefija '+(2,5)' o bien infija, '2 + 5'.

También dispone de predicados de igualdad y desigualdad.

X = Y igual

X \= Y distinto

X < Y menor

X > Y mayor

X =< Y menor o igual

X >= Y mayor o igual

Al igual que en otros lenguajes de programación es necesario tener en cuenta la precedencia y la asociatividad de los operadores antes de trabajar con ellos. 

En cuanto a precedencia, es la típica. Por ejemplo, 3+2*6 se evalúa como 3+(2*6). En lo referente a la asociatividad, PROLOG es asociativo por la izquierda. Así, 8/4/4 se interpreta como (8/4)/4. De igual forma, 5+8/2/2 significa 5+((8/2)/2).

El operador 'is'.

Es un operador infijo, que en su parte derecha lleva un término que se interpreta como una expresión aritmética, contrastándose con el término de su izquierda.

Por ejemplo, la expresión '6 is 4+3.' es falsa. Por otra parte, si la expresión es 'X is 4+3.', el resultado será la instanciación de X:

X = 7

Una regla PROLOG puede ser esta:

Densidad(X,Y) :- población(X,P), área(X,A), Y is P/A.

Algunos comandos básicos

* consult.

El predicado _consult_ está pensado para leer y compilar un programa PROLOG o bien para las situaciones en las que se precise añadir las cláusulas existentes en un determinado fichero a las que ya están almacenadas y compiladas en la base de datos. Su sintaxis puede ser una de las siguientes:

consult(fichero).

consult('fichero.ext').

consult('c:\ia\prolog\fichero').

* recon.

El predicado recon es muy parecido a consult, con la salvedad de que las cláusulas existentes en el fichero consultado, reemplazan a las existentes en la base de hechos. Puede ser útil para sustituir una única cláusula sin consultar todas las demás, situando esa cláusula en un fichero. Su sintaxis es la misma que la de consult.

*forget.

Tiene como fin eliminar de la base de datos actual aquellos

hechos consultados de un fichero determinado. Su sintaxis es:

forget(fichero).

* exitsys.

Este predicado nos devuelve al sistema operativo.

Estructura de un programa Prolog

Prolog cuenta con dos tipos de estructuras: términos y sentencias. Los términos pueden ser constantes, variables o funciones:

• Las constantes, representadas por una cadena de caracteres, pueden ser números o cualquier cadena que comience en minúscula. 
• Las variables son cadenas que comienzan con una letra mayúscula. 
• Las funciones son identificadoras que empiezan con minúscula, seguidos de una lista de parámetros (términos) entre paréntesis, separados por comas.

Las sentencias son reglas o cláusulas. Hay hechos, reglas con cabeza y cola, y consultas.

• Un hecho establece una relación entre objetos, y es la forma más objetos, y es la forma más sencilla de sentencia. 
• Una regla permite definir nuevas relaciones a partir de otras ya existentes.

Operadores

MATEMATICOS + Suma - Resta * Multiplicación / División (retorna siempre en punto flotante) // División entera (trunca) mod Resto de división ** Potenciación

RELACIONALES > Mayor que < Menor que >= Mayor o igual que =< Menor o igual que =:= Aritméticamente igual =\= Aritméticamente diferente

Objetos compuestos

Un programa en Visual Prolog está compuesto de varias secciones que se describen a continuación:

·         Directivas de compilación: que se dan al comienzo del programa.

·         Sección de constantes: puede contener cero, una o varias constantes.

·         Sección de dominios: puede contener cero, uno o varios dominios.

·         Sección de la base de datos: puede contener cero, uno o varios predicados de la base de datos.

·         Sección de predicados: puede contener cero, una o varias declaraciones de predicados.

·         Sección de cláusulas: puede contener cero, una o varias cláusulas.

·         Sección de meta: para que el programa se ejecute de forma independiente debe existir una meta construida dentro del propio programa.

Recursividad

La recursividad es un mecanismo que da bastante potencia a cualquier lenguaje de programación.

Veamos un ejemplo de programación recursiva que nos permitirá determinar si un tomo es miembro de una lista dada:

(1) miembro(X,[X|_]).

(2) miembro(X,[_|Y]) :- miembro(X,Y).

La regla (1) es el caso base de la recursión. Se evaluar como cierta siempre que coincida la variable X con la cabeza de la lista que se pasa como argumento. En la regla (2) est la definición recursiva. X es miembro de una lista si lo es de la cola de esa lista (la cabeza se comprueba en la regla (1)).

La regla (1) es una simplificación de la regla:

miembro(X,[Y|_]) :- X = Y.

La traza para el caso de 'miembro(b,[a,b,c]).' es la siguiente:

(1) miembro(b,[a,b,c]) :- b = a. ---> no.

(2) miembro(b,[a,b,c]) :- miembro(b,[b,c]).

(1) miembro(b,[b,c]) :- b = b. ---> yes.

Si necesitamos conocer la longitud de una lista, emplearemos una función recursiva como la siguiente:

longitud([],0).

longitud([_|Y],L1) :- longitud(Y,L2), L1 is L2 + 1.

Juegos mini-max

En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada.

La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.

Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenas situaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero.

El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro. La figura 1 muestra un ejemplo donde  la elección del siguiente movimiento según la búsqueda Minimax de tres niveles sería el nodo D.

El algoritmo Minimax es un procedimiento recursivo, y el corte de la recursión está dado por alguna de las siguientes condiciones:

• Gana algún jugador
• Se han explorado N capas, siendo N el límite establecido
• Se ha agotado el tiempo de exploración
• Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro

En el algoritmo MINIMAX detallado en breve la función de corte de recursión SUFICIENTE (posición, profundidad) sólo considera las dos primeras condiciones de corte.

FIGURA 1

El algoritmo MINIMAX( posición, profundidad, jugador) usa dos funciones:
 

• GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el jugador a partir de la posición
• ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la posición desde el punto de vista de jugador.

A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA devuelve valores en relación al jugador actual en vez del jugador maximizante. Por esta razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza el valor que devuelve esta función.

El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante dado que invierte los valores de un nivel a otro.

La función Minimax devuelve una estructura con

• VALOR: valor propagado de la función estática
• CAMINO: camino para llegar a la solución desde la posición

La primera llamada a la función recursiva será:

MINIMAX (posiciónactual, 0,  JUGADOR-UNO) 

PODA ALFA-BETA

Mejora del Algoritmo Minimax; aplicado en juegos de adversarios por turnos.

Se aplica en espacios de estados demasiado grandes como para analizar todos los nodos.

La información es imperfecta; es decir, no se conoce el estado del contrincante.

Por ejemplo: En juegos donde no se ve el tablero del adversario.

Características de la Poda Alfa-

Beta

• Omitir la expansión de nodos que por sus valores no pueden ser los mejores (peores).
• Interrumpe la búsqueda en algún nivel y aplica evaluaciones heurísticas a las hojas (profundidad limitada.
• Si el valor del nodo MAX (alfa) es menor que el más alto hasta este momento, entonces omitir nodo.
• SI el valor del nodo MIN (beta) es mayor que el nodo más bajo hasta el momento, entonces omitir nodo.
• Alfa-Beta permite búsqueda dos veces más profunda.
• Ordenamiento de los operadores, resultante del conocimiento o experiencia.
• Únicamente importa el orden y no los valores exactos.
• La poda no afecta al resultado final.
• Alfa-Beta es una mejora del algoritmo Minimax que evita revisar porciones dominadas del árbol, que no pueden proveer información útil sobre la jugada siguiente.

Alfa-Beta es un algoritmo de búsqueda en profundidad, rama y cota, que avanza por el árbol en un orden ya fijado (p.ej., de izquierda a derecha) y va usando la información de la valuación de los nodos hoja para podar ramas dominadas que no sirven para cambiar el valor Minimax del nodo inicio (la jugada inminente).