Teoría de los Juegos

El primer teorema de teoría de juegos apareció hace al menos cien años, y se lo debemos a Zermelo. Este demostró que en todo juego sin azar, con un número finito de posiciones, uno de los jugadores tiene una estrategia no perdedora.

El teorema, de aspecto más que inocente, engloba juegos como el ta-te-tí (o tres en raya), las damas, el ajedrez, y el go. Es sólo una cuestión de complejidad -el número inmenso de posiciones posibles- lo que los diferencia. El propio Zermelo era consciente de esta complejidad, y el mismo título  nos indica que tenía en mente el ajedrez: “Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels

Consideremos brevemente el ta-te-tí. Este es un juego simple de analizar, tiene “pocas” movidas en comparación al ajedrez. En un tablero de tres por tres, ambos jugadores van colocando fichas en alguna de las nueve casillas -el primero de un color, el segundo de otro- y el objetivo es colocar tres en una misma línea. No es difícil descubrir la estrategia que debe seguir el primer jugador para evitar perder, claro que eso no significa que el primer jugador gane: si el segundo juega correctamente, aunque no pueda obtener una victoria sí puede forzar el empate. Tampoco es difícil programar una computadora para que juegue bien al ta-te-tí, después de todo, una estrategia es una receta (o un programa) que nos dice qué hacer ante cada situación que se nos presenta.

Avanzando sobre los juegos mencionados, las damas son relativamente simples. Y el ajedrez, a juzgar por los resultados actuales de los matchs humanos-vs-computadoras, se podría creer que también lo es. Pero el ajedrez no está resuelto en los mismos términos que sí lo está el ta-te-tí: hoy las máquinas ganan a cualquiera sólo porque ven más lejos, tienen un horizonte de movidas analizadas por delante superior al que se plantean analizar los humanos. Eliminando -para el humano- la restricción temporal (esto es, dándole más tiempo para analizar las movidas, en lugar de las habituales dos horas para cuarenta movidas), la fuerza de la máquina se ve disminuida. Esto se observa en el ajedrez postal, tanto en el clásico por correo como en su versión moderna por e-mail. El go computacional, por ahora, está en una fase menos desarrollada, pero creo que es sólo cuestión de tiempo hasta que un programa comience a vencer a los seres humanos.

Otra clase de juegos incluídos en el teorema de Zermelo es aquella de juegos de retirar piedritas o varillas de un determinado grupo siguiendo ciertas reglas hasta que no haya movidas posibles. El Nim es un ejemplo clásico, pero quiero mencionar aquí otro cuyo nombre desconozco, sobre todo porque es un caso típico del monstruo matemático creado a principios del siglo XX por Zermelo y sus amigos. El juego consiste en quitar grupos de piedritas de una tabla rectangular como la siguiente:

x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x

La regla es que -una vez elegida una piedra- se quitan todas las que estén por encima y a su derecha. Por ejemplo, si se selecciona la piedra marcada con una o,

x x x x x x x x x x
x x x x x o x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x

habrá que quitar todas las piedras marcadas ahora con una o:

x x x x x o o o o o
x x x x x o o o o o
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x

Y el que haga la última movida, pierde (sería muy simple la estrategia ganadora del blanco si quien hace la última movida gana: toma la que está en el extremo inferior izquierdo y retira todas!)

Este juego, incluído en el Teorema de Zermelo, debe tener forzosamente una estrategia ganadora para uno de los jugadores, aunque tal vez dependa del tamaño del rectángulo de mxn piedras. La pregunta que les dejo para la próxima columna es ¿cual?

¡Pero cuidado! La pregunta es ¿para cual jugador hay una estrategia?, no es ¿cual es la estrategia? (bueno, si quieren probar encontrarla, adelante, ¡que yo no la conozca no quiere decir que no exista o que no sea posible descubrirla!)

Y como esta es una columna dedicada a las matemáticas pero también a la literatura, una segunda pregunta que espero responder en otra ocasión es la siguiente:

¿Y qué tiene que ver todo esto con la literatura?

La respuesta, créanme, es verdaderamente surrealista.

 

About these ads

~ por judithluisros en abril 11, 2007.

Una respuesta to “Teoría de los Juegos”

  1. Me gustaría saber quien es el autor o autora de este blog. Y también la fuente del último post. Me suena haberlo leido en alguna parte ;-)

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: