Minmax algorithm only winning when the move is in direct sight. Otherwise always allowing the player to win

Question

I've been pulling my hair for three days trying to figure out what has gone wrong in what little code I have in my first attempt at both the minimax algorithm, and recursive calls in general (I'm relatively new to programming). Basically, I have everything working in the application except for the thing I wanted to actually learn and work on in it: The minimax algorithm.

Basically, whenever a player makes a move, the computer will do one of two things:

• If there is a winning move right next to it, it will use that move. Easy as pie.
• However, if this move isn't in direct sight, it will pick whatever move lets the player win. The exact opposite of what it should be doing.

I know it's not coming from:

• The legalmove getter
• The board evaluator itself, don't know if it may be coming from some weird thing with the pointer to it, but the evaluator is returning the right scores.

Here is the code (I cut out some of the functions that get the program started):

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 Move As LegalMove
    Public Score As Integer
End Structure

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(False, Nothing)
        If Game_Ended = False Then
            Turn = "Computer"
            Best = Get_Computer_Move(COMPUTER)
            Board(Best.Move.posX, Best.Move.posY).owner = COMPUTER_PIECE
            Board(Best.Move.posX, Best.Move.posY).lbl.Text = COMPUTER_PIECE
            Call Check_Board(False, Nothing)
        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 simulation As Boolean, ByVal side As Boolean)
    Dim intindex As Integer
    Dim intindex2 As Integer
    'Vertical Check
    For intindex = 0 To 2
        If Board(intindex, 0).owner = Board(intindex, 1).owner And Board(intindex, 1).owner = Board(intindex, 2).owner And Board(intindex, 0).owner <> Nothing Then
            If simulation = False Then
                Win()
            Else
                If Board(intindex, 0).owner = COMPUTER_PIECE Then
                    Return 1
                Else
                    Return -1
                End If
            End If
        End If
    Next
    'Horizantal Check
    For intindex = 0 To 2
        If Board(0, intindex).owner = Board(1, intindex).owner And Board(1, intindex).owner = Board(2, intindex).owner And Board(0, intindex).owner <> Nothing Then
            If simulation = False Then
                Win()
            Else
                If Board(0, intindex).owner = COMPUTER_PIECE Then
                    Return 1
                Else
                    Return -1
                End If
            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 Board(intindex, intindex2).owner = Board(1, 1).owner And Board(1, 1).owner = Board(intoppindex, intoppindex2).owner And Board(intindex, intindex2).owner <> Nothing Then
                If simulation = False Then
                    Win()
                Else
                    If Board(1, 1).owner = COMPUTER_PIECE Then
                        Return 1
                    Else
                        Return -1
                    End If
                End If
            End If
        Next
    Next
    'Full Board
    Dim movedcount As Integer
    For intindex = 0 To 2
        For intindex2 = 0 To 2
            If Board(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)
    Dim mybest As New Best
    Dim reply As New Best
    Dim LegalMoveslst As List(Of LegalMove)
    LegalMoveslst = Get_Legal_Moves(Board)

    'This allows to look at other's next move.
    Dim oppside As Boolean
    If side = COMPUTER Then
        oppside = HUMAN
    Else
        oppside = COMPUTER
    End If

    'At lowest end of a given branch (win, loss, or tie), the current score is returned.
    mybest.Score = Check_Board(True, side)
    If mybest.Score <> Nothing Then
        Return mybest
    End If

    'Base values so something is always there.
    If side = COMPUTER Then
        mybest.Score = -2
    Else
        mybest.Score = 2
    End If

    For Each LegalMove In LegalMoveslst
        If side = COMPUTER Then
            Board(LegalMove.posX, LegalMove.posY).owner = COMPUTER_PIECE
        Else
            Board(LegalMove.posX, LegalMove.posY).owner = PLAYER_PIECE
        End If
        reply = Get_Computer_Move(oppside)
        Board(LegalMove.posX, LegalMove.posY).owner = Nothing
        If ((side = COMPUTER And reply.Score > mybest.Score) Or (side = HUMAN And reply.Score < mybest.Score)) Then
            mybest.Move = LegalMove
            mybest.Score = reply.Score
        End If
    Next
    Return mybest
End Function

'Returns potential legal moves on the board
Public Function Get_Legal_Moves(ByVal tempBoard(,) 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 tempBoard(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

Hope you can help!

Answer 1

I am getting lost in your application. You have broken the rules of the clean programming. And in such algorithm, with branching recursion, that vice is punished. Obviously you have got lost with the question whose move is being analyzed now.

There should not be such function as GetComputerBestMove on the AI level. Only on the UI level the prog needs to know, who will think on the move. As for AI level, you should have the function FindMyBestMove(side as Boolean, AllowedDepth as Integer) It is not about name. This function shouldn't use the value of "side" for anything else except passing its opposite to the same function when analyzing the enemy's move. _{In some games the strategies for the first and second player could differ, there you use it for the move evaluation.} AllowedDepth should be -- with every recursion step down and when it is reaching 0, the function can't use recursion on that step. You can use this variable for setting the level of AI.

Answer 2

I do not see an obvious problem with your code (but then, if there were, it would not be up on SO), but I suspect that you are initializing your "base" values in reverse. E. g., when calculating for COMPUTER, you accept the value of reply.Score if higher than mybest.Score, but the initial value, which should be reasonably low, is 2. And that's opposed to the other side starting value of -2. I did not read your estimator code, so I do not know if that can be a problem or not. Maybe the initial value of 2 is simply never bested in this case?