? ? ? ? 运用博弈树算法编写的黑白棋游戏，运行环境为Python3.9。
????????树的搜索深度默认为3（下一步向前分析2步），往前随着搜索深度的增大，算法更加聪明，但是分析时间会长很多。
? ? ? ? 可以通过修改源码中的以下部分search_depth的值来设置树的搜索深度：
????????#####################设置搜索深度###############
????????global search_depth
????????search_depth=3 #修改search_depth的值以改变搜索深度
????????#####################设置搜索深度###############
? ? ? ? 当搜索深度为4时，程序胜率较高，但由于没有启动多线程，下子后算法分析时会卡住，一般要等待半分钟左右（时间关系，没有进行剪枝处理）。由于本程序主要关注算法，用户体验先忽略不计。勿喷。
运行如下：
源码如下：
import tkinter as tk
import numpy as np
from collections import Counter
from tkinter import StringVar, IntVar
current_player=0;#0 represents the user while 1 represents the algrithm
current_situation=np.zeros([10,10])
current_situation[4][4]=1
current_situation[5][4]=-1
current_situation[4][5]=-1
current_situation[5][5]=1
#current_situation[5][6]=-1
#current_situation[6][6]=1
#current_situation[4][3]=-1
#current_situation[3][5]=-1
'''
current_situation[3][6]=-1
current_situation[5][7]=1
current_situation[5][8]=1
current_situation[4][7]=-1
current_situation[3][7]=-1
current_situation[6][9]=-1'''
def dropchess(event):
global current_player,current_situation,depth,depthr,turn
row=int(event.y/50)
col=int(event.x/50)
drop_points,change_points=get_avalible_drop(current_player,current_situation)
set_change_points_on(drop_points,change_points,[row,col])
if current_player==0 and [row,col] in drop_points:
current_situation[row][col]=-1
if current_player==0:
current_player=1
else:
current_player=0
#算法下子
situation=current_situation.copy()
#print(situation)
bestdrop=getbestdrop(situation)
#print(bestdrop)
drop_points,change_points=get_avalible_drop(current_player,current_situation)
set_change_points_on(drop_points,change_points,bestdrop)
current_situation[bestdrop[0]][bestdrop[1]]=1
current_player=0
depth=0
depthr=0
#turn.set('轮到你下子o...')
#算法下子
drop_points,change_points=get_avalible_drop(current_player,current_situation)
set_avalible_drop_on(drop_points)
draw_Chess_from_Maxtrix(current_situation)
clear_avalible_drop(drop_points)
statistical_num(current_situation)
turn.set(' ')
def draw_Chess_from_Maxtrix(current_situation):
for i in range(len(current_situation)):
for j in range(len(current_situation[0])):
if current_situation[i][j]==1:
canvas.create_oval(j*50+6,i*50+6,j*50+44,i*50+44,fill='white')#白色是算法，黑色是用户
if current_situation[i][j]==-1:
canvas.create_oval(j*50+6,i*50+6,j*50+44,i*50+44,fill='black')
if current_situation[i][j]==2:
canvas.create_oval(j*50+6,i*50+6,j*50+44,i*50+44,outline='red')
if current_situation[i][j]==0:
canvas.create_oval(j*50+6,i*50+6,j*50+44,i*50+44,outline='green')
def set_avalible_drop_on(drop_points):#通过可下子位置列表绘制可下子标识
global current_situation
for point in drop_points:
current_situation[point[0]][point[1]]=2
def clear_avalible_drop(drop_points):#每一次绘制完棋子以及可下子标识后，清空当前局面矩阵可下子点
global current_situation
for point in drop_points:
current_situation[point[0]][point[1]]=0
def set_change_points_on(avalible_drop,change_points,coordinate):
global current_situation
idx=avalible_drop.index(coordinate)
points=change_points[idx]
for point in points:
if current_situation[point[0]][point[1]]==1:
current_situation[point[0]][point[1]]=-1
else:
current_situation[point[0]][point[1]]=1
def get_avalible_drop(current_player,current_situation):#通过当前玩家序号，当前局面矩阵以及落子点计算新的局面矩阵
ava=[]
ava_row=[]
if current_player==0:
current_situation=current_situation*-1;
for row in range(len(current_situation)):
for col in range(len(current_situation[0])):
ava_row=search_row(row,col,current_player,current_situation)
ava_col=search_col(row,col,current_player,current_situation)
ava_dig=search_diagonal(row,col,current_player,current_situation)
ava_fdig=search_fdiagonal(row,col,current_player,current_situation)
if ava_row!=[]:
ava.append(ava_row)
if ava_col!=[]:
ava.append(ava_col)
if ava_dig!=[]:
ava.append(ava_dig)
if ava_fdig!=[]:
ava.append(ava_fdig)
drop_points,change_points=format_avalible_drop(ava)
current_situation=current_situation*-1
return drop_points,change_points
def search_row(row,col,current_player,current_situation):#竖向搜索 输入坐标，玩家序号，当前局面矩阵判断是否可以落子
avalible_row=[]
avalible_row_u=[]
avalible_row_d=[]
if current_situation[row][col]==0:
for i in range(row+1,10):
if current_situation[i][col]==-1:
if i==9:
avalible_row_u=[]
break
avalible_row_u.append([i,col])
else:
if current_situation[i][col]==0:
avalible_row_u=[]
break
for i in range(1,row+1):
if current_situation[row-i][col]==-1:
if row-i==0:
avalible_row_d=[]
break
avalible_row_d.append([row-i,col])
else:
if current_situation[row-i][col]==0:
avalible_row_d=[]
break
avalible_row=avalible_row_u+avalible_row_d
if len(avalible_row)>0:
return [[row,col],avalible_row]
else:
return []
def search_col(row,col,current_player,current_situation):#横向搜索
avalible_col_u=[]
avalible_col_d=[]
avalible_col=[]
if current_situation[row][col]==0:
for i in range(col+1,10):
if current_situation[row][i]==-1:
if i==9:
avalible_col_u=[]
break
avalible_col_u.append([row,i])
else:
if current_situation[row][i]==0:
avalible_col_u=[]
break
for i in range(1,col+1):
if current_situation[row][col-i]==-1:
if col-i==0:
avalible_col_d=[]
break
avalible_col_d.append([row,col-i])
else:
if current_situation[row][col-i]==0:
avalible_col_d=[]
break
avalible_col=avalible_col_u+avalible_col_d
if len(avalible_col)>0:
return [[row,col],avalible_col]
else:
return []
def search_diagonal(row,col,current_player,current_situation):#正对角线搜索
avalible_dig_u=[]
avalible_dig_d=[]
avalible_dig=[]
if current_situation[row][col]==0:
if row+col>=9:
for i in range(1,10-col):
if current_situation[row-i][col+i]==-1:
if col+i==9:
avalible_dig_u=[]
break
avalible_dig_u.append([row-i,col+i])
else:
if current_situation[row-i][col+i]==0:
avalible_dig_u=[]
break
for i in range(1,10-row):
if current_situation[row+i][col-i]==-1:
if row+i==9:
avalible_dig_d=[]
break
avalible_dig_d.append([row+i,col-i])
else:
if current_situation[row+i][col-i]==0:
avalible_dig_d=[]
break
else:
for i in range(1,row+1):
if current_situation[row-i][col+i]==-1:
if row-i==0:
avalible_dig_u=[]
break
avalible_dig_u.append([row-i,col+i])
else:
if current_situation[row-i][col+i]==0:
avalible_dig_u=[]
break
for i in range(1,col+1):
if current_situation[row+i][col-i]==-1:
if col-i==0:
avalible_dig_d=[]
break
avalible_dig_d.append([row+i,col-i])
else:
if current_situation[row+i][col-i]==0:
avalible_dig_d=[]
break
avalible_dig=avalible_dig_u+avalible_dig_d
if len(avalible_dig)>0:
return [[row,col],avalible_dig]
else:
return []
def search_fdiagonal(row,col,current_player,current_situation):#副对角线搜索
avalible_fdig=[]
avalible_fdig_u=[]
avalible_fdig_d=[]
if current_situation[row][col]==0:
if row<=col:
for i in range(1,row+1):
if current_situation[row-i][col-i]==-1:
if row-i==0:
avalible_fdig_u=[]
break
avalible_fdig_u.append([row-i,col-i])
else:
if current_situation[row-i][col-i]==0:
avalible_fdig_u=[]
break
for i in range(1,10-col):
if current_situation[row+i][col+i]==-1:
if col+i==9:
avalible_fdig_d=[]
break
avalible_fdig_d.append([row+i,col+i])
else:
if current_situation[row+i][col+i]==0:
avalible_fdig_d=[]
break
else:
for i in range(1,col+1):
if current_situation[row-i][col-i]==-1:
if col-i==0:
avalible_fdig_u=[]
break
avalible_fdig_u.append([row-i,col-i])
else:
if current_situation[row-i][col-i]==0:
avalible_fdig_u=[]
break
for i in range(1,10-row):
if current_situation[row+i][col+i]==-1:
if row+i==9:
avalible_fdig_d=[]
break
avalible_fdig_d.append([row+i,col+i])
else:
if current_situation[row+i][col+i]==0:
avalible_fdig_d=[]
break
avalible_fdig=avalible_fdig_u+avalible_fdig_d
if len(avalible_fdig)>0:
return [[row,col],avalible_fdig]
else:
return []
def format_avalible_drop(drop_list):
drop_points=[]
change_points=[]
for i in range(len(drop_list)):
if drop_list[i][0] in drop_points:
change_points[len(change_points)-1].append(drop_list[i][1][0])
else:
drop_points.append(drop_list[i][0])
change_points.append(drop_list[i][1])
return drop_points,change_points
##############################################建立博弈树##########################################
def MultipleTree(r):#建立一棵新树，根节点为r
return [r,[]]
def insertTree(root, newBranch): #在树的root节点（不一定是根节点）插入新枝newBranch
root[root.index([])]=[newBranch,[],[],[],[]]
return root
def LoadTree(root):#递归建立一棵博弈树，当深度为depth时停止递归
global depth,search_depth
#print((depth)%2)
depth+=1
#print(depth)
bs=getbranch((depth)%2,root[0][0])
if len(bs)==0:
return root
elif depth>=search_depth:
return root
for b in bs:
root.insert(root.index([]),LoadTree(b))
depth-=1
return root
def getbranch(player,situation):#获得root节点（不一定是根节点）的所有叶子节点的值
#这里可以代入每一个局面的所有可下子点
rr=[]
#print('situation is')
#print('player is'+str(player))
#print(situation)
drop_points,change_points=get_avalible_drop_rc(player,situation.copy())
#print('drop_points is'+str(drop_points))
for drop in drop_points:
new=get_new_situation(player,situation.copy(),drop)
#print('new_situation is')
#print('player is'+str(player))
#print(new)
rr.append([new,[]])
#print(rr)
return rr
def getChildren(root):#获取一个节点的所有子节点
c=[]
for i in range(1,100):
if root[i]!=[]:
c.append(root[i])
else:
break
return c
def hasChild(root):#判断一个节点是否有子节点
if root[1]==[]:
return False
else:
return True
def getMaxChild(root):#或者一个节点所有子节点的最大值
ma=-9999999999
c=getChildren(root)
if len(c)>0:
for cc in c:
if cc[0][2]>ma:
ma=cc[0][2]
return ma
else:
return root[0][2]
def getMinChild(root):#或者一个节点所有子节点的最小值
mi=9999999999
c=getChildren(root)
if len(c)>0:
for cc in c:
if cc[0][2]<mi:
mi=cc[0][2]
return mi
else:
return root[0][2]
def getMaxChildDrop(root):#获得Max and Min的下子点
ma=-9999999999
drop=[-1,-1]
c=getChildren(root)
if len(c)>0:
for cc in c:
#print(cc[0][2],cc[0][1])
if cc[0][2]>ma:
ma=cc[0][2]
drop=cc[0][1]
return drop
else:
return root[0][1]
def Max_and_Min(root):
global depthr
depthr+=1
if hasChild(root):
for i in range(1,len(root)-1):
root[i][0][0]=''
root[i][0][2]=Max_and_Min(root[i])[0]
depthr-=1
if depthr%2==1:
mc=getMaxChild(root)
else:
mc=getMinChild(root)
root[0][0]=''
root[0][2]=mc
return [mc,root]
###########################################用于递归函数的子函数#########################################
def set_change_points_on_rc(avalible_drop,change_points,situation,coordinate):
#print('set_change_points_on_rc..............')
#print('avalible_drop is:'+str(avalible_drop))
idx=avalible_drop.index(coordinate)
points=change_points[idx]
for point in points:
if situation[point[0]][point[1]]==1:
situation[point[0]][point[1]]=-1
else:
situation[point[0]][point[1]]=1
return situation
def get_avalible_drop_rc(player,situation):#通过当前玩家序号，当前局面矩阵以及落子点计算新的局面矩阵
#print('get_avalible_drop_rc..............')
#print('player ='+str(player))
#print('situation='+str(situation))
ava=[]
ava_row=[]
#print(player)
if player==0:
situation=situation*-1;
for row in range(len(situation)):
for col in range(len(situation[0])):
ava_row=search_row(row,col,player,situation)
ava_col=search_col(row,col,player,situation)
ava_dig=search_diagonal(row,col,player,situation)
ava_fdig=search_fdiagonal(row,col,player,situation)
if ava_row!=[]:
ava.append(ava_row)
if ava_col!=[]:
ava.append(ava_col)
if ava_dig!=[]:
ava.append(ava_dig)
if ava_fdig!=[]:
ava.append(ava_fdig)
drop_points,change_points=format_avalible_drop(ava)
situation=situation*-1
#print('++++++++++++++++'+str(drop_points))
return drop_points,change_points
def get_new_situation(player,situation,drop):#根据可下子列表设置当前局面矩阵
drop_points,change_points=get_avalible_drop_rc(player,situation)
set_change_points_on_rc(drop_points,change_points,situation,drop)
if player==1 and drop in drop_points:
situation[drop[0]][drop[1]]=1
if player==0 and drop in drop_points:
situation[drop[0]][drop[1]]=-1
player_algrithm,player_user=statistical(situation)
advantage=player_algrithm-player_user
return [situation,drop,advantage]
def getbestdrop(situation):
roott=MultipleTree([situation,[-1,-1],0])
r=LoadTree(roott)
mc,rr=Max_and_Min(r)
bestdrop=getMaxChildDrop(rr)
return bestdrop
def statistical(situation):#根据一个局面矩阵计算黑白子的数量
global white_num
global black_num
player_algrithm=0
player_user=0
for row in situation:
for val in row:
if val==1:
player_algrithm+=1
if val==-1:
player_user+=1
return player_algrithm,player_user
def statistical_num(situation):#根据一个局面矩阵计算黑白子的数量
global white_num
global black_num
player_algrithm=0
player_user=0
for row in situation:
for val in row:
if val==1:
player_algrithm+=1
if val==-1:
player_user+=1
white_num.set(str(player_algrithm))
black_num.set(str(player_user))
return player_algrithm,player_user
###########################################用于递归函数的子函数#########################################
#####################设置搜索深度###############
global search_depth
search_depth=3
#####################设置搜索深度###############
global depthr
global depth
global white_num
global black_num
global turn
depth=0
depthr=0
white_num=2
black_num=2
canvas=''
white_label=''
black_label=''
playerturn_label=''
rt=tk.Tk(className="bw")
rt.resizable(0,0)
white_num= StringVar()
white_num.set('2')
black_num= StringVar()
black_num.set('2')
turn= StringVar()
turn.set('轮到你下子...')
canvas=tk.Canvas(rt,width=700,height=500,bg='green')
canvas.bind()
canvas.pack(padx=10,pady=10)
white_label=tk.Label(rt,width=4,height=1,textvariable=white_num)
white_label.place(x=600,y=220)
black_label=tk.Label(rt,width=4,height=1,textvariable=black_num)
black_label.place(x=600,y=290)
drop_label=tk.Label(rt,width=7,height=1,text='可下子点')
drop_label.place(x=600,y=360)
playerturn_label=tk.Label(rt,width=10,height=2,bg='green',textvariable=turn)
playerturn_label.place(x=550,y=150)
canvas.create_line(0,0,0,500,fill='black',width=10)
canvas.create_line(0,0,500,0,fill='black',width=10)
canvas.create_line(500,500,0,500,fill='black',width=3)
canvas.create_line(500,500,500,0,fill='black',width=3)
for i in range(10):
canvas.create_line(50*i,0,50*i,500,fill='black',width=2)
canvas.create_line(0,50*i,500,50*i,fill='black',width=2)
canvas.bind(sequence='<Button-1>',func=dropchess)
canvas.create_oval(540,200,580,240,fill='white')#白色是算法，黑色是用户
canvas.create_oval(540,270,580,310,fill='black')#白色是算法，黑色是用户
canvas.create_oval(540,340,580,380,outline='red')#白色是算法，黑色是用户
drop_points,change_points=get_avalible_drop(current_player,current_situation)
set_avalible_drop_on(drop_points)
draw_Chess_from_Maxtrix(current_situation)
clear_avalible_drop(drop_points)
rt.mainloop()