5 de enero de 2014

Juegos Solucionados

Se dice que un juego esta solucionado (solved games) cuando se ha comprobado que se puede conocer resultado final del mismo (valor teórico del juego), siempre y cuando se realicen solo jugadas óptimas. Para los juegos que no son evidentes, es necesario el uso de las matemáticas junto con el poder de procesamiento de un computador para poder llegar a una solución.

Sabemos que el muy popular juego de Tic Tac Toe (i.e.: la vieja, cruces y círculos, etc.) es empate si se se juega adecuadamente cada movimiento siendo posible de lograrlo para cada jugador, es por esa misma razón que una vez que ya conocemos esas jugadas no genera ninguna interés el practicarlo.

La búsqueda de las soluciones se aplica a juegos de dos personas, con información perfecta y jugadas alternativas. La información perfecta establece que no hay información oculta, todas las piezas están mostradas y no existe el factor suerte. usualmente se les llama juegos abstractos pero sin embargo éste es un término confuso porque el juego puede tener algún tema. Los resultados posibles son ganar, perder y empatar.

No se han logrado resolver muchos juegos, de los antiguos en 1995 se resolvió el Nine Men Moriis cuyo resultado es empate, al igual que el Fanarona. Mas recientemente, en el 2007 se logró resolver el juego de Damas, lo cual fue producto de un arduo y extenso trabajo por mas de 18 años para establecer que el juego debe quedar tablas. De la familia Mancala se ha resuelto el Kalah en el 2000 y el Awari en el 2002, ambos terminan empatados, mientras que el Ohvalhu que es el Manacala con cuatro filas, gana el jugador que realiza la primera jugada. Otros antiguos como Tigres y Cabras termina en tabla y Maharaja and Sepoys es ganado por los sepoys.
Los juegos se pueden clasificar en cuatro categorías de acuerdo a la solución:

  • Categoría 1: solucionables por cualquier método.
  • Categoría 2: solucionables mediante el método de la fuerza bruta.
  • Categoría 3: solucionables por métodos basados en conocimiento.
  • Categoría 4: no solucionables.
La solución del Tic Tac Toe se obtiene fácilmente mediante fuerza bruta, es decir se prueban todas las posibilidades en cada caso hasta dar con el mejor resultado, otros juegos implican una cantidad de posibilidades tan altas que es necesario descartar aquellas absurdas para lo cual se requiere de algún conocimiento y la generación de base de datos que ya tengan resueltas muchas posiciones finales.

Juegos más modernos han sido igualmente resueltos, aquí hay un entretenido vídeo donde se muestra la solución para el Connect Four dada por primera vez en 1988 con resultado ganador.  En el Hex (1987) el primer jugador asegura una victoria si todas las jugadas son perfectas mientras que en el Quarto se termina en tablas.

Lo entendidos en el tema diferencian la clase de solución lograda, siendo posible que la misma sea ultra débil, débil o fuerte en función de nivel de perfeccionamiento de las jugadas siendo así que para el último caso es posible que no todas sean perfectas y aun así se logra llega inequívocamente a una solución. La solución del Connect Four es del primer tipo mientras que la del Awari es del último.

 Uno de los aspectos relevantes que entran en consideración es si el juego es convergente o divergente. En el primer caso en la medida que avanza el juego hay menos piezas en el tablero como sucede con el ajedrez,  mientras que en el segundo se incrementa la cantidad de piezas sobre el tablero en la medida que se desarrolla el juego, tal es el caso del Go y los juegos de conexiones en general como el Connect Four y el Hex. Curiosamente el Shogi se considera un juego que no es convergente ni divergente ya que la cantidad total de piezas no cambia durante el desarrollo del juego. 

La solución del juego de Go es el Santo Grial de la comunidad que se dedica al tema, las miriadas de posibilidades lo hacen realmente complejo, sigue siendo un campo de investigación muy utilizado para el desarrollo de la Inteligencia Artificial y algoritmos matemáticos, seguramente éste y todos los demás se llegarán a resolver.

No hay comentarios.:

Publicar un comentario