(Existen algunos desafíos que requieren usar la mejor estrategia, pero aquí no lo hacemos. Incluso si puede ganar, se le permite hacer un empate)

Desafío

Escribe un programa que juegue el juego tic-tac-toe. No debe perder (por lo tanto, debe terminar el juego con un empate o ganando).

Métodos de E / S permitidos

1. La entrada puede ser la placa actual. Puede suponer que todos los movimientos anteriores del segundo jugador fueron jugados por su motor.
2. La entrada puede ser los movimientos del primer jugador, y su función almacena qué movimientos ocurrieron en el pasado. En este caso, la función se llama varias veces, una para cada movimiento; o la entrada de solicitud de función / programa varias veces.
3. Se le permite tomar una entrada adicional que dice si es el primer jugador, o escribir dos funciones (posiblemente relacionadas) para resolver el problema del primer jugador y el del segundo jugador. Si su programa necesita usar el método de entrada 2 (llamada múltiple), puede decidir qué se pasa en la primera llamada.
4. La salida puede ser el tablero después de tu turno.
5. La salida puede ser su movimiento.
6. Un movimiento puede representarse como un par de números (puede ser indexación 0 o indexación 1), un número en el rango 0 ~ 8 o un número en el rango 1 ~ 9.
7. El tablero puede representarse como una matriz de 3 × 3, o una matriz de longitud 9. Incluso si el lenguaje tiene una matriz de indexación 0, puede usar la indexación 1.
8. Las células de la parrilla pueden utilizar cualquiera de los 3 valores diferentes para indicar X, Oy vacío.

Criterios ganadores

El código más corto en cada idioma gana.

Befunge, 181 168 bytes

>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

Las posiciones en el tablero están numeradas del 1 al 9. De forma predeterminada, obtienes el primer movimiento, pero si quieres permitir que la computadora vaya primero, puedes ingresar 0 para tu primer movimiento. Cuando haya realizado un movimiento, la computadora responderá con un número que indica su movimiento.

No hay controles para asegurarse de que no ingrese un movimiento válido, y tampoco hay controles para ver si alguien ha ganado o perdido. Una vez que no hay más movimientos por hacer, el programa simplemente entra en un bucle infinito.

Es un poco difícil probar esto en línea, ya que no hay intérpretes en línea con entrada interactiva. Sin embargo, si sabe de antemano qué movimientos va a hacer (lo que supone que sabe cómo va a responder la computadora), puede realizar una prueba en TIO con esos movimientos preprogramados.

El usuario juega primero: ¡ Pruébelo en línea!
La computadora juega primero: ¡ Pruébelo en línea!

Para que sea más fácil ver lo que está sucediendo, también tengo una versión que muestra el tablero entre movimientos.

El usuario juega primero: ¡ Pruébelo en línea!
La computadora juega primero: Pruébelo en línea!

Tenga en cuenta que tendrá que esperar a que TIO se agote antes de poder ver los resultados.

Explicación

El tablero se almacena en el área de memoria de Befunge como una matriz plana de 9 valores, indexados del 1 al 9. Esto nos permite usar el desplazamiento cero como un caso especial "sin movimiento" cuando queremos que la computadora juegue primero. Los movimientos del jugador se almacenan como 4, y la computadora se mueve como 5. Para comenzar, todas las posiciones se inicializan a 32 (el valor predeterminado de la memoria Befunge), por lo que cada vez que accedemos al tablero modificamos con 8, por lo que volveremos a 0, 4 o 5.

Dado ese arreglo, si sumamos los valores de cualquiera de las tres posiciones en el tablero, sabemos que la computadora está a un paso de ganar si el total es 10, el jugador está a un paso de ganar si el total es 8, y el las posiciones se comparten entre la computadora y el jugador (pero aún una posición es libre) si el total es 9.

Toda nuestra estrategia se basa en este concepto. Tenemos una rutina que toma una lista de triples que indican conjuntos de tres posiciones en el tablero, calculamos la suma de esas posiciones, y si la suma es igual a un cierto total, la computadora se mueve a cualquiera de las posiciones en el conjunto que esté libre.

La lista principal de triples que probamos son las combinaciones ganadoras (1/2/3, 1/5/9, 1/4/7, etc.). Primero buscamos un total de 10 (la computadora está a punto de ganar), y luego un total de 8 (el jugador está a punto de ganar y necesitamos bloquear ese movimiento). Menos obvio, también verificamos un total de 9 (si el jugador y la computadora tienen una de las posiciones, es una buena estrategia para que la computadora tome la tercera).

Antes de ese último escenario, el otro movimiento estratégico que hacemos es verificar todos los conjuntos de esquinas (1/2/4, 2/3/6, etc.), así como dos combinaciones de esquinas opuestas (1/8/9 y 3 / 7/8). Si alguna de estas combinaciones suma 8, es decir, el jugador ha tomado dos de las posiciones, es una buena estrategia para que la computadora tome la posición libre restante.

Finalmente, hay dos movimientos de casos especiales. Primero, siempre intentamos tomar la posición central antes de cualquier otro movimiento. Esto se logra con la misma rutina que todos nuestros otros movimientos, simplemente pasando un solo triple, 5/5/5 y una suma objetivo de 0. Además, si todas las otras pruebas no han podido encontrar un movimiento, intentamos tomar Una de las esquinas superiores como último recurso. Nuevamente, esto se logra simplemente probando los triples 1/1/1 y 3/3/3, con una suma objetivo de 0.

No creo que esta sea necesariamente una estrategia perfecta, puede haber juegos que dibuje la computadora que podrían haberse ganado, pero es lo suficientemente bueno como para nunca perder un partido. He ejecutado un script de prueba que trató de jugar todos los movimientos posibles contra la computadora, y para cada secuencia válida de movimientos, la computadora ganó o empató el juego.

Python 2: 399 401 349 333 317 370 bytes

2x corrección de errores: crédito a l4m2

-52 caracteres: crédito al metro subterráneo

-16 caracteres: crédito a Jonathan Frech

-26 caracteres: crédito para el usuario202729

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

Pruébalo en línea!

El primer día de un curso de álgebra lineal que tomé el semestre pasado, mi astuto instructor de posgrado me propuso que si representas el tablero de tres en raya como la matriz:

4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

luego obtener tres seguidos es equivalente a elegir tres números en el rango [1,9] que sumen 15. Esta respuesta explota esta idea. La función toma una lista que contiene nueve números que representan el tablero. 0 indica un espacio vacío, 1 está ocupado por el oponente y 2 representa una jugada previa realizada por el programa. Las primeras 3 líneas determinan qué números ha elegido el programa (p), la oposición ha elegido (o) y todavía están disponibles (a). Luego mira a través de los números disponibles y ve si alguno de ellos, combinado con dos números que ya ha elegido, suman quince. Si lo hace, elegirá esa casilla y ganará. Si no hay movimientos ganadores inmediatos, verificará si el oponente puede ganar usando el mismo método. Si pueden, tomará su casilla ganadora. Si no hay un movimiento ganador o de bloqueo disponible, Se moverá en una esquina. Esto evita que un tonto se mate:

- - - 
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Si ninguna de estas situaciones ocurre, elegirá un cuadrado arbitrariamente. La función genera un número [0,8] que representa el cuadrado indexado 0 elegido por el algoritmo.

Editar: El algoritmo ahora prioriza el centro sobre la diagonal, lo que evitará otra posibilidad de mate de tontos señalada por l4m2 y estrategias relacionadas.

Editar: Para aclarar, la función toma un tablero en forma de matriz y genera un movimiento como un entero en [0,8]. Debido a que esta estrategia de E / S es tan torpe, aquí hay un script de envoltura que lo hace más interactivo. Se necesita un argumento de línea de comando único, que debería ser 1 si el jugador va primero y 0 si el programa va primero.

import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2