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:
I know it's not coming from:
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!
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.