# Heuristic/Evaluation Function for tic-tac-toe

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:

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. Lazaro says:

Kindly respond so that I could subscribe.
Thanks.

• Thank you for bringing it to my notice. I’ve added the rss link and email subscription.

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!

• I have no idea how to do that. Maybe you should unsubscribe and subscribe again without comment notifications.

3. umair khalid says:

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.

• 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.

4. umair khalid says:

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.

• 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.

5. umair khalid says:

Thanks a lot , I understand it completely now. I’d recommend your blog to my friends too.

6. What do you mean by implementing a bot for tic-tac-toe?

• A bot is a computer player capable of playing the next move, given the board configuration. Here I’ve written two bots for tic-tac-toe: C++ implementation of two tic-tac-toe bots. One is a strategy-based player, which plays moves according to a fixed strategy and the other is a heuristic-based player, which uses the heuristic described in this post. Hope this helps!

7. Anonymous says:

please make me understand in the term of heuristic function

8. KD says:

Great Blog, please write further posts