23 junio 2007

Solución: El juego de las 10 y 10 piedras

Solución al problema El juegos de las 10 y 10 piedras.

Antes que nada decir que el título del problema es una puta mierda, pero no se me ocurrió uno mejor. El problema está inspirado en el capítulo de introducción del libro An Introduction to Bioinformatics Algorithms (el único que he leido, por cierto). En el libro lo llaman 10+10 game.

La solución más sencilla para encontrar una estrategia ganadora en este tipo de juegos suele ser la programación dinámica. Empezamos desde el caso más simple y vamos avanzando hacia casos más complicados.

En el juego 10+10 no empezaríamos en 10+10 si no en 0+0. Si te toca a ti jugar y quedan 0+0 piedras es obvia que has perdido. Si quedan 1+1, 1+0 o 0+1 siempre puedes ganar, porque al otro no le quedarán piedras para quitar. Si hay 2+0 piedras (o 0+2) y te toca jugar, sólo puedes hacer un movimiento posible y le lleva al otro jugador a 1+0 (o 0+1) en el que siempre gana.

Por tanto, cada pareja se numero x+y se le puede asociar un valor "puede ganar" o "siempre pierde". Podemos utilizar una matriz de 2 dimensiones. G indica "puede ganar" y P "siempre pierde". Si te toca jugar, puedes ver en que casilla estás para saber si puedes ganar o no la partida.

0 1 2
0 P G P
1 G G X
2 P X X

Estos son los valores que hemos calculado previamente para los casos más básicos. Vamos a calcular la posicion 1+2 utilizando la tabla. Desde la casilla (1,2) podemos ir hacia arriba (1, 1), diagonal arriba-izquierda (0, 1) o hacia la izquierda (0, 2). En los 2 primeros casos dejamos al otro jugador en una posicion "puede ganar" por lo tanto nosotros perderíamos, pero en el tercer caso le dejamos en "siempre pierde", por tanto la casilla en la que estamos es una casilla ganadora si vamos hacia la izquierda. Por tanto marcamos (1,2) con una G. (2,1) es equivalente así que también podemos marcarlo.

0 1 2 3 4 5 6 7 8 9 10
0 P G P
1 G G G
2 P G
3
4
5
6
7
8
9
10

A apartir de aqui podemos rellenar la tabla de izquierda a derecha y de arriba a abajo. En una casilla, si las casilla de arriba, izquierda y la diagonal son G, entonces esa casilla es P. En caso contrario es G.

0 1 2 3 4 5 6 7 8 9 10
0 P G P G P G P G P G P
1 G G G G G G G G G G G
2 P G P G P G P G P G P
3 G G G G G G G G G G G
4 P G P G P G P G P G P
5 G G G G G G G G G G G
6 P G P G P G P G P G P
7 G G G G G G G G G G G
8 P G P G P G P G P G P
9 G G G G G G G G G G G
10 P G P G P G P G P G P

Esta es la tabla completa para 10+10 gracias al copypaste. Como vemos si el primer jugador empieza en la casilla (10, 10) que está marcada como P, el jugador 2 siempre podrá realizar algún movimiento que le lleve a la victoria.

Muchas veces es mejor resolver un problema para casos muy básicos y cuando ya se domine, a partir de estos resolver los de mayor dificultad. Para esto sirve la programación dinámica.