Heuristic/Evaluation Function for tic-tac-toe

by

I admit that tic-tac-toe is a very simple game and can be solved all the way through with the minimax algorithm but if a simple heuristic/evaluation function can help save that computation, I guess it’s worth taking a look at.

This is a static evaluation function which assigns a utility value to each board position by assigning weights to each of the 8 possible ways to win in a game of tic-tac-toe and then summing up those weights.


Here’s an implementation in C:

#define Possible_Wins 8
const int Three_in_a_Row[Possible_Wins][3] = {
{ 0, 1, 2 },
{ 3, 4, 5 },
{ 6, 7, 8 },
{ 0, 3, 6 },
{ 1, 4, 7 },
{ 2, 5, 8 },
{ 0, 4, 8 },
{ 2, 4, 6 }
};
const int Heuristic_Array[4][4] = {
{ 0, -10, -100, -1000 },
{ 10, 0, 0, 0 },
{ 100, 0, 0, 0 },
{ 1000, 0, 0, 0 }
};
int evaluatePosition(char board[9], char player) {
char opponent = (player == 'X') ? 'O' : 'X', piece;
int players, others, t = 0, i, j;
for (i = 0; i < 8; i++) {
players = others = 0;
for (j = 0; j < 3; j++) {
piece = board[Three_in_a_Row[i][j]];
if (piece == player)
players++;
else if (piece == opponent)
others++;
}
t += Heuristic_Array[players][others];
}
return t;
}
view raw Tic Tac Toe Heuristic.cpp hosted with ❤ by GitHub

I implemented a bot for tic-tac-toe with the above described heuristic function and a lookahead of two moves. It performed really well, not losing a single game in over a 1000 matches against other bots on hackerrank.

18 thoughts on “Heuristic/Evaluation Function for tic-tac-toe”

  1. I wanted to grab your rss or email subscription link or newsletter service. Do you have any?
    Kindly respond so that I could subscribe.
    Thanks.

    Reply

  2. When I initially commented I clicked the “Notify me when new comments are added” checkbox and
    now each time a comment is added I get three emails with the same
    comment. Is there any way you can remove people from
    that service? Bless you!

    Reply

  3. hy,
    i am very amazed to see this function. it works perfect. Kindly tell me the purpose of 10 , -10 or 100 or 1000 in the heuristics array. i understood what you did in Three_in_a_Row array but i didn’t understand heurisitics array.
    how is this heuristics working.

    Reply

    • Basically for each row, column & diagonal, we count the number of our marker (call it X) and our opponent’s marker (call it O). If X == O, no player has an advantage over another and we get a utility of 0. We get a positive utility for X > O and a negative utility for X < O. When X == 3 (i.e., we have three markers in some row, column or diagonal), we win in that position and get a utility of 1000 (read Infinity). IF O == 3, we lose in that position and get a utility of -1000 (read negative infinity). Similarly, utility values for other combinations of X & O are developed.

      Reply

  4. thanks Kartik Kukreja for a quick reply. Now I understand what the values are doing in the heuristic array. But can you please tell me what’s the logic behind placing these values on specific indexes as just in the boundaries in the heuristic array.
    The reason why i am so interested in it that i am using your heuristic function in my tic tac toe project and i have used your heuristic for the hard level. It works fine on most of the cases. But in some of the cases it gets down a little. If i understood the heuristics values totally , i can change it to my scenerios.
    I completely understand your algorithm for calculating it.

    Reply

    • I thought I explained that but anyway suppose I’m player X and you are player O. In some row, column or diagonal, count of X’s is numX and that of O’s is numO. There are following four cases :

      1. numX == numO : No player has an advantage. Utility = 0. This fills the main diagonal in the heuristic array.
      2. numX > numO and numO == 0 : I have some X’s while you have none in some row, column or diagonal i.e., I have a possibility of winning so I get a positive utility depending on the number of X’s. The greater the number of X’s, the greater is my utility from the position. This fills the first column in the heuristic array.
      3. numX < numO and numX == 0 : Since the game is symmetric, this is completely analogous to the previous case except that now my utility is negative and the position is advantageous for you. This fills the first row in the heuristics array.
      4. otherwise : In all other cases, no player has a chance of making 3-in-a-row because another player has at least one of their marker there. Since the game is won by having 3-in-a-row and not just more markers there, the position offers no advantage to any player and thus should have a utility of 0. This fills the remaining entries in the heuristics array.

      When I implemented this heuristic, it wasn’t performing well with one move of lookahead but worked perfectly with two moves of lookahead. If you are using some version of minimax algorithm for tic-tac-toe, you should be fine with it. If for all possible moves, you are just enumerating the resulting positions and playing the move that leads to the highest utility, then you should probably change it.

      I implemented it this way :

      foreach of my possible moves:
    t = my utility for resulting position
    worst = -INF
    foreach of my opponent's moves from that position:
        tmp = opponent's utility for resulting position
        if tmp > worst:
            worst = tmp
    t -= worst
return the maximum value of t

      I hope this helps.

      Reply

  9. Pingback: Alpha Beta Search | Everything Under The Sun

Leave a reply to kartik kukreja Cancel reply