Pretty good heuristic evaluation rules for big TicTacToe 5x5 board

Question

I have created TicTacToe game. I use minmax algorithm.

When the board is 3x3 I just calculate every possible move for a game till the end and -1 for loss, 0 for tie, 1 for win.

When it comes to 5x5 it can't be done(to many options(like 24^24) so I have created evaluation method which gives: 10^0 for one CIRCLE inline, 10^1 for 2 CIRCLE inline, ..., 10^4 for 5 CIRCLES inline, but it is useless.

Does anybody have better idea for assesment?

Example:

O|X|X| | |
----------
 |O| | | |
----------
X|O| | | |
----------
 | | | | |
----------
 | | | | |

Evaluation -10, 2 circles across once and inline once (+200), 2 crosses inline(-100), and -1 three times and + 1 three times for single cross and circle.

This is my evaluation method now:

public void setEvaluationForBigBoards() {
        int evaluation = 0;
        int howManyInLine = board.length;
        for(; howManyInLine > 0; howManyInLine--) {
            evaluation += countInlines(player.getStamp(), howManyInLine);
            evaluation -= countInlines(player.getOppositeStamp(), howManyInLine);
        }
        this.evaluation = evaluation;
    }

    public int countInlines(int sign, int howManyInLine) {
        int points = (int) Math.pow(10, howManyInLine - 1);
        int postiveCounter = 0;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                //czy od tego miejsca jest cos po przekatnej w prawo w dol, w lewo w dol, w dol, w prawo
                if(toRigth(i, j, sign, howManyInLine))
                    postiveCounter++;
                if(howManyInLine > 1) {
                    if(toDown(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toRightDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toLeftDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                }
            }
        }
        return points * postiveCounter;
    }

Answer 1

Number of options (possible sequences of moves) after the first move is 24! and not 24^24. It is still a too much high of a number so it is correct to implement an heuristic.

Note that answers about good heuristics are necessarily based on the opinion of the writer so I give my opinion but to find out what is "the best heuristic" you should make the various ideas playing one against the other in the following way:

• take the two heuristics A and B that you want to compare
• generate at random a starting configuration
• let A play with O and B play with X
• from the same starting configuration let A play with X and B play with O
• take stats of which one wins more

Now my thoughts about good possible heuristics starting points for an nxn playfield with winning sequence length of n:

• since the winning condition for a player is to form a straight sequence of its marks my idea is to use as base values the number of possibilities that each player has still available to built such a straight sequence.
• in an empty field both O and X have ideally the possibility to realize the winning sequence in several ways:
  • horizontal possibilities: n
  • vertical possibilities: n
  • diagonal possibilities: 2
  • total possibilities: 2n+2
• in the middle of a round the number of remaining opportunities for a player are calculated as: <the number of rows without opponent's marks> + <the number of columns without opponent's marks> + <the number of diagonals without opponent's marks>
• instead than calculate all each time it can be considered that:
  • after a move of one player the number of still available possibilities are:
    • unchanged for him
    • equal or lowered for the opponent (if the mark has been placed in a row/col/diagonal where no marks had already been placed by the considered player)
• as heuristic I can propose: <my possibilities> - <opponent possibilities>
  • is possible that <my possibilities> - k * <opponent possibilities> with k > 1 give better results and in the end this can be related to how a draw is considered with regard to a lose.

One side consideration:

• playfield cells are n^2
• winning possibilities are 2n+2 if we keep the winning length equal to the field edge size
• this give me the idea that the more the size is increased the less interesting is to play because the probability of a draw after a low number of moves (with reference to the playfield area) becomes higher and higher.
• for this reason I think that the game with a winning length lower that n (for example 3 independently from the playfield size) is more interesting.
  • Named l the wining length we have that the number of possibilities is 2*((n+1-l)*(2n+1-l)) = O(n^2) and so well proportioned with the field area.