Domineering

Domineering (también llamado Stop-Gate o Crosscram) es un juego matemático que se puede jugar en cualquier colección de cuadrados en una hoja de papel cuadriculado. Por ejemplo, se puede jugar en un cuadrado de 6 × 6, un rectángulo, un polyomino completamente irregular o una combinación de cualquier número de tales componentes. Dos jugadores tienen una colección de fichas de dominó que colocan sucesivamente en la cuadrícula, cubriendo los cuadrados. Un jugador coloca las fichas verticalmente, mientras que el otro las coloca horizontalmente. (Tradicionalmente, estos jugadores se denominan "Izquierda" y "Derecha", respectivamente, o "V" y "H". En este artículo se utilizan ambas convenciones). Como en la mayoría de los juegos de teoría de juegos combinatorios, el primer jugador que no puede moverse pierde.

Domineering
Género	juego basado en fichas
Jugadores	2
Azar	no
Habilidades	estrategia
[editar datos en Wikidata]

Ejemplo de juego de Domineering jugado en un tablero de 5x5, con el jugador horizontal ("H" o "Derecha") haciendo el primer movimiento y perdiendo en la 13ª ronda de juego.

Domineering es un juego partisano, en el que los jugadores usan diferentes piezas: la versión imparcial del juego es Cram.

Ejemplos básicos

Cuadro único

Aparte del juego vacío, donde no hay cuadrícula, el juego más simple es una sola caja.

 

En este juego, claramente, ningún jugador puede moverse. Dado que es una victoria del segundo jugador, es un juego cero.

Filas horizontales

  

Este juego es una cuadrícula de 2 por 1. Existe una convención de asignar al juego un número positivo cuando la Izquierda está ganando y uno negativo cuando la Derecha está ganando. En este caso, Izquierda no tiene movimientos, mientras que Derecha puede jugar un dominó para cubrir todo el tablero, sin dejar nada, lo que claramente es un juego de cero. Por tanto, en notación numérica surreal, este juego es {| 0} = −1. Esto tiene sentido, ya que esta cuadrícula es una ventaja de 1 movimiento para Derecha.

   

Este juego también es {| 0} = −1, porque una sola casilla no se puede jugar.

    

Esta cuadrícula es el primer caso de elección. La derecha podría jugar las dos casillas de la izquierda, dejando -1. Las casillas de la derecha también dejan -1. También podría jugar las dos casillas del medio, dejando dos casillas individuales. Esta opción deja 0 + 0 = 0. Por lo tanto, este juego se puede expresar como {| 0, −1}. Este es -2. Si este juego se juega junto con otros juegos, estos son dos movimientos libres para Derecha.

Columnas verticales

Las columnas verticales se evalúan de la misma manera. Si hay una fila de 2 n o 2 n +1 casillas, cuenta como - n . Una columna de tal tamaño cuenta como + n .

Cuadrículas más complejas

  
  

Este es un juego más complejo. Si la izquierda va primero, cualquier movimiento deja una cuadrícula de 1 × 2, que es +1. La derecha, por otro lado, puede moverse a -1. Por tanto, la notación numérica surreal es {1 | −1}. Sin embargo, este no es un número surrealista porque 1> −1. Este es un juego pero no un número. La notación para esto es ± 1, y es un juego caliente, porque cada jugador quiere moverse aquí.

   
   

Esta es una cuadrícula de 2 × 3, que es aún más compleja, pero, al igual que cualquier juego de Domineering, se puede desglosar observando cuáles son los distintos movimientos para Izquierda y Derecha. La izquierda puede tomar la columna de la izquierda (o, de manera equivalente, la columna de la derecha) y moverse a ± 1, pero es claramente una mejor idea dividir el medio, dejando dos juegos separados, cada uno con un valor de +1. Por tanto, el mejor movimiento de Left es +2. La derecha tiene cuatro movimientos "diferentes", pero todos dejan la siguiente forma en alguna rotación:

   
 

Este juego no es un juego caliente (también llamado juego frío), porque cada movimiento lastima al jugador que lo hace, como podemos ver al examinar los movimientos. La izquierda puede moverse a -1, la derecha puede moverse a 0 o +1. Por lo tanto, este juego es {−1 | 0,1} = {−1 | 0} = −½.

Nuestra cuadrícula de 2 × 3, entonces, es {2 | −½}, que también se puede representar por el valor medio, ¾, junto con la bonificación por moverse (la "temperatura"), 1¼, así: ${\displaystyle \textstyle \left\{2\left|-{\frac {1}{2}}\right.\right\}={\frac {3}{4}}\pm {\frac {5}{4}}}$ 

Juego de alto nivel

El Mathematical Sciences Research Institute celebró un torneo de Domineering, con un premio de $ 500 para el ganador. Este juego se jugó en un tablero de 8 × 8. El ganador fue el matemático Dan Calistrate, que derrotó a David Wolfe en la final. El torneo se detalla en Games of No Chance de Richard J. Nowakowski (p. 85).

Estrategia ganadora

 

Representación del árbol de juego para un juego de Domineering jugado sobre un tablero 4x4, con el jugador horizontal ("H") comenzando y dos movimientos ya jugados. El árbol ha sido podado con poda alfa-beta y se incluyen valores minimax que indican que H tiene una estrategia ganadora desde la raíz.

Un problema de Domineering es calcular la estrategia ganadora para tableros grandes, y particularmente tableros cuadrados. En 2000, Dennis Breuker, Jos Uiterwijk y Jaap van den Herik calcularon y publicaron la solución para el tablero de 8x8.^[1]​ El tablero 9x9 siguió poco después de algunas mejoras de su programa. Luego, en 2002, Nathan Bullock resolvió el tablero 10x10, como parte de su tesis sobre Domineering.^[2]​ TEl tablero 11x11 fue resuelto por Jos Uiterwijk en 2016.^[3]​

Domineering es una victoria del primer jugador para los tableros cuadrados 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 y 11x11, y una victoria del segundo jugador para los tableros 1x1 y 5x5. Los otros valores conocidos para tablas rectangulares se pueden encontrar en el sitio de Nathan Bullock.^[4]​

Cram

Artículo principal: Cram

Cram es la versión imparcial de Domineering. La única diferencia en las reglas es que cada jugador puede colocar sus fichas de dominó en cualquier orientación. Parece solo una pequeña variación en las reglas, pero da como resultado un juego completamente diferente, que se puede analizar con el teorema de Sprague-Grundy.

Referencias

1. Breuker, D. M.; Uiterwijk, J. W. H. M.; van den Herik, H. J. (6 de enero de 2000). «Solving 8×8 Domineering». Theoretical Computer Science 230 (1–2): 195-206. doi:10.1016/S0304-3975(99)00082-1. 
2. Nathan Bullock Domineering:Solving Large Combinatorial Search Spaces M.Sc. thesis, 2002
3. Uiterwijk, J. W. H. 11x11 Domineering Is Solved: The First Player Wins. Computers and Games 2016. pp. 129-136. doi:10.1007/978-3-319-50935-8_12. 
4. Nathan Bullock'site : Updated Game Theoretic Values for Domineering Boards

Bibliografía

• Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters, Ltd. ISBN 978-1-56881-277-9. 
• Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for your Mathematical Plays. A K Peters, Ltd. ISBN 978-0-12-091150-9. 
• Gardner, Martin (1974). «Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies». Scientific American 230 (2): 106-108. doi:10.1038/scientificamerican0374-102. 

Enlaces externos

En inglés:

• Stop-Gate en BoardGameGeek
• Versión jugable en Pencil and Paper Games

•   Datos: Q5290335
•   Multimedia: Domineering / Q5290335