Determinación del número de estados válidos del tablero TicTacToe en función de la dimensión del tablero

Question

Intento encontrar una ecuación de forma cerrada en términos de $n$ por el número de válidos Tic-Tac-Toe estados del tablero (ignorando la simetría), donde el tablero tiene dimensión $n \times n ,\; 0 \lt n,\;n \in \Bbb Z $ .

Reglas del Tic-Tac-Toe:

• Le site $X$ la ficha se mueve primero
• Ningún jugador puede abstenerse de moverse

• El juego termina cuando:

  • Todos los espacios están llenos
  • $n$ salidas de fichas idénticas horizontales, verticales o diagonales

A partir de estas reglas, ¿cómo podemos derivar una ecuación de forma cerrada del número de estados válidos del tablero Tic-Tac-Toe cuando la dimensión del tablero cambia en términos de $n\,$ ?

---

Las observaciones de valores pequeños de $n$ :

$\;n = 1: 2\;$ estados válidos de la junta directiva (por enumeración)

[ ], [X]

$\;n = 2: 29\;$ estados válidos de la junta directiva (por enumeración)

[ ][ ]  [X][ ]  [ ][X]  [ ][ ]  [ ][ ]  [X][O]  [X][ ]  [X][ ]  [O][X]  
[ ][ ], [ ][ ], [ ][ ], [X][ ], [ ][X], [ ][ ], [O][ ], [ ][O], [ ][ ],

[ ][X]  [ ][X]  [O][ ]  [ ][O]  [ ][ ]  [O][ ]  [ ][O]  [ ][ ]  [X][O]  
[O][ ], [ ][O], [X][ ], [X][ ], [X][O], [ ][X], [ ][X], [O][X], [X][ ],

[X][O]  [X][X]  [X][ ]  [X][X]  [X][ ]  [O][X]  [O][X]  [ ][X]  [ ][X]  
[ ][X], [O][ ], [O][X], [ ][O], [X][O], [X][ ], [ ][X], [O][X], [X][O], 

[O][ ]  [ ][O]
[X][X], [X][X]

$\;n = 3: 255,168\;$ estados válidos del tablero (por referencia )

Answer 1

Una pregunta divertida.

No tengo suficiente karma para añadir esto como comentario, así que lo ofreceré como respuesta, aunque es (actualmente) una respuesta incompleta.

Algunos comentarios

La referencia que enlazas para el $N=3$ caso no dice que haya $255,168$ un tres por tres válido tableros pero que hay $255,168$ distintos tres por tres tic-tac-toe juegos .

Es decir, si haces un "árbol de juego" donde cada tablero (válido) es un nodo y cada movimiento es una arista, estás preguntando cuántos nodos están en el árbol. El artículo de la Wikipedia afirma que hay $255,168$ distintivo caminos a través del árbol (desde la raíz hasta una hoja), pero hay muchos menos nodos. De hecho, podemos establecer un límite superior para el número de tableros de tres por tres distintos ignorando las reglas del juego y observando que sólo hay $3^9$ formas de llenar un tablero de 9x9 con 3 fichas (en blanco, X y O), lo cual es sólo $19,683$ . Y muchos de ellos tienen demasiadas equis u os para ser válidos.

(El artículo de Wikipedia también tiene en cuenta la simetría, que si te entiendo bien, quieres ignorar).

Resulta que estoy trabajando en un programa que genera este árbol de juegos por razones totalmente diferentes.

Es posible que el programa tenga errores, así que tomen los números anteriores con cautela, pero a mí me parecen correctos al inspeccionarlos. Creo que he visto otras páginas en línea que corroboran la $N=3$ caso, pero en ese momento sólo trataba de validar que mi programa funcionaba correctamente, así que no me molesté en registrar el enlace.

Actualmente mi programa se queda sin memoria (en mi pequeño netbook) cuando intento generar el árbol del juego para $N=4$ pero me imagino que eso se puede arreglar con un hardware un poco más potente y/o una pequeña optimización del programa en cuanto al espacio de memoria (actualmente estoy almacenando un lote de metadatos sobre el estado de cada placa).

Si las circunstancias lo permiten, intentaré volver y actualizar esta respuesta con más información si tengo algo que compartir, pero quería poner algunas cifras concretas (y restricciones específicas) sobre la mesa porque creo que aclara parte de la confusión en el hilo de comentarios.

Supuestos

Para aclarar las limitaciones del problema, esto es lo que estoy suponiendo:

1. Nos interesa contar el número de "estados de juego" válidos en un $N$ -por- $N$ tablero de tres en raya.
2. Ignoramos la simetría, por lo que una tabla con un X en la esquina superior izquierda se considera una tabla distinta de la que tiene un X en la esquina inferior derecha.
3. X siempre se mueve primero.
4. El juego se detiene cuando uno de los dos jugadores hace una línea horizontal, vertical o diagonal de longitud $N$ . Las tablas que sólo se pueden alcanzar si se sigue jugando después de que uno de los jugadores haya hecho una línea se consideran inválidas y se ignoran.
5. (El juego también se detiene cuando nos quedamos sin espacios libres para movernos, por supuesto).

Algunos datos basados en la enumeración

Con estas limitaciones, como ha escrito, podemos confirmarlo:

• para $N=1$ hay $2$ tablas válidas y distintas
• para $N=2$ hay $29$ tablas válidas y distintas

Basándonos en la inspección (programática), creo que podemos afirmarlo:

• para $N=3$ hay $5,478$ tablas válidas y distintas
• para $N=4$ hay $9,722,011$ tablas válidas y distintas

Si se desglosan por capas (vueltas):

      N:   1   2     3        4
 -------   -  --  ----  -------
 ply  0:   1   1     1        1
 ply  1:   1   4     9       16
 ply  2:   -  12    72      240
 ply  3:   -  12   252     1680 
 ply  4:   -   0   756    10920
 ply  5:   -   -  1260    43680
 ply  6:   -   -  1520   160160 
 ply  7:   -   -  1140   400400
 ply  8:   -   -   390   895950
 ply  9:   -   -    78  1433520
 ply 10:   -   -     -  1962576
 ply 11:   -   -     -  1962576          
 ply 12:   -   -     -  1543080
 ply 13:   -   -     -   881760
 ply 14:   -   -     -   333792
 ply 15:   -   -     -    83440
 ply 16:   -   -     -     8220 
 =======   =  ==  ====  =======  
  TOTAL:   2  29  5478  9722011
 -------  

No veo una fórmula obvia para la secuencia $(2,29,5478,9722011,...)$ pero algunas observaciones interesantes (IMO) sobre esto:

• $N=3$ es el tablero más pequeño para el que el jugador O puede ganar

• $N=3$ es el tablero más pequeño que puede terminar en un juego de empate

• $N=2$ es probablemente el sólo tablero que no puede ser llenado ( X está garantizado que gane en el tercer movimiento, dejando una ranura sin cubrir)

• Los dos ejemplos pares tienen dos capas en una fila con exactamente el mismo número de tablas (para $N=2$ las capas 2 y 3 tienen $12$ tablas y para $N=4$ Las capas 10 y 11 tienen $1,962,576$ ). También son las capas más "anchas" de sus respectivos árboles. (Lo mismo ocurre con $N=1$ pero imagino que es un caso degenerado).

• (Esto no se ha mantenido para $N=4$ .) Puede que sólo sea la ley de los números pequeños, pero observo que el nivel más "amplio" del árbol del juego es aquel en el que hay $N$ espacios vacíos que quedan en el tablero. Para $N=1$ , se trata de la capa 0 con $1$ tablero, para $N=2$ esta es la capa 2 con $12$ tablas y para $N=3$ esto es la capa 6, con $1,520$ tablas.

• y, por supuesto, en $N=1$ , jugador O ni siquiera llega a moverse.

Mirando los límites superiores

Por cierto, como comprobación de cordura muy aproximada, he comparado el número de tablas válidas con $3^{(N^2)}$ (el número de formas distintas de llenar un $N\times{}N$ tablero con 3 símbolos):

       N:   1     2        3          4
 -------- ----  ----  -------  ----------
 # Valid:  2    29     5478     9722011
 3^(N^2):  3    81    19683    43046721
 % Valid: 66.7  35.8     27.8        22.6

Podemos obtener un límite superior más ajustado si observamos el número de formas de llenar un $N\times{}N$ tablero con $count(X) = count(O)$ o $count(X) = count(O)+1$ .

En realidad no es tan difícil de averiguar si cambias un poco tu forma de pensar. En lugar de alternar entre X y O, imagina que pones primero todas las X y luego todas las O.

• En la capa zeroth, no hay Xs ni Os, por lo que siempre tenemos 1 tabla. (Tenga en cuenta que esto es $N^2$ elija $0$ , escrito ${{N^2} \choose 0}$ ).

• En la primera capa, hay exactamente una X, por lo que tenemos ${{N^2} \choose 1}$ distintos tableros.

• En la segunda capa, hay exactamente una X y exactamente una O, por lo que tenemos ${{N^2} \choose 1} \times {((N^2)-1) \choose 1}$ tablas.

• En la tercera capa, hay dos X y una O, por lo que tenemos ${{N^2} \choose 2} \times {{((N^2)-2)} \choose 1}$ tablas.

• En la cuarta capa, hay dos X y dos Os, por lo que tenemos ${{N^2} \choose 2} \times {{((N^2)-2)} \choose 2}$ tablas.

Y así sucesivamente.

En el caso general

Tenga en cuenta que en la capa $p$ habrá $floor({{(p+1)}\over{2}})$ Xs y $floor({{p}\over{2}})$ Os en el tablero, así que digamos:

• $x = floor({{(p+1)}\over{2}})$

y

• $o = floor({{p}\over{2}})$

Tenga en cuenta que:

• Hay ${{N^2} \choose x}$ formas de colocar $x$ X marcas en un $N\times{}N$ tablero.

• Hay ${{N^2 - x} \choose o}$ formas de colocar $o$ O marcas en un $N\times{}N$ tablero que ya está lleno de $x$ X s.

Por lo tanto, ignorando a los ganadores lo hay:

${{N^2} \choose x} \times {{N^2 - x} \choose o}$

tablas distintas en la capa $p$ . O bien (introduciendo las definiciones de $x$ y $o$ desde arriba):

${{N^2} \choose {floor({{p+1}\over{2}})}} \times {{N^2 - {floor({{p+1}\over{2}})}} \choose {floor({p \over 2})}}$

Así que un límite superior en el número de tablas distintas sería la suma de esa fea fórmula sobre $p = 0$ a $p = N^2$ .

Me imagino que la aplicación inteligente del álgebra podría simplificar drásticamente esa expresión (sobre todo cuando se introduce la definición de $n \choose k$ para la notación de elección).

Para obtener un recuento aún mejor podríamos tener en cuenta las tablas ganadoras.

Answer 2

I disagree with some of the results in the N=3 column in the table above.
I agree with the values cited for up through ply 5.
But from that point on:
    ply:      table value:       my value:
     6           1520               1680
     7           1140               1260  
     8            390                630
     9             78                126  
    total for 9 plys:
                 5478               6046  
Basis: formula for N things taken R at a time  N! /(R! x (N-R)!
EX: Ply 7:   N = 9, R = 4 for X  9! / (4!)(9-4)! = 126
             N = 5, R = 3 for O  5! / (3!)(5-3)! = 10
             126 x 10 = 1260