Hello everyone!

Firstly let me say that I am very impressed with your site and with your work. I liked the explanations about the min-max algorithm very much and I have a problem that you could probably help me in the same domain.

I've written a Gomoku (5-in-a-row tic-tic-toe) game using alfa-beta prunning and it seems that my evaluation function doesn't quite get it right.

Let me describe what I've done so far:

1. I have chosen to evaluate each square by measuring what exists in all 8 possible directions and up to 6 squares distance.

for example: *xxx-- where:
* = square to be evaluated
X = own marker (either computer's or human's)
- = empty square
O = enemy's marker

*xxx-- would have a value of 3
*XXXX- = 4-in-a-row
*xxxO- = 0 (a solution is no longer possible on that direction)
...

2. At each move the squares that are modified are re-evaluated and the result stored in a bi-dimensional table, ordered by a) the closeness to a solution, and b) by a combinatoric value that keeps count of the own markers around the evaluated square.
This helps to end search when a win situation is found at level smaller than MaxLevel;

ComputerVals[6][225] //225 = 15x15 squares gaming board
HumanVals[6][225] //identically but from human player perspective

ComputerVals[5] = [*XXXXX] (won)
ComputerVals[4] = [*XXXX-] (win)
ComputerVals[3] = [-*xxx-] (unbeatable)
ComputerVals[2] = ...
ComputerVals[0] = [*-----] (empty spaces all around)

each ComputerVal[][] contains both value and an index into the gaming table.

My minmax algorithm looks like:

int MaxFunc(int alfa, int beta, int level)
{
__for(i=5;i>0;i--)
__{
____for each j at ComputerVal[i][j] do
____{
______PutMove(ComputerVal[i][j].index);
______ReevaluateSquares();
______if(Evaluate() == WinSituation)
______{
_________DeleteSquare(ComputerVal[i][j].index);
_________ReevaluateSquares();
_________return WinSituation;
______}
______if(level < MaxLevel)
______{
_________alfa = max(alfa, MinFunc(alfa, beta, level+1));
_________if(alfa>=beta)return beta;
______}
______else
_________return Evaluation();
______DeleteMove(ComputerVal[i][j].index);
______ReevaluateSquares();
____}
__}
__return alfa;
}

The trouble is that on a Pentium 2 at 500 Mhz I can only go 5-6 levels deep in a reasonable amount of time, and the result is that after the game finds the first *xxxx- situation the alfa-beta prunning prevents it to look for a unbeatable situation and exits.

so it may lead to:
* = next move

-----x -----x ------
-*xxx0 -xxx*0 ------
-----0 -----0 -xx*-0
-----0 -----0 -x----
-----0 ------ ------
------ ------ ------

3. Finally:

QUESTION:

DO YOU KNOW OF ANY EVALUATION FUNCTION THAT MAY WORK OR A PLACE WHERE TO LOOK FOR IT?

(any suggestions are very welcome)

Thanks a lot!

Using a transposition table should work well with these game rules for getting a faster search and allowing you to increase your search depth.

What are the usual way of implementing transposition tables?
Any ideas on how to detect "stupid" moves?

Thanks!

Yes.

Transposition tables take advantage of re-occurrence of the same game state in different branches of the search tree. When each position is encountered the "backed up" score assigned to it (by means of the look-ahead search extended from that position)is stored with the position. If that position is encountered again then it is necessary to play from that position - the previous position can simply be looked up to get a score.

Storing all these positions so that they can be looked up quickly is non-trivial and a technique called "hashing" is commonly used; it is easy to find web sites which tell you how to do this.

Your game, Gomuku, would give good results for transposition, because a lot of positions are equivalent to each other.

For example:

Look at any position and find any "pieces" that have been put down that can no longer form part of a line of 4 four - replace these pieces by a generic symbol that is the same for either side. (e.g. just put "N" in their place)

Look at any position and find any regions that can no longer have any pieces placed in them to form a line of 4 - also replace the squares in these regions by the same generic symbol (i.e. put "N" in their place).

The idea is that an "N" square is no longer of any relevance in the game, so whether it is occupied by either player should be irrelevant (but check about any strange conditions near the end of the game - you have to be careful with assumptions made when doing this sort of thing).

This will give a modified version for each position. Storing these modified positions, instead of the real positions, will make transposition much more effective as one stored position will now map onto many actual game positions.

To get an efficient search you also need something called "fast refutation" - for this you need to run through moves at every node in order of likely desirability.

You still need to look carefully at your evaluation function.

I achieved a 20% increase of speed of my gomoku program by not recounting the values for a move which is taken back. My program simply loads them form an array constructed before.

But saying that I must add that I use an oversophisticated evaluation function, counting not lines, but 'forks' (i.e. broken three + straight two on the same square). Moreover I use something that is called "H heuristics" - the program counts signs in a H-shaped pattern (the more-the better).