Unbeatable Tic Tac Toe AI Scratch_ I Bet You Can't Beat It

Hello, and welcome to my step-by-step instructions on creating an Unbeatable Tic Tac Toe game from scratch. I won't just go into the steps of how to make the game but the logic behind it as well. If you want to test it out, click here. If that doesn't work, go to https://scratch.mit.edu/projects/790856407.

All you need is a programming platform. I used to scratch, but this program is probably transferable to any program platform or language.

The first start of game design is to plan. How do you want to game to look, feel, and layout? I decided to go for an arcade theme.

Start Screen

So for my front screen backdrop, I used a drawing of an 80s arcade. On top of that, I layered a few tic tac toe boards, so everyone knows they are about to play tic tac toe. Finally, I added the title. None of the fonts on scratch worked for me, so I searched online. Here are some websites that offer free fonts.

• https://www.fontspace.com/category/fun
• https://www.1001fonts.com/fun-fonts.html

After you get your font, you can upload it to scratch as a png and add it to your backdrop.

Gameplay Screen / Tic-Tac-Toe Board

Sticking to the theme, I found a cool pre-programmed backdrop from scratch called Neo Tunnel, so I used it as my base. Next, I added a smaller rectangle box as the background for the tic-tac-toe board. Then using the draw line tool, I drew the tic-tac-toe board.

Now we need a way to get from the start screen to the tic-tac-toe board. For this, I will use a button. After you get a switch and style it to your liking, this is what you will have to code.

1. Switching Backdrops (Required) (right code picture 2) You must use the event if the sprite is clicked, then switch the backdrop to the tic-tac-toe board. This may seem like the end, but if you leave the code like this, you will run into a big problem, so after the backdrop is switched, you have to hide the sprite, or it will show up in the middle of the tic-tac-toe board, and you don't want that.
2. Effects (Not Required) (left code picture 1) This code adds movement to a static start screen to make it more dynamic. The start event is when the green flag is pressed. After that, add a forever loop. Inside the loop, you can use any effect you want. I just make the button switch colors, but you can do any number of things, including changing size, movement, or even add sounds. It is all up to you.

Now here is the complicated part. You need to figure out the game to work here is a list of things we need to have to get the game to work.

1. The game needs to register a player's input and computer input
2. The game needs to display the input and record it
3. The computer needs to understand the player's moves and respond
4. The computer needs to win

I will explain these and break them down in the next steps.

So how are we going to register a player's input? Well, one solution is adding a box in each space in the tic-tac-toe board (picture 1 is visible so you can see), and if that box is clicked, then you know what space the player clicked on. But before you rush in and start creating boxes, I advise you to create one box with all of the code and then duplicate it for the eight other spaces.

That is pretty simple right now, but here comes the complicated part--THE CODE + COSTUMES!!!

Costumes

For the box, you need three costumes: blank/highlight, X costume, and O costume(picture 3). You can use the drawing tool or the keyboard to make the X and O costume.

Variables

If you have coded before, you probably know what a variable is, but here is a quick overview for those who don't. Variables are used to represent a value in a computer. There are two types of variables one is var (one value), and the other is a list (multiple values). For example, the variable inventory is a list it could keep track of all items in your inventory, like in a game. Then in the code, when you need to show the player's inventory, you can ask the computer to display the list. For the tic-tac-toe game, we will need a lot of variables. For sprite-only vars (vars that can only be seen by one sprite), set them in the sprite. For universal vars, set them in a separate initialization sprite.

• Clicked sprite only var - This variable will test whether the sprite has been clicked. At the start, set it to 0 (pic 1).
• Box num sprite only var- What is the boxes number make sure to change it for every box, so each has a unique number (picture 1)
• WhosTurn universal var - This variable will track whose turn it is it will be either p (player) or c (computer) (pic 4)
• Occupied universal list - This is a list of occupied boxes and what they contain. (pic 4)
• Open moves universal list - This is a list of remaining moves. Set numbers 1-9 in open moves. (pic 4)

Code

Highlight (optional)

To make the game more dynamic, whenever a player's mouse hovers over a box, I want it to highlight. So to do that, I used the event after backdrop switches to the tic-tac-toe board so the boxes will be visible only on the tic tack toe board. I set the box's opacity to very low. Then I added a forever if loop. The conditions for the if were, if the mouse pointer is touching the box and the box has not been clicked, then change the opacity to 50. If else, then it would become invisible again. (picture 2 bottom left)

Player input

Now for the player input. The event will be if spite is clicked. If the variable WhosTurn is player and the variable clicked was 0, the game will register that the space was owned by the player and change its costume to an X. The game would change clicked to 1, so the game knew that box was taken. Then remove that box number from the list of open moves. The game would assign X to the occupied list for that number box. (Image 2 Bottom right)

Computer input

This is largely similar to the player input, but it is activated when it receives a broadcast of its number. So if the computer broadcasts "4" then box 4 will be O. (Image 2 bottom right)

Reset

Most programs have reset. A reset prepares the game so it can be played repeatedly (picture 2 upper left). To reset this code, all we have to do is

• Set the box number to the appropriate number
• Hide the sprite
• Set clicked to 0
• Set ghost effect to 0

So here is the core of the game. The beating heart of the program. The secret weapon that will demolish the hopes and dreams of any tic tac toe player. Drum roll please . . . . ----- The Algorithm!!!!

Ok, all jokes aside, here is the current problem. We want to create a tic-tac-toe algorithm that can play perfectly. The only problem is that there are 19683 different board states in tic-tac-toe (3 possible states per space and nine spaces, so 3⁹). How do we create an algorithm that can adapt to those states? The answer is we don't have to. The number 19683 is just how many possible combinations are possible, not considering the game's rules, like X and O have to take turns. The real number is 765(https://veliugurguney.com/blog/post/all_states_of_tic_tac_toe). But that is still a large number, so how can we narrow it down?

I did this by making the computer go first every time in the same square, square 9 (look at picture 1 step 4). This severely reduces the players' options because it gives them only eight squares to work with. While this may seem like a small reduction, it has massive effects. For example, letting the computer go first gives the computer the to force a move.

   a     b     c
      |     |     
1  -  |  -  |  -  
 _____|_____|_____
      |     |     
2  -  |  -  |  X 
 _____|_____|_____
      |     |     
3  -  |  -  |  O 
      |     |  

   a     b     c
      |     |     
1  -  |  -  |  -  
 _____|_____|_____
      |     |     
2  -  |  -  |  X 
 _____|_____|_____
      |     |     
3  O  |  X  |  O 
      |     |  

In the example above

1. Computer moves 3c
2. Player moves 2c
3. Computer moves 3a
4. This forces the player to play on 3b or lose

Using this force moves strategy, the player who goes first can control the game. This means the only move we could not control was the first move. That means all we would need to do is program the algorithm for eight possible first moves. 

Fork Win

The second part of the strategy is to create a fork win. This means creating a game situation where there are two possible winning moves. Continuing from the game above. 

   a     b     c
      |     |     
1  -  |  -  |  -  
 _____|_____|_____
      |     |     
2  -  |  O  |  X 
 _____|_____|_____
      |     |     
3  O  |  X  |  O 
      |     |  

5. Computer moves 2b 

6. The player can play 1a or 1c to block the computer from winning. But he can only block one this guarantees the win for the computer

Strategy for beginning moves

In the above image, you will see all eight possible moves first moves for the player and the subsequent algorithm for the computer to achieve a fork win situation. Unfortunately, if the player's first move is in the center, there is no guaranteed winning strategy, but we can program the computer to get a forced tie.

Another observation is there are only two 2nd moves for the computer. One being box 3 (step 4, picture one) and the other 7.

Final observation, if the player's first move is 4,2, or 8, then the winning algorithm is the same.

Now it is time to code alllllllllllll that explanation from above.

Variables (Picture 1 Top)

• Compturn universal var - This variable will track the number of turns the computer has taken. At the start, set it to 1.
• Strat universal var- Keeps track of the winning algorithm the computer uses. At the start, set it to 0.

Code

Ok, this will be a long explanation. So I will break it down into different strategies according to the star variable.

Strat 0

This will start the code (picture 1) The algorithm will start when the backdrop switches to the tic-tac-toe board. Then we will add a forever loop and an if statement that applies to the entire algorithm. The condition is that Whoes Turn has to be c. This will ensure that the computer won't accidentally make a move during the player's turn. Now when Compturn = 1, the computer will broadcast 9, our starting square, and change Compturn to 2. After the player makes their first move, our variable strat comes in. In Step 5, you see eight possible routes but only two moves for the computer to take on its second turn. So when Compturn = 2, depending on where the player placed his X then the computer will play on box 3 or box 7. To check what box contains what letter, you can search if list:occupied contains X at #number in list. So if the player played on 1,2,4,5,7,8 then broadcast box 3 and set strat to 1. If the player played 3 or 6, broadcast box 7 and set strat to 2. Then set the Compturn to 3.

When back dorp switches to tic tac toe board{
  Forever{
    if whoes turn = c{
      if compturn = 2{
        if player played = 1 or 2 or 4 or 5 or 7 or 8 {
          Brod cast 3
          Set strat = 1
          Set comp turn = 3 
        }
        if player played = 3 or 6 {
          Brod cast 7
          Set strat = 2
          Set comp turn = 3 
        }
      }
    }
  }
}

Strat 1

(Picture 2) Now when compturn = 3 and strat = 1 (picture 2). Then you need the follow the algorithm. If the player did not block the 3 in a row, broadcast box 6, and the computer wins. If the player blocked the 3 in a row, then your moves depend on the player's 1st move. If the player's first move was box 2,4, or 8, then broadcast 5 and set strat to 3. If the player's first move was in box 5 then broadcast 4 and set strat to 4. If the first move was box 7 then broadcast 1 and set strat to 5. Finally, if the first move was 1 then set strat to 6.

When back dorp switches to tic tac toe board{
  Forever{
    if whoes turn = c{
      if compturn = 2{....
      }
      if compturn = 3 {
        if strat = 1 {
          if player not played = 6 {
            Brod cast 6
            Set win = C
          }
          if player played =  2 or 4 or 8 {
            Brod cast 5
            Set strat = 3
          }
          if player played =  5 {
            Brod cast 4
            Set strat = 4
          }
          if player played =  7 {
            Brod cast 1
            Set strat = 5
          }
          if player played =  1 {
            Brod cast 4
            Set strat = 6
          }
        }
      }
    }
  }
}

Strat 2

(Picture 3) when compturn = 3 and strat = 2 (picture 2). Then you need the follow the algorithm. If the player did not block the 3 in a row, broadcast box 8, and the computer wins. If they managed to block and their first move was 3 then broadcast 1 and set strat to 7. If the player's first move was 6 then broadcast 1 and set strat to 8

When back dorp switches to tic tac toe board{
  Forever{
    if whoes turn = c{
      if compturn = 2{....
      }
      if compturn = 3{....
        if strat = 1 {....
        }
        if strat = 2 {
          if player not played = 8 {
            Brod cast 8
            Set win = C
          }
          if player played = 3 {
            Brod cast 1
            Set strat = 7
          }
          if player played = 6 {
            Brod cast 1
            Set strat = 8
          }
        }
      }
    }
  }

Strat 3

You are in a fork-win position if the player blocks on box 1, then play box 7 or vice versa. (Picture 1)

if strat = 3 {
  if player played = 1 {
  brodcast 7
  Set winner = c
  }
  if player played = 7 {
  brodcast 1
  Ser winner = c
  }
  else { 
  brodcast 7
  }
}

Strat 4

Now for this, there is no guaranteed win so we will try to get a tie so broadcast 2 or 8 whichever one is not taken. This will block the player from any chance of winning. Next turn if the player does not block you 3 in a row then broadcast box 1 or 7 one then you win, if they do block one then just play the last move and it is a tie. (Picture 2)

if strat = 4 {
  if player plaFyed = 2 {
  brodcast 8
  }
  if player played = 8 {
  brodcast 2
  Set winner = c
  }
  else {
  brodcast 2
  }
  wait 1 seccond
  if WhosTurn = c {
    if computer played 8 and player not 7 {
    brodcast 7 
    set winner = c
    }
    if computter played 2 and player not 1 {
    brodcast 1 
    set winner = c
    }
    else {play remaining move}
  }
}    

Strat 5 6 7 8

These are all the same as strat 3 just that their fork win positions are in different positions. So all you have to do is use the same format as strat 3 and change the box numbers. (Picture 3)