Almost everyone has played the classic game Tic-Tac-Toe, as shown. In other cultures, this game may be known as Noughts and Crosses. The rules are: • Two players use a grid like a hashtag or pound sign (#). • One player uses X and the other player uses O. • Players must agree on who goes first. • Players take turns placing their letter in a cell. • The first player to have three letters in a row horizontally, vertically, or diagonally wins the game the game is over. • If all the cells are full and neither player has three in a row, there is no winner the game is over. Golubovystock/Shutterstock.com Cooperative Coding Determine a Win in Tic-Tac-Toe Not every game ends in a win. When the game ends with no winner, it is called a draw. An X or O can only be played in an empty cell. It is easy for humans to determine how to play an X or O, and it is easy for humans to see when a player has won. They use their sense of sight to see three Xs or Os in a row. A computer cannot “see” without a massive program for machine vision. Self-driving cars have this type of setup. How can a computer figure out who won? An algorithm is needed for a computer to judge whether there is a win or if the game is a draw. Computational think- ers must take several things into consideration. Some questions to consider: • What constitutes a win? • How does the computer know someone won? • What are the smaller steps in the problem? • Is there a pattern to consider that can be used for X play versus O play? • Is there an algebraic equation to express a winning pattern? • Does every winning path have to be checked every time? • What is the most efficient algorithm? Assignment Work with the team assigned by your instruc- tor. Go through the four steps of computational thinking to generate an algorithm that checks for a win. Be ready to share your algorithm with the rest of the class. Select a team member to explain the algorithm and the decisions the team made. 1. What is your team’s algorithm? 2. What decisions did you find your team had to make? A game is over when someone has played three in a row or all cells are filled with Xs or Os. Chapter 1 Computational Thinking 21 Copyright Goodheart-Willcox Co., Inc.