Lose at tic-tac-toe

Question

Write a program that a will play a game of Misère tic-tac-toe. That is, the goal is to force your opponent to take three in a row.

Accept on standard input either an 'X' or an 'O'(the letter, not zero), to determine which side the program will be playing as. Then output a single digit for your move on your turn, and read a single digit on your opponents turn until the game is over (X always goes first). Once a winner is decided, output X or O for who won, or D for a draw. For example, if O gets 3 in a row, X wins.

Assume the board is numbered like so:

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

Ideally a solution will be optimal and never lose. Like tic-tac-toe, perfect play should always result in a draw. If the above protocol is adhered to, I can test submissions automatically against a variety of possible strategies.

Winner is shortest code. bonus points if it picks randomly from equally good moves to make it a bit more unpredictable.

Answer 1

Python, 383 chars

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

The board B is represented as an integer using two bits per square, with 00 and 01 representing empty, 10 representing O and 11 representing X. M is a set of bitmasks with 01 in the spots of a losing triple (21 = 0b010101 = the top row etc.) X computes if any losing triple for k is present on a board. S does minimax search for an optimal move for X, returning a pair of the score (1=win, -1=lose, 0=draw) and a square index. ^87381 (=^0b010101010101010101) flips X and O while leaving empty squares unchanged.

The computer never loses, so I didn't need to include that check :) .

There is probably an easier/shorter rule-based algorithm out there, but this works.