方法分析

在五子棋中有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会优先选取靠近中心的位置。对应代码：

<code>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