3
\$\begingroup\$

I am trying to develop an optimal evaluation function to use in minimax/alpha-beta algorithm for developing tic-tac-toe AI.

I am counting number of circles/crosses in a row/column/diagonal with empty space behind it (with three-in-a-row, there is no empty space). Based on number of symbols in such line, I multiply the separate scores with \$10^{\text{counter} - 1}\$, which results in \$1,10 \text{ or } 100\$ points.

I am sure much can be improved, because optimal solution is rarely found and I am having problems using this function in alphabeta algorithm

My question is - How can this function be improved? Small pieces of code and suggestions appreciated.

My code:

private int h(int[][] field, int depth, int player) //final score of the node
        {
            if (win(field, 1)) //if human won
                return -1000; //very bad for MAX=computer
            if (win(field, 0)) //if computer won
                return 1000;

            int heuristics = individualScore(field, 0) - individualScore(field, 1);
            return heuristics;
        }

private int individualScore(int[][] field, int player)
        {

            int sum = 0;
            int otherPlayer = -1;
            if (player == 0) //if computer is the current player
                otherPlayer = 1; //other player is human
            else
                otherPlayer = 0;//Vice versa
            for (int i = 0; i < 3; i++) // rows
            {
                int counter = 0;
                bool rowAvailable = true;
                for (int l = 0; l < 3; l++)
                {
                    if (field[i][l] == player)
                        counter++;
                    if (field[i][l] == otherPlayer)
                    {
                        rowAvailable = false;
                        break;
                    }
                }
                if (rowAvailable && counter > 0)
                    sum += (int)Math.Pow(10, counter - 1);
            }

            for (int i = 0; i < 3; i++) // columns
            {
                int counter = 0;
                bool columnAvailable = true;
                for (int k = 0; k < 3; k++)
                {
                    if (field[k][i] == player)
                        counter++;
                    if (field[k][i] == otherPlayer)
                    {
                        columnAvailable = false;
                        break;
                    }
                }
                if (columnAvailable && counter > 0)
                    sum += (int)Math.Pow(10, counter - 1);
            }
            int counterD = 0;
            bool diagonalAvailable = true;
            for (int i = 0; i < 3; i++) //diagonals
            {
                if (field[i][i] == player)
                    counterD++;
                if (field[i][i] == otherPlayer)
                {
                    diagonalAvailable = false;
                    break;
                }
            }
            if (diagonalAvailable && counterD > 0)
                sum += (int)Math.Pow(10, counterD - 1);
            counterD = 0;
            diagonalAvailable = true;
            int j = 0;
            for (int i = 2; i >= 0; i--)
            {
                if (field[i][j] == player)
                    counterD++;
                if (field[i][j] == otherPlayer)
                {
                    diagonalAvailable = false;
                    break;
                }
            }
            if (diagonalAvailable && counterD > 0)
                sum += (int)Math.Pow(10, counterD - 1);

            return sum;
        }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Offtopic, having dabbled a bit in TTT machine learning, I suggest you reward the AI for drawing a game. Two players playing optimally will only be able to force a draw (i.e. ensuring that they do not lose), they cannot actually force a win. To that end, you should reward drawing (e.g. award 250 points for a draw and 1000 for a win) because otherwise you'll create an AI that will try to win, and trying to do so inherently leads to exposing win conditions to the opponent. \$\endgroup\$ – Flater Oct 1 '18 at 9:44
5
\$\begingroup\$

I'm going to sidestep the complexities of machine learning itself, it is after all a code review.


Unclear method names and unused parameters

private int h(int[][] field, int depth, int player) //final score of the node

h is a really bad method name. What doest this method do? h isn't particularly explanatory. calculateHeuristics would be considerably better.

I have a lot to say on int[][] field which I will address at a later stage in detail.

Both depth and player are part of the method parameters, but they are never used. You should remove them from the parameter list.


Code readability

if (win(field, 1)) //if human won

if (win(field, 0)) //if computer won

0 and 1 are not particularly readably values for "human" and "computer". Use an enum instead. The good thing is that enums can automatically translate to an int, which means that the odds of encountering breaking changes is minimized.

public enum Player
{
    Computer = 0,
    Human = 1
}

And then your code becomes much easier to read, you wouldn't even need the comments anymore:

if (win(field, Player.Human))

if (win(field, Player.Computer))

Secondly, I would rename field to board. "Field" makes it ambiguous as to whether you're referring to the board (similar to "the football field") or a cell on the board (similar to "a form field").

Thirdly, win is not a good name for a method. I suggest renaming it to IsVictoryFor (or any similarly descriptive name). If you then also create a custom class for your board (instead of using int[][] - I will elaborate on this later in the answer), you can move that method to that custom class. This would give you a massive boost in readability:

if(board.IsVictoryFor(Player.Human))

Encapsulation and SRP

int[][] field

I strongly suggest wrapping your int[][] in a custom class. This allows to you use class methods, which help you categorize your methods.

In your current code, you severely lack any application of Single Responsibility Principle (SRP). Especially in topics such as machine learning, you'll find that the complexity of the code increases exponentially, and you should be prepared for this by properly separating your responsibilities before things get out of hand.

As the adage goes, failure to plan is planning to fail. To that end, I suggest improving your code to make future changes/extensions as seamless as possible.


Don't use ints as placeholder values

You have on several occasions used ints to store your data (players, tokens on board cells). Every time you do that, you inherently require whoever reads your code to be aware of the mapping between the used int value and its particular meaning. This is hugely detracting from your code readability.

As a simple fix, you should use enums.

public enum Player { Computer = 0, Human = 1 }
public enum CellValue { Empty = 0, X = 1, O = 2 }

This dramatically increased the readability of your code, as you no longer will need to use hardcoded magical numbers (0 and 1) and can instead rely on human-readable values (Token.X, Player.Human, ...)

Note: You are cleverly relying on the player int matching with the cell int. I would advise against this. If you equate the two, you're effectively hardcoding which player goes first, and it'll be nigh impossible to reuse your code to have the players switch places (or when you want the compluter to play against itself, which you are inevitably going to have to do if you want to run bulk simulations).
Separating the two does come with the disadvantage that you need to perform some additional checking logic, but the reusability of the code makes it worth it.


Magic numbers

Other than the values I already suggested to encapsulate in enums, you also use other literal values throughout your code:

return -1000;

return 1000;

While you luckily didn't spread this throughout your codebase, the principle still applies; you should use const values.

public readonly const int HEURISTIC_POINTS_VICTORY = 1000;
public readonly const int HEURISTIC_POINTS_LOSS = -1000;

This also makes it a lot easier if you want to tweak the numbers in the future, because you only have to adjust them in one location.


Reusability

Currently, you're using powers of 10 to calculate the score (1,10,100). You have used this calculation in multiple locations:

sum += (int)Math.Pow(10, counter - 1);

sum += (int)Math.Pow(10, counter - 1);

sum += (int)Math.Pow(10, counterD - 1);

sum += (int)Math.Pow(10, counterD - 1);

This is not good. If you decide to change your scoring algorithm tomorrow, you're liable to only update some of the code and potentially forget other instances of the same calculation logic. This is a breeding ground for bugs and unexpected behavior.

You can abstract this to a separate method:

public int CalculateScore(int numberOfTokensInLine)
{
    return Math.Pow(10, numberOfTokensInLine);
}

Should you in the future decide to change your score calculation, you only have to adjust this one method; and then you can be certain that you've changed all of the score calculation logic across the codebase.

Note that you could also convert 10 to a constant, but I don't think it's a requirement here, as there's no reason to assume that you want to reuse this particular value in other locations.
However, if you want to be able to tweak the configuration of your learning algorithm in the future, it may be interesting to abstract this into a const or config parameter, so you have quick access to all values from a single location.


Reusability - Part 2

When you look at the individualScore method body, it should become apparent to you that it is quite repetitive. In many different ways, you are always "checking a line of three cells".

Instead of copy/pasting your approach and slightly tweaking it for every use case, you'd be better off making this reusable. I think it's beneficial for me to explain how/why I do things, so I'll deconstruct (and later reconstruct) the algorithm instead of simply presenting you the end result.

Deconstructing/reconstructing is an invaluable tool for writing clean code.

First, some pseudocode to showcase the general pattern of your logic:

1    FOR a particular line
2        IF I am able to win here (= no opponent token in line)
3            CALCULATE score
4            ADD score to total score
5    RETURN total score

This is the most generic pattern that applies to your logic, without duplicating anything. Now, we simply need to fill in the unknowns.

4 and 5 are not difficult, you've already done these.

3 is effectively the CalculateScore method I already mentioned in the earlier chapter.

2 isn't all that hard. Simply check if the particular line contains the opponent's token in any of the fields.

The big issue is in 1, how do we iteratively check all lines?

Step one - Convert the board to a single array

I'm going to assume you already applies my earlier tips, especially implementing the Board class. This enables you to change your underlying data type. To minimize the breaking changes, I'm going to add a conversion from your old data type:

public class Board
{
    //Your old data type, but now it's using the enum
    public Token[][] Fields;

    //Converted to a single (9 cell) array
    public Token[] FieldArray => Fields.SelectMany(row => row);
}

FieldArray is going to be an array with 9 cells, with indexes ranging from 0 to 8.

Step two - Hardcode all index combinations that define a line.

I know that good code often avoids hardcoding, but I'm willing to make an exception here. There are eight possible lines on a tic tac toe board, and that's a mathematical inevitability.
It it possible to calculate these lines at runtime, and e.g. apply the same logic if you suddently decide to play on a board of variable size (4x4, 5x5, ...) but that's beyond the current scope.

public List<List<int>> AllPossibleLines = new List<List<int>>()
{
    { 0, 1, 2 }, //Top row                    |   |   
    { 3, 4, 5 }, //Middle row               0 | 1 | 2 
    { 6, 7, 8 }, //Bottom row              ___|___|___   
                                              |   |
    { 0, 3, 6 }, //Left column              3 | 4 | 5
    { 1, 4, 7 }, //Middle column           ___|___|___
    { 2, 5, 8 }, //Right column               |   |   
                                            6 | 7 | 8 
    { 0, 4, 8 }, //Diagonal \                 |   |
    { 2, 4, 6 }, //Diagonal /
};

Every "possible line" is a list of three indexes, which refer to the fields of the board. Therefore, if we iterate over AllPossibleLines, we are iterating over all possible lines on the board (all horizontals + all verticals + all diagonals).

Converting the pseudocode to actual code, with what we now know:

private int individualScore(Board currentBoard, Token currentPlayerToken)
{
    int totalScore = 0;

    //Iterate over all possible victory lines
    foreach(var line in AllPossibleLines)
    {
        //Convert the indexes to actual field values
        List<Token> tokens = line.Select(index => currentBoard.FieldArray[index]).ToList();

        //If the line contains an opponent's token, stop processing this line
        if(tokens.Any(token => token != currentPlayerToken && token != Token.Empty))
            continue;

        //Count how many player tokens are on the line
        int playerTokensOnLine = tokens.Count(token => token == currentPlayerToken);

        //Calculate the score and add it to the total
        totalScore += CalculateScore(playerTokensOnLine);
    }

   return totalScore;
}

And this has dramatically simplified your code and enhanced the readability.

Note that I did use LINQ here instead of simple for/foreach loops, specifically because I find that LINQ enhances code readability.
If you're not experienced with LINQ, I highly suggest you look up a tutorial on the basics as LINQ dramatically helps with code readability and not being bogged down by having to manually iterate over collections.


Footnote Remember your win method? You didn't post the content of that method, but you can also rework this using the AllPossibleLines approach:

public bool win(Board board, Token currentPlayerToken)
{
    return AllPossibleLines
               .Any(line => 
                         line.All(index => 
                              board.FieldArray[index] == currentPlayerToken
                         )
                      );
}

The method effectively checks "is there any line in which all of its tokens equal the current player token?".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy