python博弈树实现AI五子棋小游戏

python博弈树实现AI五子棋小游戏

运行比较慢，后续优化。

完整项目代码可从 /hfq0219/wuziqi.git 下载。

功能有选择先后手和先手禁手规则。

运行效果：

#!/usr/bin/env python3# -*- coding: UTF-8 -*-#wuziqi.py#Author:fengqifrom graphics import *import time###num = [[0 for a in range(16)] for a in range(16)]dx = [1,1,0,-1,-1,-1,0,1] #x,y方向向量dy = [0,1,1,1,0,-1,-1,-1]is_end = Falsego_first = 1 #先手标志start = 1 #轮换下棋标志ai = 1 #AI下棋标志L1_max=-100000 #剪枝阈值L2_min=100000list=[] #保存已画棋子RESTART_FLAG = FalseQUIT_FLAG = False###win = GraphWin("五子棋",550,451)aiFirst = Text(Point(500,100),"")manFirst = Text(Point(500,140),"")notice = Text(Point(500,290),"") #提示轮到谁落子notice.setFill('red')last_ai = Text(Point(500,330),"") #AI最后落子点last_man = Text(Point(500,370),"") #玩家最后落子点QUIT = Text(Point(500,20),"退出")QUIT.setFill('red')RESTART = Text(Point(500,60),"重玩")RESTART.setFill('red')#数据初始化，把棋盘上的棋子和提示清空def init():global is_end,start,go_first,RESTART_FLAGis_end=Falsestart=1go_first=1RESTART_FLAG=FalseQUIT_FLAG=Falsefor i in range(16):for j in range(16):if(num[i][j]!=0):num[i][j]=0for i in range(len(list)):list[-1].undraw()list.pop(-1)aiFirst.setText("AI 先手")manFirst.setText("我先手")notice.setText("")last_ai.setText("")last_man.setText("")#画棋盘def drawWin():win.setBackground('yellow')for i in range(0,451,30):line=Line(Point(i,0),Point(i,450))line.draw(win)for j in range(0,451,30):line=Line(Point(0,j),Point(450,j))line.draw(win)Rectangle(Point(460,5),Point(540,35)).draw(win)Rectangle(Point(460,45),Point(540,75)).draw(win)Rectangle(Point(460,85),Point(540,115)).draw(win)Rectangle(Point(460,125),Point(540,155)).draw(win)Rectangle(Point(452,275),Point(548,305)).draw(win)Rectangle(Point(452,307),Point(548,395)).draw(win)aiFirst.draw(win)manFirst.draw(win)notice.draw(win)last_ai.draw(win)last_man.draw(win)QUIT.draw(win)RESTART.draw(win)#判断该点是否在棋盘范围内def inBoard(x,y):if(x>=0 and x<=15 and y>=0 and y<=15): return Trueelse: return False#判断该点是否可落子，即是否在棋盘内且没有落子def downOk(x,y):if(inBoard(x,y) and num[x][y]==0): return Trueelse: return False#该点值是否和i值相等，即该点棋子颜色和i相同def sameColor(x,y,i):if(inBoard(x,y) and num[x][y]==i): return Trueelse: return False#在给定的方向v(v区分正负)上，和该点同色棋子的个数def numInline(x,y,v):i=x+dx[v]; j=y+dy[v]s=0; ref=num[x][y]if(ref==0): return 0while(sameColor(i,j,ref)):s=s+1; i=i+dx[v]; j=j+dy[v]return s#该点四个方向里(即v不区分正负)，活四局势的个数def liveFour(x,y):key=num[x][y]; s=0for u in range(4):samekey=1samekey,i=numofSamekey(x,y,u,1,key,samekey)if(not downOk(x+dx[u]*i,y+dy[u]*i)):continuesamekey,i=numofSamekey(x,y,u,-1,key,samekey)if(not downOk(x+dx[u]*i,y+dy[u]*i)):continueif(samekey==4):s=s+1return s#该点八个方向里(即v区分正负)，冲四局势的个数def chongFour(x,y):key=num[x][y]; s=0for u in range(8):samekey=0; flag=True; i=1while(sameColor(x+dx[u]*i,y+dy[u]*i,key) or flag):if(not sameColor(x+dx[u]*i,y+dy[u]*i,key)):if(flag and inBoard(x+dx[u]*i,y+dy[u]*i) and num[x+dx[u]*i][y+dy[u]*i]!=0):samekey-=10flag=Falsesamekey+=1i+=1i-=1if(not inBoard(x+dx[u]*i,y+dy[u]*i)):continuesamekey,i=numofSamekey(x,y,u,-1,key,samekey)if(samekey==4):s+=1return s-liveFour(x,y)*2#该点四个方向里活三，以及八个方向里断三的个数def liveThree(x,y):key=num[x][y]; s=0for u in range(4):samekey=1samekey,i=numofSamekey(x,y,u,1,key,samekey)if(not downOk(x+dx[u]*i,y+dy[u]*i)):continueif(not downOk(x+dx[u]*(i+1),y+dy[u]*(i+1))):continuesamekey,i=numofSamekey(x,y,u,-1,key,samekey)if(not downOk(x+dx[u]*i,y+dy[u]*i)):continueif(not downOk(x+dx[u]*(i-1),y+dy[u]*(i-1))):continueif(samekey==3):s+=1for u in range(8):samekey=0; flag=True; i=1while(sameColor(x+dx[u]*i,y+dy[u]*i,key) or flag):if(not sameColor(x+dx[u]*i,y+dy[u]*i,key)):if(flag and inBoard(x+dx[u]*i,y+dy[u]*i) and num[x+dx[u]*i][y+dy[u]*i]!=0):samekey-=10flag=Falsesamekey+=1i+=1if(not downOk(x+dx[u]*i,y+dy[u]*i)):continueif(inBoard(x+dx[u]*(i-1),y+dy[u]*(i-1)) and num[x+dx[u]*(i-1)][y+dy[u]*(i-1)]==0):continuesamekey,i=numofSamekey(x,y,u,-1,key,samekey)if(not downOk(x+dx[u]*i,y+dy[u]*i)):continueif(samekey==3):s+=1return s#该点在四个方向里，是否有六子或以上连线def overLine(x,y):flag=Falsefor u in range(4):if((numInline(x,y,u)+numInline(x,y,u+4))>4):flag=Truereturn flag#该黑子点是否是禁手点，黑子禁手直接判输def ban(x,y):if(sameColor(x,y,3-go_first)):return Falseflag=((liveThree(x,y)>1) or (overLine(x,y)) or ((liveFour(x,y)+chongFour(x,y))>1))return flag#统计在u方向上，和key值相同的点的个数，即和key同色的连子个数def numofSamekey(x,y,u,i,key,sk):if(i==1):while(sameColor(x+dx[u]*i,y+dy[u]*i,key)):sk+=1i+=1elif(i==-1):while(sameColor(x+dx[u]*i,y+dy[u]*i,key)):sk+=1i-=1return sk,i#游戏是否结束，如果有五子连线或出现禁手def gameOver(x,y):global is_endfor u in range(4):if((numInline(x,y,u)+numInline(x,y,u+4))>=4):is_end=Truereturn Truereturn False#对该点落子后的局势进行估分def getScore(x,y):global is_endif(ban(x,y)):return 0if(gameOver(x,y)):is_end=Falsereturn 10000score=liveFour(x,y)*1000+(chongFour(x,y)+liveThree(x,y))*100for u in range(8):if(inBoard(x+dx[u],y+dy[u]) and num[x+dx[u]][y+dy[u]]!=0):score=score+1return score#博弈树第一层def AI1():global L1_maxL1_max=-100000if(num[8][8]==0 and go_first==ai):return go(8,8)keyi=-1; keyj=-1for x in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:for y in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:if(not downOk(x,y)):continuenum[x][y]=aitempp=getScore(x,y)if(tempp==0):num[x][y]=0; continueif(tempp==10000):return go(x,y)tempp=AI2()num[x][y]=0if(tempp>L1_max): #取极大L1_max=tempp; keyi=x; keyj=ygo(keyi,keyj)#博弈树第二层def AI2():global L2_minL2_min=100000for x in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:for y in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:if(not downOk(x,y)):continuenum[x][y]=3-aitempp=getScore(x,y)if(tempp==0):num[x][y]=0; continueif(tempp==10000):num[x][y]=0; return -10000tempp=AI3(tempp)if(tempp<L1_max): #L1层剪枝num[x][y]=0; return -10000num[x][y]=0if(tempp<L2_min): #取极小L2_min=temppreturn L2_min#博弈树第三层def AI3(p2):keyp=-100000for x in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:for y in [8,7,9,6,10,5,11,4,12,3,13,2,14,1,15,0]:if(not downOk(x,y)):continuenum[x][y]=aitempp=getScore(x,y)if(tempp==0):num[x][y]=0; continueif(tempp==10000):num[x][y]=0; return 10000if(tempp-p2*2>L2_min): #L2层剪枝num[x][y]=0; return 10000num[x][y]=0if(tempp-p2*2>keyp): #取极大keyp=tempp-p2*2return keyp#选手下棋def manPlay():p=win.getMouse()if(Restart(p) or Quit(p)): returnx=round(p.getX()/30)y=round(p.getY()/30)if(downOk(x,y)): go(x,y)else: manPlay()#落下一子并且判断游戏是否结束def go(x,y):global is_endc=Circle(Point(x*30,y*30),13)if(start==ai):num[x][y]=ailast_ai.setText("AI 落子:\n(x:y)=("+str(x)+":"+str(y)+")")if(go_first==ai): c.setFill('black')else: c.setFill('white')else:num[x][y]=3-ailast_man.setText("玩家落子:\n(x:y)=("+str(x)+":"+str(y)+")")if(go_first==ai): c.setFill('white')else: c.setFill('black')c.draw(win)list.append(c)if(ban(x,y)):if(start==ai):notice.setText("AI 禁手,玩家赢!\n点击重玩")else:notice.setText("玩家禁手,AI 赢!\n点击重玩")is_end=Trueelif(gameOver(x,y)):if(start==ai):notice.setText("AI 赢!\n点击重玩")else:notice.setText("玩家赢!\n点击重玩")##是否重新开始游戏def Restart(p):global RESTART_FLAGx=p.getX(); y=p.getY()if((abs(500-x)<40) and (abs(60-y)<15)): #restartinit()RESTART_FLAG=Truenotice.setText("重新开始")time.sleep(1)return Trueelse:return False##是否退出游戏def Quit(p):global QUIT_FLAG, is_endx=p.getX(); y=p.getY()if((abs(500-x)<40) and (abs(20-y)<15)): #quitinit()QUIT_FLAG=Trueis_end=Truenotice.setText("退出")time.sleep(1)return Trueelse:return False##选择先后手def whoStart(p):global start, go_firstx=p.getX(); y=p.getY()if((abs(500-x)<40) and (abs(100-y)<15)): #AI 先手start=1go_first=1aiFirst.setText("AI 执黑")manFirst.setText("玩家执白")return Trueelif((abs(500-x)<40) and (abs(140-y)<15)): #玩家先手start=2go_first=2aiFirst.setText("AI 执白")manFirst.setText("玩家执黑")return Trueelse:return False##------------------------------------------------------------------###主程序入口if __name__=='__main__':init()drawWin()notice.setText("请选择先手")p=win.getMouse()while(not whoStart(p) and not Quit(p)):p=win.getMouse()while(not is_end):RESTART_FLAG=Falseif(start==ai):notice.setText("AI 正在下棋...")AI1()else:notice.setText("请你下棋...")manPlay()start=3-startif(RESTART_FLAG):notice.setText("请选择先手")p=win.getMouse()while(not whoStart(p) and not Quit(p)):p=win.getMouse()elif(not QUIT_FLAG and is_end):p=win.getMouse()while(not Restart(p) and not Quit(p)):p=win.getMouse()if(RESTART_FLAG):notice.setText("请选择先手")p=win.getMouse()while(not whoStart(p) and not Quit(p)):p=win.getMouse()