c#vb.netalgorithmartificial-intelligenceminimax
AlphaBeta Pruning TicTacToe is not blocking, is it eval problem?
I'm debuging this for days and i don't know what I made wrong in this piece of code for Tic-Tac-Toe game and AI (well I know its not real AI but...) I have choosen for this was Alpha-Beta pruning. Its 7x7 board so it would be too heavy for pure minimax implementation.
Problem I have is that i can't figure out why Alpha-Beta is not blocking player to stall the game and wait for player move and use proper move in his favour, or just simply tie the game.
I've decided that center of board will have more points(for end score) than the one at the edges of the board. I belive that moves more to the center will have more chance to success than the ones in the edges, thats why i made AddScoreToMove function that evaluates that move.
To Ensure that eval function will check EVERY possible moves at board I didn't made that function to work as find first xxx (for example at row0 and col0,col1,col2) and return (cause maybe there is 4X's or 4O's). Also 4X or 4O gives substantially more score than other ones and should be considered as win.
At this moment my PCplayer( O's) play like this
Can anyone tell me what i made wrong? It's my second program with AI, and first was with minimax on 3x3 board whitch worked fine.
C# code is below
VB.NET CODE:
Public Class Form1
Dim board As Char(,) = {
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "},
{" ", " ", " ", " ", " ", " ", " "}}
Class Move
Public row, col As Integer
End Class
Dim BestMoveRow As Integer = 0
Dim BestMoveCol As Integer = 0
Dim BestMoveScore As Integer = 0
Shared player As Char = "X", opponent As Char = "O"
Shared Function AddScoreToMove(thatMove As Move) As Integer
Dim row As Integer = thatMove.row
Dim col As Integer = thatMove.col
'0 score, move is at border
If ((row >= 1 And row <= 5) And col = 0) Then
Return 0
ElseIf ((row >= 1 And row <= 5) And col = 6) Then
Return 0
ElseIf (row = 0 And (col >= 0 And col <= 6)) Then
Return 0
ElseIf (row = 6 And (col >= 0 And col <= 6)) Then
Return 0
End If
'1 score, thatMove is at border +1
If ((row >= 2 And row <= 4) And col = 1) Then
Return 1
ElseIf ((row >= 2 And row <= 4) And col = 5) Then
Return 1
ElseIf (row = 1 And (col >= 1 And col <= 5)) Then
Return 1
ElseIf (row = 5 And (col >= 1 And col <= 5)) Then
Return 1
End If
'2 score, thatMove is at border +2
If (row = 2 And col = 2) Then
Return 2
ElseIf (row = 2 And col = 4) Then
Return 2
ElseIf (row = 2 And (col >= 2 And col <= 4)) Then
Return 2
ElseIf (row = 4 And (col >= 2 And col <= 4)) Then
Return 2
End If
'3 Center thatMove
If (row = 3 And col <= 3) Then
Return 3
End If
Return 0 'error not added lane
End Function
Private Shared Function eval(ByVal b As Char(,)) As Integer
Dim playerScorerow As Integer = 0
Dim playerScorecol As Integer = 0
Dim playerScorecross As Integer = 0
Dim pcScorerow As Integer = 0
Dim pcScorecol As Integer = 0
Dim pcScorecross As Integer = 0
''EVALUATE rows
For row As Integer = 0 To 3
For col As Integer = 0 To 6
'initialize moves to evaluate
Dim move3 As New Move With {
.row = row + 3,
.col = col
}
Dim move2 As New Move With {
.row = row + 2,
.col = col
}
Dim move1 As New Move With {
.row = row + 1,
.col = col
}
Dim move0 As New Move With {
.row = row,
.col = col
}
If Not b(row, col) = " " Then 'ITS NOT EMPTY - PLAYER OR PC MOVED HERE
Dim moveScore As Integer = AddScoreToMove(move0) 'EVALUATE THAT MOVE
If b(row, col) = b(row + 1, col) Then 'THERE IS 2 X or 2 O
Dim move1Score As Integer = AddScoreToMove(move1)
If b(row + 1, col) = b(row + 2, col) Then 'THERE IS 3x or 3O
Dim move2Score As Integer = AddScoreToMove(move2)
If b(row + 2, col) = b(row + 3, col) Then 'THERE IS 4X or 4O
Dim move3Score As Integer = AddScoreToMove(move3)
If b(row, col) = player Then 'PLAYER HAVE 4X HERE
playerScorerow = Math.Max(playerScorerow, 100 + move3Score + move2Score + move1Score + moveScore) 'GET HIGHEST OF ALL EVALUATIONS OF THAT FOR LOOPS
ElseIf b(row, col) = opponent Then 'PC HAVE 4O HERE
pcScorerow = Math.Min(pcScorerow, -100 - move3Score - move2Score - move1Score - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, 5 + move2Score + move1Score + moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -5 - move2Score - move1Score - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, 2 + move1Score + moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -2 - move1Score - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -moveScore)
End If
End If
Next
Next
''col win
For row As Integer = 0 To 6
For col As Integer = 0 To 3
Dim move3 As New Move With {
.row = row + 3,
.col = col
}
Dim move2 As New Move With {
.row = row + 2,
.col = col
}
Dim move1 As New Move With {
.row = row + 1,
.col = col
}
Dim move0 As New Move With {
.row = row,
.col = col
}
If Not b(row, col) = " " Then
Dim moveScore As Integer = AddScoreToMove(move0)
If b(row, col) = b(row, col + 1) Then
Dim moveScore1 As Integer = AddScoreToMove(move1)
If b(row, col + 1) = b(row, col + 2) Then
Dim moveScore2 As Integer = AddScoreToMove(move2)
If b(row, col + 2) = b(row, col + 3) Then
Dim moveScore3 As Integer = AddScoreToMove(move3)
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, 100 + moveScore3 + moveScore2 + moveScore1 + moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -100 - moveScore3 - moveScore2 - moveScore1 - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, 5 + moveScore2 + moveScore1 + moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -5 - moveScore2 - moveScore1 - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, 2 + moveScore1 + moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -2 - moveScore1 - moveScore)
End If
End If
If b(row, col) = player Then
playerScorerow = Math.Max(playerScorerow, moveScore)
ElseIf b(row, col) = opponent Then
pcScorerow = Math.Min(pcScorerow, -moveScore)
End If
End If
Next
Next
'NOT FULLY IMPLEMENTED
'cross win
For row As Integer = 0 To 3
For col As Integer = 0 To 3
If Not b(row, col) = " " Then
If (b(row, col) = b(row + 1, col + 1) AndAlso b(row + 1, col + 1) = b(row + 2, col + 2) AndAlso b(row + 2, col + 2) = b(row + 3, col + 3)) Then
If b(row, col) = player Then
Return +10
ElseIf b(row, col) = opponent Then
Return -10
End If
End If
End If
Next
Next
'NOT FULLY IMPLEMENTED
'cross win
For row As Integer = 0 To 3
For col As Integer = 3 To 6
If Not b(row, col) = " " Then
If (b(row, col) = b(row + 1, col - 1) AndAlso b(row + 1, col - 1) = b(row + 2, col - 2) AndAlso b(row + 2, col - 2) = b(row + 3, col - 3)) Then
If b(row, col) = player Then
Return +10
ElseIf b(row, col) = opponent Then
Return -10
End If
End If
End If
Next
Next
Dim scoreValues() As Integer = {playerScorerow, playerScorecol, playerScorecross, pcScorerow, pcScorecol, pcScorecross}
Dim max = scoreValues.OrderByDescending(Function(z) Math.Abs(z)).FirstOrDefault()
Return max
End Function
Private Shared Function MiniMax(ByVal board As Char(,), ByVal machineMove As Boolean, ByVal depth As Integer) As Integer
Const alpha As Integer = -10_000
Const beta As Integer = 10_000
Return AlphaBetaPruning(board, machineMove, depth, beta, alpha)
End Function
Private Shared Function AlphaBetaPruning(ByVal board As Char(,), ByVal machineMove As Boolean, ByVal depth As Integer, ByVal beta As Integer, ByVal alpha As Integer) As Integer
If depth = 0 Then Return eval(board)
If machineMove Then 'min PC MOVE
For i As Integer = 0 To 6
For j As Integer = 0 To 6
If board(i, j) = " " Then
board(i, j) = opponent
Dim score As Integer = Math.Min(AlphaBetaPruning(board, Not machineMove, depth - 1, beta, alpha), eval(board))
board(i, j) = " "
If score < beta Then
Form1.BestMoveRow = i
Form1.BestMoveCol = j
Form1.BestMoveScore = score
beta = score
End If
If alpha >= beta Then Exit For 'cutoff
End If
Next
Next
Return beta
Else 'max PLAYER MOVE
For i As Integer = 0 To 6
For j As Integer = 0 To 6
If board(i, j) = " " Then
board(i, j) = player
Dim score As Integer = Math.Max(AlphaBetaPruning(board, Not machineMove, depth - 1, beta, alpha), eval(board))
board(i, j) = " "
If score > alpha Then
alpha = score
End If
If alpha >= beta Then Exit For
End If
Next
Next
Return alpha
End If
End Function
End Class
C# CODE
public class Form1
{
private char[,] board = new[] { { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " }, { " ", " ", " ", " ", " ", " ", " " } };
class Move
{
public int row, col;
}
private int BestMoveRow = 0;
private int BestMoveCol = 0;
private int BestMoveScore = 0;
private static char player = "X";
private static char opponent = "O";
public static int AddScoreToMove(Move thatMove)
{
int row = thatMove.row;
int col = thatMove.col;
// 0 score, move is at border
if (((row >= 1 & row <= 5) & col == 0))
return 0;
else if (((row >= 1 & row <= 5) & col == 6))
return 0;
else if ((row == 0 & (col >= 0 & col <= 6)))
return 0;
else if ((row == 6 & (col >= 0 & col <= 6)))
return 0;
// 1 score, thatMove is at border +1
if (((row >= 2 & row <= 4) & col == 1))
return 1;
else if (((row >= 2 & row <= 4) & col == 5))
return 1;
else if ((row == 1 & (col >= 1 & col <= 5)))
return 1;
else if ((row == 5 & (col >= 1 & col <= 5)))
return 1;
// 2 score, thatMove is at border +2
if ((row == 2 & col == 2))
return 2;
else if ((row == 2 & col == 4))
return 2;
else if ((row == 2 & (col >= 2 & col <= 4)))
return 2;
else if ((row == 4 & (col >= 2 & col <= 4)))
return 2;
// 3 Center thatMove
if ((row == 3 & col <= 3))
return 3;
return 0; // error not added lane
}
private static int eval(char[,] b)
{
int playerScorerow = 0;
int playerScorecol = 0;
int playerScorecross = 0;
int pcScorerow = 0;
int pcScorecol = 0;
int pcScorecross = 0;
// 'EVALUATE rows
for (int row = 0; row <= 3; row++)
{
for (int col = 0; col <= 6; col++)
{
// initialize moves to evaluate
Move move3 = new Move()
{
row = row + 3,
col = col
};
Move move2 = new Move()
{
row = row + 2,
col = col
};
Move move1 = new Move()
{
row = row + 1,
col = col
};
Move move0 = new Move()
{
row = row,
col = col
};
if (!b[row, col] == " ")
{
int moveScore = AddScoreToMove(move0); // EVALUATE THAT MOVE
if (b[row, col] == b[row + 1, col])
{
int move1Score = AddScoreToMove(move1);
if (b[row + 1, col] == b[row + 2, col])
{
int move2Score = AddScoreToMove(move2);
if (b[row + 2, col] == b[row + 3, col])
{
int move3Score = AddScoreToMove(move3);
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 100 + move3Score + move2Score + move1Score + moveScore); // GET HIGHEST OF ALL EVALUATIONS OF THAT FOR LOOPS
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -100 - move3Score - move2Score - move1Score - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 5 + move2Score + move1Score + moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -5 - move2Score - move1Score - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 2 + move1Score + moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -2 - move1Score - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -moveScore);
}
}
}
// 'col win
for (int row = 0; row <= 6; row++)
{
for (int col = 0; col <= 3; col++)
{
Move move3 = new Move()
{
row = row + 3,
col = col
};
Move move2 = new Move()
{
row = row + 2,
col = col
};
Move move1 = new Move()
{
row = row + 1,
col = col
};
Move move0 = new Move()
{
row = row,
col = col
};
if (!b[row, col] == " ")
{
int moveScore = AddScoreToMove(move0);
if (b[row, col] == b[row, col + 1])
{
int moveScore1 = AddScoreToMove(move1);
if (b[row, col + 1] == b[row, col + 2])
{
int moveScore2 = AddScoreToMove(move2);
if (b[row, col + 2] == b[row, col + 3])
{
int moveScore3 = AddScoreToMove(move3);
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 100 + moveScore3 + moveScore2 + moveScore1 + moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -100 - moveScore3 - moveScore2 - moveScore1 - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 5 + moveScore2 + moveScore1 + moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -5 - moveScore2 - moveScore1 - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, 2 + moveScore1 + moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -2 - moveScore1 - moveScore);
}
if (b[row, col] == player)
playerScorerow = Math.Max(playerScorerow, moveScore);
else if (b[row, col] == opponent)
pcScorerow = Math.Min(pcScorerow, -moveScore);
}
}
}
// NOT FULLY IMPLEMENTED
// cross win
for (int row = 0; row <= 3; row++)
{
for (int col = 0; col <= 3; col++)
{
if (!b[row, col] == " ")
{
if ((b[row, col] == b[row + 1, col + 1] && b[row + 1, col + 1] == b[row + 2, col + 2] && b[row + 2, col + 2] == b[row + 3, col + 3]))
{
if (b[row, col] == player)
return +10;
else if (b[row, col] == opponent)
return -10;
}
}
}
}
// NOT FULLY IMPLEMENTED
// cross win
for (int row = 0; row <= 3; row++)
{
for (int col = 3; col <= 6; col++)
{
if (!b[row, col] == " ")
{
if ((b[row, col] == b[row + 1, col - 1] && b[row + 1, col - 1] == b[row + 2, col - 2] && b[row + 2, col - 2] == b[row + 3, col - 3]))
{
if (b[row, col] == player)
return +10;
else if (b[row, col] == opponent)
return -10;
}
}
}
}
int[] scoreValues = new[] { playerScorerow, playerScorecol, playerScorecross, pcScorerow, pcScorecol, pcScorecross };
var max = scoreValues.OrderByDescending(z => Math.Abs(z)).FirstOrDefault();
return max;
}
private static int MiniMax(char[,] board, bool machineMove, int depth)
{
const int alpha = -10_000;
const int beta = 10_000;
return AlphaBetaPruning(board, machineMove, depth, beta, alpha);
}
private static int AlphaBetaPruning(char[,] board, bool machineMove, int depth, int beta, int alpha)
{
if (depth == 0)
return eval(board);
if (machineMove)
{
for (int i = 0; i <= 6; i++)
{
for (int j = 0; j <= 6; j++)
{
if (board[i, j] == " ")
{
board[i, j] = opponent;
int score = Math.Min(AlphaBetaPruning(board, !machineMove, depth - 1, beta, alpha), eval(board));
board[i, j] = " ";
if (score < beta)
{
Form1.BestMoveRow = i;
Form1.BestMoveCol = j;
Form1.BestMoveScore = score;
beta = score;
}
if (alpha >= beta)
break; // cutoff
}
}
}
return beta;
}
else
{
for (int i = 0; i <= 6; i++)
{
for (int j = 0; j <= 6; j++)
{
if (board[i, j] == " ")
{
board[i, j] = player;
int score = Math.Max(AlphaBetaPruning(board, !machineMove, depth - 1, beta, alpha), eval(board));
board[i, j] = " ";
if (score > alpha)
alpha = score;
if (alpha >= beta)
break;
}
}
}
return alpha;
}
}
}
Solution
After another day of debuging this I'm kinda lost, but i figured out how to bypass this which might be a real solution to this problem. AlphaBeta concentrates only on winning. That's related actually to eval function, and if we take more factor's to eval function to consider then better that function is. That's why we have
- Basic Win factor -> that is evaluation of moves to win the game
- Blocking enemy factor -> to stall the game
- There's also Forking factor that i have not implemented yet. Info for that is here: https://en.wikipedia.org/wiki/Tic-tac-toe#Strategy and from https://stackoverflow.com/a/19406575/9283016
In nutshell - Simple AlphaBeta Function with simple evaluation of (only) winning does not take into consideration to play time. We have to write proper function of blocking and forking.
Private Shared Function evalBlock(ByVal b As Char(,)) As Move
Dim blockingMove As New Move With {
.row = -1,
.col = -1
}
''row block
For row As Integer = 0 To 4
For col As Integer = 0 To 6
If Not b(row, col) = " " Then
If b(row, col) = b(row + 1, col) Then '2 X or 2 O
If b(row, col) = player Then
If b(row + 2, col) = " " Then
blockingMove.row = row + 2
blockingMove.col = col
Return blockingMove
End If
If row > 0 Then
If b(row - 1, col) = " " Then
blockingMove.row = row - 1
blockingMove.col = col
Return blockingMove
End If
End If
End If
End If
End If
Next
Next
''col block
For row As Integer = 0 To 6
For col As Integer = 0 To 4
If Not b(row, col) = " " Then
If b(row, col) = b(row, col + 1) Then '2 X or 2 O
If b(row, col) = player Then
If b(row, col + 2) = " " Then
blockingMove.row = row
blockingMove.col = col + 2
Return blockingMove
End If
If col > 1 Then
If b(row, col - 1) = " " Then
blockingMove.row = row
blockingMove.col = col - 1
Return blockingMove
End If
End If
End If
End If
End If
Next
Next
'\ cross block
For row As Integer = 0 To 4
For col As Integer = 0 To 4
If Not b(row, col) = " " Then
If (b(row, col) = b(row + 1, col + 1)) Then
If b(row, col) = player Then
If b(row + 2, col + 2) = " " Then
blockingMove.row = row + 2
blockingMove.col = col + 2
End If
If (row > 0 And col > 0) Then
If b(row - 1, col - 1) = " " Then
blockingMove.row = row - 1
blockingMove.col = col - 1
End If
End If
End If
End If
End If
Next
Next
'/ cross block
For row As Integer = 0 To 4
For col As Integer = 2 To 6
If Not b(row, col) = " " Then
If (b(row, col) = b(row + 1, col - 1)) Then
If b(row, col) = player Then
If b(row, col) = " " Then
blockingMove.row = row + 2
blockingMove.col = col - 2
End If
End If
End If
End If
Next
Next
blockingMove.row = -1
blockingMove.col = -1
Return blockingMove
End Function
Of course returning blocking move don't do anything. In AlphaBeta function we have to assign proper value to this. So i figured out that our AI will block player if he made 2 winning moves and blocking is preferable than winning. Also blocking after 2 player moves makes more sense than blocking after 3 cause it might be to late if we play using rules that 4 moves win.
Something like this:
Dim score As Integer = Math.Min(AlphaBetaPruning(board, Not machineMove, depth - 1, beta, alpha), eval(board) + depth)
Dim BlockingMove As Move = evalBlock(board)
If BlockingMove.row <> -1 Then
Dim blockingMoveScore As Integer = 5000
If score < blockingMoveScore Then
Form1.BestMoveRow = BlockingMove.row
Form1.BestMoveCol = BlockingMove.col
Form1.BestMoveScore = score
End If
End If
And that's how i lost after first game with my AI.
