Keyvan Nayyeri

Friend Class TreeNode

    Public Board(3, 3, 3) As Char

    Public Turn As Integer

    Public Son As TreeNode

    Public NextNode As TreeNode

End Class

Public Class GameTree

    Sub New()

 

    End Sub

    Private Function GetNode(ByRef Board(,,) As Char, _

    ByVal Turn As Boolean) As TreeNode

        Dim Node As New TreeNode

        Board.Copy(Board, Node.Board, Node.Board.Length)

        Node.Turn = Turn

        Return Node

    End Function

    Public Sub NextMove(ByVal Board(,,) As Char, _

    ByVal LookLevel As Integer, ByVal Player As Char, _

    ByRef NewBoard(,,) As Char)

        Dim ptree As New TreeNode

        Dim best As New TreeNode

        Dim Value As Integer

 

        ptree = BuildTree(Board, LookLevel)

 

        BestBranch(ptree, Player, best, Value)

 

        best.Board.Copy(best.Board, NewBoard, _

        best.Board.Length)

    End Sub

    Private Function BuildTree(ByVal Board(,,) As Char _

    , ByVal LookLevel As Integer) As TreeNode

        Dim ptree As New TreeNode

        Board.Copy(Board, ptree.Board, _

        ptree.Board.Length)

 

        ptree.Turn = 1

        ptree.Son = Nothing

        ptree.NextNode = Nothing

 

        Expand(ptree, 0, LookLevel)

        Return ptree

    End Function

    Private Sub Expand(ByRef P As TreeNode, _

    ByVal PLevel As Integer, ByVal Depth As Integer)

        Dim q As New TreeNode

        If PLevel < Depth Then

            q = Generate(P.Board, -(P.Turn))

            P.Son = q

 

            While Not (q Is Nothing)

                If P.Turn = 1 Then

                    q.Turn = -1

                Else

                    q.Turn = 1

                End If

                q.Son = Nothing

                Expand(q, PLevel + 1, Depth)

                q = q.NextNode

            End While

        End If

    End Sub

    Private Function Generate(ByVal Board(,,) As Char, _

    ByVal Turn As Integer) As TreeNode

        Dim CharTemp As Char

        If Turn = 1 Then

            CharTemp = "X"

        Else

            If Turn = -1 Then

                CharTemp = "O"

            End If

        End If

 

        Dim objSymmetric As New Symmetric

        Dim objQueue As New Queue

        objSymmetric.MakeQueue(Board, _

        objQueue, CharTemp)

 

        Dim Head As New TreeNode

        Dim Node As New TreeNode

        If objQueue.Count <> 0 Then

            Node = objQueue.Dequeue

        End If

 

        Head = Node

        While objQueue.Count <> 0

            Node.NextNode = objQueue.Dequeue

            Node = Node.NextNode

        End While

 

        Head.Turn = Turn

        Return Head

    End Function

    Private Sub BestBranch(ByVal pnd As TreeNode, _

    ByVal Player As Char, ByRef pBest As TreeNode, _

    ByRef pvalue As Integer)

        Dim Temp As Integer = Temp.MinValue

        Dim Best As New TreeNode

        Dim Son As New TreeNode

 

        Son = pnd.Son

        While Not (Son Is Nothing)

            If Temp < MinMax(Son, Player) Then

                Temp = MinMax(Son, Player)

                pBest = Son

            End If

            Son = Son.NextNode

        End While

    End Sub

    Private Function MinMax(ByVal Node As TreeNode, _

    ByVal Player As Char) As Integer

        If Node.Son Is Nothing Then

            Dim objStatic As New StaticFunction

            Return objStatic.StaticFunction(Node.Board, _

            Player)

        Else

            Dim Temp As New TreeNode

            Temp = Node.Son

            If Node.Turn = 1 Then

                Dim Max As Integer = Max.MinValue

                While Not (Temp Is Nothing)

                    If Max < MinMax(Temp, Player) Then

                        Max = MinMax(Temp, Player)

                    End If

                    Temp = Temp.NextNode

                End While

                Return Max

            Else

                Dim Min As Integer = Min.MaxValue

                While Not (Temp Is Nothing)

                    If Min > MinMax(Temp, Player) Then

                        Min = MinMax(Temp, Player)

                    End If

                    Temp = Temp.NextNode

                End While

                Return Min

            End If

        End If

    End Function

End Class