``````def win(s):
n = len(s)
if n < 3:
return False
s = sorted(s)
for i in range(n - 2):
l = i + 1
r = n - 1
while l < r:
total = s[i] + s[l] + s[r]
if total == 15:
return True
elif total < 15:
l = l + 1
else:
r = r - 1
return False
``````

``````WIN = 10
INF = 1000

# Luo Shu magic square
MAGIC_SQUARE = [4, 9, 2,
3, 5, 7,
8, 1, 6]

def eval(x, o):
if win(x):
return WIN
if win(o):
return -WIN
return 0

def finished(x, o):
return len(x) + len(o) == 9
``````

``````def findbest(x, o, maximize):
best = -INF if maximize else INF
move = 0
for i in MAGIC_SQUARE:
if (i not in x) and (i not in o):
if maximize:
val = minmax([i] + x, o, 0, not maximize)
if val > best:
best = val
move = i
else:
val = minmax(x, [i] + o, 0, not maximize)
if val < best:
best = val
move = i
return move
``````

min-max是一个递归搜索的过程，为了尽快获胜，我们在评分上加上对向前探索步数的考虑。如果是正方，就从评分中减去递归深度，而对于反方，则加上递归深度。

``````def minmax(x, o, depth, maximize):
score = eval(x, o)
if score == WIN:
return score - depth
if score == -WIN:
return score + depth
if finished(x, o):
return 0  # draw
best = -INF if maximize else INF
for i in MAGIC_SQUARE:
if (i not in x) and (i not in o):
if maximize:
best = max(best, minmax([i] + x, o, depth + 1, not maximize))
else:
best = min(best, minmax(x, [i] + o, depth + 1, not maximize))
return best
``````

``````def board(x, o):
for r in range(3):
print("-------")
for c in range(3):
p = MAGIC_SQUARE[r*3 + c]
if p in x:
print("|X", end="")
elif p in o:
print("|O", end="")
else:
print("| ", end="")
print("|")
print("-------")

def play():
x = []
o = []
while not (win(x) or win(o) or finished(x, o)):
board(x, o)
while True:
i = int(input("[1..9]==>"))
if i not in MAGIC_SQUARE or MAGIC_SQUARE[i-1] in x or MAGIC_SQUARE[i-1] in o:
print("invalid move")
else:
x = [MAGIC_SQUARE[i-1]] + x
break
o = [findbest(x, o, False)] + o
board(x, o)
``````