I am exploring how a Minimax algorithm can be used in a connect four game. I was looking through a program and found this evaluation function.
private static int[][] evaluationTable = {{3, 4, 5, 7, 5, 4, 3},
{4, 6, 8, 10, 8, 6, 4},
{5, 8, 11, 13, 11, 8, 5},
{5, 8, 11, 13, 11, 8, 5},
{4, 6, 8, 10, 8, 6, 4},
{3, 4, 5, 7, 5, 4, 3}};
//here is where the evaluation table is called
public int evaluateContent() {
int utility = 128;
int sum = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j <columns; j++)
if (board[i][j] == 'O')
sum += evaluationTable[i][j];
else if (board[i][j] == 'X')
sum -= evaluationTable[i][j];
return utility + sum;
}
And then a MiniMax algo is used to evaluate the possible solutions.
I am not sure how/why this works. Would anyone be able to explain?
1
The numbers in the table indicate the number of four connected positions which include that space for example:
- the 3 in the upper left corner is for one each of horizontal, vertical, and diagonal lines of four which can be made with it.
- the 4 beside it is for two horizontal (one including starting in the corner, one starting on it, one vertical, and one diagonal)
This gives a measurement of how useful each square is for winning the game, so it helps decide the strategy.
I believe that the evaluateBoard function returns a number <0 if
int utility = 128
is a typo – it should be initialized to 138 (since the sum of all the values in the table is 276 = 2 x 138). This would make the evaluateBoard function return:
- < 0 if the player whose marker is ‘X’ is likely to win (has the most strategic places based on the utility function)
- = 0 if the players are equally likely to win
- > 0 if the player whose marker is ‘O’ is likely to win.
6
This evaluation function is nothing but Gaussian normal distribution centered around the mean position of board. The one with more centered positions gets higher score from this eval func. If you plot this matrix in MATLAB, you’ll find that the values form a tent and hence give bias to center position. However I must say there are way better evaluation function than this as this performs total evaluation and doesn’t do spatial analysis.
score = board.longest_chain(board.get_current_player_id()) * 10
# Prefer having your pieces in the center of the board.
# score boost
for row in range(6):
for col in range(7):
if board.get_cell(row, col) == board.get_current_player_id():
score -= abs(3-col)
elif board.get_cell(row, col) == board.get_other_player_id():
score += abs(3-col)
Above is just one example where it applies center oriented idea over spatial analysis result obtained via longest_chain.
3