Algoritmo óptimo de Tic Tac Toe sin búsqueda anticipada

Question

¿Hay cualquier algoritmo para tic tac dedo del pie que no se basa en un algoritmo de búsqueda anticipada que es perfecto para cualquier tamaño juntas?

Edit: Para las placas más grandes que $3 \times 3$, tenemos que encontrar la mejor jugada en una fila donde $k$ y tenemos un tablero de $k < n$ $n \times n$.

Answer 1

Para un $4 \times 4$ junta o más, el jugador 2 puede forzar un empate (que es el mejor que te puede pasar si el jugador 1 es jugar de manera óptima por primera jugando en las dos diagonales (o el centro si el tamaño del tablero es impar y el centro no se toma) y, a continuación, siempre jugando en una fila o columna donde el jugador 1 tiene la mayoría de las plazas tomadas y el jugador 2 no ha jugado todavía. La única manera de que el jugador 1 puede ganar es por tener dos líneas de cada uno de los cuales se completa excepto por una plaza vacía (donde la plaza vacía, no es compartida). Pero el mayor número de plazas, el jugador 1 puede tomar en una determinada línea sin jugador 2 tomar una plaza en la línea 3, que se puede demostrar por inducción, señalando que nunca es posible para el jugador 1 para hacer un movimiento que crea 2 líneas con 3 plazas (suponiendo que el jugador 2 la estrategia).