Connect 4

De Casiopea
Revisión del 15:00 17 mar 2015 de Valentina olivares (Discusión | contribuciones) (Algoritmo y solución matemática)

(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)





Caso de Estudio
Estudiado en4º DG 2015
Estudiado porValentina Olivares


Connect 4

Descripción del juego

Connect 4 o Cuatro en línea es un juego para dos personas,cada jugador posee 21 fichas identicas de un color diferente. En el original, se utilizan los colores amarillo y rojo. Se juega en un tablero vertical que consiste de 7 columnas y 6 cuadrados en cada una (6x7) Una jugada se puede definir como situar una ficha dentro de un cuadrado del tablero, dentro de turnos. Cada jugador debe conectar 4 fichas de diferentes formas, ya sea horizontal, vertical o diagonal. El primero que logre este resultado gana la partida, si las 42 fichas han sido utilizadas y ningun jugador ha logrado su meta, se considera un empate.


  • Jugadores: 2
  • Fecha de creación:1974
  • Creador: Howard Wexler y Ned Strongin
  • Publicación: por Milton Bradley y Hasbro
  • País: Estados Unidos
  • Objetivo del juego: Alinear 4 fichas del mismo color dentro del tablero, ya sea de forma vertical, horizontal o diagonal antes que el otro jugador.
  • Categoría: Estrategia abstracta


Conecta4.jpg

Estrategias

El juego pertenece a la categoría “suma cero” en donde la ganancia o pérdida de un participante equilibra las pérdidas o ganancias de los demás participantes.

  • Zugzwang/ tsuːktsvaŋ: Concepto alemán utilizado dentro del juego, se traduce como "obligación de mover". Se dice que un jugador está en zugzwang si cualquier movimiento permitido supone empeorar su situación de juego y eventualmente, perder la partida.

Este juego posee una estrategia matemática resuelta, se analiza el número de posibilidades y estados de las fichas dentro del tablero de 6x7 Existen 4,531,984,531,985,219,092 posiciones para cada espacio del tablero, ya que puede tener una ficha del color “A”, del color “B” o estar vacía.


fig.1-2-3 muestran formas en que el jugador "blanco" puede ganar, fig.4 muestra un empate


Algoritmo y solución matemática

El juego fue resuelto por Victor Allis en 1988, demostrando que con jugadas perfectas de parte de ambos jugadores, el primer jugador puede ganar siempre si juega principalmente en la columna del medio y si el elige otra columna el otro jugador siempre puede forzar una jugada. Victor Allis presentó 9 jugadas que podrían conducir a una jugada ganadora. [1]

Minimax

Antes de hacer un movimiento dentro del juego, se deben analizar todos los movimientos posibles que podría hacer el enemigo y determinar cuál es el más adecuado, basándose en la secuencia de estos.

El computador pretende que cada uno de los movimientos han tomado lugar, por cada movimiento se analizan todos los posibles movimientos que el contrincante podría realizar en respuesta.

el algoritmo se llama minimax, porque el computador busca minimizar las pérdidas a un máximo.


Fhourstones [2]: Benchmark escrito por John Tromp en 1996-2008, el cual resuelve las posiciones posibles dentro del juego por segundo, puede resolver el juego por completo dentro de 10 minutos en un PC contemporáneo.

Conclusiones

El juego presente en el caso de estudio ha sido diseñado para que los participantes elaboren sus propias estrategias, desde el momento 0. El tablero representa una grilla, en donde si se analizan ciertos movimientos, se pueden descubrir ciertos puntos de encuentro entre las fichas, en las columnas centrales, principalmente. Victor Allis plantea que el jugador que inicia la partida siempre tiene ventaja y si juega correctamente sus partidas y dentro del centro del tablero,puede ganar la mayoría de las veces.

Este juego se presenta desde lo abstracto, obligando a diseñar una estrategia propia que conlleva a lo matemático. Luego de que Allis resolviera la estrategia principal del juego, se tomó el algoritmo que contiene todos los movimientos posibles dentro del juego, lo que ha servido para el estudio y diseño de inteligencia artificial el en área de los videojuegos.