Un árbol de decisión es un subárbol del árbol del juego, con cada nodo etiquetado como “jugador A gana”, “jugador B gana” o “empate”, donde puede probarse que ese nodo tiene ese valor (asumiendo que ambos jugadores hacen el mejor movimiento) solo con examinar otros nodos del grafo.
Si atendemos a la cota superior del árbol que genera el tablero, tenemos 9!=362.880 (9 posiciones para el primer movimiento, 8 para el segundo, y así sucesivamente).
Esta cuenta incluye partidas y movimientos ilegales, ya que el juego puede haber terminado.
Si además añadimos que las rotaciones de las posiciones son consideradas las mismas, tenemos sólo 26.830 lanzamientos.
La complejidad computacional del tres en raya depende de la forma en que esté formalizado.