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("", 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("", self.paint)  # 左击鼠标是黑子
        self.cv.bind("", 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("", self.paint)  # 左击鼠标是黑子
        self.cv.bind("", 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("", 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("", 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("", 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("", 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("", 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("", 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("", 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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464