1

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?

  • This doesn't do much beyond assuming that possession of points near the center is good (included in more possible rows). This can't function as a complete evaluation function by itself since it consider partial or even complete rows at all. It's only a heuristic to distinguish between situations and moves that look similarly good after looking at (partial) rows. – CodesInChaos Nov 22 '14 at 14:51
3

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.
  • Ah! That makes sense. But I am curious about @CodesInChaos comment. Can this be considered a complete evaluation function or only a heuristic? – Michael James Nov 22 '14 at 14:57
  • This is the "utility function" describing the value of each square; I don't think it's a heuristic, but @CodesInChaos may know better than me. Nice question, BTW. – James McLeod Nov 22 '14 at 15:01
  • Thanks! Ok, this brings me to my next question. Why 128 for int utility? – Michael James Nov 22 '14 at 15:49
  • Good question. I think we might have to see how the result of this function is used to answer that. – James McLeod Nov 22 '14 at 15:56
  • Maybe it's a typo - the sum of all numbers in the table is 276 = 2 *138. Then values < 0, = 0, and > 0 have some relative meaning. – James McLeod Nov 22 '14 at 16:25
1

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.

  • Awesomme. Thanks for the explanation. Care to elaborate on longest_chain? – Michael James Oct 9 '15 at 18:01
  • @michael def longest_chain(self, playerid): longest = 0 for i in xrange(self.board_height): for j in xrange(self.board_width): if self.get_cell(i,j) == playerid: longest = max( longest, self._max_length_from_cell(i,j) ) return longest` – Vishal Sahu Oct 9 '15 at 19:20
  • @michael here max returns count of longest streak in any possible 4 position from player's position. – Vishal Sahu Oct 9 '15 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.