¿Sabes lo que es interesante aquí?
Un árbol de juego para tic-tac-toe se puede construir sin conexión.
Eso es porque la cantidad de espacio y tiempo requerido para hacerlo es bastante simple. El primer movimiento se puede hacer en 9 lugares. El segundo tiene que estar entre 8, el tercero sobre 7, y así sucesivamente.
Eso es 9! = 362880 nodos para atravesar. Si tenemos en cuenta la simetría del tablero de juego, podemos aplicar simetría horizontal, vertical y diagonal para obtener 9! / 8 = 45360 nodos.
- ¿Cuáles son algunas ideas de habitaciones para una casa en Minecraft?
- ¿Jugar es un pasatiempo caro?
- ¿Cuáles son tus juegos de rol más favoritos en dispositivos móviles?
- Team Fortress 2: ¿Cómo perdió el médico su licencia médica?
- ¿Dirías que es un videojuego de rol?
Por supuesto, no todos estos son legales. Asumimos que cada posible juego irá hasta el último movimiento. Por lo tanto, el número total de movimientos para atravesar será inferior a 30000, sin entrar en las cosas pesadas como la poda alfa-beta.
Hay muchos trucos que uno puede usar para ahorrar espacio y tiempo en la búsqueda del árbol del juego. Discuto en detalle aquí.
También existe este ingenioso truco de ‘deshacer’ un movimiento en el árbol. Puedes verlo a continuación.
¡Salud!