How to create an evaluation function for a TIC-TAC-TOE variant game

Question

I'm actually working on a board game which is a variant of the TIC-TAC-TOE game. The specifics of the game are the followings :

1. The game is played on a nxn board, with n variable.

2. A player wins if he succeeds in placing k alignments the first, k is variable.

3. An alignment is constituted of l marks (X or O) in a horizontal, vertical or diagonal. l is fixed.

4. If the nxn grid is full (no player can add a mark either X or O) and no player succeeded in placing k alignments so the game is drawn.

I'm using an minmax with alpha-beta prunning algorithm. This is my first program with artificial intelligence and I don't know exactly how to create the evaluation function to be used by the algorithm. I saw some examples on the net which use a material weighting to evaluate a position but I can't apply that in my case. Actually, I'm using a radom evaluation function which returns a value between -100 and 100.

    float Conf_eval(Configuration c)
       {
         return (rand()%201)-100;
       }

Any idea on how can I evaluate a given board configuration ?

Answer 1

This is thoroughly discussed in the book Artificial Intelligence - A Modern Approach

There are also excellent implementations available (this is java, there is also python, you can Google for more) based on the book series. Including for tic-tac-toe (and alpha-beta pruning agents).

If you're using the min-max algorithm with alpha-beta prunning, you can use a sorted "Actions" list to perform better in addition to your heuristic function (a trivial utility-function would be assigning 1 to a victory, 0 to a tie and -1 to a loss - these are all leaf nodes of the min-max expanded tree).

To sort the actions you can, for say, prefer actions that add your symbol(X, O) to a clear-to-victory path. This should eventually lead to better prunning.