【Python开发实践】AI人机对战五子棋——AI功能实现

方法分析

在五子棋中有7种有效的棋型（连五、活四、冲四、活三、眠三、活二、眠二）。我们可以创建黑棋和白棋两个数组，记录棋盘上黑棋和白棋分别形成的所有棋型的个数，然后按照一定的规则进行评分。

在棋盘上设置有15条水平线和15条竖直线，不考虑长度小于5的斜线，有21条左上到右下的斜线，21条左下到右上的斜线。然后在每一条线上分别对黑棋和白棋查找是否有符合的棋型。这种方法比较直观，但是实现不方便。

所以，我们的方法是对整个棋盘进行遍历，对于每一个白棋或黑棋，以它为中心，记录符合的棋型个数。具体的实现方式如下：

1、评估棋盘上的每个点。如果是黑棋或者白棋，则对这个点所在四个方向形成4条线分别进行评估。四个方向即水平、竖直、两个斜线，四个方向依次按照从左到右、从上到下、从左上到右下、从左下到右上来检测。

2、对于具体的一条直线，以选取点为中心，取该方向上前面4个点和后面4个点，组成一个长度为9的数组。

3、找出和中心点相连的同色棋子有几个，根据相连棋子的个数再分别进行判断，最后得出这行属于哪一种棋型。需要注意的是，已经被判断过的棋子要标记下，避免重复统计棋型。

4、根据棋盘上黑棋和白棋的棋型统计信息，按照一定的规则进行评分。假设形成该棋局的最后一步是黑棋下的，则最后的评分是（黑棋得分-白棋得分），在相同棋型、相同个数的情况下，白棋会占优，因为下一步是白棋下。比如白棋有个冲四，黑棋也有个冲四，显然白棋占优，因为下一步白棋就能形成连五。最后按照下面的规则依次匹配：

黑棋连五，评分为10000；

白棋连五，评分为-10000；

黑棋两个冲四，可以当成一个活四；

白棋有活四，评分为-9050；

白棋有冲四，评分为-9040；

黑棋有活四，评分为9030；

黑棋有冲四和活三，评分为9020；

黑棋没有冲四，且白棋有活三，评分为9010；

黑棋有2个活三，且白棋没有活三或眠三，评分为9000；

5、最后针对黑棋或白棋的活三、眠三、活二、眠二的个数依次增加分数，具体评分值为（黑棋得分-白棋得分）。

功能实现

有了上面的评估标准，当轮到AI下棋时，就要针对当前的棋局，找到一个最有利的位置。AI会尝试在每个空点下棋，每次都形成一个新的棋局，然后用评估函数来获取这个棋局的评分，只需要在最后从中选取评分最高的位置就可以了。

下面是AI获取最有利位置的逻辑：

1、首先遍历棋盘上的每一个空点，并在这个空点下棋，获取新的棋局的评分；

2、如果是更高的评分，则保存该位置；

3、然后将这个位置恢复为空点；

4、最后会获取最高评分的位置。

具体实现流程如下：

构造函数实现初始化功能

在数组record中记录所有位置的4个方向是否被检测过，使用二维数组count记录黑棋和白棋的棋型个数统计。通过position_isgreat方法给棋盘上的每个位置设一个初试分数，越靠近棋盘中心，分数越高，这样在最初没有任何棋型时，AI会优先选取靠近中心的位置。对应代码：

class MyChessAI():
    def __int__(self,chess_len):                    #构造函数
        self.len=chess_len                          #当前棋盘大小
        #二维数组，每一格存的是：横评分、纵评分、左斜评分、右斜评分
        self.record=[[[0,0,0,0] for i in range(chess_len)] for j in range(chess_len)]
        #存储当前格具体棋型数量
        self.count=[[0 for i in range(SITUATION_NUM)] for j in range(2)]
        #位置分（同条件下，越靠近棋盘中央分数越高）
        self.position_isgreat=[
            [(web_broad-max(abs(i-web_broad/2+1),abs(j-web_broad/2+1)))for i in range(chess_len)]
            for j in range(chess_len)
        ]
    def get_init(self):
        for i in range(self.len):
            for j in range(self.len):
                for k in range(4):
                    self.record[i][j][k]=0
        for i in range(len(self.count)):
            for j in range(len(self.count[0])):
                self.count[i][j]=0
        self.save_cont=0
    def isWin(self,board,turn):
        return self.evaluate(board,turn,True)

返回所有未下棋的坐标

函数genmove()能够获取棋盘上所有的空点，然后依次尝试，获得评分最高的位置并返回

    def genmove(self,board,turn):
        moves=[]
        for y in range(self.len):
            for x in range(self.len):
                if board[y][x]==0:
                    score=self.position_isgreat[y][x]
                    moves.append((score,x,y))
        moves.sort(reverse=True)
        return moves

返回当前最优解下标

此函数是上述AI逻辑的代码实现。先通过genmove()获取棋盘上所有的空点，然后依次尝试，获得评分最高的位置并返回：

    def search(self,board,turn):
        moves=self.genmove(board,turn)
        bestmove=None
        max_score=-9999
        for score,x,y in moves:
            board[y][x]=turn.value
            score=self.evaluate(board,turn)
            board[y][x]=0
            if score>max_score:
                max_score=score
                bestmove=(max_score,x,y)
        return bestmove

AI的入口函数

    def findBestChess(self,board,turn):
        score,x,y=self.search(board,turn)
        return (x,y)

对黑棋和白棋进行区分

    def getScore(self, mychess, yourchess):
        mscore, oscore = 0, 0
        if mychess[FIVE] > 0:
            return (10000, 0)
        if yourchess[FIVE] > 0:
            return (0, 10000)
        if mychess[S4] >= 2:
            mychess[L4] = mychess[L4] + 1
        if yourchess[L4] > 0:
            return (0, 9050)
        if yourchess[S4] > 0:
            return (0, 9040)
        if mychess[L4] > 0:
            return (9030, 0)
        if mychess[S4] > 0 and mychess[L3] > 0:
            return (9020, 0)
        if yourchess[L3] > 0 and mychess[S4] == 0:
            return (0, 9010)
        if (mychess[L3] > 1 and yourchess[L3] == 0 and yourchess[S3] == 0):
            return (9000, 0)
        if mychess[S4] > 0:
            mscore = mscore + 2000
        if mychess[L4] > 1:
            mscore = mscore + 500
        elif mychess[L3] > 0:
            mscore = mscore + 100
        if yourchess[L3] > 0:
            oscore = oscore + 2000
        elif yourchess[L3] > 0:
            oscore = oscore + 400
        if mychess[S3] > 0:
            mscore = mscore + mychess[S3] * 10
        if yourchess[S3] > 0:
            oscore = oscore + yourchess[S3] * 10
        if mychess[L2] > 0:
            mscore = mscore + mychess[L2] * 4
        if yourchess[L2] > 0:
            oscore = oscore + yourchess[L2] * 4
        if mychess[S2] > 0:
            mscore = mscore + mychess[S2] * 4
        if yourchess[S2] > 0:
            oscore = oscore + yourchess[S2] * 4

对得分进行进一步处理

参数turn表示最近一步棋是谁下的，根据turn决定的me（表示自己棋的值）和you（对手的棋，也就是下一步棋是谁下），在对评分时会用到。checkWin用来判断是否有一方获胜：

    def evaluate(self,board,turn,checkWin=False):
        self.get_init()
        if turn == map_enum.player1:
            me=1
            you=2
        else:
            me=2
            you=1
        for y in range(self.len):
            for x in range(self.len):
                if board[y][x]==me:
                    self.evaluatePoint(board,x,y,me,you)
                elif board[y][x]==you:
                    self.evaluatePoint(board, x, y, you,me)
        mychess=self.count[me-1]
        yourchess=self.count[you-1]
        if checkWin:
            return mychess[FIVE] > 0
        else:
            mscore,oscore=self.getScore(mychess,yourchess)
            return (mscore-oscore)

对某一个位置的4个方向分别进行检查

    def evaluatePoint(self,board,x,y,me,you):
        direction=[(1,0),(0,1),(1,1),(1,-1)]
        for i in range(4):
            if self.record[y][x][i]==0:
                self.getBasicSituation(board,x,y,i,direction[i],me,you,self.count[me-1])
            else:
                self.save_cont=self.save_cont+1

把当前方向棋型存储下来

保存棋型时为了方便后续使用，此函数能够根据棋子的位置和方向，获取上面说的长度为9的线。如果线上的位置超出了棋盘范围，就将这个为止的值设置成对手的值，因为超出范围和被对手棋挡着，对棋型判断的结果是相同的。

    def getLine(self,board,x,y,direction,me,you):
        line=[0 for i in range(9)]
        #光标移到最左端
        tmp_x=x+(-5*direction[0])
        tmp_y=y+(-5+direction[1])
        for i in range(9):
            tmp_x=tmp_x+direction[0]
            tmp_y=tmp_y+direction[1]
            if (tmp_x<0 or tmp_x>=self.len or tmp_y<0 or tmp_y>=self.len):
                line[i]=you
            else:
                line[i]=board[tmp_y][tmp_x]
        return line

把当前方向的棋型识别成具体情况

例如把MMMX识别成活四冲四、活三眠三等：

    def getLine(self,board,x,y,direction,me,you):
        line=[0 for i in range(9)]
        #光标移到最左端
        tmp_x=x+(-5*direction[0])
        tmp_y=y+(-5+direction[1])
        for i in range(9):
            tmp_x=tmp_x+direction[0]
            tmp_y=tmp_y+direction[1]
            if (tmp_x<0 or tmp_x>=self.len or tmp_y<0 or tmp_y>=self.len):
                line[i]=you
            else:
                line[i]=board[tmp_y][tmp_x]
        return line
    def getBasicSituation(self,board,x,y,dir_index,dir,me,you,count):
        #record赋值
        def setRecord(self,x,y,left,right,dir_index,direction):
            tmp_x=x+(-5+left)*direction[0]
            tmp_y=y+(-5+left)*direction[1]
            for i in range(left,right):
                tmp_x=tmp_x+direction[0]
                tmp_y=tmp_y+direction[1]
                self.record[tmp_y][tmp_x][dir_index]=1
        empty=map_enum.be_empty.value
        left_index,right_index=4,4
        line=self.getLine(board,x,y,dir,me,you)
        while right_index<8:
            if line[right_index+1]!=me:
                break
            right_index=right_index+1
        while left_index>0:
            if line[left_index-1]!=me:
                break
            left_index=left_index-1
        left_range,right_range=left_index,right_index
        while right_range<8:
            if line[right_range +1]==you:
                break
            right_range=right_range+1
        while left_range>0:
            if line[left_range-1]==you:
                break
            left_range=left_range-1
        chess_range=right_range-left_range+1
        if chess_range<5:
            setRecord(self,x,y,left_range,right_range,dir_index,dir)
            return SITUATION.NONE
        setRecord(self,x,y,left_index,right_index,dir_index,dir)
        m_range=right_index-left_index+1
        if m_range==5:
            count[FIVE]=count[FIVE]+1
        #活四冲四
        if m_range==4:
            left_empty=right_empty=False
            if line[left_index-1]==empty:
                left_empty=True
            if line[left_index+1]==empty:
                right_empty=True
            if left_empty and right_empty:
                count[L4]=count[L4]+1
            elif left_empty or right_empty:
                count[S4]=count[S4]+1
        #活三眠三
        if m_range==3:
            left_empty=right_empty=False
            left_four=right_four=False
            if line[left_index-1]==empty:
                if line[left_index-2]==me:
                    setRecord(self,x,y,left_index-2,left_index-1,dir_index,dir)
                    count[S4]=count[S4]+1
                    left_four=True
                left_empty=True
            if line[right_index+1]==empty:
                if line[right_index+2]==me:
                    setRecord(self,x,y,right_index+1,right_index+2,dir_index,dir)
                    count[S4]=count[S4]+1
                    right_four=True
                right_empty=True
            if left_four or right_four:
                pass
            elif left_empty and right_empty:
                if chess_range>5:       #XMMMXX,XXMMMX
                    count[L3]=count[L3]+1
                else:                   #PXMMMXP
                    count[S3]=count[S3]+1
            elif left_empty or right_empty:
                count[S3] = count[S3] + 1
        #活二眠二
        if m_range==2:
            left_empty=right_empty=False
            left_three=right_three=False
            if line[left_index-1]==empty:
                if line[left_index-2]==me:
                    setRecord(self,x,y,left_index-2,left_index-1,dir_index,dir)
                    if line[left_index-3]==empty:
                        if line[right_index+1]==empty:
                            count[L3]=count[L3]+1
                        else:
                            count[S3] = count[S3] + 1
                        left_three=True
                    elif line[left_index-3]==you:
                        if line[right_index+1]==empty:
                            count[S3] = count[S3] + 1
                            left_three=True
                left_empty=True
            if line[right_index+1]==empty:
                if line[right_index+2]==me:
                    if line[right_index+2]==me:
                        setRecord(self,x,y,right_index+1,right_index+2,dir_index,dir)
                        count[S4]=count[S4]+1
                        right_three=True
                    elif line[right_index+3]==empty:
                        if left_empty:
                            count[L3]=count[L3]+1
                        else:
                            count[S3]=count[S3]+1
                        right_three=True
                right_empty=True
            if left_three or right_three:
                pass
            elif left_empty and right_empty:
                count[L2]=count[L2]+1
            elif left_empty or right_empty:
                count[S2]=count[S2]+1
        #特殊活二眠二
        if m_range==1:
            left_empty=right_empty=False
            if line[left_index-1]==empty:
                if line[left_index-2]==me:
                    if line[left_index-3]==empty:
                        if line[right_index+1]==you:
                            count[S2]=count[S2]+1
                left_empty=True
            if line[right_index+1]==empty:
                if line[right_index+2]==me:
                    if line[right_index+3]==empty:
                        if left_empty:
                            count[L2]=count[L2]+1
                        else:
                            count[S2]=count[S2]+1
                elif line[right_index+2]==empty:
                    if line[right_index+3]==me and line[right_index+4]==empty:
                        count[L2]=count[L2]+1
        return SITUATION.NONE