Stracić w kółko i krzyżyk

Napisz program, w który zagrasz w Misère kółko i krzyżyk. Oznacza to, że celem jest zmuszenie przeciwnika do wzięcia trzech z rzędu.

Zaakceptuj na standardowym wejściu albo „X”, albo „O” (litera, a nie zero), aby ustalić, po której stronie będzie grał program. Następnie wypisz jedną cyfrę na swój ruch podczas swojej tury i czytaj jedną cyfrę na swojej turie przeciwników, aż gra się skończy (X zawsze idzie pierwszy). Po rozstrzygnięciu zwycięzcy wypisz X lub O dla wygranej lub D dla remisu. Na przykład, jeśli O otrzyma 3 z rzędu, X wygrywa.

Załóżmy, że plansza jest ponumerowana w następujący sposób:

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

Idealnie rozwiązanie będzie optymalne i nigdy nie straci. Podobnie jak w kółko i krzyżyk, idealna gra powinna zawsze kończyć się remisem. Jeśli powyższy protokół jest przestrzegany, mogę automatycznie testować zgłoszenia pod kątem różnych możliwych strategii.

Zwycięzca jest najkrótszym kodem. punkty bonusowe, jeśli wybierze losowo z równie dobrych ruchów, aby uczynić go nieco bardziej nieprzewidywalnym.

Python, 383 znaków

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

Tablica Bjest reprezentowana jako liczba całkowita wykorzystująca dwa bity na kwadrat, z 00i 01reprezentująca pustą, 10reprezentująca O i 11reprezentująca X. Mjest zbiorem masek bitowych z 01miejscami potrójnego przegranego ( 21= 0b010101= górny rząd itp.) XOblicza, jeśli jakieś przegrane triple for kjest obecny na planszy. Srobi minimax w poszukiwaniu optymalnego ruchu dla X, zwracając parę wyniku (1 = wygrana, -1 = przegrana, 0 = remis) i indeks kwadratowy. ^87381(= ^0b010101010101010101) odwraca X i O, pozostawiając puste kwadraty bez zmian.

Komputer nigdy nie przegrywa, więc nie musiałem dołączać tego czeku :).

Istnieje prawdopodobnie łatwiejszy / krótszy algorytm oparty na regułach, ale to działa.