Ejercicio: Ganar al 3 en ralla

De Edutec Wiki
Saltar a: navegación, buscar


El juego del tres en ralla es un muy buen ejemplo de algoritmia aplicada a la vida real. En este ejercicio aprenderemos dos sistemas distintos para ganar al tres en ralla, de los cuales puede salir una discusión interesante sobre la resolución de problemas complejos en computación.

Las reglas del juego

El juego del tres en ralla es un juego de mesa para dos jugadores, y se juega sobre un tablero de 3x3 casillas cuadradas.

Se decide al azar quien comienza la partida, y el jugador que empieza lleva las fichas en forma de X, el otro las fichas en forma de O.

En cada turno, el jugador correspondiente está obligado a colocar una ficha en una casilla vacía del tablero.

Ganará la partida quien consiga obtener primero una línea de tres de sus fichas, tanto ortogonal como diagonalmente. Si termina la partida sin que nadie haya conseguido tres fichas en línea, el juego resulta en empate.

Adjuntamos un ejemplo de partida en qué el jugador que lleva las cruces gana:

Tic-tac-toe-game-1

Materiales necesarios

Este ejercicio puede realizarse de muchas formas distintas. Si se desea, se pueden usar tableros reales de madera u otros materiales.

En caso de no tener tableros y fichas disponibles, se pueden confeccionar con madera, papel, o cartón.

Otra forma rápida de jugar al tres en ralla es trazar el tablero sobre papel y usar un lápiz para marcar las Os y las Xs.

Ganar al 3 en ralla - 01.png

Pensar como un ordenador

Estudiaremos la partida del tres en ralla desde el punto de vista del jugador que empieza la partida, el que lleva las Xs.

Para ello, estableceremos una serie de órdenes o instrucciones, que deberemos seguir estrictamente y por orden.

En computación, cada una de estas colecciones de instrucciones ordenadas se denomina algoritmo. Como veremos, existen varios algoritmos distintos para atacar un mismo problema, y cada uno de ellos aporta ventajas y desventajas.

Fuerza bruta

En computación, un primer acercamiento habitual a un problema de este tipo es contar todos los casos posibles y escoger, en cada turno, el que mejor resultado nos proporcione.

En el caso del tres en ralla, podemos realizar un diagrama parecido a este para contar con cuantas posibles situaciones podemos encontrarnos:

Tic-tac-toe-game-tree

Fijaos como, en el primer movimiento, solo hay tres posibilidades iniciales: jugar en el centro, jugar en un lateral o jugar en una esquina. Cualquier otra posición es simétrica a una de estas y, por lo tanto, no es necesario considerarla.

Dependiendo del movimiento elegido, el jugador que lleva las Os tendrá posibilidades completamente distintas.

Asimismo, dependiendo del segundo movimiento, el jugador que lleva las Xs volverá a tener distintas posibilidades.

Intentad terminar el árbol por vuestra cuenta teniendo en cuenta las simetrías. ¿Cuantas situaciones posibles existen? ¿Creéis que éste es un buen acercamiento al juego?

Crecimiento no lineal

Si habéis intentado completar el diagrama, os habréis dado cuenta de que el número de posibilidades aumenta de forma muy rápida. En otras palabras, os va a hacer falta un papel muy grande para poder dibujar todas las posibles partidas.

En el primer turno tenemos tres posiciones posibles, en el segundo turno tenemos 12, en el tercer turno 38, en el cuarto 108, etc. En total, existen 26830 posibles partidas distintas del tres en ralla, ¡y eso es habiendo eliminado las simetrías!

Este tipo de problema de crecimiento no lineal es el que más dolores de cabeza nos supone en computación. Aunque las computadoras son muy rápidas y pueden calcular una gran cantidad de movimientos por segundo, hay algunos problemas que ni siquiera una computadora es capaz de solucionar en un tiempo razonable siguiendo este sistema.

Por ejemplo, imaginaos este mismo acercamiento para solucionar el juego del ajedrez. Si en el tres en ralla tenemos 26830 partidas distintas, ¿cuantas creéis que tendremos para el ajedrez?

La respuesta es que existen unas 10123 partidas de ajedrez posibles. Esto es el número uno seguido de 123 ceros detrás, es decir: ¡más partidas de ajedrez que estrellas en el universo!

Si bien el tres en ralla ha sido solucionado computacionalmente usando fuerza bruta, siempre es preferible buscar un algoritmo que nos permita ahorrar capacidad de computación.

Desglosar por movimientos

Presentamos un algoritmo que, con un total de cinco instrucciones, nos garantiza que nunca perderemos una partida del tres en ralla.

Cada vez que sea nuestro turno, deberemos jugar según la instrucción que corresponda al número de tirada. Fijaos en que algunas instrucciones son condicionales, es decir, dependiendo de una condición tendremos que jugar en un lugar u otro.

  • Movimiento número 1: Colocar una ficha en una esquina.
  • Movimiento número 2:
    • ¿Está libre la esquina opuesta a la ocupada en el movimiento número 1?
      • : Colocar una ficha en esa esquina.
      • No: Colocar una ficha en cualquier otra esquina libre.
  • Movimiento número 3:
    • ¿Hay en el tablero dos Xs y una casilla vacía en línea?
      • : Colocar una ficha en esa casilla vacía.
      • No:
        • ¿Hay en el tablero dos Os y una casilla vacía en línea?
          • : Colocar una ficha en esa casilla vacía.
          • No: Colocar una ficha en cualquier esquina vacía.
  • Movimiento número 4:
    • ¿Hay en el tablero dos Xs y una casilla vacía en línea?
      • : Colocar una ficha en esa casilla vacía.
      • No:
        • ¿Hay en el tablero dos Os y una casilla vacía en línea?
          • : Colocar una ficha en esa casilla vacía.
          • No: Colocar una ficha en cualquier esquina vacía.
  • Movimiento número 5: Jugar en la única casilla vacía.

Comprobad este algoritmo jugando contra otra persona. ¿Se os ocurre alguna forma de simplificarlo todavía más?

Hay algunos pasos muy parecidos, y algunos que son exactamente iguales. Pensad en como los agruparíais para acortar el algoritmo.

Complejidad de un algoritmo

La complejidad de un algoritmo se define, a grandes rasgos, como la capacidad computacional que vamos a necesitar para solucionar el problema que tratamos usando este algoritmo.

Para entendernos, fijaos como, en nuestro caso, la fuerza bruta nos suponía tener que rellenar una hoja de papel gigante para poder dibujar todo el árbol entero. Una vez tuviéramos el árbol, para cada tirada tendríamos que ir siguiendo el camino que nos lleve a una situación óptima.

En el algoritmo del desglose por movimientos hemos conseguido reducir muchísimo el problema. Tanto, que con cinco instrucciones nos ha bastado y solo hemos necesitado media hoja de papel para escribir este algoritmo. Es evidente que la complejidad de este algoritmo es muchas magnitudes menor que la fuerza bruta.