17
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Sneaky sneaky bitwise witchcraft +1 \$\endgroup\$ – Rohan Jhunjhunwala Sep 24 '16 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.