Python實現基於alpha-beta剪枝技術的五子棋

目錄
第1章 問題描述 3
第2章 問題分析 3
第3章 算法設計 4
3.1 算法概述 4
3.2 極大極小樹 4
3.3 α-β剪枝算法 5
3.3總體設計 6
3.3.1 系統流程圖 7
3.3.2 基本設計 7
3.4 預處理 8
第4章 算法實現 11
4.1 估價函數 11
4.2 alpha-beta剪枝算法 15
4.2.1 算法流程圖 15
4.2.2 代碼實現 16
第5章 成果展示與性能分析 18
5.1 成果展示 18
5.2 性能分析 23
第6章 結論與心得體會 23
6.1 結論 23
6.2 實驗心得 24
參考文獻 28
第1章 問題描述
我們的五子棋博弈實現的是雙人的、完備信息的五子棋問題，即游戲規則為雙方嚴格的輪流走步，且任何一方能完全知道對方已走過的步和以後可以走的所有步，當某方有在一條直線上連續的五子時，游戲結束。游戲模式可以分為人機對弈和雙人對弈兩種模式。雙人對弈模式比較容易實現，程序只需要判斷是否產生勝利者即可。人機對弈模式則需要我們的程序代碼實現機器落子的位置的選擇確定，本程序采用基於啟發式MAX/MIN算法的alpha-beta剪枝技術來選擇出最佳的機器落子位置。除此之外，我們還設置了殘局闖關模式，在增加了游戲趣味性的同時給用戶們帶來了更好的游戲體驗。
第2章 問題分析
要想實現一個基本的五子棋博弈游戲，我們要面對的問題可大概總結為如何判斷勝負，如何嚴格限制雙方輪流下棋，游戲界面的呈現形式以及最主要的如何確定機器落子的最佳位置。經過我們團隊的初步討論後，最終決定游戲以界面的方式呈現出來，用戶下棋時直接將鼠標點擊在想落子的位置即可。至於判斷勝負則只需要編寫一個簡單的函數，從橫、豎、斜上、斜下四個方向逐步判斷是否有五個連續的同色棋子就可實現判斷。嚴格控制雙方輪流落子通過改變flag的值間接確定當前位置是哪一方下棋，再通過相互調用對方落子的函數具體實現輪流下棋。
最後就是解決最關鍵的問題：在人機對弈模式中如何選擇出機器落子的最佳位置，這是我們整個程序代碼中最核心的部分，也是算法實現中最困難的部分。就像本次課程設計的題目敘述的那樣，我們經討論決定采用啟發式MAX/MIN算法的alpha-beta剪枝技術來准確且較為快速地確定機器的落子位置，其中涉及到的alpha-beta技術的具體實現以及確定最佳位置時采用的“算分機制”會在之後的模塊中詳細闡述。
至此，我們就基本上完成了五子棋游戲的整體問題分析，剩下的就是一些界面優化，殘局棋譜設計等非關鍵問題，我們的團隊在不斷的實踐和優化中最終實現了一個功能完善，界面優美且操作流暢的五子棋博弈小游戲。
本文轉載自：http://www.biyezuopin.vip/onews.asp?id=16537

import time
import tkinter
from tkinter import *
from tkinter import messagebox
import numpy as np
import Winner
from alpha_beta import searcher
global chess_b
global flag
class chess_borad():
def __init__(self):
# 創建並添加 canvas
# 創建窗口
self.root = Tk()
self.root.title("五子棋")
self.root.iconphoto(False, PhotoImage(file='black.png'))
self.menubar = Menu(self.root) # 創建菜單欄
# 創建“文件”下拉菜單
filemenu = Menu(self.menubar, tearoff=0)
filemenu.add_command(label="人機對弈（機器先手）", command=self.AI_first)
filemenu.add_command(label="人機對弈（玩家先手）", command=self.person_first)
filemenu.add_command(label="雙人模式（白子先）", command=self.player_W)
filemenu.add_command(label="雙人模式（黑子先）", command=self.player_B)
filemenu.add_separator()
filemenu.add_command(label="退出", command=self.root.quit)
# 創建“編輯”下拉菜單
editmenu = Menu(self.menubar, tearoff=0)
editmenu.add_command(label="第一關", command=self.game_Chanllnenge1)
editmenu.add_command(label="第二關", command=self.game_Chanllnenge2)
editmenu.add_command(label="第三關", command=self.game_Chanllnenge3)
editmenu.add_command(label="第四關", command=self.game_Chanllnenge4)
editmenu.add_command(label="第五關", command=self.game_Chanllnenge5)
# 創建“幫助”下拉菜單
helpmenu = Menu(self.menubar, tearoff=0)
helpmenu.add_command(label="關於", command=self.about_us)
# 將前面三個菜單加到菜單欄
self.menubar.add_cascade(label="開始游戲", menu=filemenu)
self.menubar.add_cascade(label="殘局挑戰", menu=editmenu)
self.menubar.add_cascade(label="關於我們", menu=helpmenu)
# 最後再將菜單欄整個加到窗口 root
self.root.config(menu=self.menubar)
self.gaird_width = 40
self.gaird_count = 16
self.widths = self.gaird_width * self.gaird_count + 20
self.root.maxsize(self.widths, self.widths)
self.root.minsize(self.widths, self.widths)
self.cv = Canvas(self.root, background='white')
self.black=PhotoImage(file='black.png')
self.white = PhotoImage(file="white.png")
self.message = Label(self.root, text="開始游戲請先在菜單欄選擇模式！")
self.message.pack(side=BOTTOM)
self.reset()
# 清空並重置棋盤函數
def reset(self):
self.cv.destroy()
self.message.destroy()
# 創建並添加Canvas
self.cv = Canvas(self.root, background='white',cursor="star")
self.cv.pack(fill=BOTH, expand=YES)
# 畫一個外邊框為白的 , 填充棋盤顏色
self.cv.create_rectangle(10, 10, self.gaird_width * self.gaird_count + 10,
self.gaird_width * self.gaird_count + 10, outline="white",
fill="pink") ##CD8500
# 在棋盤裡面畫 畫格子
for num in range(1, self.gaird_count):
self.cv.create_line(num * self.gaird_width + 10,
self.gaird_width + 10,
num * self.gaird_width + 10,
self.gaird_width * (self.gaird_count - 1) + 10,
width=2,
fill="#595959")
for num in range(1, self.gaird_count):
self.cv.create_line(self.gaird_width + 10,
num * self.gaird_width + 10,
(self.gaird_count - 1) * self.gaird_width + 10,
num * self.gaird_width + 10,
width=2,
fill="#595959"
)
self.message = Label(self.root, text="開始游戲請先在菜單欄選擇模式！")
self.message.pack(side=BOTTOM)
# 初始化
# self.cv.bind("<Button-1>", self.paint2) # 左擊鼠標是黑子
self.flag = '' # flag記錄到誰，w代表白棋,b代表黑子
self.chess_b = np.zeros((15, 15), dtype=int)
self.xx= self.cv.create_line(- 10, - 10, 0, 0, arrow=tkinter.LAST)
# --------------------------------------菜單函數----------------------------------
def about_us(self):
about = Tk()
about.title('about us')
#about.iconphoto(True, PhotoImage(file='white.png'))
about.maxsize(400, 400)
about.minsize(400, 400)
label=Label(about,text='開發者：何元梅',bg='pink')
label.place(x=70, y=70,width='260',height='260')
about.mainloop()
def file_open(self):
pass
def player_W(self):
self.reset()
self.message.destroy()
self.flag = 'w' # flag記錄到誰，w代表白棋,b代表黑子
# 事件綁定
self.cv.bind("<Button-1>", self.paint) # 左擊鼠標是黑子
self.cv.bind("<Button-3>", self.paint) # 右擊鼠標是白子
self.message = Label(self.root, text="Turn to white player")
self.message.pack(side=BOTTOM)
# 雙人對弈 黑子先
def player_B(self):
self.reset()
self.message.destroy()
self.flag = 'b' # flag記錄到誰，w代表白棋,b代表黑子
# 事件綁定
self.cv.bind("<Button-1>", self.paint) # 左擊鼠標是黑子
self.cv.bind("<Button-3>", self.paint) # 右擊鼠標是白子
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
# 人機對弈，Ai先手
def person_first(self):
self.reset()
self.cv.bind("<Button-1>", self.paint_x) # 左擊鼠標是黑子
#人機對弈，Ai先手
def AI_first(self):
self.reset()
self.AI_start()
def AI_start(self):
# self.chess_b = np.zeros((16, 16), dtype=int)
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.flag = 'w'
ai = searcher(self.chess_b)
ai.board = self.chess_b
score, x, y = ai.search(2, 2)
#print('white（{0},{1}）'.format(x, y))
if self.chess_b[x][y] == 2 or self.chess_b[x][y] == 1:
pass
else:
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
self.flag = 'b'
flag1 = Winner.winner(self.chess_b)
if flag1 == 1:
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
messagebox.showinfo(title='victory', message='你贏啦！')
self.reset()
return 1
elif flag1 == 2:
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
messagebox.showinfo(title='defeat', message='AI勝利！')
self.reset()
return 2
else:
self.cv.bind("<Button-1>", self.paint_x) # 左擊鼠標是黑子
def paint_x(self,event):
self.message.destroy()
self.message = Label(self.root, text="Turn to white player")
self.message.pack(side=BOTTOM)
flag1 = Winner.winner(self.chess_b)
if self.flag == 'w' or flag1 == 1 or flag1 == 2:
pass
else:
x: int = int((event.x + 0.5 * self.gaird_width - 10) / self.gaird_width)
y: int = int((event.y + 0.5 * self.gaird_width - 10) / self.gaird_width)
#print('bule({0},{1})'.format(x, y))
if x == 0 or y == 0 or y > 15 or x > 15:
messagebox.showinfo(title='錯誤', message='該位置不允許放棋子！')
else:
if self.chess_b[x-1][y-1] == 2 or self.chess_b[x-1][y-1 ] == 1:
pass
else:
x1, y1 = (x * self.gaird_width), (y * self.gaird_width)
x2, y2 = (x * self.gaird_width + 20), (y * self.gaird_width + 20)
self.cv.create_image(int((x1+x2)/2), int((y1+y2)/2),image=self.black)
self.cv.update()
self.chess_b[x-1][y-1 ] = 1
flag1 = Winner.winner(self.chess_b)
if flag1 == 1:
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
messagebox.showinfo(title='恭喜', message='你贏啦！')
self.reset()
return 1
elif flag1 == 2:
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
messagebox.showinfo(title='sad', message='AI勝利！')
self.reset()
return 2
else:
#print('棋盤狀態：', self.chess_b)
self.AI_start()
#雙人對弈時，玩家畫棋子
def paint(self, event):
flag1 = Winner.winner(self.chess_b)
if flag1 == 1 or flag1 == 2:
pass
else:
x: int = int((event.x + 0.5 * self.gaird_width - 10) / self.gaird_width)
y: int = int((event.y + 0.5 * self.gaird_width - 10) / self.gaird_width)
print('white({0},{1})'.format(x, y))
if x == 0 or y == 0 or y > 15 or x > 15:
messagebox.showinfo(title='錯誤', message='該位置不允許放棋子！')
else:
if self.chess_b[y-1 ][x-1 ] == 2 or self.chess_b[y-1 ][x-1 ] == 1:
pass
else:
x1, y1 = (x * self.gaird_width), (y * self.gaird_width)
x2, y2 = (x * self.gaird_width + 20), (y * self.gaird_width + 20)
#self.cv.create_oval(x1, y1, x2, y2, fill=python_green)
if self.flag=='b':
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
else:
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[y-1][x-1] = 2 if self.flag=='w' else 1
self.flag = 'b' if self.flag=='w' else 'w'
self.message.destroy()
self.message = Label(self.root, text="Turn to white player") if self.flag=='w' else Label(self.root, text="Turn to bule player")
self.message.pack(side=BOTTOM)
flag1 = Winner.winner(self.chess_b)
if flag1 == 1:
messagebox.showinfo(title='恭喜', message='黑子勝利！')
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
return
elif flag1 == 2:
self.message.destroy()
self.message = Label(self.root, text="Game over")
self.message.pack(side=BOTTOM)
self.cv.update()
messagebox.showinfo(title='恭喜', message='白子勝利！')
self.reset()
return
else:
pass
def game_Chanllnenge1(self):
self.reset()
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.cv.update()
list_w = [(6, 6), (6, 7), (8, 6), (9, 6), (10, 5), (12, 5), (7, 8), (10, 9)]
list_b = [(5, 8), (7, 6), (8, 5), (8, 7), (9, 8), (10, 7), (10, 8), (11, 6)]
for li1 in list_w:
x = int(li1[0])
y = int(li1[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
for li2 in list_b:
x = int(li2[0])
y = int(li2[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
self.chess_b[x][y] = 1
self.cv.bind("<Button-1>", self.paint_x)
def game_Chanllnenge2(self):
self.reset()
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.cv.update()
list_w = [(3, 7), (5, 7), (6, 6), (10, 6), (8, 8), (8, 9), (9, 10), (7, 11), (6, 11), (4, 10), (10, 12), (7, 8)]
list_b = [(4, 8), (5, 9), (6, 10), (6, 9), (6, 8), (6, 7), (7, 7), (7, 9), (8, 10), (9, 11), (10, 8), (10, 7)]
for li1 in list_w:
x = int(li1[0])
y = int(li1[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
for li2 in list_b:
x = int(li2[0])
y = int(li2[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
self.chess_b[x][y] = 1
self.cv.bind("<Button-1>", self.paint_x)
def game_Chanllnenge3(self):
self.reset()
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.cv.update()
list_w = [(5, 6), (7, 6), (8, 6), (6, 7), (8, 7), (10, 6), (11, 6), (10, 7), (10, 4), (7, 9)]
list_b = [(4, 7), (6, 8), (6, 5), (9, 5), (10, 5), (9, 6), (11, 7), (6, 8), (7, 8), (7, 7), (8, 9)]
for li1 in list_w:
x = int(li1[0])
y = int(li1[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
for li2 in list_b:
x = int(li2[0])
y = int(li2[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
self.chess_b[x][y] = 1
self.cv.bind("<Button-1>", self.paint_x)
def game_Chanllnenge4(self):
self.reset()
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.cv.update()
list_w = [(6, 5), (7, 6), (6, 7), (9, 8), (9, 3), (10, 4), (10, 6), (6, 5)]
list_b = [(7, 5), (8, 5), (9, 5), (9, 4), (8, 6), (7, 7), (9, 6)]
for li1 in list_w:
x = int(li1[0])
y = int(li1[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
for li2 in list_b:
x = int(li2[0])
y = int(li2[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
self.chess_b[x][y] = 1
self.cv.bind("<Button-1>", self.paint_x)
def game_Chanllnenge5(self):
self.reset()
self.message.destroy()
self.message = Label(self.root, text="Turn to black player")
self.message.pack(side=BOTTOM)
self.cv.update()
list_w = [(3, 7), (8, 6), (8, 7), (8, 8), (7, 8), (6, 9), (8, 10), (5, 11)]
list_b = [(5, 7), (4, 8), (7, 7), (6, 8), (5, 9), (7, 9), (8, 9), (5, 10)]
for li1 in list_w:
x = int(li1[0])
y = int(li1[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.white)
self.chess_b[x][y] = 2
for li2 in list_b:
x = int(li2[0])
y = int(li2[1])
x1, y1 = ((x + 1) * self.gaird_width), ((y + 1) * self.gaird_width)
x2, y2 = ((x + 1) * self.gaird_width + 20), ((y + 1) * self.gaird_width + 20)
self.cv.create_image(int((x1 + x2) / 2), int((y1 + y2) / 2), image=self.black)
self.chess_b[x][y] = 1
self.cv.bind("<Button-1>", self.paint_x)
# <Button-1>：鼠標左擊事件
# <Button-2>：鼠標中擊事件
# <Button-3>：鼠標右擊事件
# <Double-Button-1>：雙擊事件
# <Triple-Button-1>：三擊事件
def main():
chess_Borad = chess_borad()
chess_Borad.root.mainloop()
main()