Lab 15: Testing

Tac-tac-toe (see above) is a simple game that we can use to try to play against a smart computer opponent. In the example above X moves first and ends up winning by getting three in a row. Tic-tac-toe has been implemented in various ways, including using Tinkertoys (original copy on WayBackMachine).

Lab Prep Outline Questions

Answer the questions below for your lab preparation outlines. Submit your outline to the same Reading Outline Submission Form that we have been using.

1. Play a few games of Tic-Tac-Toe at playtictactoe.org. What is your general strategy?

2. Read about the Tinkertoy Tic-Tac-Toe computer linked above. What is a general description of how it worked?

3. If symmetries are not considered, there are 255, 168 distinct TicTacToe games, but only 138 if symmetries are considered. How would the use of symmetries cut down on the number of cases needed to make a "smart" move, in the board representations shown at the bottom of this page? Give a specific example.

Lab Activity

The patterns the computer is looking for to make "smart" moves are shown below. With your partner answer these questions:

1. If symmetries are considered, and are used to cut down on the number of cases that need to be stored (as shown in the table at the bottom of this page), then how many cases would we have to capture all the information in the table shown at the bottom of this page? Explain your answer.

2. The cases shown at the bottom of this page are incomplete, and running the program based off the Tinkertoy version reveals imperfect play by the computer.

   1. 1. What is your strategy to try to find the flaws in this program?

      2. What are the test cases needed to reveal the flaws in this program? How many flaws were you able to find?