@Aqua-Dream 2016-10-19T01:34:40.000000Z 字数 4206 阅读 1290

# 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#是否能直接胜利？如果可以，返回落子位置，否则返回-1def 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 _#  _ _ Odef 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连棋？如果可以，返回落子位置，否则返回-1def 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#作出决定，返回值为落子位置，若无位置可下则返回-1def 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()

#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 -1target=('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 nameio.read_until('Round')  #Round number 1.count=0while(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局之后不再游戏        breakprint(io.read_until(EOF))   #输出Flagio.interact()

• 私有
• 公开
• 删除