Perdre au tic-tac-toe

Écrivez un programme qui va jouer une partie de Misère tic-tac-toe. Autrement dit, l'objectif est de forcer votre adversaire à en prendre trois d'affilée.

Acceptez sur l'entrée standard un «X» ou un «O» (la lettre, pas zéro), pour déterminer de quel côté le programme sera joué. Puis sortez un seul chiffre pour votre mouvement à votre tour, et lisez un seul chiffre sur le tour de vos adversaires jusqu'à la fin du jeu (X va toujours en premier). Une fois qu'un gagnant est décidé, affichez X ou O pour celui qui a gagné, ou D pour un match nul. Par exemple, si O obtient 3 d'affilée, X gagne.

Supposons que le tableau soit numéroté comme suit:

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

Idéalement, une solution sera optimale et ne perdra jamais. Comme le tic-tac-toe, un jeu parfait devrait toujours entraîner un match nul. Si le protocole ci-dessus est respecté, je peux tester automatiquement les soumissions par rapport à une variété de stratégies possibles.

Le gagnant est le code le plus court. des points bonus s'il choisit au hasard parmi des mouvements tout aussi bons pour le rendre un peu plus imprévisible.

Python, 383 caractères

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

La carte Best représentée comme un entier en utilisant deux bits par carré, avec 00et 01représentant vide, 10représentant O et 11représentant X. Mest un ensemble de masques de bit avec 01dans les taches d'un triple perdant ( 21= 0b010101= la ligne du haut, etc.) Xcalcule s'il y a une perte triple pour kest présent sur une planche. Sest-ce que minimax recherche un mouvement optimal pour X, renvoyant une paire du score (1 = gagnant, -1 = perdant, 0 = nul) et un index carré. ^87381(= ^0b010101010101010101) retourne X et O tout en laissant les cases vides inchangées.

L'ordinateur ne perd jamais, donc je n'avais pas besoin d'inclure cette vérification :).

Il existe probablement un algorithme basé sur des règles plus facile / plus court, mais cela fonctionne.