五子棋人工智能权重估值算法
绝世美人儿
970次浏览
2021年01月18日 14:51
最佳经验
本文由作者推荐
文件删除了怎么恢复-适合毕业唱的歌
五子棋人工智能权重估值算法
一、五子棋介绍
五子棋是中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”,英
译为“Renju ”,英文称之为“Gobang”或“FIR”(Five in a Row
的缩写
),亦有
“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称
谓。 五子棋不仅能增强思维能力
,
提高智力
,
而且富含哲理
,
有 助于修身养性。五子
棋既有现代休闲的明显特征“短、平、快”,又有古典哲学的高深学问“阴阳易理”;既有简单易学的特性
,
为人民群众所喜闻乐见
,
又有深奥的技巧和 高水平的国
际性比赛
;
它的棋文化源渊流长
,
具有东方的神秘和西方 的直观
;
既有“场”的概念
,
亦有“点”的连接。它是中西文化的交流点,
是古今哲理的结晶。黑白双方依次落
子
,
任一方先在棋盘上形成横向、 竖向、斜向的连续的相同颜色的五个
(
含五个以上
)
棋子的一方为胜。这种规 则适合初学的五子棋爱好者。因为这种规则下黑棋胜算较
大。甚至已经有人证明在黑白双方都不出现错误 的情况下
,
黑棋可以必胜。所以一
般要求连续玩两盘
,
即任一方执黑
,
执白各一次。
二、逻辑变量与常量
逻辑变量与常量的分析如下
:
Public Const Five As Integer = 3000 '
五子连线得分
Public Const FFDL As Integer = 2900 '
双活四得分
Public Const FFSL As Integer = 2800 '
活四成四得分
Public Const FTDL As Integer = 2700 '
活四活三得分
Public Const FL As Integer = 2600 '
单活四得分
Public Const FFNL As Integer = 2500 '
双成四得分
Public Const FTSL As Integer = 2400 '
成四活三得分
Public Const TTDL As Integer = 2300 '
双活三得分
Public X%, Y% '
水平与垂直坐标
Public Xt%, Yt% '
临时横纵坐标
Public CountNum% '
棋步总数记录变量
Public Piece() As Integer ' 0
表示空闲
,1
为玩家
1,2
为玩家
2
Public Piecet() As Integer '
用于估值函数使用的临时数组
Public GameOrNot As Boolean '
是否游戏中
Public Flag As Byte '
行棋变量
,
表示该谁下棋
,
数值与棋子变量相同
Public PieceRec() As Integer '
定义棋步记录变量以记录所走棋步
Public AIOrNot As Boolean '
是否人机对战模式
,
人机对战则为
True
Public LBlock(4) As Boolean, RBlock(4) As Boolean '
左堵右堵记录变量
数组
Public EmptyNumE(4) As Byte '
定义空个数记录变量数组
Public PieceNum(4) As Byte '
定义棋子个数记录数组
Public ScoreE(4) As Integer '
定义得分数组
Public ScoreS As Integer '
定义得分记录空间变量
Public FirstMove As Boolean '
是否玩家先行
注
:
以上声明均在模块中进行。
三、算法概述
为了实现电脑行棋的人工智能化
,
需要 实现对棋局面分析与估值的人工智能
化。即实现对一定棋局的数值化反馈。首先应有一个函数来判断某一 条直线上的棋
形。根据单线棋形的不同
,
可将不同的单线棋形分为五字连线、活四、成 四、活三
等情况
,
再将反馈值交由一个局面评估函数进行量化处理
,
即得相应局面某点的评估
分数的数值化表示。但进行量化处理的过程中需注意
:
每种棋 形的得分值是唯一的
,
即程序头所确定的特殊棋形得分与所计算的不同棋形得分间不应存在交集 。最后有
一个取最优走法函数根据得分最高值取得相应的最佳走法。在算法实现的过程中有
一定 的近似计算
,
即只需判断两个方向上的单线棋形即可。这
是科 学的
,
因为多元
(
受棋子数、端堵情况、空子数三个变量制约
)估值函数
接近实际值的必要而不充分条件为
(
自变量为相应棋形的棋
< br>子数
),
且由于三线共线棋形成立的条件为单线或双线棋形
,
其得分上 也存在相
应的继承性
;
故其与特殊棋形与计算分值间存在分值的量级差相一致。事实也 证明
,
这样做明显提高了程序的执行效率。
四、程序
首先建立基本界面。分别建立一个窗体和模块
,
并将窗体调整为合适长宽。
VB
中提供了强大的面向对象的设计功能
,
但为了提高程序模块化程度
,
所有关键变量均
使用形参的形式传递。参数为实现画棋盘操作的窗体类。在模块中输入画棋 盘函数
:
Public Function Drawpad(ByRef FormTar As Form) '
用画直线命令画棋盘
Dim i%: dth = 3: yle = 1
(17, 16)-(20 + 30 * 14 + 3, 20 + 30 * 14 + 4), , B:
dth = 1: yle = 0
For i = 0 To 14
(20, 30 * i + 20)-(20 + 30 * 14, 30 * i + 20)
(20 + i * 30, 20)-(20 + 30 * i, 20 + 14 * 30)
Next i
End Function
以下是画棋子 函数。首参为欲实现画棋子操作的窗体类
,
第二个参数为欲画棋
子在棋盘上的水平坐标
,
第三参数为欲画棋子在棋盘上竖直方向的纵坐标
,
第四参数
为代表 玩家信息的身份变量。
Public Function DrawPiece(ByRef FormTar As Form, ByVal XHorizontal%,
ByVal YVertical%, ByVal Flag As Byte)
'
在画好棋盘的窗体上画棋子
,
参数
Fl ag
表示玩家的情况
,
数值与棋子的表示
相同
If Flag = 1 Then
lor = RGB(0, 0, 0)
(20 + (XHorizontal - 1) * 30, 20 + (YVertical - 1) *
30), 13, RGB(255, 255, 255)
ElseIf Flag = 2 Then
lor = RGB(255, 255, 255)
(20 + (XHorizontal - 1) * 30, 20 + (YVertical - 1) *
30), 13, RGB(0, 0, 0)
End If
End Function
除了棋盘界面的画棋子函数
,
需要实现棋局数组在棋 盘上的动态显示
;
可利用
两个函数访问保存棋局信息的数组
,
并调用 画棋盘与画棋子函数来动态更新棋盘之
显示。以下即为实现动态变更棋子数组的落子函数
:
Public Function LayPiece(ByRef Piece() As Integer, ByVal XInt%,
ByVal YInt%, ByVal Flag As Byte) '
落子
Piece(XInt, YInt) = Flag: X = XInt: Y = YInt: CountNum = CountNum +
1
PieceRec(SearchNode(PieceRec) + 1) = (YInt - 1) * 15 + XInt
'
扩大记步数组变量范围以保存本步
If JudgeWinner(Piece, XInt, YInt, Flag) = True Then MsgBox IIf(Flag
= 1,
黑棋
白棋
获胜
!
False '
调用判断赢家函数判断胜负
If CountNum = 220 Then MsgBox
和棋。
End Function
数据能够实时更新后
,
又有了画棋子与画棋盘函数的支持
;
以下即为在前面几
个函数基础之上的棋盘数据实时更新函数
:
Public Function PadRefresh(ByRef FormTar As Form, ByRef Piece() As
Integer) '
棋盘恢复函数
Drawpad FormTar
Dim i%, j%
For i = 1 To 15
For j = 1 To 15
If Piece(i, j) <> 0 Then DrawPiece FormTar, i, j, Piece(i, j)
'
如果该位置非空子
,
则画棋子
Next j
Next i
End Function
在单线棋形判断函数基础之上的玩家胜负判断函数
:
Public Function JudgeWinner(ByRef Piece() As Integer, ByVal XInt%,
ByVal YInt%, ByVal Flag As Byte) As Boolean '
棋局胜负判断函数
X = XInt: Y = YInt
If JudgeNum(Piece, 1, 0, Flag) >= 5 Or JudgeNum(Piece, 1, 1,
Flag) >= 5 Or JudgeNum(Piece, 0, 1, Flag) >= 5 Or JudgeNum(Piece, -1, 1,
Flag) >= 5 Then _
JudgeWinner = True: Exit Function '
判断标记为
Flag
的玩家是否已胜利
JudgeWinner = False
End Function
本程序为了实现动态 判断是否有棋可悔
,
悔棋存储数组逻辑实质为堆栈结
构
;VB
中未提 供现成的
Stack
类
,
需要以下函数来完成对数组栈顶的搜索工作。
Public Function SearchNode(ByRef PieceRec() As Integer) As Integer '
寻找
棋步记录数组中的最大定义值
Dim i%
For i = 225 To 1 Step -1
If PieceRec(i) <> 0 Then Exit For
Next i
SearchNode = i
End Function
Public Function GetNode(ByRef PieceTar() As Integer, ByRef XTar%,
ByRef YTar%, ByVal Xt%, ByVal Yt%, ByVal XInt%, ByVal YInt%, ByVal Flag
As Byte) '
本函数用来返回一条直线上的结 点
,
承载变量为
XTar,YTar;XInt
和
YInt
为方向判断变量
;
注
:
本函数的待测坐标若为非空值则返回待测点坐标
Dim i%, j%
i = Xt: j = Yt
Do
i = i + XInt: j = j + YInt
If PieceTar(i, j) <> Flag Then Exit Do
Loop Until i < 1 Or i > 15 Or j < 1 Or j > 15
XTar = i - XInt: YTar = j - YInt
End Function
为了判断玩家的获胜情况
,需要一个执行效率较高的函数来判断单线棋形最大
棋子数。以下函数实现了上述功能。第二和第三参 数两两决定了四种棋盘方向。
Public Function JudgeNum(ByRef Piece() As Integer, ByVal XFluctuate%,
ByVal YFluctuate%, ByVal Flag As Byte) As Integer
'
判断最多有多少棋子共线
(
连续
),
这是执行效率较高的 一种算法
Dim i%, j%, Value%: i = X: j = Y: Value = 0
Do
If Piece(i, j) <> Piece(X, Y) Then Exit Do
i = i + XFluctuate: j = j + YFluctuate '
分别在两个方向上加上改变量
,
下同
Value = Value + 1
Loop Until i < 1 Or i > 15 Or j < 1 Or j > 15
i = X: j = Y
Do
If Piece(i, j) <> Piece(X, Y) Then Exit Do
i = i - XFluctuate: j = j - YFluctuate
Value = Value + 1
Loop Until i < 1 Or i > 15 Or j < 1 Or j > 15
JudgeNum = Value - 1 '
减去落子点本身所代表的重复计算过一次的
1 End
Function
为了在窗体棋盘上某一点恰当地估值
,
需要分析在该点处的落子前后棋形之 差
异。而棋形判断函数又分为单线和多线两类
,
多线以单线为基础
,
再利用数组排序选
出最高的两值作为多线棋形判断依据。单线棋形制约因素主要有三个
:
棋子数、端
堵情况和空子数。实现的核心代码如下
:
Public Function JudgeLineNum(ByRef PieceTar() As Integer, ByVal Xt%,
ByVal Yt%, ByVal XInt%, ByVal YInt%, ByVal ArrNum As Byte, ByVal Flag As
Byte) As Byte
'
单线棋形判断函数
,
用来判断棋形并计算相应分值
;
参数
ArrNum
代表的是储
存方向 情况与得分情况的数组成员序号
,
定义为
1
为
(1,0),2
为
(1,1),3
为
(0,1), 4
为
(-1,1);
实现算法的关键是基础的单线棋形的判断与反馈
Dim ExitFor As Boolean, LB As Boolean, RB As Boolean, PieceNum%,
EmptyNum%, i%, Xtmp%, Ytmp%, Count%, Score%, Value%
Xtmp = Xt: Ytmp = Yt: PieceNum = 1: EmptyNum = 0: Count = 0 '
初始时
棋子个数为
1
For i = 1 To 4 '
计算第一个方向
ExitFor = True '
循环开始处初始化跳出记录变量为真
Count = Count + 1
Xt = Xtmp - i * XInt: Yt = Ytmp - i * YInt
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then LB = True: Exit For
'
如果减去递增变量后坐标出界
,
则左堵为真
If PieceTar(Xt, Yt) = Flag Then PieceNum = PieceNum + 1 '
若下一位置
处棋子类型相同
,
则将相同棋子记录变量加
1
If PieceTar(Xt, Yt) = IIf(Flag = 1, 2, 1) Then LB = True: Exit For
'
该位置处棋子类型相反
,
则左堵为真
If PieceTar(Xt, Yt) = 0 Then
Xt = Xt - XInt: Yt = Yt - YInt '
若该位置处为空格
,
则进一步判断下一个
位置
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then LB = False: Exit For
'
若下一个位置出界
,
则左堵为假
If PieceTar(Xt, Yt) = 0 Then LB = False: Exit For
'
若下一个位置仍为空格
,
则左堵为假
If PieceTar(Xt, Yt) = Flag Then EmptyNum = EmptyNum + 1 '
若空后位置
处与目标棋子类型相同
,
则将空格数加
1
If PieceTar(Xt, Yt) = IIf(Flag = 1, 2, 1) Then LB = False: Exit For
'
若空位置后为相反棋子类型则左堵亦为假
End If
ExitFor = False
Next i
If ExitFor = False Then
Xt = Xt - XInt: Yt = Yt - YInt
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then
LB = True '
若最后一子后一位置出界
,
则左堵为真
ElseIf PieceTar(Xt, Yt) = 0 Then LB = False
ElseIf PieceTar(Xt, Yt) = IIf(Flag = 1, 2, 1) Then LB = True End If
Else: Count = Count - 1 '
提前跳出循环的情况下
,
在
(XInt,YIn t)
方向上最
多只能有
(Count-1)
个子
End If
Xt = Xtmp: Yt = Ytmp
For i = 1 To 4 - Count '
计算前面的相反方向
ExitFor = True
Xt = Xtmp + i * XInt: Yt = Ytmp + i * YInt
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then RB = True: Exit For
If PieceTar(Xt, Yt) = Flag Then PieceNum = PieceNum + 1
If PieceTar(Xt, Yt) = IIf(Flag = 1, 2, 1) Then RB = True: Exit For
If PieceTar(Xt, Yt) = 0 Then
Xt = Xt + XInt: Yt = Yt + YInt
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then RB = False: Exit For
If PieceTar(Xt, Yt) = 0 Then RB = False: Exit For
If PieceTar(Xt, Yt) = Flag Then EmptyNum = EmptyNum + 1 If
PieceTar(Xt, Yt) = IIf(Flag = 1, 2, 1) Then RB = False: Exit For
End If
ExitFor = False
Next i
If ExitFor = False Then
Xt = Xt + XInt: Yt = Yt + YInt
If Xt < 1 Or Xt > 15 Or Yt < 1 Or Yt > 15 Then
RB = True
ElseIf PieceTar(Xt, Yt) = 0 Then RB = False
ElseIf PieceTar(Xt, Yt) = IIf(Flag = 2, 1, 2) Then RB = True End If
End If
LBlock(ArrNum) = LB: RBlock(ArrNum) = RB: Value = IIf(EmptyNum = 0,
5 ^ PieceNum, 5 ^ PieceNum - 5 ^ EmptyNum)
EmptyNumE(ArrNum) = EmptyNum
'
左右状态赋值给其相应的记录数组
;
并将分值赋给相应记分数组
ScoreE(ArrNum) = IIf(RB, IIf(LB, 1, Value / 2), IIf(LB, Value / 2,
Value))
JudgeLineNum = PieceNum '
返回最大共线子数
End Function
在单线棋形判断函数的基础上
,
可评估某点综合棋局情况时多重方向上的棋形
叠加。如前所述
,
用冒泡排序法 选出两种最优单线棋形得分
;
这样做在不改变程序核
心的权重估值算法的前提下很大程 度上提高了程序执行效率。以下为多线棋形评估
函数
:
Public Function DoGen(ByRef PieceTar() As Integer, ByVal Xt%, ByVal
Yt%, ByVal Flag As Byte) '
棋局综合情况评估函数
PieceNum(1) = JudgeLineNum(Piece, Xt, Yt, 1, 0, 1, Flag)
'
在调用函数进行数组赋值时可以同时进行返回值处理
PieceNum(2) = JudgeLineNum(Piece, Xt, Yt, 1, 1, 2, Flag)
PieceNum(3) = JudgeLineNum(Piece, Xt, Yt, 0, 1, 3, Flag)
PieceNum(4) = JudgeLineNum(Piece, Xt, Yt, -1, 1, 4, Flag) Call
ArraySort(ScoreE, PieceNum, EmptyNumE, LBlock, RBlock)
'
调用数组排序函数对得分数组进行排序
If (LBlock(1) = False And RBlock(1) = False) And (LBlock(2) = False
And LBlock(2) = False) And PieceNum(1) = 4 And PieceNum(2) = 4 Then _
DoGen = FFDL: Exit Function '
如果双活四则返回双活四得分
If ((LBlock(2) = False And RBlock(2) = True) Or (LBlock(2) = True
And RBlock(2) = False)) And (LBlock(1) = False And RBlock(1) = False)
And PieceNum(1) = 4 _
And PieceNum(2) = 4 Then DoGen = FFSL: Exit Function '
返回成四与活
四得分
If (LBlock(1) = False And RBlock(1) = False) And (LBlock(2) = False
And RBlock(2) = False) And PieceNum(1) = 4 And PieceNum(2) = 3 Then _
DoGen = FTDL: Exit Function '
返回活四活三得分