[关闭]
@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大胜。

  1. #coding=utf-8
  2. #敌方为-1,我方为1,无子为0
  3. #参数chess为棋盘数组,参数camp为1(我方)或-1(敌方)
  4. #可以使用PlayGame函数开始游戏~
  5. #游戏是否结束?返回值:-1,0,1,2,输,平,赢,未结束
  6. def CheckEnd(chess):
  7. for i in range(3):
  8. if chess[3*i]==chess[3*i+1]==chess[3*i+2] and chess[3*i]!=0:
  9. return chess[3*i]
  10. elif chess[i]==chess[3+i]==chess[6+i] and chess[i]!=0:
  11. return chess[i]
  12. if chess[0]==chess[4]==chess[8] and chess[0]!=0:
  13. return chess[0]
  14. elif chess[2]==chess[4]==chess[6] and chess[2]!=0:
  15. return chess[2]
  16. for i in range(9):
  17. if chess[i]==0:
  18. return 2
  19. return 0
  20. #是否能直接胜利?如果可以,返回落子位置,否则返回-1
  21. def ToWin(chess,camp):
  22. for i in range(3):
  23. if chess[3*i]==0 and chess[3*i+1]+chess[3*i+2]==2*camp:
  24. return 3*i
  25. elif chess[3*i+1]==0 and chess[3*i]+chess[3*i+2]==2*camp:
  26. return 3*i+1
  27. elif chess[3*i+2]==0 and chess[3*i]+chess[3*i+1]==2*camp:
  28. return 3*i+2
  29. elif chess[i]==0 and chess[i+3]+chess[i+6]==2*camp:
  30. return i
  31. elif chess[i+3]==0 and chess[i]+chess[i+6]==2*camp:
  32. return i+3
  33. elif chess[i+6]==0 and chess[i+3]+chess[i]==2*camp:
  34. return i+6
  35. if chess[0]==0 and chess[4]+chess[8]==2*camp:
  36. return 0
  37. elif chess[4]==0 and chess[0]+chess[8]==2*camp:
  38. return 4
  39. elif chess[8]==0 and chess[0]+chess[4]==2*camp:
  40. return 8
  41. elif chess[2]==0 and chess[4]+chess[6]==2*camp:
  42. return 2
  43. elif chess[4]==0 and chess[2]+chess[6]==2*camp:
  44. return 4
  45. elif chess[6]==0 and chess[2]+chess[4]==2*camp:
  46. return 6
  47. else:
  48. return -1
  49. #处理特殊情况,如下图,X不能走角位置,否则会输
  50. # O _ _
  51. # _ X _
  52. # _ _ O
  53. def ToSpecial(chess):
  54. 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):
  55. return 1
  56. return -1
  57. #能否走成2-2连棋?如果可以,返回落子位置,否则返回-1
  58. def ToDouble(chess,camp):
  59. chess=chess[:]
  60. for i in range(9):
  61. if chess[i]==0:
  62. chess[i]=camp
  63. position=ToWin(chess,camp)
  64. if position!=-1:
  65. chess[position]=-camp
  66. if ToWin(chess,camp)!=-1:
  67. return i
  68. chess[position]=0
  69. chess[i]=0
  70. return -1
  71. #作出决定,返回值为落子位置,若无位置可下则返回-1
  72. def MakeChoice(chess):
  73. n=ToWin(chess,1)
  74. if n!=-1:
  75. return n
  76. n=ToWin(chess,-1)
  77. if n!=-1:
  78. return n
  79. n=ToSpecial(chess)
  80. if n!=-1:
  81. return n
  82. n=ToDouble(chess,1)
  83. if n!=-1:
  84. return n
  85. n=ToDouble(chess,-1)
  86. if n!=-1:
  87. return n
  88. to_choose=(4,0,2,6,8,1,3,5,7) #按中心>角>棱的优先级随便走
  89. for i in to_choose:
  90. if chess[i]==0:
  91. return i
  92. return -1
  93. #输出棋盘
  94. def Output(chess):
  95. print('┏━┳━┳━┓')
  96. for i in range(3):
  97. out="┃"
  98. for j in range(3):
  99. if chess[3*i+j]==-1:
  100. out+='╳'
  101. elif chess[3*i+j]==0:
  102. out+=str(3*i+j)+' '
  103. else:
  104. out+='●'
  105. out+='┃'
  106. print(out)
  107. if i<2:
  108. print('┣━╋━╋━┫')
  109. else:
  110. print('┗━┻━┻━┛')
  111. #开始游戏,我方即AI,敌方即玩家
  112. def PlayGame():
  113. n=0
  114. flag=0
  115. while(1):
  116. n+=1
  117. state=2
  118. chess=[0,0,0,0,n%2,0,0,0,0]
  119. print("Let's have fun!")
  120. while(1):
  121. Output(chess)
  122. print('It\'s your turn. Please input a number between 0 and 8:')
  123. s=input()
  124. try:
  125. i=int(s)
  126. if i<0 or i>8 or chess[i]!=0:
  127. raise
  128. except:
  129. flag=1
  130. break
  131. chess[i]=-1
  132. state=CheckEnd(chess)
  133. if state==2:
  134. i=MakeChoice(chess)
  135. chess[i]=1
  136. state=CheckEnd(chess)
  137. if state==1:
  138. print("You lose!")
  139. break
  140. elif state==0:
  141. print("Nobody win!")
  142. break
  143. elif state==-1:
  144. print("You win!")
  145. break
  146. if flag==1:
  147. break
  148. print()

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

  1. #coding=utf-8
  2. #使用了AI里面的函数,在这里没有写出来,见上面
  3. from zio import *
  4. import re
  5. #通过字符串读入棋盘数组,role=1代表我方为'O',为-1代表我方为'X'
  6. def readChess(io,role):
  7. chess=[0,0,0,0,0,0,0,0,0]
  8. for i in range(3):
  9. s=io.readline()
  10. ss=s.split('|')
  11. for j in range(3):
  12. if ss[j].find('O')!=-1:
  13. chess[3*i+j]=role
  14. elif ss[j].find('X')!=-1:
  15. chess[3*i+j]=-role
  16. io.readline()
  17. return chess
  18. #第一次棋盘发回来的时候,如果是空的,那么我们是先手'X',否则我们是后手'O'
  19. def checkRole(chess):
  20. for i in range(9):
  21. if chess[i]!=0:
  22. return 1
  23. return -1
  24. target=('95.213.237.91',45679)
  25. io=zio(target,print_read=False,print_write=False,timeout=9999999)
  26. io.readline()
  27. io.readline()
  28. io.writeline('fmyl') #Input your name
  29. io.read_until('Round') #Round number 1.
  30. count=0
  31. while(1):
  32. count+=1
  33. print(io.readline()) #Round number X
  34. io.readline() #当前比分啊啥的
  35. flag=0 #flag检测现在是不是本局第一次下,如果是则要判断我们是哪一方
  36. role=1
  37. while(1):
  38. flag+=1
  39. chess=readChess(io,role)
  40. if flag==1:
  41. role=checkRole(chess)
  42. if CheckEnd(chess)!=2: #CheckEnd是AI里面的函数,判断游戏状态(为2表示未结束)
  43. break
  44. m=MakeChoice(chess) #MakeChoice是AI里面的函数,根据当前棋况决定落子位置
  45. chess[m]=1
  46. io.writeline(str(m)) #下棋
  47. if CheckEnd(chess)!=2:
  48. break
  49. if count==500: #500局之后不再游戏
  50. break
  51. print(io.read_until(EOF)) #输出Flag
  52. io.interact()
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注