Tres en raya

Tic-tac-toe [1]  es un juego lógico entre dos oponentes en un campo cuadrado de 3 por 3 celdas o más (hasta un "campo infinito"). Uno de los jugadores juega con "cruces", el segundo, con "noes". El juego tradicional chino ( Gomoku ) utiliza piedras blancas y negras.

La versión clásica

Reglas del juego

Los jugadores se turnan para poner signos de 3×3 en las celdas libres del campo (uno siempre es cruces, el otro siempre es ceros). El primero en alinear 3 de sus piezas en vertical, horizontal o diagonal gana. El primer movimiento lo hace el jugador colocando cruces.

Normalmente, al final del juego, el bando ganador tacha con una línea sus tres caracteres (cero o cruz), que forman una fila continua.

Análisis

Son conocidos los algoritmos para cada una de las partes, que garantizan un empate en cualquier juego del oponente, y si se equivoca, te permiten ganar. Por lo tanto, el juego está en un estado de " muerto muerto ".

A continuación se presentan algunas de estas estrategias. Se cree que el jugador siempre respeta dos reglas que tienen prioridad sobre todas las demás:

Para cruces

Haz el primer movimiento hacia el centro. El resto de movimientos, si no son aplicables las reglas 1-2, se realizan al de las esquinas libres, que es el más alejado del anterior movimiento de ceros , y si esto no es posible, a cualquier celda.

     
  X  
  O  

Demostremos que esta estrategia conduce a una victoria o un empate. Si el cero va hacia un lado, entonces la posición (hasta la simetría) será la siguiente:

  O  
  X  
X    

Después de eso, las reglas 1 y 2 llevarán a la posición:

X O O
  X  
X    

ganar _

Si el cero va a una esquina, la posición (hasta la simetría) será la siguiente:

O    
  X  
    X

Dependiendo del próximo movimiento del cero, surgirá una de tres posiciones:

O O
  X  
    X
O
  X O
    X
O O 
X
X

Ganan los cruces en las dos primeras posiciones  . En el tercero, un empate .

Para ceros

Recuerde que las reglas 1-2, si corresponde, prevalecen sobre todo lo escrito a continuación.

  • Si los cruces realizan el primer movimiento hacia el centro, diríjase a cualquier esquina hasta el final del juego, y si esto no es posible, a cualquier celda.
O
X
  • Si los cruces realizan el primer movimiento hacia la esquina, responde con un movimiento hacia el centro.
X
O
   
  • En el siguiente movimiento, tome la esquina opuesta al primer movimiento de las cruces, y si esto no es posible, vaya al costado.
X
  O
 O X
  • Si los cruces hicieron el primer movimiento hacia un lado, responda con un movimiento hacia el centro.
  • Si el próximo movimiento de las cruces es hacia la esquina, tome la esquina opuesta:
X O
  O
X  
  • Si el próximo movimiento de las cruces es en el lado opuesto, vaya a cualquier esquina:
O X
O  
  X  
  • Si el próximo movimiento de las X es hacia el lado junto a su primer movimiento, vaya a la esquina al lado de ambas X.
O X
X O  
     

Árbol de situaciones de juego

El árbol de situaciones de juego para el juego tres en raya, donde el jugador de "tres en raya" va primero y actúa de acuerdo con el algoritmo anterior, y el jugador de "tres en raya" puede hacer lo que quiera ( además, se da un vértice para un acto racional y para un irracional, es decir, cualquier otro), consta de 50 nodos.

Solución informática

Para resolver este tipo de juegos, se construye en una computadora un árbol de situaciones de juego de acuerdo con el método minimax . El número total de nodos en dicho árbol es 255168 [2] . Este número se obtiene como la suma de todos los movimientos posibles - 9 opciones en el primer paso, 8 - para cada una de las 9 en el segundo paso, 7 - en cada una de las 72 opciones en el tercer paso, etc., menos las situaciones de Final anticipado del juego (ganador).

Un ejemplo de una implementación más simple para encontrar al jugador ganador: https://github.com/evgnor86/XO_game.git

Generalizaciones

Líneas más largas

Podemos considerar un juego en el que el ganador es el jugador que primero construyó signos idénticos en un campo rectangular lo suficientemente grande para esto. En este caso, puedes limitar el campo a algún tamaño (empezando por ), o no limitarlo en absoluto (en este caso, hablan de un campo “infinito”).

Jugar hasta 4 signos idénticos en un campo sin fin no es interesante, porque un principiante construye un "tenedor" con bastante rapidez y gana. El juego en tampoco es interesante debido a la "muerte del sorteo". Hay estrategias que evitan que el enemigo construya la línea deseada nunca. Sin embargo, cuando el juego se vuelve mucho más significativo. Esta opción tiene un nombre especial: gomoku . Gomoku se jugó originalmente en un tablero de 19 × 19, luego se redujo a 15 × 15 cuadrados.

La principal táctica ganadora cuando se juega en un campo sin fin es la construcción de intersecciones ("horquillas"), que no le dan al enemigo la oportunidad de bloquear todas las formas posibles de construir un cinco. Para no perder, es necesario interrumpir oportunamente las líneas del enemigo con una longitud de tres piezas o más.

La práctica ha demostrado que con reglas iguales para los jugadores, el que hace el primer movimiento tiene una ventaja que le permite ganar con un juego suficientemente hábil, lo que posteriormente se demostró estrictamente [3] [4] . Para mantener el interés en el juego, se propusieron varias opciones para modificar las reglas del juego.

Entonces, con la introducción de faltas (movimientos prohibidos) para un jugador que comienza primero, tiene prohibido construir tenedores 3 × 3, 4 × 4, así como construir una "fila larga" de sus piezas - un nuevo juego llamado Se obtuvo renju , con una amplia variedad de estrategias de juego e igualdad de oportunidades de los jugadores.

Modificación de campo

El aumento del tamaño del campo ya se ha discutido anteriormente. La riqueza más simple, pero más táctica del juego, es agregar un cuadrado a lo largo de un lado del tablero de 3x3.

Otra opción es cambiar la topología del campo. Por ejemplo, uno puede considerar que los lados opuestos del campo están pegados, formando así la superficie de un cilindro o toro , o un plano proyectivo . También puedes aumentar la dimensión, por ejemplo, jugar en un cubo de 4x4x4, en un hipercubo, etc.

Intercambio de iconos

Puede cancelar la regla que les dice a los jugadores que coloquen solo su propio tipo de íconos.

Por ejemplo, una variante del juego podría ser: los jugadores ponen una cruz o un cero (lo que quieran); el primero gana si construye una línea de la longitud requerida a partir de los mismos iconos, el segundo gana si esto no sucede antes de que se llene el campo.

Otra opción: el ícono "propio" cambia con cada movimiento.

Las condiciones ganadoras cambian

En lugar de terminar el juego construyendo la primera línea de la longitud deseada, no puede detenerse allí y continuar hasta que el campo esté completamente lleno. Por ejemplo, en cualquier campo puedes jugar en quién construirá la mayor cantidad de "cuatro" a partir de sus signos.

También existe una variante del tres en raya de Silverman . Utiliza un campo de juego de celdas 4x4. Las cruces ganan si hay una fila de 4 iconos idénticos (cruces o ceros), de lo contrario ganan los ceros.

También existe una variante del juego con el clásico campo 3×3, en el que es necesario hacer dos filas para ganar, mientras que el algoritmo contrario solo necesita una. [5] [6]

Alargamiento del trazo

Otra opción para modificar el juego es poner en cada movimiento no uno de tus signos, sino dos o más. Tal es el juego Connect6 , en el que las negras hacen el primer movimiento al exponer un signo, después de lo cual los jugadores exponen alternativamente dos signos, el primero en construir una línea de 6 o más de sus signos gana.

Tres en raya en la cultura

Hay tres canciones dedicadas a este juego.

  • La canción "Tic Tac Toe" del compositor Veniamin Basner con los versos de Mikhail Matusovsky interpretada por Taisiya Kalinchenko se convirtió en la laureada de "Songs-74" [7] . Posteriormente fue cantada por Eduard Khil [8]
  • Katya Lel cantó otra canción con el mismo nombre [9]
  • La tercera canción fue cantada por Viktor Rybin y Natalya Senchukova [10] a dúo .

Véase también

Notas

  1. ↑ En el siglo XIX, junto con el nombre “tic-tac-toe” (ver N. A. Leikin , “A school day at a German school”, 1871), también se usaba “heriki-oniki” o “heriki”  - según el nombre antiguo del alfabeto de letras rusas "X" - "dick" y "O" - "it" ( "Dahl" en el Diccionario de Dahl Copia de archivo fechada el 14 de junio de 2011 en Wayback Machine ), "ceros" ( N. P. Gilyarov-Platonov , "De la experiencia", 1886
  2. ↑ ¿Cuántos juegos de tres en raya (tres en raya)? . www.se16.info. Consultado el 16 de agosto de 2019. Archivado desde el original el 15 de febrero de 2020.
  3. ↑ Allis, LV (1994). Búsqueda de soluciones en juegos e inteligencia artificial, Ph.D. Tesis, Universidad de Limburg, Maastricht.
  4. ↑ Allis, LV, Herik, HJ van den y Huntjens, MPH (1996). Go-Moku resuelto por nuevas técnicas de búsqueda. Inteligencia computacional, vol. 12
  5. ↑ Dos veces cruces-círculos | videojuego | videogamegeek
  6. ↑ Twice crosses-circles: descarga gratuita, préstamo y transmisión: Internet Archive
  7. ↑ Taisiya Kalinchenko "Tic-tac-toe" (1974) . Consultado el 17 de enero de 2022. Archivado desde el original el 17 de enero de 2022.
  8. ↑ Eduard Khil, - Tres en raya . Consultado el 17 de enero de 2022. Archivado desde el original el 17 de enero de 2022.
  9. ↑ Katya Lel - Tres en raya . Consultado el 17 de enero de 2022. Archivado desde el original el 17 de enero de 2022.
  10. ↑ Viktor Rybin y Natalya Senchukova - Tic-Tac-Toe . Consultado el 17 de enero de 2022. Archivado desde el original el 17 de enero de 2022.

Literatura

  • Gardner M. Tres en raya. —M.: Mir, 1988. ISBN 5-03-001234-6 .