What I Learned from Tic Tac Toe
A Programming Adventure
Some Analysis, Some Design and Implementation
Introduction
Tic tac toe is a seemingly simple game. One that most of us have played before. The game is known for its simplicity and easy-to-follow rules. Anyone can readily provide a good description of what the game is all about. And is easy to play. The game tends to be a 'paper-game' whereby the game board is written on a piece of paper. Two players then take turns with either an 'X' or 'O' on a game grid of nine boxes. See figure 1.
Figure 1 (game board/grid)
To win at tic tac toe is just as easy as understanding the game. The first player to occupy three rows of the same token (icon) wins the game. See figure 2.
Figure 2 (Sample win scenario)
The grid in turns provides a total of eight win scenarios that are possible within the game. See figure 3 where each color identifies a win-scenario within a gray grid.
Figure 3 (All possible win scenarios)
As stated previously, the game is very easy. How does this translate into programming? Unlike computers, humans have the ability to assume certain specifics of the game. We tend to play instinctively rather than by rules (with a basic premise of the rules in mind). For example, when player one enters a value on the grid, player two understands they are unable to use the same grid-block player one used. Furthermore, physical players are able to make 'smart-decisions' (use strategy) when playing against an opponent. In contrast, when the game is translated into the computer we are not so fortunate; we must program for every possible assumption. This is where even a game as simple as tic tac toe becomes complex to model.
Within the next few pages I provide a description of my own implementation of the game as well as specific implementation details of the game. I write this paper in terms of what I have learned while writing (coding) the game in C. I provide specific details on the challenges and questions I had while performing the task. I also wanted to write this in a form of tutorial. In many cases I find tutorials to focus very little in providing 'thought'. They tend to tell you what the outcome of thought is and assume you to fill-in certain gaps. I hope to provide a 'mere-mortal' description.
About Me
Before beginning I must admit that the way this paper is written is not in a dedicated technical direction. I am not a developer (and fall short of the term) by career and are self-taught. I fall within the new-age term of 'hacker' as I have a crazy love for computers and especially programming. Programming I believe to be one of the most challenging and fulfilling activities I have ever come to perform. With this in mind I take responsibility for sections in which I do not sound extensively technical or for which I may be incorrect in implementation details. These are artifacts of being self-taught. I rely heavily on books I have read. However, for the most part I have worked hard to ensure correctness.
Terms
The following terms are used heavily:
- Physical Player - Indicates a person; not a computer.
- Grid/Block/Coordinate - Terms are used interchangeably to indicate one of the areas where a tic tac toe token ('X' or 'O') can be placed.
- Environment/World - Indicates the area in which the game exists in terms of its physical properties. Used primarily as a metaphor.
- CPU - Computer.
- Matrix/Grid - similar to 2.
- Player Move - A player's coordinates to set a grid block with a value.
Implementation Parameters
Some implementation parameters must be established. These are the limitations of the program:
- The game is implemented in the C language. A fair use of the standard library is used.
- The game is implemented as a console application for simplicity.
- The game is implemented using the ASCII character set (though may handle other character sets, these have not been tested for).
- The game was compiled and tested with MSVC, GNU and MinG
Game's Physical World
The main reason I chose the tic tac toe game was with an attempt at my own implementation from scratch. Indeed there are many implementations of the game on the web and source code readily available. However, writing my own code and figuring out implementation details was of extreme importance to me. I believe that one should re-invent the wheel every once in a while; as this provides a deeper understanding of certain concepts.
Naturally, the first step before writing any code was to obtain a good understanding of the rules of the game. By rules I did not just want to cover 'how to play' the game but also how the game is played. As I began to write several of these down, I quickly came to realize some challenges. Turns out that rules of the game tend to change slightly when we try to model it within a computer system. Before the game-rules come into existence, we must consider the environment (world) in which the game exists. In the real-world, the game exists on a piece of paper, within a hand-written grid (or a drawn grid). In a program, we must first create this world before players are allowed to exist themselves. I modeled this type of world using two distinct containers of data. The first was an implementation of a two-dimensional array matrix of three elements, which would yield a total of nine elements. See figure 4.
Figure 4 (2D matrix code and example of grid elements)
int matrix[MAX_MATRIX_ELEMENTS][MAX_MATRIX_ELEMENTS];
The variable MAX_MATRIX_ELEMENTS correspond to a defined value of 3.
The second was a display mechanism which would translate the matrix into a physical representation of the grid. This would then be displayed on the computer screen. The physical representation was created using a set of for loops which would run through the matrix and format characters in a way that would create the grid on the screen. See code figure 5 and figure 6.
Figure 5 (Display code)
void printmatrix(){
printf("\n");
for(int i = 0; i < MAX_MATRIX_ELEMENTS; i++){
printf("|-----------|\n");
for(int j = 0; j < MAX_MATRIX_ELEMENTS; j++){
if(matrix[i][j] == NO_MOVES){
printf("| %c ", ' ');
}else{
if(matrix[i][j] == PLAYER1){
printf("| %c ", PLAYER1ICON);
}else{
printf("| %c ", PLAYER2ICON);
}
}
}
printf("|\n");
}
printf("|-----------|\n");
}
Figure 6 (Display result of display mechanism)
Coordinate System
Once I had the matrix grid in place, the next challenge became figuring out how to determine each playable block on the grid. The two-dimensional matrix had some capability built in, but my main question was how to determine the best way in which to place the player values within this grid. How do I tell the computer to write 'O' on grid-block number 2? I found the answer by looking at the matrix differently. Instead of a grid-block number (as shown in figure 4), I decided to identify each as a composition of two values. A coordinate of x and y respectively. See figure 7.
Figure 7 (x and y coordinate system)
With this insight in place, I could now tell the computer how to place a move on the grid. This also simplified the number of values necessary to represent each block. The coordinate system was a huge realization of representing player moves. Value 'X' on block two could now be represented as 2, 2 (x = 2 and y = 2). In order to collect this information, I implemented the coordinate system as a structure of two values. See figure 8. Notice from figure 7 that the values begin at 0. This is a subtlety of the implementation as the array subscripts begin at 0 instead of 1.
Figure 8 (Coordinate structure)
struct coord{
int x;
int y;
}c;
Internal Block Values
Representing the tic tac toe grid is a two-dimensional matrix of 3x3 elements. I quickly ran across a subtle problem. The question was how I should differentiate player values with non-player values so that these could be checked properly for a winner or draw. On paper we write an 'X' or 'O' and determine that a blank space on the grid represents a block that can be used for a move. I did not want to model my tic tac toe system in this fashion because I thought about the possibility that player tokens (icons) could be represented by any character. Say for example that 'X' should be a 'A' and 'O' should be a 'B'. Using characters 'X' and 'O' is classic of the game but created some inflexibility. Additionally, characters presented another problem. 'x' and 'X' are two distinct characters inside the computer. I wanted to ensure there would be no need for conversions on this type of data. However, I found my design of the matrix to solve the problem automatically. The matrix was internally a representation of integer values (int matrix[][]). I decided that the internal values of the matrix could be designated as follows (figure 9):
Figure 9 (Internal representation of blocks)
-1 (negative) = No moves on grid (empty grid or a block that held no player move)
0 = Player one move (or 'X' or any character we choose)
1 (positive) = Player two move (or 'O' or any character we choose)
The tic tac toe game now had a very good skeleton by which I could represent the physical world of the game. With this model, I could now play a very simple (albeit unfriendly) game of tic tac toe. See figures 10 - 13.
Figure 10 (Matrix + display with no moves on grid = -1)
Figure 11 (Player 1 move = 0)
Figure 12 (Player 2 move = 1)
Basic Game Flow
Once I had a good model of the tic tac toe game's physical world as needed to be represented in a computer program I was faced with determining the order-of-events within the game. Initially, I assumed that the flow was sequential in nature. Player one would move first, followed by player two, etc. Secondly, I thought that a total of nine moves would be played, one for each player with the first player allowed a final move. I soon found these to be somewhat incorrect. Player two should/would be allowed to go first if required; and the total number of moves was indeed nine but yielded a total of five playable ROUNDS. Due to these incorrect assumptions, testing for a winner became difficult. They led me to reconsider what the game-flow should look like in order to allow the game to be played fairly and appropriately. I then wrote a 'basic' game-flow as follows (figure 13):
Figure 13 (Basic game-flow)
- Fill the matrix with no-moves (-1)
- Check if moves are available; if so step 3, else step 5
- Get player moves in five rounds
- Check winner/draw; if winner/draw, step 5, else step 2
- End game
These basic rules provided me with a much needed understanding of what the program needed to look like. As I mentioned previously, these are assumptions that physical players perform without thought, but must be modeled in a computer program.
Checking For Winner/Draw
Checking for a winner became a fairly complex task (for me). How is winner determined? programmatically that is. Modeling the way we determine a winner from our physical players did not seem like the obvious method. I determined that by-design, designating the internal values of -1, 0 and 1 was an exceptional way to model the system and also the best way to check for a winner or a draw as well. This was not so obvious to me at first. From a programming perspective, the matrix model was absolutely perfect. It provided a mechanism by which would allow me to write code only once, instead of potentially duplicating code to work with characters 'X' and 'O' or others. Although, I had come to a good place, the how to check for a winner still seemed to allude me. At first thought, I needed to loop through all matrix values and somehow determine vertical, horizontal and diagonal wins, but still...how?. Unfortunately, after trial and error, I failed...miserably. Instead, I found it simpler to check for a winner by writing all possible win scenarios. This did not seem too complex; after all, all I had to check for was eight possible win scenarios (see figure 3). This simplified the code to the following (figure 14):
Figure 14 (Checking for winner)
int iswinner(int player){
int win = 0;
if(matrix[0][0] == player && matrix[0][1] == player && matrix[0][2] == player){
win = 1;
}
/* Other win scenarios */
return win;
}
The code checks for blocks in use by 'player' and if it equals one of eight win scenarios, then the player wins. Similarly, checking for a draw was even simpler. If none of the eight win scenarios are occupied by any player, then a draw flag is raised, in this case the code returns its default value of 0 to indicate 'no-winner'.
Blocks Already in-Use
As mentioned previously, in our real world physical players know that they cannot occupy a block that already has a move set. Unfortunately, I could not make this assumption in the program. When I implemented the initial version of the game, I found this detail problematic and I did not realize it as a problem until I began implementing CPU player code. I assumed that no player would ever be clumsy enough to set a move on a block already used. However, players could overwrite each other's blocks. Disallowing 'cheats' or bugs like this added some extra work, but a necessary one. Gladly, because the design used internal values -1, 0 and 1 respectively, adding the necessary checks was fairly simple. All I needed was to check for values already set which determined if the block was 'writable'. If a writable block was available, then the player was allowed to write into that block, otherwise, they would be prompted to select another. See figure 15.
Figure 15 (Checking writable blocks)
do{
printf("\n");
printf("Player %i (%c), enter coordinates: ", (player+1), playvalue);
xgets(coordinate, MAX_COORD_CHARS);
currmove.x = xatoi((coordinate[0]-1));
currmove.y = xatoi((coordinate[2]-1));
}while(ismoveset(currmove));
The ismoveset() function expands to:
int ismoveset(struct coord coor){
if(matrix[coor.x][coor.y] != NO_MOVES){
invalidmove();
return 1;
}else{
return 0;
}
}
Ranges, Ranges, Ranges
Once I had a familiar idea of some potential problems with certain real-world assumptions, the next problem I encountered was one similar to writable blocks. Physical players know the limitations or ranges of the game. You can't write into a block that does not exists or is not within the range of the game. Doing so is silly or simply does not make sense and does nothing. For example, the block coordinate 2, 2 which writes to the center of the grid is a valid move. But coordinates 2, 4 is invalid. The second parameter tries to set a coordinate that does not exist in the game. I had to code for this behavior as well and prevent such nonsense from creeping in. The solution was one similar to the code that collects a player move. See figure 15.
Figure 16 (Checking ranges)
do{
printf("\n");
printf("Player %i (%c), enter coordinates: ", (player+1), playvalue);
xgets(coordinate, MAX_COORD_CHARS);
currmove.x = xatoi((coordinate[0]-1));
currmove.y = xatoi((coordinate[2]-1));
}while(iscoordoutrange(currmove));
The iscoordoutrange() function expands to:
int iscoordoutrange(struct coord coor){
if(coor.x > MAX_COORDS_RANGE || coor.y > MAX_COORDS_RANGE || coor.x <= NO_MOVES || coor.y <= NO_MOVES){
cooroutrange();
return 1;
}else{
return 0;
}
}
With these sets of rules now in place, I now had a fairly 'intelligent' tic tac toe game. Two players could now play the game, only valid moves were now allowed, and a winner could be determined. Furthermore, the program could display the player icons accordingly and was able to interact appropriately. I also had some separation between internal representations of data vs external (user land) representations of the same data within the matrix.
The AI CPU Player - Into the Unknown
Implementing a two player game of tic tac toe was a great exercise and to a certain degree, fairly straight-forward and simple. Each player actually performs the same type of actions. Once I had this simple version in place, I quickly became bored and compelled to make the game more challenging. The obvious route was to try and allow a single player to play the game with a CPU player. Adding this capability, however, prompted additional complexity. More so than those of the two player version already coded for. How does the CPU know which block to fill? How does it know not to write to into an incorrect block? How do I prevent it from setting moves out of range? How does it know it is its turn to move?
After some careful thought and analysis, I found that the computer did not need to be of any special type of player. Some of the same behaviors I had implemented for physical players could be re-used for the CPU with moderate changes. The main question became how the computer could make logical moves. I found the answer in adding some kind of randomization to the CPU logic. This is fairly similar to physical players: we don't always know where we want to move, we instinctively move (provided with some strategy) randomly.
In order to add this flexibility I came across some logical problems. When I implemented the CPU's randomization mechanism, in many cases it randomized to out-of-range values. To circumvent this problem, I added logic that would first check for the greatest possible number of open 'slots' (blocks) that the computer could fill. Once I had these values, I could control randomization to only random values within this range. See figure 17.
Figure 17 (Controlled randomization values)
void getcomputermove(){
struct coord cpucoord;
srand(time(NULL));
int x = 0;
int y = 0;
/* Determine available slots for CPU move */
for(int i = 0; i < MAX_MATRIX_ELEMENTS; i++){
for(int j = 0; j < MAX_MATRIX_ELEMENTS; j++){
if(matrix[i][j] == NO_MOVES){
x = i;
y = j;
}
}
}
do{
cpucoord.x = rand() % (x + 1);
cpucoord.y = rand() % (y + 1);
}while(matrix[cpucoord.x][cpucoord.y] != NO_MOVES || cpucoord.x > MAX_COORDS_RANGE || cpucoord.y > MAX_COORDS_RANGE || cpucoord.x <= NO_MOVES || cpucoord.y <= NO_MOVES);
c.x = cpucoord.x;
c.y = cpucoord.y;
setcoord(c, COMPUTER);
}
This now allowed our CPU player the ability to set 'smart' coordinates and appropriate moves and without going out of range.
AI CPU Player - Smarter
Providing the CPU player with randomization allowed it to play with some intelligence. It was able to move to proper grid blocks and when I tested the code, provided good results. However, the CPU was still pretty 'stupid'. When faced with a physical player, it could easily loose. This was obviously unacceptable. Physical players strategize quite successfully. We can identify when an opponent is near to win. This became very challenging when attempting to make the CPU player smarter. For example, see figure 18.
Figure 18 (CPU = O vs Physical player = X game sequence)
On the example in figure 18 the CPU is not able to identify a key aspect of strategy; it is unable to tell that the physical player can win on their next move. Instead, it can decide to place its move on grid value 2, 1 (orange) which yields a loss for the CPU. This became a complex problem for me. I was astonished at how 'dumb' the CPU was. I decided to model its behavior in a similar way we (humans) strategize our moves. Given a real opponent, what do we do in order to prevent them from winning? Obviously, we place our move into their winning block. Another question arose, how do I check for this?
I realized that I had already done something similar when determining the winner. The same type of check could be used to 'look-ahead' by determining a 'possible-win' scenario. See figure 19.
Figure 19 (Look-ahead for possible winner)
int iswinpossible(int player){
int posswin = 0;
if(matrix[0][0] == player && matrix[0][1] == player && matrix[0][2] == NO_MOVES){
posswin = 1;
}
/* Other possible win scenarios */
return posswin;
}
Similarly to checking for winner, I thought about looping through the matrix and somehow determine the possibility of a win scenario for a given player. However, I had to resort to checking the possibilities by hand (figure 19). A total of 24 possible scenarios were found. What the code checks for is if the player has taken up two blocks where a third would yield a win if occupied. If this scenario is found, the CPU is able to determine that its opponent will potentially win.
CPU Player - Prevent the win (override coordinates)
The CPU player performs most of its actions in 'random-mode' (when there are no possible wins by its opponent, it sets a random value on the tic tac toe grid). Once I added code to allow it to be smarter, I then had to determine what to do. Obviously, we prevent the player from making the move that wins. I thought about this allot. I started to notice that allot of this AI code was pretty much duplicate of previous code but with subtle differences for the occasion. What I modeled was a function that would override the CPU's random coordinates whenever a potential win case was found. See figure 20.
Figure 20 (Override coordinates - prevent win)
struct coord preventwincoord(int player){
struct coord preventwin;
if(matrix[0][0] == player && matrix[0][1] == player && matrix[0][2] == NO_MOVES){
preventwin.x = 0;
preventwin.y = 2;
}
/* Other override cases */
return preventwin;
}
The function returns a set of coordinates that can be used to override any coordinates already defined. The scenario of figure 18 could now be as follows (figure 21):
Figure 21 (Smarter AI game sequence)
Once I tested the new code I was happy to see such cool reaction from the CPU. It could now 'think' about what its next move should be.
CPU Player: Even More Intelligent
I quickly realized that the CPU was a bit of both intelligent and stupid. It could prevent me from possibly winning. However, it was also not intelligent enough to win. Its abilities were two-fold: if the opponent has the possibility to win, prevent it, otherwise just fill any block of tic tac toe. I present the scenario in figure 21.
Figure 21 (No-win for CPU play sequence)
As you can tell from the example, the CPU can win the game if it could specify block coordinates 1, 3 (red parentheses). Instead, it identified that its opponent had the possibility of winning and to ensure it could not, chose to set its move on block 2, 3 (orange). This became a real problem. Again, thinking of the solution pointed me toward code already implemented but it was not too clear for me at first. I was looking for a way to make the CPU a bit more intelligent but how could I make it self-ware of its own moves? The solution was to apply the iswinpossible() function. I was glad to have made the function flexible by requiring a player argument which would then check specifically for that player's win possibility. This simplified the check and allowed me to make the CPU player 'self-aware' (can I possibly win?). I then had to override its own coordinates to allow it to win. See figure 22.
Figure 22 (CPU self-aware code)
void getcomputermove(){
struct coord cpucoord;
srand(time(NULL));
int x = 0;
int y = 0;
/* Determine available slots for CPU move */
for(int i = 0; i < MAX_MATRIX_ELEMENTS; i++){
for(int j = 0; j < MAX_MATRIX_ELEMENTS; j++){
if(matrix[i][j] == NO_MOVES){
x = i;
y = j;
}
}
}
do{
if(iswinpossible(PLAYER1)){
cpucoord = preventwincoord(PLAYER1);
}else{
cpucoord.x = rand() % (x + 1);
cpucoord.y = rand() % (y + 1);
}
/* AI win if it can */
if(iswinpossible(COMPUTER)){
cpucoord = preventwincoord(COMPUTER);
}
}while(matrix[cpucoord.x][cpucoord.y] != NO_MOVES);
/* If all is well, set the coordinates */
c.x = cpucoord.x;
c.y = cpucoord.y;
setcoord(c, COMPUTER);
}
After testing this code, the CPU could now make proper decisions and win the game if it could. The scenario of figure 21 was now a win-scenario for the CPU player. See figure 23.
Figure 23 (Win-scenario for CPU play sequence)
General Improvements (Get Rid of Assumptions)
My implementation of the tic tac toe game was riddled with assumptions. In particular, I thought allot about the order of players. Initially, player one would always be first in making a move on the grid. This 'linear' playing-field was not ideal because I quickly determined that player two would always be at a disadvantage: player one receives five move opportunities while player two receives four. This was obviously not the best way to play the game. By the time this requirement became apparent, lots of code had been written. For a moment I thought I needed to re-design the game from the start in order to make 'order' a possibility.
The game spends most of its time in a play() function whose purpose is primarily to take care of all player moves. It did so in a linear fashion. If blocks determined the order of the players, but I wanted to make the game flexible so its order could be determined by the players, rather than the system. After careful thought, I decided to make this configuration option based on a variable called moveorder defined as an integer value. I then gave this variable meaning as follows (figure 24):
Figure 24 (Move order designation)
1 (positive) = linear move order (player one first)
-1 (negative) = reverse move order (player two first)
I then wrapped the
if blocks where the player moves were collected inside the
play() function so it could check for this order designator. The code is as follows (figure 25):
Figure 25 (Move order code)
void play(){
for(int i = 0; i < MAX_MOVES; i++){
/* Get moves in sequential order */
if(moveorder == 1){
getmove(PLAYER1, PLAYER1ICON);
if(iswinner(PLAYER1)){
winner(PLAYER1);
break;
}
/* Check draw after last move by player */
if(i == (MAX_MOVES - 1)){
draw();
break;
}
if(players == 2){
getmove(PLAYER2, PLAYER2ICON);
}else{
getcomputermove();
}
if(iswinner(PLAYER2)){
winner(PLAYER2);
break;
}
}else{
/* Get moves in reverse order */
if(players == 2){
getmove(PLAYER2, PLAYER2ICON);
}else{
getcomputermove();
}
if(iswinner(PLAYER2)){
winner(PLAYER2);
break;
}
/* Check draw after last move by player */
if(i == (MAX_MOVES - 1)){
draw();
break;
}
getmove(PLAYER1, PLAYER1ICON);
if(iswinner(PLAYER1)){
winner(PLAYER1);
break;
}
}
}
}
I must admit that at first, performing the right sequence of events was difficult. However, the
moveorder variable eased the implementation significantly.
Programming Bugs (Nightmares realized, time consumed)
Thus far I have presented allot of details on the implementation of the tic tac toe game. And as any developer can tell you, even the simplest programs are riddled with bugs. Some obvious and others not so. I have always been keen on this subject and tend to take it quite seriously. I tend to consider certain bugs as 'acceptable'; for example, a bad result from improper logic or calculation. What I don't consider acceptable are bugs that affect the data, such as 'buffer-overflows'. I decided to compile the program in several different translators and test in several debuggers. I was trusting that certain translators and debuggers would identify unknown problems better than others. While performing this task within the MSVC translator, a subtle but obvious bug was reported.
Buffer-Overflow
One of the goals of the project was to use the C language exclusively. This meant also using the C library. All input into the tic tac toe program used the function gets() which reads input from stdin into its argument.
However, gets() is unreliable because it can read more data than its argument can hold. This was the bug identified by MSVC: buffer-overflow. Bugs of this type can actually go unnoticed; in my case even in certain situations extra bytes in the stream were not enough to crash my program or cause noticeable side-effects. However, bugs like these are ticking time bombs. Figure 26 shows the bug.
Figure 26 (Buffer-overflow bug)
/* inside a function */
char numplayers[MAX_CHARS];
gets(numplayers); /* BUG!!! */
/* end function */
In most cases my data only holds up to three values including the null terminator. A value of '123456' would cause a buffer-ovrflow. To remedy this I decided to replace all instances of
gets() with my own version, which would ensure only to copy what was required. See figure 27.
Figure 27 (Buffer-overflow fix)
/* inside a function */
char numplayers[MAX_CHARS];
xgets(numplayers, MAX_CHARS); /* BUG fixed */
/* end function */
The
xgets() function expands to:
void xgets(char *s, int length){
int i = 0;
for(; i < length - 1; i++){
s[i] = getchar();
}
s[i] = '\0';
}
The function is quite simple. It loops and obtains a character from the input stream using the
getchar() function. It copies only up to
length-1 characters: ensuring no overflow.
Flushing the input stream
After implementing the xgets() function, I ran into a problem. There was still characters in the input stream. Another call to xgets() would yield whatever values that still 'hung-out' in the stream. This caused catastrophic problems as the stream was now corrupted. I had to figure out a way to remove these overs so that the stream was clean of these artifacts. I spent a very long time on this. How can I remove the overs? A stream by design is a sequence of characters divided into lines; each line is a sequence of one of more characters terminated by a newline character (C programming language by K & R book). I decided to use this detail to determine how to flush the input stream. See figure 28.
Figure 28 (Flushing the input stream of overs)
void xgets(char *s, int length){
int i = 0;
for(; i < length - 1; i++){
s[i] = getchar();
}
s[i] = '\0';
/* Flush stdin */
char c = getchar();
for(; c != '\n'; c = getchar()){
;
}
}
With this new code in place, subsequent calls to
xgets() were now clear of 'hanging' stream values.
Blank (empty) Input
I found another subtle problem with the xgets() function. One that was more of an annoyance rather than a bug. But I considered it a bug anyway. Whenever the function is called, it expects values to be in the input stream so that its work is performed without it waiting inside the function. This was the case when there was nothing in the input stream. When it reached the for loop, it would wait for input values from the getchar() function. To correct this behavior, I added logic to check for the newline character upon entry within the for loop. If the first character received was a newline, then it meant that nothing was supplied by the user and we could safely return back to the caller. The code was changed to figure 29.
Figure 29 (Checking for actual input)
void xgets(char *s, int length){
int i = 0;
for(; i < length - 1; i++){
s[i] = getchar();
/* Blank - no input */
if(s[i] == '\n'){
s[i] = '\0';
return;
}
}
s[i] = '\0';
/* Flush stdin */
char c = getchar();
for(; c != '\n'; c = getchar()){
;
}
}
This now caused the function to return as soon as there was nothing in the input stream with a null character. My
xgets() was incredibly improved.
Assume Nothing, Expect Everything
I also ran into a problem with input received for the coordinate system. I assumed that input would come in the form of {x value} {space} {y value} where the x and y values are separated with a space character. However, input could be received as 'abcdef' or '123456' etc. In the latter case, with the xgets() function reading in up to length-1 characters, it meant that the read-in value was '123'. I'm sure you can see where the problem was. In the code, I explicitly checked for array values [0] and [2] for coordinates (assuming array subscript 1 to be a space), value '2' would then be ignored. Though this is ok, it just irked me to have this type of behavior and have it be acceptable. I decided to correct this by handling the case by creating an isproperformat() function. See figure 30.
Figure 30 (Expect proper format)
int isproperformat(char *coordinate){
if(isspace(coordinate[1])){
return 1;
}else{
improperformat();
return 0;
}
}
The function checks that the format is correct and displays a message until the correct format is specified.
Separating Complexity
The more complex the game became the large the code-base also became. This caused allot of problems while developing. I soon found my single main file with nearly 200+ lines of code. There was allot more logic than I had planned for and in certain cases, following along was a bit of an inconvenience. I decided to take some time in separating the system into meaningful functions and files. I categorized the functions into their respective types of actions and similar purposes. This significantly simplified the development of additional functionality. In fact, some of the AI code would probably not have been easy to write if I had not perform this type of separation. And isolating functionality in this fashion helped with debugging. The end result was a total of 10 header files and 39 distinct functions. These are as follows (figure 31 and 32):
Figure 31 (Headers)
1) ai.h - Where most of the AI logic reside, such as preventwin(), etc.
2) rules.h - Where all isxxx() functions reside such as ismoveset(), etc.
3) data.h - Where the data resides, such as matrix, coordinate structure, etc.
4) decls.h - Where declarations of functions is performed.
5) defs.h - Where definitions are made for certain types of data, such as MAX_MATRIX_ELEMENTS, etc.
6) game.h - Where all game functions are defined, such getmove(), etc.
7) matrix.h - Where the 'displayable' matrix is defined.
8) msgs.h - Where all game messages are defined, such as 'it's a draw!!', etc.
9) system.h - Where initialization of data is performed.
10) xfuncs.h - Where custom functions reside, such as xgets(), etc.
Figure 32 (Functions)
int iswinpossible(int player);
struct coord preventwin(int player);
int iswinner(int player);
int iscoordoutrange(struct coord cmover);
int ismoveset(struct coord cmove);
int isproperformat(char *coordinate);
int isiconused();
void setcoord(struct coord c, int player);
struct coord getmove(int player, char playvalue);
void play();
struct coord getcomputermove(int asplayer, int opponent);
void setplayers();
void setcustomicon();
void setmoveorder();
int playagain();
void simmplay();
void printmatrix();
void improperformatmsg(char *input);
void headermsg();
void playersmsg();
void winnermsg(int player, char icon);
void drawmsg();
void doneplaymsg();
void playagainmsg();
void invalidmovemsg();
void cooroutrangemsg();
void moveordermsg();
void defaulterrormsg(const char *msg);
void customiconmsg(int player);
void iconusedmsg();
void simmplaymsg();
void invertorder();
int xatoi(char c);
char *xgets(char *s, int length);
void initmatrix();
void initicons();
void init();
void initcoord();
Coding For Debug
Before beginning the project I thought about how I wanted to test. I anticipated that, for the most part, the game would be too simple for elaborate testing. To a certain degree complex testing would be unnecessary. Instead, I thought about performing what I can only describe as inline-testing by providing my code with debug functionality at every step. Similar to assert's NDEBUG, I defined a variable called DEBUG which could have either a true or false meaning (0 and 1 respectively). I then added debug code in every function call and area where I needed to check for data values. Most of my code implements the following (figure 33):
Figure 33 (DEBUG code)
if(DEBUG){
printf("in {functionxxx()} => {var-name} => {type} => %{value}\n", xxx);
}
I found this helpful in looking at the data while testing the game.
Features
As I completed implementation, I began to think of ways in which to improve the game. As you can imagine the tic tac toe game can quickly become boring; unfortunately there is not allot of features that can be added to make the game 'funner' to play. The features I thought of were pretty simple in nature and more-or-less of idealism rather than necessity or because it would certainly make the game more interesting. However, I did want to add features that could test the design a bit. If you recall from a previous section, I mentioned that I wanted to stray away from using characters within the matrix grid. This was because I wanted to avoid comparisons on characters and because I thought players would probably want to use custom tokens (icons). Using int to represent the matrix allowed this functionality easy to increment. All I had to do was add logic specifically to collect the custom icon, then apply it. No other changes to existing code was necessary. I did need to change the way the icons were set, however. Initially they were set using a set of #define constants, this made things a bit inconvenient but not remotely complicated. I moved the definitions to a structure which I could easily call and set. See figure 34 and 35.
Figure 34 (New Icon structure)
struct icons{
char PLAYER1ICON;
char PLAYER2ICON;
}playicons;
Figure 35 (Setting custom icon)
void setcustomicon(){
char customicon[MAX_CHARS];
if(players == 1){
do{
customiconmsg(PLAYER1);
xgets(customicon, MAX_CHARS);
if(customicon[0] != '\0'){
playicons.PLAYER1ICON = toupper(customicon[0]);
}else{
defaulterror("icon!!");
}
}while(isiconused());
}else{
for(unsigned int i = 0; i < players; i++){
do{
customiconmsg((i));
xgets(customicon, MAX_CHARS);
if(customicon[0] == '\0'){
defaulterror("icon!!");
continue;
}
switch(i){
case 0:
playicons.PLAYER1ICON = toupper(customicon[0]);
break;
case 1:
playicons.PLAYER2ICON = toupper(customicon[0]);
break;
}
}while(isiconused());
}
}
}
I also had to create a checking function in order to verify that the icon being chosen had not already been selected. This is so there was no confusion on the part of the players and an obvious implementation detail. Figure 36 shows an example of the game with custom icons set.
Figure 35 (Custom Icons, Player 1 = @, Player 2 = &)
Simulation Play and Improvements
Another feature I thought about was the ability to see the computer play itself. A simulation, based on all the rules in place. This feature presented allot of challenges but which I believe helped identify flaws in my implementation. I will discuss them briefly. The first was that certain functions needed to return something instead of
void (nothing). I identified two functions,
getmove() and
getcomputermove() as being the ones that should return coordinates. Initially, the coordinates were set inside the functions via
setcoord() but while testing the AI simulation code I noticed that they were best designed to return coordinates, of their 'move'. In any case, after these improvements, I began to look at the code more in depth in order to make 'other' similar improvements. They did become quite a few, to the point where I was thinking of 'setters' and 'getters' allot more. Due to time constraint and the simplicity of the game, I decided to leave much of the code unchanged. Improvements added were functions inside
system.h that could initialize data, handling of messages with details on errors in side
msgs.h, and passing values properly to functions.
I also added 'reversing' of the game-play after selecting to play-again, which provided 'fairness' to multiple players.
Simplified Coordinate System
One feature I felt I had to implement was to simplify the coordinate system. After some consideration I felt that requiring a user to enter two values was not ideal. It felt 'proper' at first but not user-friendly. In thought of this I wanted to create a way for the system to handle the coordinates automatically. I kind of went back to an earlier idea of counting based on grid blocks. The total number of blocks are nine and so I thought that maybe all a user needed to do was enter the block in which they wanted to add their move. I thought for a moment that my design would certainly break. I was surprised however that adding the flexibility was simpler than expected and to an extent, quite 'natural'. Firstly, I created a translation table that would use values 1-9 and create the coordinates based on these numbers. See figure 36.
Figure 36 (Block to Coordinate Translation table)
struct coord blocktocoord(int block){
coord ret;
switch(block){
case 1:
ret.x = 0;
ret.y = 0;
break;
case 2:
ret.x = 0;
ret.y = 1;
break;
case 3:
ret.x = 0;
ret.y = 2;
break;
case 4:
ret.x = 1;
ret.y = 0;
break;
case 5:
ret.x = 1;
ret.y = 1;
break;
case 6:
ret.x = 1;
ret.y = 2;
break;
case 7:
ret.x = 2;
ret.y = 0;
break;
case 8:
ret.x = 2;
ret.y = 1;
break;
case 9:
ret.x = 2;
ret.y = 2;
break;
}
return ret;
}
Once I had the trsanslation table all set. Providing a mechanism to perform it's work was all a matter of adding a single if block within the
play() function so that it could receive single values. I did have to tweak the
isproperformat() function in order to allow a single value to be considered a valid case. Additionally, some checks were placed in order ensure the single values were in a range of 1-9. Once these changes were in place, all else worked the same way. See figure 37:
Figure 37 (Recieve block values)
/* check for single value to indicate a block between 1 - 9 */
if(xstrlen(coordinate) == 1 && xatoi(coordinate[0]) >= 1 && xatoi(coordinate[0]) <= 9){
currmove = blocktocoord(xatoi(coordinate[0]));
}else{
currmove.x = xatoi((coordinate[0]-1));
currmove.y = xatoi((coordinate[2]-1));
}
This turned out to be a pretty cool feature. Users could now enter 1 1 for block 1 or 1 for the same. The program could now handle either case.
Game Examples (Screen-shots)
Here are a few screen-shots of the game in action, including debug output for reference:
Final Thoughts - Nature of Programs & Learning
Computer programs are by nature, complex. This is mainly due to how we perceived our physical world. We are an assumptive people, and take complexity for granted because we have become familiar with it at a simplistic level. This project taught me allot about the nature of programs. It taught me to think beyond simplicity. It taught me to model after something familiar so that a complex problem could be broken down into its simple parts. Above all, it allowed me to code. Every step of the way was a great experience. I must admit that there were times when I became frustrated when my code did not work, or when I had to step back and think about what my code was doing. I was even more frustrated when large chunks of code had to be changed because a certain set of functionality did not meet requirements or was not cohesive enough. Despite these challenges, I had allot of fun; and I learned allot.
The tic tac toe game presents several key concepts on programming. It is not as straight-forward in certain cases and allows the developer insight into programming ideas. The AI player for example presented allot of challenges even with its simple nature and basic rules. Further, coding with design in mind also presented a key aspect of properly handling the work. If done correctly, adding features and making changes could present easy challenges. I took allot of pride in writing the code and also in taking the tic tac toe game seriously. I made an effort in looking to make a good program; one with good design decisions. In the process, I also learned that a program should be designed well for simplicity: in order remove constraints that may create problems later.
It may seem silly to write a paper on such a simple game, but I hope anyone reading finds something useful within these pages.
The full source code can be found on github
https://github.com/ringjstorm/tictactoe
