|
Post by anthonyrbrown on Feb 10, 2024 22:12:04 GMT
Can anyone get this Code to run? It's some Tic Tac Toe C++ Code converted to VB the first is the Original C++ and the next is the VB which nearly works!!!
// C++ program to find the next optimal move for // a player #include<bits/stdc++.h> using namespace std;
struct Move { int row, col; };
char player = 'x', opponent = 'o';
// This function returns true if there are moves // remaining on the board. It returns false if // there are no moves left to play. bool isMovesLeft(char board[3][3]) { for (int i = 0; i<3; i++) for (int j = 0; j<3; j++) if (board[i][j]=='_') return true; return false; }
// This is the evaluation function as discussed // in the previous article ( http://goo.gl/sJgv68 ) int evaluate(char b[3][3]) { // Checking for Rows for X or O victory. for (int row = 0; row<3; row++) { if (b[row][0]==b[row][1] && b[row][1]==b[row][2]) { if (b[row][0]==player) return +10; else if (b[row][0]==opponent) return -10; } }
// Checking for Columns for X or O victory. for (int col = 0; col<3; col++) { if (b[0][col]==b[1][col] && b[1][col]==b[2][col]) { if (b[0][col]==player) return +10;
else if (b[0][col]==opponent) return -10; } }
// Checking for Diagonals for X or O victory. if (b[0][0]==b[1][1] && b[1][1]==b[2][2]) { if (b[0][0]==player) return +10; else if (b[0][0]==opponent) return -10; }
if (b[0][2]==b[1][1] && b[1][1]==b[2][0]) { if (b[0][2]==player) return +10; else if (b[0][2]==opponent) return -10; }
// Else if none of them have won then return 0 return 0; }
// This is the minimax function. It considers all // the possible ways the game can go and returns // the value of the board int minimax(char board[3][3], int depth, bool isMax) { int score = evaluate(board);
// If Maximizer has won the game return his/her // evaluated score if (score == 10) return score;
// If Minimizer has won the game return his/her // evaluated score if (score == -10) return score;
// If there are no more moves and no winner then // it is a tie if (isMovesLeft(board)==false) return 0;
// If this maximizer's move if (isMax) { int best = -1000;
// Traverse all cells for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=='_') { // Make the move board[i][j] = player;
// Call minimax recursively and choose // the maximum value best = max( best, minimax(board, depth+1, !isMax) );
// Undo the move board[i][j] = '_'; } } } return best; }
// If this minimizer's move else { int best = 1000;
// Traverse all cells for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=='_') { // Make the move board[i][j] = opponent;
// Call minimax recursively and choose // the minimum value best = min(best, minimax(board, depth+1, !isMax));
// Undo the move board[i][j] = '_'; } } } return best; } }
// This will return the best possible move for the player Move findBestMove(char board[3][3]) { int bestVal = -1000; Move bestMove; bestMove.row = -1; bestMove.col = -1;
// Traverse all cells, evaluate minimax function for // all empty cells. And return the cell with optimal // value. for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=='_') { // Make the move board[i][j] = player;
// compute evaluation function for this // move. int moveVal = minimax(board, 0, false);
// Undo the move board[i][j] = '_';
// If the value of the current move is // more than the best value, then update // best/ if (moveVal > bestVal) { bestMove.row = i; bestMove.col = j; bestVal = moveVal; } } } }
printf("The value of the best Move is : %d\n\n", bestVal);
return bestMove; }
// Driver code int main() { char board[3][3] = { { 'x', 'o', 'x' }, { 'o', 'o', 'x' }, { '_', '_', '_' } };
Move bestMove = findBestMove(board);
printf("The Optimal Move is :\n"); printf("ROW: %d COL: %d\n\n", bestMove.row, bestMove.col ); return 0; }
Oops! I just remembered I did not use the Original C++ code above because I could not find a C++ to VB converter,so first I converted the above to C# or should I say I used the C# version below...
// C# program to find the // next optimal move for a player using System; using System.Collections.Generic;
class GFG { class Move { public int row, col; };
static char player = 'x', opponent = 'o';
// This function returns true if there are moves // remaining on the board. It returns false if // there are no moves left to play. static Boolean isMovesLeft(char [,]board) { for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (board[i, j] == '_') return true; return false; }
// This is the evaluation function as discussed // in the previous article ( http://goo.gl/sJgv68 ) static int evaluate(char [,]b) { // Checking for Rows for X or O victory. for (int row = 0; row < 3; row++) { if (b[row, 0] == b[row, 1] && b[row, 1] == b[row, 2]) { if (b[row, 0] == player) return +10; else if (b[row, 0] == opponent) return -10; } }
// Checking for Columns for X or O victory. for (int col = 0; col < 3; col++) { if (b[0, col] == b[1, col] && b[1, col] == b[2, col]) { if (b[0, col] == player) return +10;
else if (b[0, col] == opponent) return -10; } }
// Checking for Diagonals for X or O victory. if (b[0, 0] == b[1, 1] && b[1, 1] == b[2, 2]) { if (b[0, 0] == player) return +10; else if (b[0, 0] == opponent) return -10; }
if (b[0, 2] == b[1, 1] && b[1, 1] == b[2, 0]) { if (b[0, 2] == player) return +10; else if (b[0, 2] == opponent) return -10; }
// Else if none of them have won then return 0 return 0; }
// This is the minimax function. It considers all // the possible ways the game can go and returns // the value of the board static int minimax(char [,]board, int depth, Boolean isMax) { int score = evaluate(board);
// If Maximizer has won the game // return his/her evaluated score if (score == 10) return score;
// If Minimizer has won the game // return his/her evaluated score if (score == -10) return score;
// If there are no more moves and // no winner then it is a tie if (isMovesLeft(board) == false) return 0;
// If this maximizer's move if (isMax) { int best = -1000;
// Traverse all cells for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { // Check if cell is empty if (board[i, j] == '_') { // Make the move board[i, j] = player;
// Call minimax recursively and choose // the maximum value best = Math.Max(best, minimax(board, depth + 1, !isMax));
// Undo the move board[i, j] = '_'; } } } return best; }
// If this minimizer's move else { int best = 1000;
// Traverse all cells for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { // Check if cell is empty if (board[i, j] == '_') { // Make the move board[i, j] = opponent;
// Call minimax recursively and choose // the minimum value best = Math.Min(best, minimax(board, depth + 1, !isMax));
// Undo the move board[i, j] = '_'; } } } return best; } }
// This will return the best possible // move for the player static Move findBestMove(char [,]board) { int bestVal = -1000; Move bestMove = new Move(); bestMove.row = -1; bestMove.col = -1;
// Traverse all cells, evaluate minimax function // for all empty cells. And return the cell // with optimal value. for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { // Check if cell is empty if (board[i, j] == '_') { // Make the move board[i, j] = player;
// compute evaluation function for this // move. int moveVal = minimax(board, 0, false);
// Undo the move board[i, j] = '_';
// If the value of the current move is // more than the best value, then update // best/ if (moveVal > bestVal) { bestMove.row = i; bestMove.col = j; bestVal = moveVal; } } } }
Console.Write("The value of the best Move " + "is : {0}\n\n", bestVal);
return bestMove; }
// Driver code public static void Main(String[] args) { char [,]board = {{ 'x', 'o', 'x' }, { 'o', 'o', 'x' }, { '_', '_', '_' }};
Move bestMove = findBestMove(board);
Console.Write("The Optimal Move is :\n"); Console.Write("ROW: {0} COL: {1}\n\n", bestMove.row, bestMove.col ); } }
|
|
|
Post by anthonyrbrown on Feb 10, 2024 22:12:45 GMT
Imports System Imports System.Collections.Generic
Class GFG Class Move Public row, col As Integer End Class
Shared player As Char = "x"c, opponent As Char = "o"c
Private Shared Function isMovesLeft(ByVal board As Char(,)) As Boolean For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1 If board(i, j) = "_"c Then Return True Next Next
Return False End Function
Private Shared Function evaluate(ByVal b As Char(,)) As Integer For row As Integer = 0 To 3 - 1
If b(row, 0) = b(row, 1) AndAlso b(row, 1) = b(row, 2) Then
If b(row, 0) = player Then Return +10 ElseIf b(row, 0) = opponent Then Return -10 End If End If Next
For col As Integer = 0 To 3 - 1
If b(0, col) = b(1, col) AndAlso b(1, col) = b(2, col) Then
If b(0, col) = player Then Return +10 ElseIf b(0, col) = opponent Then Return -10 End If End If Next
If b(0, 0) = b(1, 1) AndAlso b(1, 1) = b(2, 2) Then
If b(0, 0) = player Then Return +10 ElseIf b(0, 0) = opponent Then Return -10 End If End If
If b(0, 2) = b(1, 1) AndAlso b(1, 1) = b(2, 0) Then
If b(0, 2) = player Then Return +10 ElseIf b(0, 2) = opponent Then Return -10 End If End If
Return 0 End Function
Private Shared Function minimax(ByVal board As Char(,), ByVal depth As Integer, ByVal isMax As Boolean) As Integer Dim score As Integer = evaluate(board) If score = 10 Then Return score If score = -10 Then Return score If isMovesLeft(board) = False Then Return 0
If isMax Then Dim best As Integer = -1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player best = Math.Max(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best Else Dim best As Integer = 1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = opponent best = Math.Min(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best End If End Function
Private Shared Function findBestMove(ByVal board As Char(,)) As Move Dim bestVal As Integer = -1000 Dim bestMove As Move = New Move() bestMove.row = -1 bestMove.col = -1
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player Dim moveVal As Integer = minimax(board, 0, False) board(i, j) = "_"c
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal) Return bestMove End Function
Public Shared Sub Main(ByVal args As String()) Dim board As Char(,) = { {"x"c, "o"c, "x"c}, {"o"c, "o"c, "x"c}, {"_"c, "_"c, "_"c}} Dim bestMove As Move = findBestMove(board) Console.Write("The Optimal Move is :" & vbLf) Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) End Sub End Class
|
|
|
Post by bplus on Feb 11, 2024 3:02:32 GMT
This is what I come up with:
Option _Explicit Type Move As Integer row, col End Type
Dim Shared player$, opponent$ player$ = "x": opponent$ = "o"
'Public Shared Sub Main(ByVal args As String()) Dim board$(2, 2) board$(0, 0) = "x": board$(0, 1) = "o": board$(0, 2) = "x" board$(1, 0) = "o": board$(1, 1) = "o": board$(1, 2) = "x" board$(2, 0) = "_": board$(2, 1) = "_": board$(2, 2) = "_" Dim bestMove As Move findBestMove board$(), bestMove Print "row, col"; bestMove.row; bestMove.col ' ????????????????? vbLF ' Console.Write("The Optimal Move is :" & vbLf) ' Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) 'End Sub
Function isMovesLeft% (board$()) Dim As Integer i, j For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then isMovesLeft% = -1: Exit Function Next Next 'else return 0 End Function
Function evaluate% (b$()) ' winner? Dim As Integer row, col For row = 0 To 2 If b$(row, 0) = b$(row, 1) And b$(row, 1) = b$(row, 2) Then If b$(row, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
For col = 0 To 2 If b$(0, col) = b$(1, col) And b$(1, col) = b$(2, col) Then If b$(0, col) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
If b$(0, 0) = b$(1, 1) And b$(1, 1) = b$(2, 2) Then If b$(0, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
If b$(0, 2) = b$(1, 1) And b$(1, 1) = b$(2, 0) Then
If b$(0, 2) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
'else returns 0 End Function
Function minimax% (board$(), depth%, isMax%) Dim As Integer score, best, i, j score = evaluate%(board$()) If score = 10 Or score = -10 Then minimax% = score: Exit Function If isMovesLeft%(board$()) = 0 Then minimax% = 0: Exit Function
'copy board because QB64 doesn't do by val need recursive level dependent values Dim copyB$(2, 2) For i = 0 To 2 For j = 0 To 2 copyB$(i, j) = board$(i, j) Next Next If isMax% Then best = -1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = player$ best = max%(best, minimax%(copyB$(), depth% + 1, Not isMax%)) copyB$(i, j) = "_" End If Next Next minimax% = best Else best = 1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = opponent$ best = min%(best, minimax(copyB$(), depth% + 1, Not isMax%)) copyB$(i, j) = "_" End If Next Next minimax% = best End If End Function
Sub findBestMove (board$(), thisMove As Move) Dim As Integer bestVal, i, j, moveVal bestVal = -1000 Dim bestMove As Move bestMove.row = -1 bestMove.col = -1
For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then board$(i, j) = player$ moveVal = minimax%(board$(), 0, 0) board$(i, j) = "_"
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
' Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal) thisMove = bestMove End Sub
Function max% (n1%, n2%) If n1% > n2% Then max% = n1% Else max% = n2% End Function Function min% (n1%, n2%) If n1% > n2% Then min% = n2% Else min% = n1% End Function
|
|
|
Post by anthonyrbrown on Feb 11, 2024 7:58:15 GMT
That is fantastic blus,and it works! So what I would like to know going back to the VB Code version,below... Imports System Imports System.Collections.Generic
Class GFG Class Move Public row, col As Integer End Class
Shared player As Char = "x"c, opponent As Char = "o"c
Private Shared Function isMovesLeft(ByVal board As Char(,)) As Boolean For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1 If board(i, j) = "_"c Then Return True Next Next
Return False End Function
Private Shared Function evaluate(ByVal b As Char(,)) As Integer For row As Integer = 0 To 3 - 1
If b(row, 0) = b(row, 1) AndAlso b(row, 1) = b(row, 2) Then
If b(row, 0) = player Then Return +10 ElseIf b(row, 0) = opponent Then Return -10 End If End If Next
For col As Integer = 0 To 3 - 1
If b(0, col) = b(1, col) AndAlso b(1, col) = b(2, col) Then
If b(0, col) = player Then Return +10 ElseIf b(0, col) = opponent Then Return -10 End If End If Next
If b(0, 0) = b(1, 1) AndAlso b(1, 1) = b(2, 2) Then
If b(0, 0) = player Then Return +10 ElseIf b(0, 0) = opponent Then Return -10 End If End If
If b(0, 2) = b(1, 1) AndAlso b(1, 1) = b(2, 0) Then
If b(0, 2) = player Then Return +10 ElseIf b(0, 2) = opponent Then Return -10 End If End If
Return 0 End Function
Private Shared Function minimax(ByVal board As Char(,), ByVal depth As Integer, ByVal isMax As Boolean) As Integer Dim score As Integer = evaluate(board) If score = 10 Then Return score If score = -10 Then Return score If isMovesLeft(board) = False Then Return 0
If isMax Then Dim best As Integer = -1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player best = Math.Max(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best Else Dim best As Integer = 1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = opponent best = Math.Min(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best End If End Function
Private Shared Function findBestMove(ByVal board As Char(,)) As Move Dim bestVal As Integer = -1000 Dim bestMove As Move = New Move() bestMove.row = -1 bestMove.col = -1
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player Dim moveVal As Integer = minimax(board, 0, False) board(i, j) = "_"c
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal) Return bestMove End Function
Public Shared Sub Main(ByVal args As String()) Dim board As Char(,) = { {"x"c, "o"c, "x"c}, {"o"c, "o"c, "x"c}, {"_"c, "_"c, "_"c}} Dim bestMove As Move = findBestMove(board) Console.Write("The Optimal Move is :" & vbLf) Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) End Sub End Class
Is when you try to make the VB code run as QB64 code you get the error message below... which I am sure you have seen... Expected &H... or &0...on line 133 (click here or Ctrl+Shift+G to jump there) Can the VB version run? by changing the code to the correct code as shown above? or will it only work the way you have done it? Sorry to be so Picky now that you have solved the problem it's just that when I see some code I do not understand,then I like to dissect as much as possible until I understand it,Will the VB version work?
|
|
|
Post by bplus on Feb 11, 2024 14:00:49 GMT
i don't know what vbLf is, maybe it's a routine in here: Imports System Imports System.Collections.Generic
|
|
|
Post by anthonyrbrown on Feb 11, 2024 14:32:01 GMT
|
|
|
Post by bplus on Feb 11, 2024 15:07:55 GMT
That's it! just the clue I needed. Lets see if I can finish translation better?
|
|
|
Post by bplus on Feb 11, 2024 15:21:06 GMT
No this isn't right:
Option _Explicit Type Move As Integer row, col End Type
Dim Shared player$, opponent$ player$ = "x": opponent$ = "o"
'Public Shared Sub Main(ByVal args As String()) Dim board$(2, 2) board$(0, 0) = "x": board$(0, 1) = "_": board$(0, 2) = "_" board$(1, 0) = "_": board$(1, 1) = "o": board$(1, 2) = "_" board$(2, 0) = "x": board$(2, 1) = "_": board$(2, 2) = "o" Dim bestMove As Move findBestMove board$(), bestMove Print "The Optimal Move is:" Print "Row:"; bestMove.row; " Col:"; bestMove.col ' ????????????????? vbLF ' Console.Write("The Optimal Move is :" & vbLf) ' Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) 'End Sub
Function isMovesLeft% (board$()) Dim As Integer i, j For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then isMovesLeft% = -1: Exit Function Next Next 'else return 0 End Function
Function evaluate% (b$()) ' winner? Dim As Integer row, col For row = 0 To 2 If b$(row, 0) = b$(row, 1) And b$(row, 1) = b$(row, 2) Then If b$(row, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
For col = 0 To 2 If b$(0, col) = b$(1, col) And b$(1, col) = b$(2, col) Then If b$(0, col) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
If b$(0, 0) = b$(1, 1) And b$(1, 1) = b$(2, 2) Then If b$(0, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
If b$(0, 2) = b$(1, 1) And b$(1, 1) = b$(2, 0) Then
If b$(0, 2) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
'else returns 0 End Function
Function minimax% (board$(), depth%, isMax%) Dim As Integer score, best, i, j score = evaluate%(board$()) If score = 10 Or score = -10 Then minimax% = score: Exit Function If isMovesLeft%(board$()) = 0 Then minimax% = 0: Exit Function
'copy board because QB64 doesn't do by val need recursive level dependent values Dim copyB$(2, 2) For i = 0 To 2 For j = 0 To 2 copyB$(i, j) = board$(i, j) Next Next If isMax% Then best = -1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = player$ best = max%(best, minimax%(copyB$(), depth% + 1, Not isMax%)) copyB$(i, j) = "_" End If Next Next minimax% = best Else best = 1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = opponent$ best = min%(best, minimax(copyB$(), depth% + 1, Not isMax%)) copyB$(i, j) = "_" End If Next Next minimax% = best End If End Function
Sub findBestMove (board$(), thisMove As Move) Dim As Integer bestVal, i, j, moveVal bestVal = -1000 Dim bestMove As Move bestMove.row = -1 bestMove.col = -1
For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then board$(i, j) = player$ moveVal = minimax%(board$(), 0, 0) board$(i, j) = "_"
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
' Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal)
Print "The value of the best Move is"; bestVal thisMove = bestMove End Sub
Function max% (n1%, n2%) If n1% > n2% Then max% = n1% Else max% = n2% End Function Function min% (n1%, n2%) If n1% > n2% Then min% = n2% Else min% = n1% End Function
Best move for either player in this case is Row 1, Col 0 not Row 0, Col 1
PS I hate code that lists Row before Col in arrays, does not match graphics (x, y) but does match Locate Row, Col for old teletype printers.
|
|
|
Post by bplus on Feb 11, 2024 15:56:21 GMT
I was suspicious of NOT not working as expected so I made my own function KNot%, no change in best move.
Then I checked that Minimax was getting called recursively it was:
Still getting same wrong answer:
Option _Explicit Type Move As Integer row, col End Type
Dim Shared player$, opponent$ player$ = "x": opponent$ = "o"
'Public Shared Sub Main(ByVal args As String()) Dim board$(2, 2) board$(0, 0) = "x": board$(0, 1) = "_": board$(0, 2) = "_" board$(1, 0) = "_": board$(1, 1) = "o": board$(1, 2) = "_" board$(2, 0) = "x": board$(2, 1) = "_": board$(2, 2) = "o" Dim bestMove As Move findBestMove board$(), bestMove Print "The Optimal Move is:" Print "Row:"; bestMove.row; " Col:"; bestMove.col ' ????????????????? vbLF ' Console.Write("The Optimal Move is :" & vbLf) ' Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) 'End Sub
Function isMovesLeft% (board$()) Dim As Integer i, j For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then isMovesLeft% = -1: Exit Function Next Next 'else return 0 End Function
Function evaluate% (b$()) ' winner? Dim As Integer row, col For row = 0 To 2 If b$(row, 0) = b$(row, 1) And b$(row, 1) = b$(row, 2) Then If b$(row, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
For col = 0 To 2 If b$(0, col) = b$(1, col) And b$(1, col) = b$(2, col) Then If b$(0, col) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
If b$(0, 0) = b$(1, 1) And b$(1, 1) = b$(2, 2) Then If b$(0, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
If b$(0, 2) = b$(1, 1) And b$(1, 1) = b$(2, 0) Then
If b$(0, 2) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
'else returns 0 End Function
Function minimax% (board$(), depth%, isMax%) 'debug Print "minimax% depth% coming into recursive sub is:"; depth% Dim As Integer score, best, i, j score = evaluate%(board$()) If score = 10 Or score = -10 Then minimax% = score: Exit Function If isMovesLeft%(board$()) = 0 Then minimax% = 0: Exit Function
'copy board because QB64 doesn't do by val need recursive level dependent values Dim copyB$(2, 2) For i = 0 To 2 For j = 0 To 2 copyB$(i, j) = board$(i, j) Next Next If isMax% Then best = -1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = player$ best = max%(best, minimax%(copyB$(), depth% + 1, KNot%(isMax%))) copyB$(i, j) = "_" End If Next Next minimax% = best Else best = 1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = opponent$ best = min%(best, minimax%(copyB$(), depth% + 1, KNot%(isMax%))) copyB$(i, j) = "_" End If Next Next minimax% = best End If End Function
Sub findBestMove (board$(), thisMove As Move) Dim As Integer bestVal, i, j, moveVal bestVal = -1000 Dim bestMove As Move bestMove.row = -1 bestMove.col = -1
For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then board$(i, j) = player$ moveVal = minimax%(board$(), 0, 0) board$(i, j) = "_"
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
' Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal)
Print "The value of the best Move is"; bestVal thisMove = bestMove End Sub
Function max% (n1%, n2%) If n1% > n2% Then max% = n1% Else max% = n2% End Function Function min% (n1%, n2%) If n1% > n2% Then min% = n2% Else min% = n1% End Function Function KNot% (x%) If x% <> 0 Then KNot% = 0 Else KNot% = -1 End Function
Possibly I flipped row and col somewhere? I double and triple checked.
|
|
|
Post by anthonyrbrown on Feb 11, 2024 15:59:54 GMT
Great bplus I will take a look back later.
|
|
|
Post by bplus on Feb 12, 2024 15:36:55 GMT
Fixed the above posted example I found that missed the obvious correct winning move BUT I found another board that it missed the perfect move to make (or spoil by o).
I have the problem board uncommented x can't lose if makes move at 2, 0!!! but minimax says 0, 2 = missed opportunity
Option _Explicit _Title "TTT with MiniMax% translation one fix but..." ' b+ 2024-02-12 Type Move As Integer row, col End Type
Dim Shared player$, opponent$ player$ = "x": opponent$ = "o"
'Public Shared Sub Main(ByVal args As String()) Dim board$(2, 2)
' original board from translation 'board$(0, 0) = "x": board$(0, 1) = "o": board$(0, 2) = "x" 'board$(1, 0) = "o": board$(1, 1) = "o": board$(1, 2) = "x" 'board$(2, 0) = "_": board$(2, 1) = "_": board$(2, 2) = "_" ' 2, 2 OK 2024-02-12 with modified MiniMax%
' test some more boards 'board$(0, 0) = "x": board$(0, 1) = "o": board$(0, 2) = "x" 'board$(1, 0) = "o": board$(1, 1) = "o": board$(1, 2) = "_" 'board$(2, 0) = "_": board$(2, 1) = "x": board$(2, 2) = "_" ' 1, 2 OK 2024-02-12 with modified MiniMax%
' test some more boards try uneven x, o 'board$(0, 0) = "o": board$(0, 1) = "x": board$(0, 2) = "o" 'board$(1, 0) = "_": board$(1, 1) = "x": board$(1, 2) = "_" 'board$(2, 0) = "x": board$(2, 1) = "_": board$(2, 2) = "_" ' 2, 1 win or block win OK 2024-02-12
' 2024-02-12 Yeah! ' FIXED BOARD WHERE BUG WAS FOUND IN MINIMAX% logic!!!!!! 'board$(0, 0) = "x": board$(0, 1) = "_": board$(0, 2) = "_" 'board$(1, 0) = "_": board$(1, 1) = "o": board$(1, 2) = "_" 'board$(2, 0) = "x": board$(2, 1) = "_": board$(2, 2) = "o" ' best is 1, 0 yes! OK 2024-02-12 with modified MiniMax%
'====================== end tests with correct moves start bad or questionable moves
' crap still off board$(0, 0) = "x": board$(0, 1) = "o": board$(0, 2) = "_" board$(1, 0) = "_": board$(1, 1) = "o": board$(1, 2) = "_" board$(2, 0) = "_": board$(2, 1) = "x": board$(2, 2) = "_" ' best is 2, 0 nope it's saying 0, 2 ??? that move sucks! 2024-02-12
' test some more boards best move to start? 'board$(0, 0) = "_": board$(0, 1) = "_": board$(0, 2) = "_" 'board$(1, 0) = "_": board$(1, 1) = "_": board$(1, 2) = "_" 'board$(2, 0) = "_": board$(2, 1) = "_": board$(2, 2) = "_" ' 1, 1 middle is my guess! OK 2024-02-12 with modified MiniMax% ' 0, 0 ??? ' but a tie might be achieved from any position or any corner?
' after first corner move? 'board$(0, 0) = "x": board$(0, 1) = "_": board$(0, 2) = "_" 'board$(1, 0) = "_": board$(1, 1) = "_": board$(1, 2) = "_" 'board$(2, 0) = "_": board$(2, 1) = "_": board$(2, 2) = "_" ' 0, 1 not 1, 1 hmmm ?
Dim bestMove As Move findBestMove board$(), bestMove Print "The Optimal Move is:" Print "Row:"; bestMove.row; " Col:"; bestMove.col ' ????????????????? vbLF ' Console.Write("The Optimal Move is :" & vbLf) ' Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) 'End Sub
Function isMovesLeft% (board$()) Dim As Integer i, j For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then isMovesLeft% = -1: Exit Function Next Next 'else return 0 End Function
Function evaluate% (b$()) ' winner? Dim As Integer row, col For row = 0 To 2 If b$(row, 0) = b$(row, 1) And b$(row, 1) = b$(row, 2) Then If b$(row, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
For col = 0 To 2 If b$(0, col) = b$(1, col) And b$(1, col) = b$(2, col) Then If b$(0, col) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If Next
If b$(0, 0) = b$(1, 1) And b$(1, 1) = b$(2, 2) Then If b$(0, 0) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
If b$(0, 2) = b$(1, 1) And b$(1, 1) = b$(2, 0) Then
If b$(0, 2) = player$ Then evaluate% = 10 Else evaluate% = -10: Exit Function End If
'else returns 0 End Function
Function minimax% (board$(), depth%, isMax%) 'debug Print "minimax% depth% coming into recursive sub is:"; depth% ' might try print of whole board if I get desparate
Dim As Integer score, best, i, j score = evaluate%(board$())
'old faulty line 'If score = 10 Or score = -10 Then minimax% = score: Exit Function
'it is vital to distinguish a win from level 1 and a win from level >1 !!! If score = 10 Or score = -10 Then minimax% = score - depth%: Exit Function
If isMovesLeft%(board$()) = 0 Then minimax% = 0: Exit Function
'copy board because QB64 doesn't do by val need recursive level dependent values Dim copyB$(2, 2) For i = 0 To 2 For j = 0 To 2 copyB$(i, j) = board$(i, j) Next Next If isMax% Then best = -1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = player$ best = max%(best, minimax%(copyB$(), depth% + 1, KNot%(isMax%))) copyB$(i, j) = "_" End If Next Next minimax% = best Else best = 1000 For i = 0 To 2 For j = 0 To 2 If copyB$(i, j) = "_" Then copyB$(i, j) = opponent$ best = min%(best, minimax%(copyB$(), depth% + 1, KNot%(isMax%))) copyB$(i, j) = "_" End If Next Next minimax% = best End If End Function
Sub findBestMove (board$(), thisMove As Move) Dim As Integer bestVal, i, j, moveVal bestVal = -1000 Dim bestMove As Move bestMove.row = -1 bestMove.col = -1
For i = 0 To 2 For j = 0 To 2 If board$(i, j) = "_" Then board$(i, j) = player$ moveVal = minimax%(board$(), 0, 0) board$(i, j) = "_"
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
' Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal)
Print "The value of the best Move is"; bestVal thisMove = bestMove End Sub
Function max% (n1%, n2%) If n1% > n2% Then max% = n1% Else max% = n2% End Function Function min% (n1%, n2%) If n1% > n2% Then min% = n2% Else min% = n1% End Function Function KNot% (x%) If x% <> 0 Then KNot% = 0 Else KNot% = -1 End Function
|
|
|
Post by anthonyrbrown on Feb 12, 2024 20:28:55 GMT
OK! I am trying to understand what you are saying bplus ? I think because you are so concentrated on what you are doing that you forget I am not you! So is it possible to explain in a step by step way what you are saying? Like if I do this move then it does this move type of stuff! Or am I totally confused and what you have post above is the finished VB code? and it works?
|
|
|
Post by bplus on Feb 13, 2024 16:36:03 GMT
OK! I am trying to understand what you are saying bplus ? I think because you are so concentrated on what you are doing that you forget I am not you! So is it possible to explain in a step by step way what you are saying? Like if I do this move then it does this move type of stuff! Or am I totally confused and what you have post above is the finished VB code? and it works? MiniMax uses recursive calls to itself to do what it does in very short and simple little routine BUT these recursive routines are very, very tricky to setup. Remember these recursive calls go deeper and deeper into seeking thousands of combinations of places to try, very complex mechanism for such a simple looking little routine. No the MiniMax I "translated" does not find simple direct solution to immediate win or can spoil an obvious move the opponent can make to win immediately. I spent one frustrating afternoon yesterday trying to cover both cases primarily and ended up just writing those 2 immediate concerns separately and still minimax translation sucked! I gave up on the stuff because it was not working and couldn't figure out way to get it working. I already wrote a perfect AI for TTT that I understand completely so MiniMax version would have been interesting but NOT so vital. I use recursive solver in Sudoku (someone else had written in JB) and I came up with my own recursive cell clearer for Free Cell along with a Pathfinder in a maze and an Alternate Paint method. The VB or C code is too foreign I may have missed a nuance if that code actually works in it's original PL. BTW I put out a call for Help at Discord but so far nuttin!
|
|
|
Post by anthonyrbrown on Feb 13, 2024 18:22:27 GMT
I understand bplus I have already made a perfect playing Tic-Tac-Tac in 18/08/2021 link below... www.petesqbsite.com/phpBB3/viewtopic.php?t=14873This is it beating TIC TAC TOE by Paul Meyer & TheBOB... petesqbsite.com/phpBB3/viewtopic.php?t=14868So that's not what I am after, all I was trying to solve is why does the VB code version nearly runs 100% except for the "Expected &H... or &0...on line 133 (click here or Ctrl+Shift+G to jump there)" Which looked like a 5 minute fix which I could not solve as I have very little knowledge of the code,so anyway thank's a lot for trying it will be interesting if we get some feed back from Discord A.R.B
|
|
|
Post by bplus on Feb 13, 2024 20:02:38 GMT
Oh! crap sometimes you have to repeat a point to me because I never tried the VB code cold in QB64, ha! I will try now and see about line 133, it should be just about getting the answer printed back. But how do you get past.... I need to check that code again. You might be right a quick 5 min fix. OK we are talking about this: Imports System Imports System.Collections.Generic
Class GFG Class Move Public row, col As Integer End Class
Shared player As Char = "x"c, opponent As Char = "o"c
Private Shared Function isMovesLeft(ByVal board As Char(,)) As Boolean For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1 If board(i, j) = "_"c Then Return True Next Next
Return False End Function
Private Shared Function evaluate(ByVal b As Char(,)) As Integer For row As Integer = 0 To 3 - 1
If b(row, 0) = b(row, 1) AndAlso b(row, 1) = b(row, 2) Then
If b(row, 0) = player Then Return +10 ElseIf b(row, 0) = opponent Then Return -10 End If End If Next
For col As Integer = 0 To 3 - 1
If b(0, col) = b(1, col) AndAlso b(1, col) = b(2, col) Then
If b(0, col) = player Then Return +10 ElseIf b(0, col) = opponent Then Return -10 End If End If Next
If b(0, 0) = b(1, 1) AndAlso b(1, 1) = b(2, 2) Then
If b(0, 0) = player Then Return +10 ElseIf b(0, 0) = opponent Then Return -10 End If End If
If b(0, 2) = b(1, 1) AndAlso b(1, 1) = b(2, 0) Then
If b(0, 2) = player Then Return +10 ElseIf b(0, 2) = opponent Then Return -10 End If End If
Return 0 End Function
Private Shared Function minimax(ByVal board As Char(,), ByVal depth As Integer, ByVal isMax As Boolean) As Integer Dim score As Integer = evaluate(board) If score = 10 Then Return score If score = -10 Then Return score If isMovesLeft(board) = False Then Return 0
If isMax Then Dim best As Integer = -1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player best = Math.Max(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best Else Dim best As Integer = 1000
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = opponent best = Math.Min(best, minimax(board, depth + 1, Not isMax)) board(i, j) = "_"c End If Next Next
Return best End If End Function
Private Shared Function findBestMove(ByVal board As Char(,)) As Move Dim bestVal As Integer = -1000 Dim bestMove As Move = New Move() bestMove.row = -1 bestMove.col = -1
For i As Integer = 0 To 3 - 1
For j As Integer = 0 To 3 - 1
If board(i, j) = "_"c Then board(i, j) = player Dim moveVal As Integer = minimax(board, 0, False) board(i, j) = "_"c
If moveVal > bestVal Then bestMove.row = i bestMove.col = j bestVal = moveVal End If End If Next Next
Console.Write("The value of the best Move " & "is : {0}" & vbLf & vbLf, bestVal) Return bestMove End Function
Public Shared Sub Main(ByVal args As String()) Dim board As Char(,) = { {"x"c, "o"c, "x"c}, {"o"c, "o"c, "x"c}, {"_"c, "_"c, "_"c}} Dim bestMove As Move = findBestMove(board) Console.Write("The Optimal Move is :" & vbLf) Console.Write("ROW: {0} COL: {1}" & vbLf & vbLf, bestMove.row, bestMove.col) End Sub End Class
I tell you what, start commenting out all the redlined code you run into and tell me what's left of the code that runs in QB64.
|
|