array, two-dimensional array array, tic-tac-toe, noughts and crosses
Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a simple "paper and pencil" game. Two players alternate turns; the first player marks an X on a 3-by-3 game board, and the second player marks an O. The goal of each player is to make three of their marks in a row, while blocking their opponent from doing the same.
Tic-tac-toe was one of the first (possibly the first) games programmers used to explore artificial intelligence. As the Wikipedia link suggests, writing a computer program to play a perfect game is relatively simple (see the section on strategy). However, the text only uses the game to demonstrate two-dimensional arrays and how to pass them as function arguments.
The Tic-Tac-Toe Problem
Write a C++ program that allows two players to play tic-tac-toe.
Program Requirements:
Use a two-dimensional array to represent the playing board
Initialize the array to represent an empty board
Clear the screen and display the game board before every move and at the end of the game
Prompt each player to move in their turn
Players move by entering a row and column number, and the program marks the corresponding array element with either an X or an O.
The program validates each move, ensuring that the row and column are in bounds and the space is empty. If the move is invalid, it loops, prompting the player for another move.
As a special case, if the player enters -1 for either the row or the column, the game ends
After each move, the program tests to see if there is a winner
If there is a winner, the program displays the board, announces the winner, and ends
The program declares a draw and ends when no moves remain
Even when a program is small and simple, programmers often have a great deal of flexibility in how they choose to implement it, and that flexibility increases with the program's size and complexity. It's impractical to demonstrate the myriad variations, but it's beneficial to explore a few fundamental options. One goal of the tic-tac-toe example is to demonstrate the use of two-dimensional arrays. Therefore, the example begins with one possible way of distributing the program's tasks across various functions.s
Tic-Tac-Toe Functions
array, functions, functional decomposition
Functions are a programming mainstay, helping programmers manage program complexity and eliminate duplicate code in a program. Arguably, their most significant contribution is allowing programmers to view problem solutions as logical operations, independent of their specific implementation details - they allow software developers to focus on what needs to be done rather than on how to do it. During implementation, functions allow programmers to focus on one small sub-problem at a time, while temporarily ignoring the full problem.
Functional decomposition for the tic-tac-toe program.
There are many ways to decompose a problem, and two experienced software designers may decompose it differently. Furthermore, both decompositions may work and may be "good" as judged by some abstract measure. And, even if the decompositions are similar, the function names may not be. The hierarchy provides a workable decomposition that resolves the tic-tac-toe problem into a set of mutually interoperable functions.
main
Defines the board array and other variables, sequences the function calls, and loops until the game ends
init_board
Initializes the game board
display
Displays the game board, including the marks made by the players
get_move
Alternates moves between players, getting their moves as a row and column number
test_win
Calls test_board to see if either player has won; if a player has won, displays the winner and the final state of the game board, and ends the program
test_board
Examines the rows, columns, and diagonals for three of the same marks in a row and returns the winning player, if there is one, as a character: X or O
Tic-Tac-Toe Data Storage And Algorithms
array, two-dimensional array, ASCII, extended ASCII, fence post problem, mod operator, %, integer division
The second option the example explores is how to store and process the game data. As the tic-tac-toe problem appears in a chapter describing arrays, arrays are the expected storage technique, as specified in the program requirements. Opponents play the game on a 3×3 board. As we have done all semester, we draw the board with ASCII characters. Surprisingly, this constraint still provides two options. The program can use standard ASCII characters (codes 0-127). Following this approach, the program uses '|' and '-' to represent vertical and horizontal lines, and '+' to represent the intersection or cross lines. Although this approach works, it doesn't result in smooth, unbroken lines. A second approach uses the extended ASCII characters (codes 128-255), but different systems interpret these codes in various ways. Specifically, the program can use the extended ASCII drawing codes available on Windows systems.
The tic-tac-toe game board drawn with keyboard characters doesn't produce smooth lines, but the characters have wide support.
The tic-tac-toe game board drawn with graphic characters produces an attractive board with unbroken lines, but the characters have limited support.
Symbolic constants for the standard ASCII characters drawing the game board. Although not as attractive as the extended drawing characters, which produce broken lines, they are widely supported.
Symbolic constants for the extended ASCII drawing characters. Using these characters results in smooth lines that look more drawn than printed. These values work on Windows computers but may not work on others.
The symbolic constants help make the program more portable as described in the next section.
Requirement 3 specifies that players enter their moves as row and column numbers; the program validates the move and marks a valid move with an X or O. The moves players can make during their turn depend on the previous moves made by both players: once a player makes a mark on one of the board spaces, that space is no longer available. The program uses a two-dimensional array to capture the game's state after each move. To help players make valid, strategic moves, the program must display the game's current state - the spaces filled with Xs and Os - and the rows and columns a player can choose. How game developers implement the playing board affects the algorithms used to solve these problems. They can store the board drawing characters in the array, or embed the drawing characters as constants in the display function code.
Drawing and Move Characters In board
Only Move Characters In board
(a)
(b)
(c)
Options for representing the tic-tac-toe moves and game board.
Two ways of dealing with the board drawing characters: storing the drawing characters in the board array with the characters denoting the players' moves, or drawing the board characters with programming logic and output statements. Both versions label the rows and columns to help the players identify valid, strategic moves. Storing the drawing characters in board substantially increases the init_board function's complexity compared to only storing the players' moves.
Drawing the board is straightforward, requiring only nested for-loops. However, drawing the labels requires a modest amount of additional code. This version labels all rows and columns, but the player can only enter rows or columns corresponding to non-drawing characters (those with even index values), which can be confusing or awkward.
This version still includes the drawing characters in the array, but only labels playable rows and columns. Only evenly indexed rows and columns are playable. The display function uses the mod operator to distinguish between odd and even rows and columns: if (row % 2) and if (col % 2). It also uses integer division to map loop control variables to the board labels:
cout << row / 2 << " ";
cout << col / 2;
The get_move function maps the move row and column to valid array indexes: board[row * 2][col * 2] = player;
Only the moves are stored in the 2D array - separate statements in the display function draw and label the board. The display function presents a two-dimensional fence post solution: The playing spaces represent the fence posts, while the board characters represent the fence spans. Consequently, the outer loop draws the first two rows, while treating the last row as a special case. The inner loop draws the first two columns, and the function draws the last column separately. The init_board function is small, and the final display function's size is between the versions (a) and (b).
The text includes the complete, commented programs linked at the bottom of the page.
Portable Code And System Dependencies
conditional compilation, preprocessor directives, #ifdef, #else, elif, #endif, hybrid-language, interpreted language, virtual machine, interpreter, commented out code, system
Programs can always use the standard ASCII characters to draw the tic-tac-toe board. However, using extended drawing characters when available results in a more attractive game board. This paradox illustrates the broader problem of dealing efficiently with system-dependent code. Hybrid and interpreted languages solve this problem with language-specific operations that rely on a virtual machine or interpreter, ported to a specific system, to implement the system-dependant operations. Various C++ solutions are possible.
Programmers can maintain separate, parallel code files, each tailored for a specific system. However, the likelihood of failing to update a given file increases with a program's longevity, the number of its files, and the rate at which the files are modified. This approach is rare in authentic production settings. Many examples throughout the text include multiple options for performing an operation. Most of the options are commented out, leaving only one to complete the program. This approach is appropriate for small demonstration programs whose purpose is to illustrate various problem-solving strategies, but it suffers from the same likely errors as the first: at some time, someone will fail to switch the comments before releasing an updated version. Fortunately, a C and C++ offer a better approach implemented with preprocessor directives.
Tic-Tac-Toe System Dependencies
Conditional Compilation Directives
#ifdef _MSC_BUILD
// extended ASCII - Windows only
const char VERT = (char)179;
const char HORIZ = (char)196;
const char CROSS = (char)197;
void clear() { system("cls"); }
#else
// basic ASCII - all systems
const char VERT = '|';
const char HORIZ = '-';
const char CROSS = '-';
void clear() { system("clear"); }
#endif
Directive
Description
#ifdefid
Compiles if identifier id is defined
#ifndefid
Compiles if identifier id is not defined
#if(id)
Compiles if identifier id is defined
#elif(id)
Compiles if identifier id is defined
#else
Compiles if the preceding ifdef, if, or elif didn't
#endif
Ends a conditional compilation sequence
#defineid
Defines identifier id, a value is unnecessary
#undefid
Undefines identifier id
(a)
(b)
Conditional compilation with preprocessor directives.
A long-standing practice gathers system-specific code into conditional compilation units. The preprocessor automatically passes one unit to the compiler component while filtering out the others.
This example gathers the tic-tac-toe drawing characters into two units controlled by the _MSC_BUILD identifier. _MSC_BUILD is a pre-defined identifier, defined automatically by the Visual Studio compiler. Discovering appropriate identifiers is often challenging, and other Windows compilers may not define this one. Consequently, some programs have long conditional chains or ladders, beginning with #ifdef or #if, ending with #endif, and with numerous #elif directives in between, each processing code for a specific system.
Program Requirement 3 stipulates that the program must clear the screen before displaying the current game board. Historically, users connected a variety of terminals to computers, and each had a distinct ASCII control character sequence for clearing it. As a result, C++ doesn't have a built-in screen-clearing operation; instead, it uses a console command: "cls" or "clear." Modern versions of Windows open a console window with cmd or PowerShell, and "cls" clears either one. POSIX systems allow users to choose their terminal window (bash is a popular choice), and "clear" clears all of them, and also clears a PowerShell window. The C++ system library function passes its string argument to the console window, and the conditional directives use it to create a small function that clears the console.
The preprocessor directives support conditional compilation. See the following links for additional details:
