Problema de teoría de juegos: Colaborar es la clave (Solución)

Aquí está la solución al problema de teoría de juegos: "Colaborar es la clave".

Mi metodología de resolución, pasa por codificar las sentendias del problema. Es decir, el resultado de la moneda para Alice y Bob,

Ma = "Lanzamiento de Alice"
Mb = "Lanzamiento de Bob"

y las predicciones de Alice y Bob.

Pa = "Predicción de Alice"
Pb = "Predicción de Bob"

Los valores que pueden tomar las cuatro variables anteriores con cara (C) o cruz (X).

Las posibildades para Ma y Mb , las cuales son aleatorias, se dan en la tabla de la figura 1.

Figura 1: Posibilidades para los lanzamientos de Alice y Bob.

La clave está en darse cuenta de que primero se lanza la moneda, y después se hace la predicción.  Así que las estrategias definidas por Alice y Bob para hacer las previsiones de cada uno sobre el lanzamiento del otro, Pa y Pb, dependerán de lo que pacten Alice y Bob. Pero hay que darse cuenta, que Pa y Pb, pueden usar la información que resulta de su lanzamiento de moneda Ma y Mb.

Primero veamos cuales son las posibilidade de pérdidas. Ambos, Alice y Bob deberán fallar simultáneamente. Codifiquemos las siguientes sentencias:

Fa = "Alice falla en su previsión"
Fb = "Bob falla en su previsión"

Relacionando Fa con Pa y Mb, y Fb con Pb y Ma, tendremos las siguientes equivalencias:

Fa = (Pa = C ^ Mb=X) v (Pa=X ^ Mb=C)
Fb = (Pb = C ^ Ma=X) v (Pb=X ^ Ma=C)

Siendo ^ y v, los operadores lógicos copulativo y disyuntivo respectivamente, es decir, AND y OR.

Por tanto, perder el juego implicaría que:  Fa ^ Fb sea cierta

Por el contrario, ganar el juego, sería que

1. (Fa = cierta) ^ (Fb = falsa)   ,o bien,
2. (Fa = falsa)  ^ (Fb = cierta)  ,o bien,
3. (Fa = falsa)  ^ (Fb = falsa)

Es decir, que no fallen ambos a la vez. Desde la definición de Fa y Fb, podemos tratar de crear una estrategia que defina la previsión Pa y Pb. Recordar, que no podemos usar Ma para la predicción de Pb, ni Mb para la predicción de Pa, eso sería hacer trampas. Alice y Bob están aislados, pero sí pueden hacer la predicción después de lanzar su moneda.

Eligiendo la primera condición de una de las tres sentencias anteriores, se deduce que debe cumplirse los siguiente:

• Desde que Fa es cierta:
• Si Mb = X, entonces Pa = C
• Si Mb = C, entonces Pa = X
• Desde que Fb es falsa:
• Si Ma = X, entonces Pb = X
• Si Ma = C, entonces Pb = C

En forma de tabla es lo siguiente:

	Ma = C	Ma = X
Mb = C	Pa = X y Pb = C	Pa = X y Pb = X
Mb = X	Pa = C y Pb =C	Pa = C y Pb = X

Desde la anterior tabla, teniendo en cuenta, que para la estrategia Pa, sólo se dispone de Ma, y lo mismo para Pb, 

Se puede definir las estrategias siguientes:

• Pa = Ma
• Pb = Nor Mb

La cual permite ganar siempre al juego (-: 

La exposición anterior, ha sido bastante forma, pero se entiende que la estreategia que deben seguir Alice y Bob, son para Alice, tomar como previsión el mismo resultado de su moneda, y para Bob, el resultado contrario del lanzamiento de su moneda. 

Esto implica que en todos los casos de lanzamientos de Alice y Bob, al menos uno de los dos acertará con su previsión, por tanto ganarán el juego.  

Problema de teoría de juegos: Colaborar es la clave (Planteamiento)

En esta entrada voy a plantear un problema de teoría de juegos, derivado del dilema del prisionero. Es un problema en el que la solución , es encontrar una estrategia, para que dos individuos que trabajan juntos, ganen o pierdan a la vez.  Esto implica que tienen que colaborar para ganar.
Como casi siempre, los problemas que se exponen en matemáticas para ilustrar algún concepto de la vida real, son ejemplos de juguete en la vida real.

A continuación, voy a explicar el problema:

Alice y Bob juegan a un juego. Son compañeros de equipo, de modo que ganan o pierden a la vez. 

Antes de que comience el juego se les explica las reglas y pueden hablar y ponerse de acuerdo sobre una extrategia.

Entonces comienza el juego. Alice y Bob van a habitaciones separadas y completamente aisladas - no pueden comunicarse de ninguna forma.

Cada uno lanza una moneda al aire y anota si el resultado es cara o cruz. (No vale usar triquiñuelas: el lanzamiento ha de ser honesto y deben decir la verdad a continuación sobre cuál ha sido el resultado).

Entonces Alice escribe su predicción intentando adivinar cuál ha sido el resultado de la moneda de Bob. Bob a su vez hace lo mismo intentando adivinar el resultado de la moneda de Alice.

Si alguna de las respuestas, o ambas, son correctas, Alice y Bob ganan el juego como equipo que son. Pero si ambos fallan, ambos pierden.

Ahora toca pensar antes de explicar la solución. Es más fácil de lo que aparenta.

Presentaré la solución en una entrada posterior.

Metaprogramación: Programas que hacen programas

La metaprogramación o programación genérica es más antigua de lo que se puede pensar.  Es un concepto que trata de programas que hacen programas, y según esta definición, es una programación que manipula los símbolos de otro lenguaje como si fuesen datos de sus variables, formando sentencias correctas del lenguaje manipulado, para después ser ejecutadas como las sentencias del lenguaje manipulador.  

En general, son mecanismos que permite a un programador ganar una mayor compresión y expresividad en sus programas.  En un principio la metaprogramación surgió como herramienta para mejorar la productivada de los ingenieros de software. 

Nos podemos preguntar,  ¿no es suficiente complejidad un sólo lenguaje de programación?, ¿por qué deberíamos utilizar este tipo de recursividad?.
 Veamos algunos ejemplos, comenzando con el primer metaprograma, sin ir mas lejos sería el compilador. 

Obra del pintor M.C. Escher que inspirar el concepto de recursividad 

Los Compiladores 

Un compilador permite manejar indirectamente los 0s y 1s de un ordenador, a través de un conjunto de instrucciones y sentencias bien definidos y estructurados.  Los compiladores son un tema muy extenso, y no es mi intención hacer una entrada sobre ellos, aunque los describiré brevemente, ya que son una forma de metaprogramción.

Proceso de un compliador: Léxico, Sintáctico, Semántico, Optimización y Generación.

En la imagen anterior, se describe el proceso que sigue un compilador con su lenguaje fuente a compliar.  En primer lugar, a partir del código fuente, se verifica el léxico de cada sentencia. Segundo, se hace una parsing o análisis sintáctico y semántico. Además se realiza una optimización del código intermedio antes de generar el código en ensamblador y finalmente en código máquina.
En conclusión, se puede ver un compilador cómo programa que analiza un lenguaje para obtener otro lenguaje. Es posible, que no sea estrictamente un metalenguaje, ya que un compliador no expresa, procesa, y puede ser visto quizá como un simple traductor. De cualquier forma, existen programas generadoras de analizadores léxicos y sintácticos como Lex y Yacc, que potencian y elevan a los compiladores a una gramática formal.

PHP formateando HTML

PHP es un lenguaje orientado a WEB, interpretado y  ejecutado en el servidor web. El código PHP se encarga de reunir los datos de diferentes fuentes, formatearlos en una presentación utilizando etiquetas HTML, y enviarlos al navegador del cliente o usuario.

Funcionamiento del código PHP en un entorno de servicio web

Veamos el ejemplo mas sencillo posible.

<!DOCTYPE html>
<html>
<body>

<?php
$txt = "Metaprogramacion en Estalogica!";
$x = 5;
$y = 10.5;

echo $txt;
echo "<br>";
echo $x;
echo "<br>";
echo $y;
?>

</body>
</html>

Estamos ante un lenguaje de programación que manipula símbolos de otro lenguaje de programación, es por tanto, que se puede decir que estamos haciendo metaprogramación sobre HTML.
En el listado anterior, en color rojo, el código PHP, que incluye en sus datos, código HTML.
Entonces, tenemos que PHP genera código HTML a partir de sus variables. Podemos presentar el código HTML intermedio como sigue:

<!DOCTYPE html>
<html>
<body>
MetaProgramacion en Estalogica!
<br>5
<br>10.5
</body>
</html>

Finalmente la ejecución del HTML anterior producirá en el navegador del usuario la salida:

MetaProgramacion en EstaLogica!
5
10.5

Plantillas de C++

En esta subsección, presentaré la programación genérica de C++, la cual hace uso de tipos de datos arbitrarios dentro de los programas. Se habla de plantillas o templates, los cuales, permite manipular símbolos representando estos tipos de datos abstractos, y sobre los cuales se aplica un procedimiento genérico (supongo que el lector conoce la sintaxis básica de C++, en otro caso no estarías aquí leyendo esta entrada).

Diagrama de los mecanismos de metaprogramación

Veamos un ejemplo sencillo. Suponer que queremos un código genérico para  calcular el máximo de dos números. Si queremos que los números sean entereos, utilizaremos el tipo de datos int .

int maximo(int a, int b )
{
   if (a<b)
      return b;
   return a;
}

En cambio, si queremos que sean número con decimales, utilizaremos el tipo de datos float.

float maximo(float a, float b )
{
   if (a<b)
      return b;
   return a;
}

Como podemos observar, el cuerpo es exactamente igual, y lo único que cambia son las palabras clave float e int indicando del tipo de dato.  ¿Cómo podemos fusionar ambos códigos en unos solo?, para esto utilizaremos los templates de C++, como se puede ver a continuación:

template <class TipoGenerico>
TipoGenerico maximo(TipoGenerico a, TipoGenerico b )
{
   if (a<b)
     return b;
   return a;
}

La utilización de la función, puede hacerse en ambos casos, tanto si los tipos de datos de los argumentos son enteros como flotantes,

....
int a=5, int b=8, c;
float d=3.0, e=5.1, f;
c=maximo(a,b);
f=maximo(d,e);
...

Estamos ante un ejemplo de metaprogramación, desde que hacemos referencia a la forma de especificar en C++ los tipos de datos.

Arte con el Spectrum +3: Melody-8 bits-Sincro-Plot-Stock-Market

Qué polvoriento estaba mi Spectrum +3 cuando lo he visto esta mañana en mi casa. He pensado usarlo un poquito para recordar viejos tiempos. Sin corto ni perezoso, he cogido la televisión de mi dormitorio, un ladrón eléctrico, y me he ido a colocarlo al salón de mi casa.

Una vez colocados todos los trastos sobre una mesa plegable, he enchufado la corriente de la TV, la de la fuente de alimentación del Spectrum +3, y he conectado el cable de antena desde el viejuno cumputador a la TV no tan viejuna, pero que todavía soporta canales analógicos. 

Encendiendo los aparatos, no es suficiente para verlos funcionar. Hay que recordar que lo primero que había que hacer era sintonizar el canal de vídeo analógico que sale de la maquinita y llega a la TV. Por tanto, configurando el canal desde el menú de la TV, y tras un rato de búsqueda automática de canales analógicos, esta ha conseguido sintonicar la señal deseada en la pantalla, presentando un menú de inicio con cuatro opciones. En este momento me he dicho, ¡bravo!, funciona!, bueno no del todo, la TV emitía un ruido de fondo no demasiado molesto, y la disquetara parecía no estar en las condiciones de fábrica, porque se ecuchaba también un ruido bastante raro proveniente de su interior. En fin, el tiempo y el trasiego hacen de las suyas a la electrónica, gracias que se sintoniza y el teclado paracía que respondía, por lo menos los cursores.

En ese momento, ya era hora de hacer algo con el micro computador de 8 bits. Pues bien, me sentado delante de ese arcaico teclado, y de la TV no tan antigua, pero bien sintonizada, y el primer problema al que me enfrentadaba era descifrar ese teclado tan diferente de los modernos, y tan specífico para aquellas máquina domésticas. Aunque al menos poseen una distribución QWERTY, el resto de teclas especiales, CONTRO, ESCAPE, SHIFT, BACKSPACE, están en lugares dispares, que responde a razones del maestro que lo creo, nuestro querido y fallecido Sir Clive Sinclair.

Ante mí jeta, una pantalla en blanco se presentaba. Había que echarle imaginación al asunto, porque aunque las opciones con una computadora, como máquina universal son infinitas, tienes su aquel un poco ortopédico, trabajar con aquellas antiguallas. Es estas circunstancias, además del conocimiento técnico de la máquina y del lenguaje que incorpora, la creatividad debe aflorar para poder trabajar con ellas. Es una situación de cubículo, donde no se dispone de internet, y no puedes hacer zapping entre los diferentes contenidos para ayudarte en el avance hacia alguna parte.

He seleccionado la opción de BASIC+3, donde una pantalla blanca y un cursor parpadenate se presentan ante el usuario. Entonces he empezado a recordar el lenguaje que se utilizaba. Era un lenguaje que precisaba un número de línesa al comienzo, y utilizaba comandos bastante básicos en comparación a los lenguajes más modernos. Aún así, incorpora todo lo que se le puede pedir a un lenguaje de programación imperativa, desde la declaración de variables numéricas y alfanuméricas, arrays de datos,  comando de control, como bucles FOR-NEXT y IF-THEN-ELSE, así como subrutunas GOSUB-RETURN y funciones. El nombre del lenguaje BASIC+3, una extensión del BASIC para el Spectrum 48K. Para más información sobre el misno, basta buscar en la wikipedia sobre las especificaciones del lenguaje. 

Era hora de programar algo,  y aleatoriamente, me he puesto ha jugar con el  famosos comando BEEP, que permitía activar el altavoz interno del ordenador. Eran sonido bastante estridentes e insoportables, es decir, apenas se emite un pitido, pero gracias a que el comando dispone de 2 parámetros, uno para fijar la duración y otro la frecuencia, se puede hacer algo más intersante. Al principio, no he hecho mas que la típica escalera de notas, arriba y abajo en frecuencia, pero poco a poco he ido añadiendo cambios, como las funciones matemáticas SIN y RND, que la han hecho más interesante y sofisticada. En esos moento, me recordabam a aquellas melodías que incorporaban los videojuegos de los 80s, o lo que hoy también se llaman 8-BIT Melody. 

El programa introducido ha sido muy sencillo, y escrito sin ninguna planificación y en el momento. Como se ven en la imagen más abaja, son varios bucles anidados, que dan algo de estructura a la melodía computerizada, con varias secciones, cambiando los parámetros en cada sección para los comandos BEEP, BORDER, SIN y RND. Además, he jugado con los gráficos más simple, representando una gráfica pseudo-aleatoria, que se pinta punto a punto estando sicronizada con las diferentes secciones de la melodía. 

El comando mas básico utilizado para pintar en estos antiguos ordenadores era PLOT, el cual admitiía 2 parámetros, la ordenada y la abscisa del plano de la pantalla.  

A continuación, se puede el listado muy básico, que permite reproducir la demo musico-visual explicada:  

Primera parte del Listado (1/2): Melody-8 bits-Sincro-Plot-Stock-Market

La segunda parte del listado (2/2)

Resultado de la ejecuación de mi proto-programa en basic de mi Spectrum +3. La gráfica que sale, puede recordar a la formación de precios en las bolsas de los mercados financieros

Hasta aquí hemos llegado, espero que os haya gustado la entrada del blog. 

Saludetes en 8-bits!!

Programando el Cubo de Rubik (I)

Desde un tiempo, me rondaba por la cabeza hacer un programa que resolviera el cubo de Rubik. Hace años, estuve haciendo algunos bocetos, y tirando algunas líneas de código, pero lo dejé a medias, sin completarlo. Voy a retomarlo tratando de trabajar por partes, es decir, documentando mis avances en éste Blog, entrada trás entrada. 

Las fases de trabajo son, desde definir los requisitos del programa, hacer un diseño razonable y  que sea suficientemente flexible. Además, hay que definir cómo implementarlo en  código fuente. Una vez escrito el código, se debería diseñar una batería de pruebas, para verificar la corrección y eficiencia del programa, viendo cómo aplica una estrategias de resolución al cubo físico. Sin más, he pensado en la bien conocidas solución por 3 capas, que se puede encontrar en muchos sitios y foros en internet (http://www.rubikaz.com/).

En principio, no quiero hacer un diseño demasiado genérico, yendo directamente a la resolución concreta del problema del cubo de Rubik. Tampoco quiero hacer una programación imperativa clásica, que sea difícil de seguir, poco clara y farragosa de entender. Esto es para los fanáticos del ensamblador :).

Para que llegue a la gran audiencia, voy utilizar el lenguaje C++, orientado a objetos, correindo bajo Linux/Gnu Debian. La orientación a objetos permite repartir las responsabilidades y encapsulando las diferentes funcionalidades, así como desacoplar lo máximo posible (buen diseño) las tareas a realizar por el programa.

Respecto a los gráficos, no he pensado en nada complejo.  Simplemente voy a trabajar en modo texto, siendo necesario un cubo físico, para comprobar las soluciones en modo texto entregadas por el programa.   

Es muy importante pensar bien cómo representar el cubo, con sus caras, caritas, colores y operaciones de girado. Para ello, voy a utilizar una notación bien conocida por los "profesionales" del cubo de Rubik.  

¿Cómo es esta notación?. Pues bien, desde que el cubo tiene 6 caras, basta asociar a cada cara una letra, o bien una letra con una prima(') . Esto indicará un giro en sentido horario o anti-horario de la cara, según tenga o no prima. Las caras se denotan:

F: Front, B: Back, L: Left, R: Right, U:Up, D: Down, 

es decir, en castellano, delantera, trasera, izquierda, derecha, arriba y abajo, respectivamente.  

Además, si colocamos un dos delante de una letra, esto indica un giro de 180 grados.

De esta forma, podemos presentar cualquier combinación de movimientos. Veamos un ejemplo a continuación. Suponer que tenemos la siguiente cadena de letras definidas como antes: 

FB2DF'B', 

Esta ristra de caracteres anterior querría decir lo siguiente: 

1. Giramos la cara delantera 90 grados sentido horario: F
2. Giramos cara trasera 90 grados sentido horario: B
3. Giramos cara de abajo 180 grados: 2D
4. Giramos cara delantera 90' sentido anti-horario: F'
5. y por último giramos 90 grados la cara trasera en sentido anti-horario: B'

Ahora, pasamos a la parte de la programación, que da título a esta entrada. Un programa en C++, debería ser pensado, con el objetivo de repartir las funcionalidades o responsabilidades requeridas, entre las diferentes clases que lo componen. Por tanto, definamos que es lo que queremos de nuestro programa claramente:

1. Representar cualquier estado del cubo de Rubik: Situación de cada cara y color.
2. Mezclador del cubo de Rubik, mediante un número de giros indicado por el usuario.
3. Buscador de la posición de una carilla cualquiera, ya sea una arista, o un vértice del cubo.
4. Desarrollar un algoritmo que resuelva  del cubo de Rubik desde cualquier estado.
5. Aceptar por consola o fichero, la descripción del estado de un cubo de Rubik, a ser resuelto.
6. Presentar la salida de la estrategia, en notación de Rubik (vista arriba), la solución al cubo desde un estado aleatorio sacado del mezclador, o introducido por el usuario. 
7. El usuario debe ser capaz de resolver su cubo de Rubik físico, a partir de la solución.

Podríamos pedir más funcionalidades, como puede ser trabajar con diferentes estrategias de resolución y devolver estadísticas para cada una de las estrategias. Incluso, hacer un programa más genérico, que permita trabajar con cubos de lado mayor a tres. No voy a entrar en esas complejidades, hasta que al menos hayamos acabado con una primera versión sencilla, que sea capaz de resolverlo con una estrategia básica.

¿Cómo realizamos el diseño del programa?. Pues bueno, después de jugar con el cubo físico y, garabatear algunos dibujos y diagramas para representar las operaciones y el estado del cubo, he llegado a un diseño de clases para C++ mas o menos bueno. Esto es un proceso algo intuitivo y creativo, así que es difícil de describir ordenadamente. Podría poner aquí esos diagramas, pero no serviría de mucho, ya que son bastante desordenado y subjetivos.
Ahora, veamos cómo el diseño, nos va a permitir distribuir las funcionalidades descritas. Estas podrían estar agrupadas utilizando las siguientes clases de objetos:

• Clase Cara: Encargada de representar y mantener los colores de las 9 carillas de una cara del cubo de Rubik, además de su disposición.  Es clave en esta clase, es su auto-referencia, para realizar conexiones entre instancias. Esto permitirá pasar información entre las caras conectadas, cuando se realice una operación de girado en alguna de ellas.
• Clase Rubik: Aglutinará 6 instancias de la clase Cara, además de encapsular las conexiones entre las instancias de las Caras,  y de las operaciones realizadas. 
• Clase Mezclador: Recibirá una instancia de clase Rubik, operando sobre ella, mezclando los colores mediante operaciones de giro en cada cara del la instancia de Rubik.
• Clase Estrategia: Encargada de recibir una instancia de Rubik, y aplicar una estrategia de resolución sobre la misma. Deberá entregar la lista de operaciones en notación de Rubik.

Acabamos aquí con esta entrega. En la próxima, continuaremos definiendo las interfaces de las clases del diseño anterior. Espero que os haya gustando. Cualquier sugerencia o pregunta es bienvenida.
Saludos ;)