'Test application to tes the minmax algorithm, as well as alpha-beta pruning inside of it. A tic-tac--toe program that will never lose. By Keegan Parker
Public Class Form1
    Public Const PLAYER_PIECE As String = "X"
    Public Const COMPUTER_PIECE As String = "O"
    Public Const HUMAN_WIN As Integer = -1
    Public Const COMPUTER_WIN As Integer = 1
    Public Const TIE As Integer = 0
    Public Const COMPUTER As Boolean = True
    Public Const HUMAN As Boolean = False
    Public Game_Ended As Boolean = False
    Public Turn As String = "Human"
    Public Board(2, 2) As Board
    'Sets all objects up (mostly labels, and the board)
    Private Sub On_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim intindex As Integer
        Dim intindex2 As Integer
        For intindex = 0 To 2
            For intindex2 = 0 To 2
                Dim Label As New Label
                Label.Name = "lbl" & intindex & intindex2
                Label.AutoSize = False
                Label.TextAlign = ContentAlignment.MiddleCenter
                Label.Font = New Font("Arial", 48, FontStyle.Bold)
                Label.Size = New System.Drawing.Size(100, 100)
                Label.Location = New System.Drawing.Point(intindex * 100, intindex2 * 100)
                Label.BorderStyle = Windows.Forms.BorderStyle.FixedSingle
                Board(intindex, intindex2).lbl = Label
                Board(intindex, intindex2).posX = intindex
                Board(intindex, intindex2).posY = intindex2
                Me.Controls.Add(Label)
                AddHandler Board(intindex, intindex2).lbl.Click, AddressOf Player_Move
            Next
        Next
    End Sub
    'If a player clicks on one of the labels, it will attmpt to put a player piece on that tile, and direct the game to the computer's turn.
    Sub Player_Move(ByVal sender As System.Object, ByVal e As System.EventArgs)
        Dim Current_Board As Board = GetBoard(sender)
        Dim Best As Best
        If Current_Board.owner = Nothing Then
            Board(Current_Board.posX, Current_Board.posY).owner = PLAYER_PIECE
            Board(Current_Board.posX, Current_Board.posY).lbl.Text = PLAYER_PIECE
            Call Check_Board(Board, False)
            If Game_Ended = False Then
                Turn = "Computer"
                Best = Get_Computer_Move(COMPUTER, Board)
                Board(Best.MovePosX, Best.MovePosY).owner = COMPUTER_PIECE
                Board(Best.MovePosX, Best.MovePosY).lbl.Text = COMPUTER_PIECE
                Call Check_Board(Board, False)
            End If
            Game_Ended = False
            Turn = "Human"
        End If
    End Sub

    'Checks win/tie conditions. If it is a simulation (for ai), then it will return a number. If it is for legitimate checking, it will call the win function, or tie.
    Function Check_Board(ByVal opBoard(,) As Board, ByVal simulation As Boolean)
        Dim intindex As Integer
        Dim intindex2 As Integer
        'Vertical Check
        For intindex = 0 To 2
            If opBoard(intindex, 0).owner = opBoard(intindex, 1).owner And opBoard(intindex, 1).owner = opBoard(intindex, 2).owner And opBoard(intindex, 0).owner <> Nothing Then
                If simulation = False Then
                    Win()
                Else
                    Return 1
                End If
            End If
        Next
        'Horizantal Check
        For intindex = 0 To 2
            If opBoard(0, intindex).owner = opBoard(1, intindex).owner And opBoard(1, intindex).owner = opBoard(2, intindex).owner And opBoard(0, intindex).owner <> Nothing Then
                If simulation = False Then
                    Win()
                Else
                    Return 1
                End If
            End If
        Next
        'Diagonal Check
        Dim intoppindex As Integer
        Dim intoppindex2 As Integer
        For intindex = 0 To 2 Step 2
            For intindex2 = 0 To 2 Step 2
                If intindex = 0 Then
                    intoppindex = 2
                Else
                    intoppindex = 0
                End If
                If intindex2 = 0 Then
                    intoppindex2 = 2
                Else
                    intoppindex2 = 0
                End If
                If opBoard(intindex, intindex2).owner = opBoard(1, 1).owner And opBoard(1, 1).owner = opBoard(intoppindex, intoppindex2).owner And opBoard(intindex, intindex2).owner <> Nothing Then
                    If simulation = False Then
                        Win()
                    Else
                        Return 1
                    End If
                End If
            Next
        Next
        'Full Board
        Dim movedcount As Integer
        For intindex = 0 To 2
            For intindex2 = 0 To 2
                If opBoard(intindex, intindex2).owner <> Nothing Then
                    movedcount += 1
                End If
            Next
        Next
        If movedcount = 9 Then
            If simulation = False Then
                MessageBox.Show("It is a tie. Resetting the board.")
                For intindex = 0 To 2
                    For intindex2 = 0 To 2
                        Board(intindex, intindex2).owner = Nothing
                        Board(intindex, intindex2).lbl.Text = Nothing
                    Next
                Next
                Game_Ended = True
            Else
                Return 0
            End If
        End If
        Return Nothing
    End Function

    'Allows labels to be processed in to the board
    Public Function GetBoard(ByVal sender As Label)
        Dim intindex As Integer
        Dim intindex2 As Integer
        For intindex = 0 To 2
            For intindex2 = 0 To 2
                If Board(intindex, intindex2).lbl.Name = sender.Name Then
                    Return Board(intindex, intindex2)
                End If
            Next
        Next
        Return Nothing
    End Function
    'If a player wins, it will display a message box and reset the board
    Sub Win()
        MessageBox.Show(Turn & " has won. Resetting the board.")
        Dim intindex As Integer
        Dim intindex2 As Integer
        For intindex = 0 To 2
            For intindex2 = 0 To 2
                Board(intindex, intindex2).owner = Nothing
                Board(intindex, intindex2).lbl.Text = Nothing
            Next
        Next
        Game_Ended = True
    End Sub

    'Minmax algorithm that tries to get best possible move by accessing every possible scenario in the game tree. NOT WORKING. Returns a "best" object, that is then used to place the computer's piece.
    Public Function Get_Computer_Move(ByVal side As Boolean, ByVal opBoard(,) As Board)
        Dim mybest As New Best
        Dim reply As Best
        Dim LegalMoves As New List(Of LegalMove)

        LegalMoves = Get_Legal_Moves(opBoard)

        Dim oppside As Boolean
        If side = COMPUTER Then
            oppside = HUMAN
        Else
            oppside = COMPUTER
        End If

        If Check_Board(opBoard, True) <> Nothing Then
            mybest.Score = Check_Board(opBoard, True)
            Return mybest
        End If

        If side = COMPUTER Then
            mybest.Score = -2
        Else
            mybest.Score = 2
        End If

        For Each LegalMove In LegalMoves
            If side = COMPUTER Then
                opBoard(LegalMove.posX, LegalMove.posY).owner = COMPUTER_PIECE
            Else
                opBoard(LegalMove.posX, LegalMove.posY).owner = PLAYER_PIECE
            End If
            reply = Get_Computer_Move(oppside, opBoard)
            opBoard(LegalMove.posX, LegalMove.posY).owner = Nothing
            If (side = COMPUTER And reply.Score > mybest.Score) Or (side = HUMAN And reply.Score < mybest.Score) Then
                mybest.MovePosX = LegalMove.posX
                mybest.MovePosY = LegalMove.posY
                mybest.Score = reply.Score
            End If
        Next
        Return mybest
    End Function
    'Returns potential legal moves on the board
    Public Function Get_Legal_Moves(ByVal opboard(,) As Board)
        Dim intindex As Integer
        Dim intindex2 As Integer
        Dim legalmoves As New List(Of LegalMove)
        For intindex = 0 To 2
            For intindex2 = 0 To 2
                If opboard(intindex, intindex2).owner = Nothing Then
                    Dim legalmove As New LegalMove
                    legalmove.posX = intindex
                    legalmove.posY = intindex2
                    legalmoves.Add(legalmove)
                End If
            Next
        Next
        Return legalmoves
    End Function
End Class

Public Structure Board
    Public lbl As Label
    Public owner As String
    Public posX As Integer
    Public posY As Integer
End Structure

Public Structure LegalMove
    Public posX As Integer
    Public posY As Integer
End Structure

Public Structure Best
    Public MovePosX As Integer
    Public MovePosY As Integer
    Public Score As Integer
End Structure