五子棋的人工智能

yutian

五子棋的人工智能

                                                          ———— 利用策略类AI和vb.net实现五子棋

                                                                                    作者：张宇

                                                        引言

              人工智能也就是所谓的AI(Artificial Intelligence)，它是一门很抽象的技术，AI程序的编写不需要依据任何既定的思考模式或者规则。尤其是游戏中的AI可以完全依程序设计者本身的思考逻辑制作。我个人认为人工智能的核心应该是使计算机具有自动的处理事件的能力，而我们的所有的研究也应该围绕着这一方向。我们今天讨论的是策略类的人工智能。

              策略类人工智能可以说是AI中比较复杂的一种，最常见的策略类AI游戏就是棋盘式游戏。在这类游戏中，通常的策略类AI程序都是使计算机判断目前状况下所有可走的棋与可能的获胜状况，并计算当前计算机可走棋步的获胜分数或者玩家可走棋步的获胜分数，然后再决定出一个最佳走法。下面我们先介绍一下五子棋的AI构想。

                                                 第一部分       五子棋的AI构想

              有句话叫“当局者迷，旁观者清。”，但这句话在由AI所控制的计算机玩家上是不成立的，因为计算机必须知道有那些获胜方式，并计算出每下一步棋到棋盘上任一格子的获胜几率，也就是说，一个完整的五子棋的AI构想必须：1,能够知道所有的获胜组合，2,建立和使用获胜表，3，设定获胜的分数，4，使电脑具有攻击和防守的能力。

一，求五子棋的获胜组合

在一场五子棋的游戏中，计算机必须要知道有那些的获胜组合，因此我们必须求得

获胜组合的总数。我们假定当前的棋盘为10*10。

              （1），计算水平方向的获胜组合数，每一列的获胜组合是：6，共10列，所以水平方向的获胜组合数为：6*10=60

              （2），计算垂直方向的获胜组合总数，每一行的获胜组合是：6，共10行，则垂直方向的获胜组合数为：6*10=60

              （3），计算正对角线方向的获胜组合总数，正对角线上的获胜组合总数为6+（5+4+3+2+1）*2=36

              （4），计算反对角线方向的获胜组合总数，反对角线上的获胜组合总数为6+（5+4+3+2+1）*2=36

              这样所有的获胜组合数为：60+60+36+36=192

二，建立和使用获胜表

              我们已经计算出了一个10*10的五子棋盘会有192种获胜方式，这样我们可以利用数组建立获胜表，获胜表的主要作用是：1，判断当前的获胜方式是否有效；2，判断当前的获胜方式中到底有多少子落入该获胜组合中。详细的使用您将在后面的程序中可以看出。

三，分数的设定

在游戏中为了让计算机能够决定下一步最佳的走法，必须先计算出计算机下到棋盘

上任一空格的分数，而其中最高分数便是计算机下一步的最佳走法。

原理：我们判定当前讨论的空格与当前讨论的点有几种获胜的方式，有几种该空格就加几分。这种原理初听起来似乎是无法入手，没关系，当您了解我们后面的程序后您就会明白这种决策原理了。

这种决策有一些缺陷，因为如果只根据这个模型设计，就有可能出现电脑或玩家有三个子连成一线的时候，计算机却判断不出，它认为其他某些空格是当前的获胜的最佳位置而不去攻击或防守。没关系我们完全可以通过一个加强算法来改变当前的分值情况，也就是说当电脑或玩家有三个子或四个子连成一线时，我们通过加强算法将当前与三个子或四个子有关的空格的分值提高，从而可以弥补这一缺憾。

四，攻击与防守

              以上的方式，事实上计算机只是计算出了最佳的攻击位置，为了防守我们还应计算当前玩家的最佳的攻击位置。这样有什么用呢？道理很简单，如果玩家最佳攻击位置的分数大于计算机最佳攻击位置上的分数，那么计算机就将下一步的棋子摆在玩家的最佳攻击位上以阻止玩家的进攻，否则计算机便将棋子下在自己的最佳攻击位置上进行攻击。

              事实上，这个AI构想是很强大的如果你不是很厉害的五子棋高手的话，可能很快会被计算机打败。我在联众上可是中级棋手啊，跟这种构想打的时候胜率也不是很高。

yutian

五子棋的人工智能

                                                          ———— 利用策略类AI和vb.net实现五子棋

                                                                                    作者：张宇

   

                                                 第二部分       使用vb.net编写五子棋

一，编写前的准备：

1，  用计算机的思想描述整个下棋的过程。

考虑步骤：

（1）为了简便我们可以先让电脑先走第一步棋，电脑每走一步就会封掉许多玩家的获胜可能情况。

（2）当玩家走棋的时候我们首先应该考虑玩家走棋的合法性。

（3）如果合法，那么玩家也会封掉许多电脑的获胜的可能情况。

（4）电脑的思考路径：首先判断当前玩家和电脑的所有获胜组合是否需要进行加强赋值，

是进行加强赋值，否则进行普通的赋值。

（5）比较当前玩家和电脑谁的分值最大。将分值最大的点作为电脑的下一步走法。

2，  利用vb.net窗体和图形工具建立五子棋的棋盘界面。

（1）添加一个picturebox控件。

              作用：使用picturebox控件绘制棋子和棋盘

（2）添加一个label控件。

              作用：显示当前的获胜标志，也就是当某一方获胜或和棋时显示此标签。

（3）添加一个mainmenu控件。

              作用：控制游戏的开始或结束。

（4）添加一个mediaplay组件。

              作用：使程序可以播放音乐。

3，设置整体框价

       我们采取10*10的棋盘，为主要的平台。利用数组定义整个棋盘桌面，利用数组定义获胜组合以及获胜标志等。

二，声明全局数组和变量

定义虚拟桌面：

Dim table(9, 9) As Integer

定义当前玩家桌面空格的分数：

Dim pscore(9, 9) As Integer

定义当前电脑桌面空格的分数：

Dim cscore(9, 9) As Integer

定义玩家的获胜组合：

Dim pwin(9, 9, 191) As Boolean

定义电脑的获胜组合：

Dim cwin(9, 9, 191) As Boolean

定义玩家的获胜组合标志：

Dim pflag(191) As Boolean

定义电脑的获胜组合标志：

Dim cflag(191) As Boolean

定义游戏有效标志：

Dim theplayflag As Boolean

三，初始化游戏

    '*****************************************************************************

    '** 模块名称:  initplayenvironment

    '**

    '** 描述:        此函数主要功能如下:

    '**                 1. 设置背景音乐。

    '**                 2. 设置游戏状态有效。

    '**                 3. 初始化游戏状态标签。

    '**                 4. 直接指定电脑的第一步走法。

    '**                 5. 初始化基本得分桌面。

    '**                 6. 电脑和玩家获胜标志初始化。

    '**                 7. 初始化所有获胜组合。

    '**                 8. 重新设定玩家的获胜标志。

    '**

    '*****************************************************************************

    Sub initplayenvironment()

        player.FileName = ".\music\zhyu01.mid"

        player.Play()

        theplayflag = True

        '游戏有效

        Label1.Visible = False

        '游戏状态标签不显示

        PictureBox1.Refresh()

        '清空picturebox1的内容

        yuandian(130, 130)

        '调用绘图函数绘制当前电脑先走的位置

        Dim i, j, m, n As Integer

        For i = 0 To 9

            For j = 0 To 9

                table(i, j) = 0

            Next

        Next

        '桌面初始化

        For i = 0 To 191

            pflag(i) = True

            cflag(i) = True

        Next

        '获胜标志初始化

        table(4, 4) = 1

        '由于我们设定电脑先手，并下了4，4位所以将其值设为1

        ''' ********                       初始化获胜组合                 ********

        n = 0

        For i = 0 To 9

            For j = 0 To 5

                For m = 0 To 4

                    pwin(j + m, i, n) = True

                    cwin(j + m, i, n) = True

                Next

                n = n + 1

            Next

        Next

        For i = 0 To 9

            For j = 0 To 5

                For m = 0 To 4

                    pwin(i, j + m, n) = True

                    cwin(i, j + m, n) = True

                Next

                n = n + 1

            Next

        Next

        For i = 0 To 5

            For j = 0 To 5

                For m = 0 To 4

                    pwin(j + m, i + m, n) = True

                    cwin(j + m, i + m, n) = True

                Next

                n = n + 1

            Next

        Next

        For i = 0 To 5

            For j = 9 To 4 Step -1

                For m = 0 To 4

                    pwin(j - m, i + m, n) = True

                    cwin(j - m, i + m, n) = True

                Next

                n = n + 1

            Next

        Next

        ''' ********                        初始化获胜组合结束                ********

        For i = 0 To 191

            If pwin(4, 4, i) = True Then

                pflag(i) = False

            End If

        Next

        '由于电脑已下了4，4位所以我们需要重新设定玩家的获胜标志

    End Sub

yutian

五子棋的人工智能

                                                          ———— 利用策略类AI和vb.net实现五子棋

                                                                                    作者：张宇

    四，处理鼠标事件

    '*****************************************************************************

    '** 模块名称:  themousedown

    '**

    '** 描述:       此函数主要实行以下功能：

    '**                 1. 判定当前游戏标志是否有效。

    '**                 2. 将实际坐标转化成虚拟坐标。

    '**                 3. 绘制玩家的棋子。

    '**                 4. 执行检查获胜函数。

    '**                 5. 执行电脑算法函数。

    '**

    '*****************************************************************************

    Sub themousedown(ByVal x As Integer, ByVal y As Integer)

        If theplayflag = False Then

            Exit Sub

        End If

        '检查游戏状态是否有效

        Dim i, j As Integer

        Dim zhx, zhy As Integer

        zhx = Int((x - 10) / 30)

        zhy = Int((y - 10) / 30)

        For i = 0 To 9

            For j = 0 To 9

                If table(zhx, zhy) >; 0 Then

                    Exit Sub

                End If

            Next

        Next

        '检查当前鼠标点击的格子是否有效

        Dim mycolor As Color

        Dim g As System.Drawing.Graphics

        g = PictureBox1.CreateGraphics

        mycolor = Color.White

        Dim brush1 As System.Drawing.Brush = New SolidBrush(mycolor)

        g.FillEllipse(brush1, zhx * 30 + 10, zhy * 30 + 10, 30, 30)

        '绘制玩家的棋子

        table(zhx, zhy) = 2

        For i = 0 To 191

            If cwin(zhx, zhy, i) = True Then

                cflag(i) = False

            End If

        Next

        '重设电脑的获胜标志

        checkwin()

        '检查当前玩家是否获胜

        diannao()

        '调用电脑算法

    End Sub

五，获胜检查算法。

    '*****************************************************************************

    '** 模块名称:  checkwin

    '**

    '** 描述:       此模块执行以下功能:

    '**                 1. 检查是否和棋。

    '**                 2. 检查电脑是否获胜。

    '**                 3. 检查玩家是否获胜。

    '**

    '*****************************************************************************

    Sub checkwin()

        Dim i, j, k, m, n As Integer

        Dim ca As Integer

        Dim pa As Integer

        Dim cnormal As Integer = 0

        For i = 0 To 191

            If cflag(i) = False Then

                cnormal = cnormal + 1

            End If

        Next

        If cnormal = 190 Then

            Label1.Visible = True

            Label1.Text = "和棋，请重新开始！"

            PictureBox1.Refresh()

            theplayflag = False

            Exit Sub

        End If

        '设定和棋规则

        For i = 0 To 191

            If cflag(i) = True Then

                ca = 0

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 1 Then

                            If cwin(j, k, i) = True Then

                                ca = ca + 1

                            End If

                        End If

                    Next

                Next

                If ca = 5 Then

                    Label1.Visible = True

                    Label1.Text = "电脑获胜,请重新开始"

                    PictureBox1.Refresh()

                    theplayflag = False

                    Exit Sub

                End If

            End If

        Next

        '检查电脑是否获胜

        For i = 0 To 191

            If pflag(i) = True Then

                pa = 0

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 2 Then

                            If pwin(j, k, i) = True Then

                                pa = pa + 1

                            End If

                        End If

                    Next

                Next

                If pa = 5 Then

                    Label1.Visible = True

                    Label1.Text = "玩家获胜,请重新开始"

                    PictureBox1.Refresh()

                    theplayflag = False

                    Exit Sub

                End If

            End If

        Next

        '检查玩家是否获胜

    End Sub

yutian

五子棋的人工智能

                                                          ———— 利用策略类AI和vb.net实现五子棋

                                                                                    作者：张宇

  六，电脑算法（1）

    '*****************************************************************************

    '** 模块名称:  diannao

    '**

    '** 描述:   此程序主要执行以下功能：

    '**                 1. 初始化赋值系统。

    '**                 2. 赋值加强算法。

    '**                 3. 计算电脑和玩家的最佳攻击位。

    '**                 4. 比较电脑和玩家的最佳攻击位并决定电脑的最佳策略。

    '**                 5. 执行检查获胜函数。

    '**

'*****************************************************************************



    Sub diannao()

        Dim i, j, k, m, n As Integer

        Dim dc As Integer

        Dim cab As Integer

        Dim pab As Integer

        For i = 0 To 9

            For j = 0 To 9

                pscore(i, j) = 0

                cscore(i, j) = 0

            Next

        Next

        '初始化赋值数组

        ''' ********                        电脑加强算法                ********

        For i = 0 To 191

            If cflag(i) = True Then

                cab = 0

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 1 Then

                            If cwin(j, k, i) = True Then

                                cab = cab + 1

                            End If

                        End If

                    Next

                Next

                Select Case cab

                    Case 3

                        For m = 0 To 9

                            For n = 0 To 9

                                If table(m, n) = 0 Then

                                    If cwin(m, n, i) = True Then

                                        cscore(m, n) = cscore(m, n) + 5

                                    End If

                                End If

                            Next

                        Next

                    Case 4

                        For m = 0 To 9

                            For n = 0 To 9

                                If table(m, n) = 0 Then

                                    If cwin(m, n, i) = True Then

                                        yuandian(m * 30 + 10, n * 30 + 10)

                                        table(m, n) = 1

                                        For dc = 0 To 191

                                            If pwin(m, n, dc) = True Then

                                                pflag(dc) = False

                                                checkwin()

                                                Exit Sub

                                            End If

                                        Next

                                    End If

                                End If

                            Next

                        Next

                End Select

            End If

        Next

        For i = 0 To 191

            If pflag(i) = True Then

                pab = 0

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 2 Then

                            If pwin(j, k, i) = True Then

                                pab = pab + 1

                            End If

                        End If

                    Next

                Next

                Select Case pab

                    Case 3

                        For m = 0 To 9

                            For n = 0 To 9

                                If table(m, n) = 0 Then

                                    If pwin(m, n, i) = True Then

                                        pscore(m, n) = pscore(m, n) + 30

                                    End If

                                End If

                            Next

                        Next

                    Case 4

                        For m = 0 To 9

                            For n = 0 To 9

                                If table(m, n) = 0 Then

                                    If pwin(m, n, i) = True Then

                                        yuandian(m * 30 + 10, n * 30 + 10)

                                        table(m, n) = 1

                                        For dc = 0 To 191

                                            If pwin(m, n, dc) = True Then

                                                pflag(dc) = False

                                                checkwin()

                                                Exit Sub

                                            End If

                                        Next

                                    End If

                                End If

                            Next

                        Next

                End Select

            End If

        Next

        ''' ********                   电脑加强算法结束                       ********

yutian

子棋的人工智能

                                                      ———— 利用策略类AI和vb.net实现五子棋

                                                                                    作者：张宇



六电脑算法（2）

''' ********                    赋值系统                              ********

        For i = 0 To 191

            If cflag(i) = True Then

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 0 Then

                            If cwin(j, k, i) = True Then

                                For m = 0 To 9

                                    For n = 0 To 9

                                        If table(m, n) = 1 Then

                                            If cwin(m, n, i) = True Then

                                                cscore(j, k) = cscore(j, k) + 1

                                            End If

                                        End If

                                    Next

                                Next

                            End If

                        End If

                    Next

                Next

            End If

        Next

        For i = 0 To 191

            If pflag(i) = True Then

                For j = 0 To 9

                    For k = 0 To 9

                        If table(j, k) = 0 Then

                            If pwin(j, k, i) = True Then

                                For m = 0 To 9

                                    For n = 0 To 9

                                        If table(m, n) = 2 Then

                                            If pwin(m, n, i) = True Then

                                                pscore(j, k) = pscore(j, k) + 1

                                            End If

                                        End If

                                    Next

                                Next

                            End If

                        End If

                    Next

                Next

            End If

        Next

        ''' ********                    赋值系统结束                            ********

        ''' ********                    分值比较算法                            ********

        Dim a, b, c, d As Integer

        Dim cs As Integer = 0

        Dim ps As Integer = 0

        For i = 0 To 9

            For j = 0 To 9

                If cscore(i, j) >; cs Then

                    cs = cscore(i, j)

                    a = i

                    b = j

                End If

            Next

        Next

        For i = 0 To 9

            For j = 0 To 9

                If pscore(i, j) >; ps Then

                    ps = pscore(i, j)

                    c = i

                    d = j

                End If

            Next

        Next

        If cs >; ps Then

            yuandian(a * 30 + 10, b * 30 + 10)

            table(a, b) = 1

            For i = 0 To 191

                If pwin(a, b, i) = True Then

                    pflag(i) = False

                End If

            Next

        Else

            yuandian(c * 30 + 10, d * 30 + 10)

            table(c, d) = 1

            For i = 0 To 191

                If pwin(c, d, i) = True Then

                    pflag(i) = False

                End If

            Next

        End If

        ''' ********                    分值比较算法结束                        ********

        checkwin()

End Sub

FFUZZY

泛看了一下
智能思路还是有参考价值的。

aopinion

不错的，挺受启发的！[/code]

schaumV

这个学期刚刚收到老师的作业,要设计一个bauerschach的游戏，给的例子是五子棋，但它AI是用二叉数构造最佳路径的，最后居多，然后大概只能用三成。当时看了就像这个算法太繁琐，这里这个简单多了。