Perca no jogo da velha

Escreva um programa que a jogue Misère tic-tac-toe. Ou seja, o objetivo é forçar seu oponente a levar três seguidos.

Aceite na entrada padrão um 'X' ou um 'O' (a letra, não zero), para determinar de que lado o programa estará tocando. Em seguida, imprima um único dígito para a sua jogada no seu turno e leia um único dígito no turno do seu oponente até o jogo terminar (X sempre acontece primeiro). Depois que um vencedor é decidido, imprima X ou O para quem ganhou ou D para um empate. Por exemplo, se O obtiver 3 em sequência, X vence.

Suponha que o quadro esteja numerado da seguinte maneira:

0|1|2
-----
3|4|5
-----
6|7|8

Idealmente, uma solução será ótima e nunca perderá. Como jogo da velha, jogo perfeito deve sempre resultar em empate. Se o protocolo acima for respeitado, posso testar os envios automaticamente em relação a uma variedade de estratégias possíveis.

O vencedor é o código mais curto. pontos de bônus se escolher aleatoriamente movimentos igualmente bons para torná-lo um pouco mais imprevisível.

Python, 383 caracteres

M=[21,1344,86016,4161,16644,66576,65793,4368]
X=lambda B,k:any(m*k==B&m*3for m in M)
def S(B):
 if X(B,2):return 1,
 M=[i for i in range(0,18,2)if B>>i&3<2]
 return max((-S((B|3<<i)^87381)[0],i)for i in M)if M else(0,)
r='D'
c=ord(raw_input())&1
B=0
for i in range(9):
 if i&1==c:m=S(B^c*87381)[1];print m/2;B|=3-c<<m
 else:
  B|=2+c<<input()*2
  if X(B,2+c):r='XO'[c];break
print r

A placa Bé representada como um número inteiro usando dois bits por quadrado, com 00e 01representando vazio, 10representando O e 11representando X. Mé um conjunto de máscaras de bits com 01pontos de triplo perdedor ( 21= 0b010101= a linha superior etc.) Xcalcula se houver perda triple for kestá presente em um quadro. So minimax procura uma jogada ideal para X, retornando um par de pontos (1 = vitória, -1 = derrota, 0 = empate) e um índice quadrado. ^87381(= ^0b010101010101010101) vira X e O enquanto deixa os quadrados vazios inalterados.

O computador nunca perde, então não precisei incluir essa verificação :).

Provavelmente existe um algoritmo mais fácil / mais curto baseado em regras, mas isso funciona.