(Existem alguns desafios que exigem o uso da melhor estratégia, mas aqui não o fazemos. Mesmo se você conseguir vencer, poderá empatar)

Desafio

Escreva um programa que jogue o jogo da velha. Não deve perder (portanto, deve terminar o jogo com um empate ou ganhando).

Métodos de E / S permitidos

1. A entrada pode ser a placa atual. Você pode assumir que todos os movimentos anteriores do 2º jogador foram jogados pelo seu mecanismo.
2. A entrada pode ser a jogada do primeiro jogador, e sua função armazena as jogadas que ocorreram no passado. Nesse caso, a função é chamada várias vezes, uma vez para cada movimento; ou a entrada do prompt de função / programa várias vezes.
3. Você pode receber uma entrada extra dizendo se você é o primeiro jogador ou escrever duas funções (possivelmente relacionadas) para resolver o problema do primeiro jogador e o do segundo jogador. Se o seu programa precisar usar o método de entrada 2 (chamada múltipla), você poderá decidir o que será passado na primeira chamada.
4. A saída pode ser o quadro após o seu turno.
5. A saída pode ser sua jogada.
6. Uma movimentação pode ser representada como um par de números (pode ser indexação 0 ou 1), um número no intervalo de 0 a 8 ou um número no intervalo de 1 a 9.
7. A placa pode ser representada como uma matriz 3 × 3 ou uma matriz de comprimento 9. Mesmo se o idioma tiver uma matriz com indexação 0, você pode usar a indexação 1.
8. As células na rede pode usar quaisquer 3 valores diferentes para indicar X, Oe esvaziar.

Critérios de vitória

O código mais curto em cada idioma vence.

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

As posições no quadro são numeradas de 1 a 9. Por padrão, você obtém a primeira jogada, mas se quiser permitir que o computador seja a primeira, basta digitar 0 para a primeira jogada. Quando você faz uma mudança, o computador responde com um número indicando a mudança.

Não há verificações para garantir que você não insira uma jogada válida e também não há verificações para ver se alguém ganhou ou perdeu. Uma vez que não há mais movimentos a serem feitos, o programa entra em um loop infinito.

É um pouco difícil testar isso online, pois não há intérpretes online com entrada interativa. No entanto, se você souber quais movimentos você fará com antecedência (o que pressupõe que você saiba como o computador responderá), poderá testar o TIO com esses movimentos pré-programados.

O usuário joga primeiro: experimente online!
O computador toca primeiro: Experimente online!

Para facilitar a visualização do que está acontecendo, também tenho uma versão que mostra o quadro entre os movimentos.

O usuário joga primeiro: experimente online!
O computador é o primeiro a jogar: Experimente online!

Observe que você precisará aguardar o tempo limite do TIO para poder ver os resultados.

Explicação

A placa é armazenada na área de memória Befunge como uma matriz plana de 9 valores, indexada de 1 a 9. Isso nos permite usar o deslocamento de zero como um caso especial "sem movimento" quando queremos deixar o computador tocar primeiro. Os movimentos do jogador são armazenados como 4, e o computador se move como 5. Para começar com todas as posições, é inicializado em 32 (o padrão de memória Befunge); portanto, sempre que acessamos o quadro, modificamos com 8, então retornamos 0, 4 ou 5.

Dado esse arranjo, se somarmos os valores de quaisquer três posições no quadro, sabemos que o computador está a um passo de vencer se o total for 10, o jogador está a um passo de vencer se o total for 8 e o as posições são compartilhadas entre o computador e o player (mas ainda uma posição é gratuita) se o total for 9.

Toda a nossa estratégia é baseada nesse conceito. Temos uma rotina que faz uma lista de triplos indicando conjuntos de três posições no quadro, calculamos a soma dessas posições e, se a soma é igual a um determinado total, o computador se move para a posição que estiver livre no conjunto.

A lista principal de triplos que testamos são as combinações vencedoras (1/2/3, 1/5/9, 1/4/7, etc.). Primeiro, procuramos um total de 10 (o computador está prestes a vencer) e, em seguida, um total de 8 (o jogador está prestes a vencer e precisamos bloquear esse movimento). Menos obviamente, também verificamos um total de 9 (se o jogador e o computador tiverem uma das posições, é uma boa estratégia para o computador assumir a terceira).

Antes desse último cenário, a outra jogada estratégica que fazemos é verificar todos os conjuntos de cantos (1/2/4, 2/3/6 etc.), bem como duas combinações de cantos opostas (1/8/9 e 3 / 7/8). Se alguma dessas combinações for 8, ou seja, o jogador assumiu duas das posições, é uma boa estratégia para o computador assumir a posição livre restante.

Finalmente, existem dois movimentos especiais de caso. Primeiro, sempre tentamos tomar a posição central antes de qualquer outro movimento. Isso é conseguido com a mesma rotina de todos os nossos outros movimentos, passando apenas um triplo, 5/5/5 e uma soma-alvo de 0. Além disso, se todos os outros testes falharem em encontrar um movimento, tentamos um dos cantos superiores como último recurso. Novamente, isso é simplesmente conseguido testando as triplas 1/1/1 e 3/3/3, com uma soma alvo de 0.

Eu não acho que essa seja necessariamente uma estratégia perfeita - pode haver jogos desenhados pelo computador que poderiam ter sido vencidos - mas é bom o suficiente para nunca perder uma partida. Eu executei um script de teste que tentou executar todos os movimentos possíveis contra o computador e, para cada sequência válida de movimentos, o computador venceu ou empatou o jogo.

Python 2: 399 401 349 333 317 370 bytes

2x Correção de bug: crédito em l4m2

-52 caracteres: crédito para undergroundmonorail

-16 caracteres: crédito para Jonathan Frech

-26 caracteres: crédito para o usuário202729

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])

Experimente Online!

No primeiro dia de um curso de álgebra linear que fiz no semestre passado, meu astuto instrutor de pós-graduação propôs que, se você representa a placa do jogo da velha como matriz:

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

então, obter três em linha é equivalente a escolher três números no intervalo [1,9] que somam 15. Essa resposta explora essa idéia. A função pega uma lista contendo nove números que representam o quadro. 0 indica um espaço vazio, 1 é ocupado pelo oponente e 2 representa uma jogada anterior feita pelo programa. As três primeiras linhas descobrem quais números o programa selecionou (p), a oposição selecionou (o) e ainda estão disponíveis (a). Em seguida, ele examina os números disponíveis e vê se algum deles, combinado com dois números que já escolheu, somados a quinze. Se isso acontecer, ele escolherá o quadrado e vencerá. Se não houver jogadas vencedoras imediatas, ele verificará se o oponente pode ganhar usando o mesmo método. Se puderem, será o quadrado vencedor. Se não houver um movimento vencedor ou de bloqueio disponível, ele se moverá em um canto. Isso evita que os tolos acasalem:

- - - 
- X -
- - -

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

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

Se nenhuma dessas situações ocorrer, ele escolherá um quadrado arbitrariamente. A função gera um número [0,8] representando o quadrado indexado 0 escolhido pelo algoritmo.

Edit: O algoritmo agora prioriza o centro sobre a diagonal, o que impedirá outra possibilidade de acasalamento apontada por l4m2 e estratégias relacionadas.

Editar: para esclarecer, a função recebe uma placa na forma de uma matriz e gera um movimento como um número inteiro em [0,8]. Como essa estratégia de E / S é tão desajeitada, aqui está um script de wrapper que a torna mais interativa. É necessário um único argumento de linha de comando, que deve ser 1 se o jogador for o primeiro e 0 se o programa for o primeiro.

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