目錄
第1章 問題描述 3
第2章 問題分析 3
第3章 算法設計 4
3.1 算法概述 4
3.2 Very small tree 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章 Results presentation and performance analysis 18
5.1 成果展示 18
5.2 性能分析 23
第6章 結論與心得體會 23
6.1 結論 23
6.2 實驗心得 24
參考文獻 28
第1章 問題描述
Our backgammon game is two-player、Gobang problem with complete information,That is to say, the rules of the game are strict rotation of the two sides,And either party can fully know the steps the other party has taken and all the steps that can be taken in the future,When a party has five consecutive sons in a straight line,游戲結束.The game mode can be divided into two modes: man-machine game and two-player game.The two-player game mode is relatively easy to implement,The program only needs to decide whether to produce a winner.The human-machine game mode requires our program code to realize the selection and determination of the position of the machine's move,This procedure is based on heuristicsMAX/MIN算法的alpha-betaPruning technology to choose the best machine placement.除此之外,We also set up an endgame mode,It brings a better gaming experience to users while increasing the fun of the game.
第2章 問題分析
To implement a basic backgammon game,The problem we have to face can be roughly summed up as how to judge the winner or loser,How to strictly limit the two sides to take turns playing chess,The presentation form of the game interface and most importantly, how to determine the best position for the machine to move.After an initial discussion with our team,In the end, it was decided that the game was presented in an interface,When the user plays chess, they can directly click the mouse on the position where they want to move.As for judging victory or defeat, you only need to write a simple function,from the horizontal、豎、斜上、The judgment can be realized by gradually judging whether there are five consecutive pieces of the same color in four directions.Strictly control both sides taking turns to pass the changeflagThe value of , indirectly determines which side is playing at the current position,Then, it is implemented to play chess in turn by calling each other's functions of each other's moves.
The last is to solve the most critical problem：How to choose the best position for the machine to move in the man-machine game mode,This is the core part of our entire program code,It is also the most difficult part of the algorithm implementation.As described in the title of this course design,After discussion, we decided to use heuristicsMAX/MIN算法的alpha-betaPruning technology to accurately and relatively quickly determine the placement of the machine,其中涉及到的alpha-betaThe specific implementation of the technology and used to determine the best location“Scoring mechanism”It will be elaborated in later modules.
至此,We have basically completed the overall problem analysis of the Gobang game,All that's left is some interface optimization,Non-critical issues such as endgame score design,Our team finally achieved a functional improvement through continuous practice and optimization,Gobang game with beautiful interface and smooth operation.
本文轉載自：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="雙人模式（Bai Zixian）", command=self.player_W)
filemenu.add_command(label="雙人模式（Sunspot first）", 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)
# Add the first three menus to the menu bar
self.menubar.add_cascade(label="開始游戲", menu=filemenu)
self.menubar.add_cascade(label="殘局挑戰", menu=editmenu)
self.menubar.add_cascade(label="關於我們", menu=helpmenu)
# Finally, add the entire menu bar to the window 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="To start the game, please select the mode in the menu bar first！")
self.message.pack(side=BOTTOM)
self.reset()
# Empty and reset the board function
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)
# Draw an outer border of white , Fill the checkerboard color
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
# Draw inside the chessboard 畫格子
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="To start the game, please select the mode in the menu bar first！")
self.message.pack(side=BOTTOM)
# 初始化
# self.cv.bind("<Button-1>", self.paint2) # Left-clicking the mouse is a sunspot
self.flag = '' # flagWho is recorded,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='開發者：He Yuanmei',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' # flagWho is recorded,w代表白棋,b代表黑子
# 事件綁定
self.cv.bind("<Button-1>", self.paint) # Left-clicking the mouse is a sunspot
self.cv.bind("<Button-3>", self.paint) # Right-click the mouse is a white child
self.message = Label(self.root, text="Turn to white player")
self.message.pack(side=BOTTOM)
# 雙人對弈 Sunspot first
def player_B(self):
self.reset()
self.message.destroy()
self.flag = 'b' # flagWho is recorded,w代表白棋,b代表黑子
# 事件綁定
self.cv.bind("<Button-1>", self.paint) # Left-clicking the mouse is a sunspot
self.cv.bind("<Button-3>", self.paint) # Right-click the mouse is a white child
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) # Left-clicking the mouse is a sunspot
#人機對弈,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) # Left-clicking the mouse is a sunspot
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='No pawns are allowed in this position！')
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()
#When playing a two-player game,Players draw chess pieces
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='No pawns are allowed in this position！')
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='Sunspot wins！')
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='White wins！')
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()
