人机对战初体验—四子棋游戏
继去年3月人机大战引发全球瞩目以来，围棋AI（人工智能）再度引发跨领域的关注：一个叫Master的围棋AI，几天时间，面对中日韩顶尖职业围棋选手，已取得60胜0败的恐怖战绩，展现出的围棋技艺已经到了人类理解不了的程度。这可以视为人工智能在围棋领域的一次“大征服”，而在此之外的意义则是，告诉了我们人工智能在征服一项领域或职业时，究竟速度有多快。理解这一点，对于人类，乃至每一个人，都非常重要。通过本实验的学习，可以对人机对战有初步了解。
一、实验介绍
1.1 实验内容
实验利用Python模拟AI和玩家进行四子棋游戏，利用游戏实验Pygame库，为游戏提供界面和操作支持。AI算法借用蒙特卡洛搜索树思想。通过设置AI的难度系数，即AI所能考虑到的未来棋子的可能走向，从而选择出最佳的方案和玩家对抗。难度系数越大，AI搜索范围越广，它所能做出的决定越明智。
游戏最终效果截图：
1.2 实验知识点
Pygame的基础操作蒙特卡洛搜索树1.3 实验环境
Python2.7gedit1.4 适合人群
本课程难度一般，属于初级课程，适合具有Python基础并对Pygame有所了解的用户学习。
1.5 代码获取
你可以通过下面命令将代码下载到实验楼环境中，作为参照对比进行学习。
$ wget http://labfile./courses/746/fourinrow.py
二、四子棋游戏
四子棋游戏是在7*6的格子中。轮流从格子最上方落下棋子。棋子会落在该列格子中最下面的空格子里。先将四个棋子连成一条线（水平直线，竖直直线，或倾斜直线）者获胜，游戏结束。
三、项目文件结构
四、实验步骤
4.1 开发准备
在Code目录下进行创建工程文件Fourinrow，在终端执行命令
cd Code && mkdir Fourinrow
下载本次实验所需的图片资源到Fourinrow文件下
$ cd Fourinrow$ wget http://labfile./courses/746/images.zip$ unzip images.zip
安装依赖包
$ sudo apt-get update$ sudo apt-get install python-pygame
4.2 游戏流程
4.3 初始化变量
用到的变量包括，棋盘的宽度，长度（可以修改，设计不同规格的棋盘），难度系数，棋子大小以及一些设计坐标变量的设定。
在FourinRow.py文件中输入如下代码：
import random, copy, sys, pygamefrom pygame.locals import *BOARDWIDTH = 7 # 棋子盘的宽度栏数BOARDHEIGHT = 6 # 棋子盘的高度栏数assert BOARDWIDTH >= 4 and BOARDHEIGHT >= 4, 'Board must be at least 4x4.'#python assert断言是声明其布尔值必须为真的判定，如果发生异常就说明表达示为假。#可以理解assert断言语句为raise-if-not，用来测试表示式，其返回值为假，就会触发异常。DIFFICULTY = 2 # 难度系数，计算机能够考虑的移动级别#这里2表示，考虑对手走棋的7种可能性及如何应对对手的7种走法SPACESIZE = 50 # 棋子的大小FPS = 30 # 屏幕的更新频率，即30/sWINDOWWIDTH = 640 # 游戏屏幕的宽度像素WINDOWHEIGHT = 480 # 游戏屏幕的高度像素XMARGIN = int((WINDOWWIDTH - BOARDWIDTH * SPACESIZE) / 2)#X边缘坐标量，即格子栏的最左边YMARGIN = int((WINDOWHEIGHT - BOARDHEIGHT * SPACESIZE) / 2)#Y边缘坐标量，即格子栏的最上边BRIGHTBLUE = (0, 50, 255)#蓝色WHITE = (255, 255, 255)#白色BGCOLOR = BRIGHTBLUETEXTCOLOR = WHITERED = 'red'BLACK = 'black'EMPTY = NoneHUMAN = 'human'COMPUTER = 'computer'
除此之外我们还需要定义一些pygame的全局变量。这些全局变量在之后的各个模块中会被多次调用。其中很多是存储载入图片的变量，准备工作有点长，请大家耐心一点哦。
#初始化pygame的各个模块pygame.init()#初始化了一个Clock对象FPSCLOCK = pygame.time.Clock()#创建游戏窗口DISPLAYSURF = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT))#游戏窗口标题pygame.display.set_caption(u'four in row')#Rect(left,top,width,height)用来定义位置和宽高REDPILERECT = pygame.Rect(int(SPACESIZE / 2), WINDOWHEIGHT - int(3 * SPACESIZE / 2), SPACESIZE, SPACESIZE)#这里创建的是窗口中左下角和右下角的棋子BLACKPILERECT = pygame.Rect(WINDOWWIDTH - int(3 * SPACESIZE / 2), WINDOWHEIGHT - int(3 * SPACESIZE / 2), SPACESIZE, SPACESIZE)#载入红色棋子图片REDTOKENIMG = pygame.image.load('4row_red.png')#将红色棋子图片缩放为SPACESIZEREDTOKENIMG = pygame.transform.smoothscale(REDTOKENIMG, (SPACESIZE, SPACESIZE))#载入黑色棋子图片BLACKTOKENIMG = pygame.image.load('4row_black.png')#将黑色棋子图片缩放为SPACESIZEBLACKTOKENIMG = pygame.transform.smoothscale(BLACKTOKENIMG, (SPACESIZE, SPACESIZE))#载入棋子面板图片BOARDIMG = pygame.image.load('4row_board.png')#将棋子面板图片缩放为SPACESIZEBOARDIMG = pygame.transform.smoothscale(BOARDIMG, (SPACESIZE, SPACESIZE))#载入人胜利时图片HUMANWINNERIMG = pygame.image.load('4row_humanwinner.png')#载入AI胜时图片COMPUTERWINNERIMG = pygame.image.load('4row_computerwinner.png')#载入平局提示图片TIEWINNERIMG = pygame.image.load('4row_tie.png')#返回一个Rect实例WINNERRECT = HUMANWINNERIMG.get_rect()#游戏窗口中间位置坐标WINNERRECT.center = (int(WINDOWWIDTH / 2), int(WINDOWHEIGHT / 2))#载入操作提示图片ARROWIMG = pygame.image.load('4row_arrow.png')#返回一个Rect实例ARROWRECT = ARROWIMG.get_rect()#操作提示的左位置ARROWRECT.left = REDPILERECT.right + 10 #将操作提示与下方红色棋子实例在纵向对齐ARROWRECT.centery = REDPILERECT.centery
至此我们完成了前期的准备工作。
4.4 棋盘设计
初始时，将棋盘二维列表清空，然后根据玩家和AI的走法将棋盘相应位置设定颜色。
def drawBoard(board, extraToken=None):#DISPLAYSURF 是我们的界面，在初始化变量模块中有定义DISPLAYSURF.fill(BGCOLOR)#将游戏窗口背景色填充为蓝色spaceRect = pygame.Rect(0, 0, SPACESIZE, SPACESIZE)#创建Rect实例for x in range(BOARDWIDTH):#确定每一列中每一行中的格子的左上角的位置坐标for y in range(BOARDHEIGHT):spaceRect.topleft = (XMARGIN + (x * SPACESIZE), YMARGIN + (y * SPACESIZE))#x =0,y =0时，即第一列第一行的格子。if board[x][y] == RED:#如果格子值为红色#则在在游戏窗口的spaceRect中画红色棋子DISPLAYSURF.blit(REDTOKENIMG, spaceRect)elif board[x][y] == BLACK: #否则画黑色棋子DISPLAYSURF.blit(BLACKTOKENIMG, spaceRect)# extraToken 是包含了位置信息和颜色信息的变量# 用来显示指定的棋子if extraToken != None:if extraToken['color'] == RED:DISPLAYSURF.blit(REDTOKENIMG,(extraToken['x'],extraToken['y'], SPACESIZE, SPACESIZE))elif extraToken['color'] == BLACK:DISPLAYSURF.blit(BLACKTOKENIMG, (extraToken['x'], extraToken['y'], SPACESIZE, SPACESIZE))# 画棋子面板for x in range(BOARDWIDTH):for y in range(BOARDHEIGHT):spaceRect.topleft = (XMARGIN + (x * SPACESIZE), YMARGIN + (y * SPACESIZE))DISPLAYSURF.blit(BOARDIMG, spaceRect)# 画游戏窗口中左下角和右下角的棋子DISPLAYSURF.blit(REDTOKENIMG, REDPILERECT) # 左边的红色棋子DISPLAYSURF.blit(BLACKTOKENIMG, BLACKPILERECT) # 右边的黑色棋子def getNewBoard():board = []for x in range(BOARDWIDTH):board.append([EMPTY] * BOARDHEIGHT)return board #返回board列表，其值为BOARDHEIGHT数量的None
4.5 AI获取最佳移动算法
简单介绍一下蒙特卡洛搜索树的思想：
利用一维中的掷点法完成对围棋盘面的评估。具体来讲,当我们给定某一个棋盘局面时,程序在当前局面的所有可下点中随机选择一个点摆上棋子,并不断重复这个随机选择可下点(掷点)的过程,直到双方都没有可下点(即对弈结束),再把这个最终状态的胜负结果反馈回去,作为评估当前局面的依据。
在该实验当中AI通过不断选择不同的栏，然后考虑双方的获胜结果进行评估，AI最终会选择评估较高的策略。
在浏览下面图片和文字之前请先看一下后面的代码，然后在对应讲解内容。
观察下面图示中AI和player的对决
实验中有些变量可以直观反映了AI棋子操作的过程：
PotentialMoves：返回一个列表，表示AI将棋子移动到列表中任一栏时获胜的可能性大小，其数值为-7~0的随机数，数值为负数时表示AI将棋子移动到这一栏时，玩家可能会在接下来两步取胜，数值越小表示玩家获胜可能性越大。为0，表示玩家不会获胜，并且AI也不可能获胜，为1表示AI可以获胜。
bestMoveFitness：适应度是选取PotentialMoves中最大的数值
bestMoves：如果PotentialMoves中有多个最大值，则表示AI将棋子移动到这些值所在的栏时，玩家获胜的几率都是最小的。所以将这些栏重新添加到列表bestMoves中。
column：当bestMoves为多个值时随机选择bestMoves中的一栏作为AI的移动。若是唯一值，则column为这个唯一值。
实验中通过打印这些 bestMoveFitness ,bestMoves , column ,potentialMoves得出在上图中AI的每一步参数：
AI moves:
通过第三步AI的选择，更加细致地了解算法的原理：
下图是部分AI走法示意图，该图显示了如果AI将棋子落在第一格中，Player的可能选择，以及AI接下来的一步对player获胜产生的影响，正是通过这种搜索，迭代AI可以判定在接下来两步中对手和自己的获胜情况，从而做出抉择。
下图是计算AI适应度值的流程图，实验中难度系数为2，需考虑7 ^ 4=2041次：
通过以上流程图，不难发现。AI的第一步棋子，若为0，1，2，4，5，6。则Player总有可能将剩下的两个棋子全部放在3，从而获胜。以AI=0为例，若player =0,即红色的第1枚棋子不在3，第2枚红色棋子不论在哪，都不可能获胜，为方便表述，用序列表示各种组合，序列第一个表是AI第一步，第二个数表示Player的回应，第三个数表示AI的回应。X表示任意有效移动。 所以[0,0,x]=0，推理得，当序列为[0,x<>3,x]，player都不能获胜。只有当player的第2枚棋子为3时，AI的第二枚在不为3的情况下都能获胜，所以[0,x=3,x<>3] =-1。共有6种情况。最终的结果为（0+0+…(43个)-1*6）/7 =-1 同理对于其他的四种，结果都为-1。当AI第一步就在3的话，Player就不可能获胜，并且AI也不能获胜，所以为0。AI会选择最高适应度值来走，即会在第3列落下棋子。
同理可以分析接下来AI的选择。归纳起来便是，如果AI的一步使得Player获胜的可能性越大，AI的适应度值越低，AI也选择适应度较高的，即按照阻止Player获胜的走法进行。当然，如果它自己能够获胜，它会优先将自己获胜的走法设置最高适应度。
def getPotentialMoves(board, tile, lookAhead):if lookAhead == 0 or isBoardFull(board):'''如果难度系数为0，或格子已满则返回列表值全为0,即此时适应度值和列的潜在移动值相等。此时AI将随机降落棋子，失去智能'''return [0] * BOARDWIDTH#确定对手棋子颜色if tile == RED:enemyTile = BLACKelse:enemyTile = REDpotentialMoves = [0] * BOARDWIDTH #初始一个潜在的移动列表，其数值全部为0for firstMove in range(BOARDWIDTH):#对每一栏进行遍历，将双方中的任一方的移动称为firstMove#则另外一方的移动就称为对手，counterMove。#这里我们的firstMove为AI，对手为玩家。 dupeBoard = copy.deepcopy(board)#这里用深复制是为了让board和dupeBoard不互相影响if not isValidMove(dupeBoard, firstMove):#如果在dupeBoard中黑色棋子移到firstMove栏无效continue #则继续下一个firstMovemakeMove(dupeBoard, tile, firstMove)#如果是有效移动，则设置相应的格子颜色if isWinner(dupeBoard, tile): #如果获胜potentialMoves[firstMove] = 1 #获胜的棋子自动获得一个很高的数值来表示其获胜的几率#数值越大，获胜可能性越大，对手获胜可能性越小。break #不要干扰计算其他的移动else:if isBoardFull(dupeBoard): #如果dupeBoard中没有空格potentialMoves[firstMove] = 0 #无法移动else:for counterMove in range(BOARDWIDTH):#考虑对手的移动dupeBoard2 = copy.deepcopy(dupeBoard)if not isValidMove(dupeBoard2, counterMove):continuemakeMove(dupeBoard2, enemyTile, counterMove)if isWinner(dupeBoard2, enemyTile):potentialMoves[firstMove] = -1 #如果玩家获胜，则AI的在此栏值最低breakelse:# 递归调用getPotentialMovesresults = getPotentialMoves(dupeBoard2, tile, lookAhead - 1)potentialMoves[firstMove] += (sum(results) / BOARDWIDTH) / BOARDWIDTHreturn potentialMoves
4.6 玩家操作
拖拽棋子，判断棋子所在位置的格子，验证棋子的有效性，调用棋子下落函数，完成操作。
def getHumanMove(board, isFirstMove):draggingToken = Falsetokenx, tokeny = None, Nonewhile True:# pygame.event.get()来处理所有的事件for event in pygame.event.get(): if event.type == QUIT:#停止，退出pygame.quit()sys.exit()elif event.type == MOUSEBUTTONDOWN and not draggingToken and REDPILERECT.collidepoint(event.pos):#如果事件类型为鼠标按下，notdraggingToken为True，鼠标点击的位置在REDPILERECT里面draggingToken = Truetokenx, tokeny = event.poselif event.type == MOUSEMOTION and draggingToken:#如果开始拖动了红色棋子tokenx, tokeny = event.pos #更新被拖拽的棋子的位置elif event.type == MOUSEBUTTONUP and draggingToken:#如果鼠标松开，并且棋子被拖拽#如果棋子被拖拽在board的正上方if tokeny < YMARGIN and tokenx > XMARGIN and tokenx < WINDOWWIDTH - XMARGIN:column = int((tokenx - XMARGIN) / SPACESIZE)#根据棋子的x坐标确定棋子会落的列（0,1...6)if isValidMove(board, column):#如果棋子移动有效"""掉落在相应的空格子中，这里只是显示一个掉落的效果不用这个函数也能通过下面的代码实现棋子填充空格"""animateDroppingToken(board, column, RED)#将空格中最下面的格子设为红色board[column][getLowestEmptySpace(board, column)] = REDdrawBoard(board)#在落入的格子中画红色棋子pygame.display.update()#窗口更新returntokenx, tokeny = None, NonedraggingToken = Falseif tokenx != None and tokeny != None:#如果拖动了棋子,则显示拖动的棋子drawBoard(board, {'x':tokenx - int(SPACESIZE / 2), 'y':tokeny - int(SPACESIZE / 2), 'color':RED})#并且通过调整x,y的坐标使拖动时，鼠标始终位于棋子的中心位置。else:drawBoard(board)#当为无效移动时，鼠标松开后，因为此时board中所有格子的值均为none#调用drawBoard时，进行的操作是显示下面的两个棋子，相当于棋子回到到开始拖动的地方。if isFirstMove:DISPLAYSURF.blit(ARROWIMG, ARROWRECT)#AI先走，显示提示操作图片pygame.display.update()FPSCLOCK.tick()
4.7 AI操作
实现AI棋子自动移动并降落到相应位置的函数。
def animateComputerMoving(board, column):x = BLACKPILERECT.left#下面黑色棋子的左坐标y = BLACKPILERECT.top #下面黑色棋子的上坐标speed = 1.0while y > (YMARGIN - SPACESIZE):#当y的值较大，即棋子位于窗口下方时y -= int(speed)#y不断减小，即棋子不断上移speed += 0.5#减小的速度增加drawBoard(board, {'x':x, 'y':y, 'color':BLACK})#y不断变化，不断绘制红色棋子，形成不断上升的效果pygame.display.update()FPSCLOCK.tick()#当棋子上升到borad顶端时y = YMARGIN - SPACESIZE#y重新赋值，此时棋子的最下边和board的最上边相切speed = 1.0while x > (XMARGIN + column * SPACESIZE):#当x值大于需要移到的列的x坐标时x -= int(speed)#x值不断减小，即左移speed += 0.5drawBoard(board, {'x':x, 'y':y, 'color':BLACK})#此时y坐标已经不变，即从board上端向左平移到所在列。pygame.display.update()FPSCLOCK.tick()#黑色棋子降落到计算得到的空格animateDroppingToken(board, column, BLACK)
通过返回的potentialMoves，选择其列表中最高的数字作为适应度值，并从这些适应度高栏中随机选择作为最后的移动目标。
def getComputerMove(board):potentialMoves = getPotentialMoves(board, BLACK, DIFFICULTY)#潜在的移动，是一个含BOARDWIDTH个值的列表。。print potentialMoves #列表值与设置的难度系数有关bestMoves = []bestMoveFitness =max(potentialMoves) print bestMoveFitness #建立bestMoves空列表for i in range(len(potentialMoves)): if potentialMoves[i] == bestMoveFitness and isValidMove(board, i):bestMoves.append(i) #列出所有可以移动到的列，该列表可能为空，可能只有一个值，也可能有多个值 print bestMovesreturn random.choice(bestMoves)#从可以移动到的列中，随机选择一个作为移动到的目标
4.8 棋子移动操作
通过不断改变棋子的相应坐标，实现下落的动画效果。
def getLowestEmptySpace(board, column):# 返回最一列中最下面的空格for y in range(BOARDHEIGHT-1, -1, -1):if board[column][y] == EMPTY:return yreturn -1def makeMove(board, player, column):lowest = getLowestEmptySpace(board, column)#返回一栏中if lowest != -1:#如果格子中的有空格board[column][lowest] = player'''则将player(red/black)赋值给一栏中的最low的一个空格因为，棋子是落在一栏当中所有空格的最下面一个空格即认定这个格子中的颜色'''def animateDroppingToken(board, column, color):x = XMARGIN + column * SPACESIZE #x坐标y = YMARGIN - SPACESIZE #y坐标dropSpeed = 1.0#棋子降落的速度lowestEmptySpace = getLowestEmptySpace(board, column)#一列的空格当中最下面的一个空格while True:y += int(dropSpeed)#y的坐标以dropSpeed叠加dropSpeed += 0.5#dropSpeed也在加速，即棋子下落的加速度为0.5if int((y - YMARGIN) / SPACESIZE) >= lowestEmptySpace:#判断到达最下面的空格returndrawBoard(board, {'x':x, 'y':y, 'color':color})#y不断变化，不断绘制红色棋子，形成不断降落的效果pygame.display.update()FPSCLOCK.tick()
4.9 一些判断函数
判断棋子的移动是否有效，判断棋盘是否还有空格
def isValidMove(board, column):#判断棋子移动有效性if column < 0 or column >= (BOARDWIDTH) or board[column][0] != EMPTY:#如果列<0,或>BOARDWIDTH,或列中没有空格子return False #则为无效的移动，否则有效return Truedef isBoardFull(board):#如果格子中没有空余，则返回Truefor x in range(BOARDWIDTH):for y in range(BOARDHEIGHT):if board[x][y] == EMPTY:return Falsereturn True
4.10 获胜条件判断
几张示意图方便了解，获胜的四种情况。图中所示是x，y取极值时所对应的位置。
def isWinner(board, tile):# 检查水平方向棋子情况for x in range(BOARDWIDTH - 3):#x的取值为0,1,2,3for y in range(BOARDHEIGHT):#遍历所有行#如果x=0,则看第y行前4个棋子否都是相同的棋子，以此类推可以遍历所有的水平棋子四子相连情况.只要有一个x，y成立就可以判定获胜if board[x][y] == tile and board[x+1][y] == tile and board[x+2][y] == tile and board[x+3][y] == tile:return True# 检查竖直方向棋子情况，与水平情况类似for x in range(BOARDWIDTH):for y in range(BOARDHEIGHT - 3):if board[x][y] == tile and board[x][y+1] == tile and board[x][y+2] == tile and board[x][y+3] == tile:return True# 检查左倾斜方向棋子情况for x in range(BOARDWIDTH - 3):#x取值0,1,2,3for y in range(3, BOARDHEIGHT):#因为左倾斜连成四子时，最坐下面的棋子至少为列中距离最上面四个格子，即y>=3if board[x][y] == tile and board[x+1][y-1] == tile and board[x+2][y-2] == tile and board[x+3][y-3] == tile:#判定左倾斜四子同色return True# 检查右倾斜方向棋子情况，与左倾斜类似for x in range(BOARDWIDTH - 3):for y in range(BOARDHEIGHT - 3):if board[x][y] == tile and board[x+1][y+1] == tile and board[x+2][y+2] == tile and board[x+3][y+3] == tile:return Truereturn False
4.11 程序运行
def main():isFirstGame = True #初始isFirstGamewhile True: #使游戏一直能够运行下去runGame(isFirstGame)isFirstGame = Falsedef runGame(isFirstGame):if isFirstGame:# 刚刚启动游戏第一局时#让AI先走第一步棋子，以便玩家可以观察到游戏是怎么玩的turn = COMPUTERshowHelp = Trueelse:# 从第二剧开始，随机分配if random.randint(0, 1) == 0:turn = COMPUTERelse:turn = HUMANshowHelp = False
五、实验总结
基于蒙特卡洛搜索树算法，利用Pygame模块使用Python代码实现了，人工自由选择棋子，AI通过算法智能跳到的人机大战效果。整个实验，让我们熟悉了pygame创建实例和移动的基础知识，也初步了解了蒙特卡洛算法的具体应用。
六、参考资料
/info-detail-1261189.html
蒙特卡洛搜索树介绍：/posts//09/intro-to-monte-carlo-tree-search/
