代码收藏家 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()
