Tic tac toe game tutorial

13 January 2016

Hi,

Few hours ago I tried to make a tic tac toe game for the first time. I just wanted to see how long it would take me. The result was less than 30min. Now you may wonder how I did it, so I'm going to explain it.

First create a new script call it as you like since this will be the only script used in this project.

Code:

    public int SideWon = 0;
    public char SideToPlay = 'O';
    public char[] Grid;
    private int AtMove = 0;

I declared this variables in the script. Side won is telling us which side has won the game. Side to play tells us which turn it is and at move variable holds a number which represents how many moves were made. Grid array will be used to represent board or tiles that you can see above. Each element in this array could be set to 'O' , 'X' or ' ' which is empty space.

In the start method initialize the grid.

Code:

    void Start() {
        Grid = new char[9];
        for (int i = 0; i < 9; i++)
            Grid[i] = ' ';
    }

Now create a method which will be used when we want to switch the turn by changing side to play value.

Code:

    void SwitchTurn() {
        SideToPlay = SideToPlay == 'O' ? 'X' : 'O';
    }

We could visualize the grid even now but there is still no need to since we need to write few more methods before we can actually do anything in the game.

We need two methods, one to make a move and the other one to undo 'any' move.

Code:

    void MakeMove(int move) {

        Grid[move] = SideToPlay;

        SwitchTurn();
        AtMove++;
    }

    void UndoMove(int move) {
        Grid[move] = ' ';

        SwitchTurn();
        AtMove--;
    }

As you can see when making a move we are using move as an index and we are setting character of the current side to play and then we are switching turn and we increase the AtMove value by one.
It's almost the same thing when doing undo method. This time we set the grid at the move position or index to empty space. Then we again switch the turn and we decrease AtMove by one.

Now let's write evaluation method to check if there is match in the grid, in another words we check to see if one of the sides won the game, if so we return the int value(1 for O and -1 for X) but if there is no match we simply return the 0.

Code:

    int Evaluate() {

        //Horizontal check
        if (Grid[0] != ' ' && Grid[0] == Grid[1] && Grid[1] == Grid[2]) 
            return SideWonTheGame();

        if (Grid[3] != ' ' && Grid[3] == Grid[4] && Grid[4] == Grid[5])
            return SideWonTheGame();

        if (Grid[6] != ' ' && Grid[6] == Grid[7] && Grid[7] == Grid[8])
            return SideWonTheGame();

        //Vertical check
        if (Grid[0] != ' ' && Grid[0] == Grid[3] && Grid[3] == Grid[6])
            return SideWonTheGame();

        if (Grid[1] != ' ' && Grid[1] == Grid[4] && Grid[4] == Grid[7])
            return SideWonTheGame();

        if (Grid[2] != ' ' && Grid[2] == Grid[5] && Grid[5] == Grid[8])
            return SideWonTheGame();
        
        //Diagonal check
        if (Grid[0] != ' ' && Grid[0] == Grid[4] && Grid[4] == Grid[8])
            return SideWonTheGame();

        //Anti diagonal check
        if (Grid[2] != ' ' && Grid[2] == Grid[4] && Grid[4] == Grid[6])
            return SideWonTheGame();

        return 0;
    }

    int SideWonTheGame() {
        if (SideToPlay == 'O')
            return 1;
        else
            return -1;
    }

Now as you can see this is really simple and rough check. We just make sure that the one element in the array we are checking against is not empty. Then we check that with the next element and one more time. Since there need to be 3 matched.

Now let's write the method to check if there could be made any more move in the game. To do that we need to check if the game is not already over - we will need to call the evaluate method and we will also need to make sure the whole board is not filled.

Code:

    bool NoMoreMoves() {

        if (Evaluate() != 0)
            return true;


        for (int i = 0; i < Grid.Length; i++)
        {
            if (Grid[i] == ' ')
                return false;
        }

        return true;
    }

Now let's visualize the game. For that I used OnGUI method then I looped through each element in the grid array and for each I created a button on the screen. The button is labeled with the grid character at the given index. If that button is pressed we check if there are still moves to be made and if SideWon is still 0 (no need to do anything if you already lost the game) and we also need to check if the button that was clicked is empty. After checking all this we make a move and we evaluate the new position. If there is still possible moves and the player did not win ( which is impossible but we still check for some reason ) we make the computer move.

Code:

    void OnGUI() {
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++)
            {
                if (GUI.Button(new Rect(x*70, y*70  , 70, 70), Grid[x + y * 3].ToString()) && !NoMoreMoves() && SideWon == 0 && Grid[x+y*3] == ' ') {
                    MakeMove(x + y * 3);
                    SideWon = Evaluate();
                    if (!NoMoreMoves() && SideWon == 0)
                    { //Computer to play here

                    }
                }
            }
        }
    }

The hardest part is how to learn the computer to play the best move. He doesn't know how to think on his own and what's the point in the game so we will need to tell him. One possible solution is to use minimax algorithm which is how I did the AI. I won't go in details cause you can find way better explanation on the wikipedia if you want.

Rough explanation: Two players min and max they are both trying to get the best score. Computer plays all moves for the one side and after the each move before undoing the action he calls the opponent to make all of his possible moves( let's say that the opponent was MAX). Now the MAX calls MIN to play his moves and it goes over and over until no moves are possible or the game over was found. When that occurs we evaluate the position. MAX is trying to maximize the outcome and MIN is trying to minimize the outcome. While doing computer at the end assumes that if I play my best move, he'll plays his best move, I'll play my best move, he will play his best move, doing like this I'm going to get the best possible outcome. However if the player makes a mistake the outcome will be better for the one side.

So the computer in the tic tac toe where he can see all the possible game endings, He is unbeatable.

For my implementation I used negamax algorithm which is easier to write, once you understand it.

Code:

    int NegateScore(int score) {
        if (SideToPlay == 'O')
        {
            return -score;
        }
        else
            return score;
    }

    int MiniMax(int atMove) {
        if (NoMoreMoves())
        {
            return NegateScore(Evaluate()); //From different perspectives
        }

        int move = GetNextMove(0); //First move
        int bestValue = -2; //Worst score
        int bestMove = 0;
        while (move != -1) { //We have no more moves to perform
            MakeMove(move);
            int score = -MiniMax(-1); //Call opponent with -1 since atMove == AtMove will always be false
            if (score > bestValue) { //Beaten the worst score - must be beaten
                bestValue = score;
                bestMove = move;
            }
            UndoMove(move);
            move = GetNextMove(move+1); //Getting the next move
        }

        if (atMove == AtMove) //Instead of score returning best move which is also int
            return bestMove;

        return bestValue;
    }

    int GetNextMove(int last) {
        for (int i = last; i < Grid.Length; i++) {
            if (Grid[i] == ' ') 
                return i;
        }
        return -1;
    }

We are getting the next move with the method GetNextMove with the offset value called last. Since we don't want to pick the moves we already picked. Once there are no more moves we return -1.

At the root node instead of the score we return the bestMove which was recorded during the process.

Now we just need to call minimax which would analyze and return the best move. I call it when the button was pressed like this:

Code:

                        MakeMove(MiniMax(AtMove));
                        SideWon = Evaluate();

Now you should have fully working tic tac toe game with unbeatable AI.

Optional task; Can you make it beatable but still smart?

Thank you for reading!

All the best,
Dragutin!

Subscribe to Posts | Subscribe to Comments

Unity plus

Tic tac toe game tutorial

Leave a Reply