User Tools

Site Tools





For our next lab, we will implement a program that can play an unbeatable game of Tic-Tac-Toe. This project will consist of three individual milestones that you will pass off one-by-one (display, algorithm, control). That way you can get partial credit if you don't complete the entire lab. A word of warning: some of you may find this lab very challenging. You will implement the algorithm for the computer player using a recursive minimax search. The algorithm is not that complex but recursive algorithms can be a challenge to debug so start early to give yourself extra time. If you are a little squeamish about recursion, make sure to start early.

This lab will consist of three milestones:

  1. Algorithm. You will write the software that makes it impossible to beat the computer.
  2. Display. You will write the routines that implement the Tic-Tac-Toe board and the drawing of the X's and the O's.
  3. Control. You will implement the game control using the state-machine concepts discussed in the class, similar to what you did for the clock lab.

You will implement and test the Display and Algorithm milestones separately. The Control milestone will bring everything together to implement the entire game.


  1. Practice developing your own state diagrams.
  2. More practice implementing synchronous state machines.
  3. Practice implementing and debugging your synchronous controller state machine.
  4. Gain more experience using the touch-controller and graphics library.
  5. Develop your own state-diagram for control and implement it using the synchronous state-machine techniques discussed in class.
  6. Implement a recursive mini-max algorithm and use it to create an unbeatable game of tic-tac-toe.

Program Organization

The program is divided into three main parts or packages:

  1. minimax: provides the algorithm that you will need to create your unbeatable game.
  2. ticTacToeDisplay: provides the functions to draw the board and players “X” and “O”.
  3. ticTacToeControl: provides the top-level control of the game, invoking minimax and the display functions as necessary.

Implementation Details

Your program will be implemented in three separate milestones that correspond to the three different packages that you will implement: ticTacToeDisplay, minimax, ticTacToeControl. Each milestone will be passed off separately and the requirements are stated at the end of the description for each of the milestones below.

1. Milestone 1: Minimax Algorithm Details and Pass-Off
2. Milestone 2: Minimax Display Details and Pass-Off
3. Milestone 3: Minimax Game and Control Details and Pass-Off

Helps: Including Files From Previous Labs

You can easily include files from previous labs so there is no need to move them or to recopy them. Assuming that each lab was placed in its own enclosing folder, the following example demonstrates how to do this. Let's say that I am working on Lab5 and I wanted to include some files from Lab 2. Your include statement would look something like:

#include “../Lab2/buttons.h”

The “..” tells the compiler to go up to the next directory.

Overall Grading

  1. Milestone 1 (algorithm): 25%
  2. Milestone 2 (display): 10%
  3. Milestone 3 (control): 10% + 10% (if you miss no more than 1 interrupt) + 15% (if your game is unbeatable).
  4. Code Quality (adhering to the coding standard): 30%
  5. If you are unable to make your game play at the same speed as the video, you may pass off with a 10% penalty.
  6. Subtract 10% if your game allows strange game play: no overwriting of X's and O's, no cheating, no playing after the game is over, etc.

Submitting Source Code

Follow this procedure to submit your source code to learning-suite.

Notes to the TAs

  1. Make sure that students have written at least 10 additional test-boards and that they have tested their minimax algorithm using these additional test boards.
lab_5.txt · Last modified: 2019/05/07 12:31 by hutch