你好,欢迎来到电脑编程技巧与维护杂志社! 杂志社简介广告服务读者反馈编程社区  
合订本订阅
 
 
您的位置:杂志经典 / 图形图象处理与游戏编程
5.2 五子棋人工智能权重估值算法(上)
 

一、五子棋介绍

五子棋是中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”,英译为“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为玩家12为玩家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 '是否玩家先行

注:以上声明均在模块中进行。

三、算法概述

    为了实现电脑行棋的人工智能化,需要实现对棋局面分析与估值的人工智能化。即实现对一定棋局的数值化反馈。首先应有一个函数来判断某一条直线上的棋形。根据单线棋形的不同,可将不同的单线棋形分为五字连线、活四、成四、活三等情况,再将反馈值交由一个局面评估函数进行量化处理,即得相应局面某点的评估分数的数值化表示。但进行量化处理的过程中需注意:每种棋形的得分值是唯一的,即程序头所确定的特殊棋形得分与所计算的不同棋形得分间不应存在交集。最后有一个取最优走法函数根据得分最高值取得相应的最佳走法。在算法实现的过程中有一定的近似计算,即只需判断两个方向上的单线棋形即可。这是科学的,因为多元(受棋子数、端堵情况、空子数三个变量制约)估值函数 接近实际值的必要而不充分条件为 (自变量 为相应棋形的棋子数),且由于三线共线棋形成立的条件为单线或双线棋形,其得分上也存在相应的继承性;故其与特殊棋形与计算分值间存在分值的量级差相一致。事实也证明,这样做明显提高了程序的执行效率。棋步处理流程如图1所示:

   图1 棋步处理流程图                

四、程序

首先建立基本界面。分别建立一个窗体和模块,并将窗体调整为合适长宽。VB中提供了强大的面向对象的设计功能,但为了提高程序模块化程度,所有关键变量均使用形参的形式传递。参数为实现画棋盘操作的窗体类。在模块中输入画棋盘函数:

Public Function Drawpad(ByRef FormTar As Form)  '用画直线命令画棋盘

    Dim i%: FormTar.DrawWidth = 3: FormTar.FillStyle = 1

        FormTar.Line (17, 16)-(20 + 30 * 14 + 3, 20 + 30 * 14 + 4), , B: FormTar.DrawWidth = 1: FormTar.FillStyle = 0

    For i = 0 To 14

        FormTar.Line (20, 30 * i + 20)-(20 + 30 * 14, 30 * i + 20)

        FormTar.Line (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)

'在画好棋盘的窗体上画棋子,参数Flag表示玩家的情况,数值与棋子的表示相同

    If Flag = 1 Then

        FormTar.FillColor = RGB(0, 0, 0)

        FormTar.Circle (20 + (XHorizontal - 1) * 30, 20 + (YVertical - 1) * 30), 13, RGB(255, 255, 255)

    ElseIf Flag = 2 Then

        FormTar.FillColor = RGB(255, 255, 255)

        FormTar.Circle (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, "黑棋", "白棋") & "获胜!", vbExclamation + vbOKOnly: GameOrNot = False '调用判断赢家函数判断胜负

    If CountNum = 220 Then MsgBox "和棋。", vbOKOnly + vbExclamation

End Function

数据能够实时更新后,又有了画棋子与画棋盘函数的支持;以下即为在前面几个函数基础之上的棋盘数据实时更新函数:

Public Function PadRefresh(ByRef FormTar As Form, ByRef Piece() As Integer) '棋盘恢复函数

    FormTar.Cls

    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)

'本函数用来返回一条直线上的结点,承载变量为XTarYTarXIntYInt为方向判断变量;注:本函数的待测坐标若为非空值则返回待测点坐标

    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,YInt)方向上最多只能有(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

  推荐精品文章

·2024年9月目录 
·2024年8月目录 
·2024年7月目录 
·2024年6月目录 
·2024年5月目录 
·2024年4月目录 
·2024年3月目录 
·2024年2月目录 
·2024年1月目录
·2023年12月目录
·2023年11月目录
·2023年10月目录
·2023年9月目录 
·2023年8月目录 

  联系方式
TEL:010-82561037
Fax: 010-82561614
QQ: 100164630
Mail:gaojian@comprg.com.cn

  友情链接
 
Copyright 2001-2010, www.comprg.com.cn, All Rights Reserved
京ICP备14022230号-1,电话/传真:010-82561037 82561614 ,Mail:gaojian@comprg.com.cn
地址:北京市海淀区远大路20号宝蓝大厦E座704,邮编:100089