目录
第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
3.3.2 基本设计
1．界面设计：基于tkinter设计的界面，包括游戏模式菜单、残局菜单，关于菜单三个部分组成，游戏模式菜单部分包括了人机对弈（AI先手）、人机对弈（玩家先手）、双人对弈（白子先手）、双人对弈黑子先手）等多种模式，各种模式的随意切换，突出程序灵活的特性。残局菜单栏我们设计了五种残局，难易程度程度依次递增，增强了游戏的趣味性，这个五个残局我们在网上小程序找的棋局，难度还可以。‘关于’菜单栏部分我们设计的事宜子界面，里面就显示我们小组开发过程负责的各模块的信息。
2. 棋盘设计：
我们的程序棋盘的显示部分是利用tkinter库的画布实现的，画布的背景设置为粉色，界面的美观性大大增强。在画布上画上1414的小格子表示棋盘，交点处放棋子，所以棋盘的大小为1515。程序中的棋盘对应15*15的二维数组chess_b，初始化为0，黑子用1填充数组，白子用2填充数组。至于画棋子，我们是根据棋盘数组将对应的位置用贴图的方法将黑棋白棋贴上去。
3. 胜负判断：
只需考虑横、竖、左斜和右斜四个方向，当棋盘数组chess_b中某个方向存在连续的五个‘1’或者‘2’时即黑子或者白子胜利，程序调用重置函数，清空棋盘，进入初始换界面，然后选择模式可继续开新局。
3.4 预处理
1.设定：
黑子：1
白子：2
空白：0
人机对弈时AI用白子，人用黑子。
2.五子棋估值函数主要的棋型：
五连：
五子棋是以谁先把五颗同色棋子连成一线为胜。 我们把五颗子同色棋子连在一起的棋形称为“五连”或‘“连五”。
def winner(chessboard):
#横方向
for i in range(15):
for j in range(0,11):
if chessboard[i][j]==chessboard[i][j+1]==chessboard[i][j+2]==chessboard[i][j+3]==chessboard[i][j+4]==1:
return 1
if chessboard[i][j]==chessboard[i][j+1]==chessboard[i][j+2]==chessboard[i][j+3]==chessboard[i][j+4]==2:
return 2
#竖方向
for j in range(15):
for i in range(0, 11):
if chessboard[i][j] ==chessboard[i+1][j]==chessboard[i+2][j]==chessboard[i+3][j]==chessboard[i+4][j] ==1:
return 1
if chessboard[i][j] ==chessboard[i+1][j]==chessboard[i+2][j]==chessboard[i+3][j]==chessboard[i+4][j] ==2:
return 2
#右斜
for i in range(4,15):
for j in range(11):
if chessboard[i][j] == chessboard[i -1][j+1] == chessboard[i -2][j+2] == chessboard[i - 3][j+3] == \
chessboard[i - 4][j+4] == 1:
return 1
if chessboard[i][j] == chessboard[i -1][j+1] == chessboard[i -2][j+2] == chessboard[i - 3][j+3] == \
chessboard[i - 4][j+4] == 2:
return 2
# 左斜
for i in range(10,-1,-1):
for j in range(11):
if chessboard[i][j] == chessboard[i + 1][j + 1] == chessboard[i + 2][j + 2] == chessboard[i + 3][j + 3] == \
chessboard[i + 4][j + 4] == 1:
return 1
if chessboard[i][j] == chessboard[i + 1][j + 1] == chessboard[i + 2][j + 2] == chessboard[i + 3][j + 3] == \
chessboard[i + 4][j + 4] == 2:
return 2
return 0
