3

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 ?

blackbishop
  • 30,945
  • 11
  • 55
  • 76
  • In games, for which finding a good heuristics is too hard, the Monte Carlo approach seems to work the best (with the great success in the board game GO). – lejlot Jan 01 '14 at 19:29

1 Answers1

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.

Reut Sharabani
  • 30,449
  • 6
  • 70
  • 88
  • what do you mean by a sorted "Actions" list? – blackbishop Jan 02 '14 at 00:41
  • The min-max algorithm is based on actions. You apply an action on a state and the result is a new state. If you have the "available Actions" list sorted by what you think yields the best results - you can have better prunning by getting the "good" results for each player faster (that is, if you're right). – Reut Sharabani Jan 02 '14 at 06:51
  • Thanks for the links. I started to build a linear evaluation function. – blackbishop Jan 02 '14 at 16:06
  • Good luck, can't say I'm an expert, and you may have better luck asking here: http://cstheory.stackexchange.com/ – Reut Sharabani Jan 02 '14 at 16:08