Tic-Tac-Toe (VolgaCTF 2016)

算法

Tic-Tac-Toe An important step towards the strong AI is the ability of an artificial agent to solve a well-defined problem. A project by the name 'tic-tac-toe' was one of such test problems. It's still up... nc tic-tac-toe.2016.volgactf.ru 45679

Tic-Tac-Toe就是小时候玩过的井字棋游戏。用nc连上去后，服务器会和你玩游戏。它每次走一步后传回来一个棋盘，然后你输入一个编号（0~8，分别代表9个格子，表示你要在某个格子上走棋），这样就可以进行游戏了。每局胜利者获得1分，失败者不得分，平局则双方各得0.5分。进行500局后若我们得分多就能拿到Flag。

500局手动不现实，就要写AI实现。Tic-Tac-Toe的AI是比较容易写的。这样的AI可能不是最强，但击败服务器AI是绰绰有余了。最后得分是456:44大胜。

#coding=utf-8
#敌方为-1，我方为1，无子为0
#参数chess为棋盘数组，参数camp为1（我方）或-1（敌方）
#可以使用PlayGame函数开始游戏~
#游戏是否结束？返回值：-1,0,1,2，输,平,赢,未结束
def CheckEnd(chess):
    for i in range(3):
        if chess[3*i]==chess[3*i+1]==chess[3*i+2] and chess[3*i]!=0:
            return chess[3*i]
        elif chess[i]==chess[3+i]==chess[6+i] and chess[i]!=0:
            return chess[i]
    if chess[0]==chess[4]==chess[8] and chess[0]!=0:
        return chess[0]
    elif chess[2]==chess[4]==chess[6] and chess[2]!=0:
        return chess[2]
    for i in range(9):
        if chess[i]==0:
            return 2
    return 0
#是否能直接胜利？如果可以，返回落子位置，否则返回-1
def ToWin(chess,camp):
    for i in range(3):
        if chess[3*i]==0 and chess[3*i+1]+chess[3*i+2]==2*camp:
            return 3*i
        elif chess[3*i+1]==0 and chess[3*i]+chess[3*i+2]==2*camp:
            return 3*i+1
        elif chess[3*i+2]==0 and chess[3*i]+chess[3*i+1]==2*camp:
            return 3*i+2
        elif chess[i]==0 and chess[i+3]+chess[i+6]==2*camp:
            return i
        elif chess[i+3]==0 and chess[i]+chess[i+6]==2*camp:
            return i+3
        elif chess[i+6]==0 and chess[i+3]+chess[i]==2*camp:
            return i+6
    if chess[0]==0 and chess[4]+chess[8]==2*camp:
        return 0
    elif chess[4]==0 and chess[0]+chess[8]==2*camp:
        return 4
    elif chess[8]==0 and chess[0]+chess[4]==2*camp:
        return 8
    elif chess[2]==0 and chess[4]+chess[6]==2*camp:
        return 2
    elif chess[4]==0 and chess[2]+chess[6]==2*camp:
        return 4    
    elif chess[6]==0 and chess[2]+chess[4]==2*camp:
        return 6
    else:
        return -1
#处理特殊情况，如下图，X不能走角位置，否则会输
#  O _ _
#  _ X _
#  _ _ O
def ToSpecial(chess):
    if chess[1]==chess[3]==chess[5]==chess[7]==0 and chess[4]==1 and (chess[0]+chess[8]==-2 or chess[2]+chess[6]==-2):
        return 1
    return -1
#能否走成2-2连棋？如果可以，返回落子位置，否则返回-1
def ToDouble(chess,camp):
    chess=chess[:]
    for i in range(9):
        if chess[i]==0:
            chess[i]=camp
            position=ToWin(chess,camp)
            if position!=-1:
                chess[position]=-camp
                if ToWin(chess,camp)!=-1:
                    return i
                chess[position]=0
            chess[i]=0
    return -1
#作出决定，返回值为落子位置，若无位置可下则返回-1
def MakeChoice(chess):
    n=ToWin(chess,1)
    if n!=-1:
        return n
    n=ToWin(chess,-1)
    if n!=-1:
        return n
    n=ToSpecial(chess)
    if n!=-1:
        return n
    n=ToDouble(chess,1)
    if n!=-1:
        return n
    n=ToDouble(chess,-1)
    if n!=-1:
        return n
    to_choose=(4,0,2,6,8,1,3,5,7)   #按中心>角>棱的优先级随便走
    for i in to_choose:
        if chess[i]==0:
            return i
    return -1
#输出棋盘
def Output(chess):
    print('┏━┳━┳━┓')
    for i in range(3):
        out="┃"
        for j in range(3):
            if chess[3*i+j]==-1:
                out+='╳'
            elif chess[3*i+j]==0:
                out+=str(3*i+j)+' '
            else:
                out+='●'
            out+='┃'
        print(out)
        if i<2:
            print('┣━╋━╋━┫')
        else:
            print('┗━┻━┻━┛')
#开始游戏，我方即AI，敌方即玩家
def PlayGame():
    n=0
    flag=0
    while(1):
        n+=1
        state=2
        chess=[0,0,0,0,n%2,0,0,0,0]
        print("Let's have fun!")
        while(1):
            Output(chess)
            print('It\'s your turn. Please input a number between 0 and 8:')
            s=input()
            try:
                i=int(s)
                if i<0 or i>8 or chess[i]!=0:
                    raise
            except:
                flag=1
                break
            chess[i]=-1
            state=CheckEnd(chess)
            if state==2:
                i=MakeChoice(chess)
                chess[i]=1
                state=CheckEnd(chess)
            if state==1:
                print("You lose!")
                break
            elif state==0:
                print("Nobody win!")
                break
            elif state==-1:
                print("You win!")
                break
        if flag==1:
            break
        print()

这次顺便学习了一下Python的zio库的使用方法。有一个坑要注意一下，每局先动的可能是玩家也可能不是（是随机还是轮流我没注意），但总是先走的为'X'，后走的为'O'，所以还要写个代码确认一下自己是哪一方。

#coding=utf-8
#使用了AI里面的函数，在这里没有写出来，见上面
from zio import *
import re
#通过字符串读入棋盘数组，role=1代表我方为'O'，为-1代表我方为'X'
def readChess(io,role):
    chess=[0,0,0,0,0,0,0,0,0]
    for i in range(3):
        s=io.readline()
        ss=s.split('|')
        for j in range(3):
            if ss[j].find('O')!=-1:
                chess[3*i+j]=role
            elif ss[j].find('X')!=-1:
                chess[3*i+j]=-role
        io.readline()
    return chess
#第一次棋盘发回来的时候，如果是空的，那么我们是先手'X'，否则我们是后手'O'
def checkRole(chess):
    for i in range(9):
        if chess[i]!=0:
            return 1
    return -1
target=('95.213.237.91',45679)
io=zio(target,print_read=False,print_write=False,timeout=9999999)
io.readline()
io.readline()
io.writeline('fmyl')    #Input your name
io.read_until('Round')  #Round number 1.
count=0
while(1):
    count+=1
    print(io.readline())    #Round number X
    io.readline()   #当前比分啊啥的
    flag=0      #flag检测现在是不是本局第一次下，如果是则要判断我们是哪一方
    role=1
    while(1):
        flag+=1
        chess=readChess(io,role)
        if flag==1:
            role=checkRole(chess)
        if CheckEnd(chess)!=2:  #CheckEnd是AI里面的函数，判断游戏状态（为2表示未结束）
            break
        m=MakeChoice(chess) #MakeChoice是AI里面的函数，根据当前棋况决定落子位置
        chess[m]=1
        io.writeline(str(m))    #下棋
        if CheckEnd(chess)!=2:
            break
    if count==500:          #500局之后不再游戏
        break
print(io.read_until(EOF))   #输出Flag
io.interact()