Learn Programming in Java

Tic-Tac-Toe


<<Previous | ToC | Next >>

Lesson #4a: Iteration in a Game

Last time we built a simple guessing game program with a loop to decide when to end. Now we'll look at a much more complicated program. The first thing to do when writing any program is think about what it needs to do. The professional educators in this business call this "Problem Solving," but I think it's more a matter of "thinking like a computer" while analyzing the problem. You know five things a computer can do: sequence, assignment (and expressions), conditionals, iteration, and (simple) input and output. We will put those five skills to work in telling the computer how to play Tic-Tac-Toe.

First we need sequence: The game-playing program needs to display the current state of the TTT board, and then decide if the game is over, and if not, accept the user's play, and then choose its own play, and then repeat. That's almost the whole ball of wax right there: output, condition testing, input, (something, we don't know what yet, to choose a play), and iteration. Let's write that up like a computer program:

  public static void main() {
    /// some variables probably go here, dunno what
    while (true) { // decide later, after drawing the board, if it's over
      /// 1. Display the board..
      /// 2. Is game over?
      /// 3. Accept X play
      /// 4. Calculate O play
    } // end of outer game loop
    /// congratulate winner
} // end of main program


I use three-slant comments to mark parts of the program that need more work, so they are easy to see. Anyway, this is called "top-down design" which was popular some years ago, but not so much lately. You still need to do it, but maybe they have a different name for it. Whatever.

Anyway, if you try to run this program as-is, it will hang (get stuck in an infinite loop) because there is no exit from the while loop. This will happen to you a lot, get used to it. But mostly we try -- not always with success -- to prevent it. First, how to get out... In the main BlueJ window (with the two yellow rectangles), near the lower left corner, there is a horizontal barber pole which is usually black and gray stripes. When your program is running, it will be rotating red and gray stripes, which you can right-click to pop up a single-item menu to stop everything, like this:

The newer version of BlueJ has a little curvy arrow in the lower right corner that you can click to do the same thing, but the best way to prevent our budding TTT program from hanging is to provide a default termination for its outside loop, like with a for-loop. There are only nine squares, so the most number of times a play could be made is nine -- actually four and a half, because we make two plays each time around -- so I'm going to replace that open while loop with this:

for (int max=0;max<9;max++) { // default termination if game does not end normal


If we do the rest of the program correctly, the for-loop will always exit early when X or O wins. This is a safety net, because mistakes happen.

There are nine squares in a TTT board, and the usual numbering is like a telephone keypad, so:

 1 | 2 | 3
---+---+---
 4 | 5 | 6
---+---+---
 7 | 8 | 9


What we need is an integer array of nine elements numbered 1 to 9 -- Java starts all arrays at index [0], but we can make it ten elements and ignore zero -- where each element of the array represents that numbered position on the game board, and it can be 0 (nothing there) +1 (X played there) or -2 (O played there).

Obviously we can't have both X and O on the same square, and the program can insure that there are no more O's than X's and so on. The game starts with the board empty and nobody won (yet), that is,

    int[] board = new int[10];
    boolean Xwon = false, Owon = false, cats = false;
We also need to initialize the board to all zeroes:
    for (int nx=1;nx<=9;nx++) board[nx] = 0;
We will add more variables as we need them. We can do the unfinished tasks in any order, but I think deciding if the game is over is easy, so let's do that first. The game is over if X won, or if O won, or if it's a cat's game. We know it's a cat game if all nine squares are filled. So I set the boolean variable cats to true, then walk through the whole board (obviously not [0]) to see if there are any unfilled spaces, and if so, cats is false:
      /// 2. Is game over?
      if (Xwon) break;
      if (Owon) break;
      cats = true;
      for (int nx=1;nx<=9;nx++) if (board[nx]==0) cats = false;
      if (cats) break;


Similarly, at the end you can supply the appropriate congratulator finish:

    // congratulate winner
    if (Xwon) System.out.println("You won, oh well.");
    else if (Owon) System.out.println("I won, I won, I won!");
      else if (cats) System.out.println("Cat's game.");


How does the program know to set Xwon or Owon to true? You win at TTT when you have three X's (or O's) in a row horizontally, vertically, or diagonally. So we need to test those conditions, eight separate tests. The top row is cells 1,2,3; the next row is cells 4,5,6,  the first column is cells 1,4,7, the down diagonal is cells 1,5,9, and so on.

      if (board[1]>0) if (board[2]>0) if (board[3]>0) Xwon = true; // top row
      if (board[4]>0) if (board[5]>0) if (board[6]>0) Xwon = true; // middle row
...
      if (board[3]>0) if (board[5]>0) if (board[7]>0) Xwon = true; // up diagonal
I would put these eight lines after the user has input his play ("/// 3." in our incomplete program). Then you need to do the exact same thing for Owon, testing for <0, after the computer has decided what to play, but before the end of the loop.

Another relatively easy (only slightly complicated) task is displaying the game board. We could do this in a single for-loop across all nine squares, but it gets a little messy at the line ends, so I will opt for a pair of nested for-loops, each square in a given row within each of the three rows:

    for (int ro=1;ro<=3;ro++) { // do three rows..
      /// prepare to display one row..
      for (int co=1;co<=3;co++) { // do 3 squares in that row..
        /// display one square
      } // end of 3 squares
    } // end of 3 rows


Each square shows "X" if that element of the array is greater than zero, or "O" if that element of the array is less than zero, and the square number otherwise. We will need another index to step through the nine positions of the board, I called it "doing" and put its declaration at the front, next to where the booleans are declared:

    int[] board = new int[10];
    int doing;
    boolean Xwon = false, Owon = false, cats = false;
We also need to initialize it to zero before we draw the board:
    doing = 0;
    for (int ro=1;ro<=3;ro++) { // do three rows..
Inside the inner loop we will increment doing to the next board cell, then test that cell:
      for (int co=1;co<=3;co++) { // do 3 squares in that row..
        /// display one square...
        doing++;
        if (board[doing]>0) System.out.print("X");
        else if (board[doing]<0) System.out.print("O");
          else System.out.print(doing);
      } // end of 3 squares


If you insert this code into the program so far and run it, you will just get a row of numbers "123456789" each of the nine times through, but all in one line. We still need to display the horizontal and vertical divider lines. Between rows we want to display the horizontal line with plusses where the vertical lines cross it. If we do that before displaying one row of numbers, then we might get an extra line above the board, so I used a conditional to omit it there. When I first wrote it the board was jammed up against the answers to the previous questions, so I added an extra blank println to cover that case, which also terminates the previous line. Similarly, between each pair of squares in a given row is a vertical line segment surrounded by spaces, except before the first one is only the single space from the margin:

    int aBit = 1, doing = 0;
    for (int ro=1;ro<=3;ro++) { // do three rows..
      // prepare to display one row..
      System.out.println("");
      if (ro>1) System.out.println("---+---+---");
      for (int co=1;co<=3;co++) { // do 3 squares in that row..
        // display one square...
        if (co>1) System.out.print(" | ");
          else System.out.print(" ");
        doing++;
        if (board[doing]>0) System.out.print("X");
        else if (board[doing]<0) System.out.print("O");
          else System.out.print(doing);
      } // end of 3 squares
    } // end of 3 rows


When it finishes, it's a good idea to end the line (I added a second blank line for good looks):

    } // end of 3 rows
    System.out.println("");
    System.out.println("");


Now if you insert this code into your program, it will print the empty (numbered) board nine times then quit. How do you know the X's and O's print correctly, since nothing has been played? The only way is to initialize the board with a partially played game, like

    board[1] = 1; // play X in top left corner
    board[5] = -2; // play O in middle
    ...
and so on. Do this at the front, right after the for-loop that sets it all zero, then run once. Then delete these test code lines. Or comment them out (put "//" at the front of each line) so you can re-run them (by removing the inserted slants) if something goes wrong.

Two more tasks to go. Again saving the hardest for the last, let's do the input next. You already know how to input a number, don't you? (See "Conditionals & Input"). This is the same thing. The number you get in is the square number you want to put their play in. We can put it into doing. Then we need to check to see if it has already been played:

if (board[doing] != 0) System.out.print("Taken! ");


If that square is taken, then we should go back for another try at input, which means the input thing must be inside a while loop. When you put this together in your program, don't forget to reset your initializations to zero, we don't want the computer to cheat, do we?

      /// 3. Accept X play
      System.out.print("Your play: ");
      while (true) {
        doing = Zystem.ReadInt();
        if (doing>9) doing = 0; // so a single test catches all off-board plays
        if (doing<1) break; // invalid input, user wants out
        if (board[doing] == 0) { // valid play..
          board[doing]++; // mark X as having played this square
          break;}
        System.out.print("Taken! "); // ..then go back for another input
      } // end of input loop
      if (doing<1) break; // invalid input


Notice that breaking out of the imput loop did not also break out of the outer loop, that takes a second break on the same condition. Otherwise the program proceeds to decide if the new play won the game. You can put what we have together and try it, but of course nobody is playing O, so the game is a little one-sided :-)
 

O Heuristic

An algorithm in computing is a sequence of steps guaranteed to get the right (or best) answer; a heuristic is a sequence of steps that usually works, but might fail. The word is derived from the Greek verb meaning to find, the same verb as in "Eureka" = "I found it!" There is a never-lose strategy (algorithm) for TTT, but it's messy and/or tedious, so we will implement a simple heuristic that works pretty good, but can be beaten. Besides, it's more fun to beat the computer, right?

What we do is go through all the unplayed squares and assign a score (create another variable, re-initialized to zero each time before starting the analysis) based on how good a play in that square is likely to be. Obviously, if it's a winning play for O, that's the best possible play. I picked 99 as the high score. On a bigger board (a different game) there might be other ways to get a score of 99, so we would need to use a bigger "high score" number. If a candidate position is not a win for O but it blocks a win for X, that's still a very high score, just not as good as O winning. I figured that adding 22 to the current score is about right. When you do heuristics like this, sometimes you have to try several values before you find one that works. Otherwise (if not a win or block) we count the number of rows and columns through this square with one or no plays in that row yet; another O there is aggressively scored 4 points, a single X there is scored two points, and empty is scored one point. If there is already both X and O in that direction, it's playable, but worthless. By then we already know there are no rows or columns or diagonals with two or more X's or O's, so we can depend on that for making subsequent tests.

We will use a for-loop to run through the board and test each square (like the display loop). Here is the stubbed-out version of the heuristic:

int doing, best = -1, chose = 0, both = eX|Oh, score, sum;
  /// 4. Calculate O play
  for (doing=1;doing<=9;doing++) { // try all available squares
    if (board[doing] !=0) continue; // already played, go to next square
    score = 0;
    /// for each row/column/diagonal doing is in, add up the sum..
    /// if doing wins, score = 99
    /// if doing blocks X win, score = score+22
    /// if this line is empty, score++
    /// if this line has one X, score = score+2
    /// if this line has one O, score = score+4
    ///   otherwise (assume one each) no change to score
    /// if score>best, remember chose = doing, best = score
  } // end of heuristic for-loop
  /// play chose
 
Let's solidify this logic in our minds before we run off in all directions at once. How do we know if this play (whatever doing is) would win? That would be if after you played it, there would be a win for O. We don't actually play it yet, we just want to think about what would happen if we did. Suppose doing=1; (the first square we look at). How would that become a win for O? Perhaps O is already in squares 2 and three, or maybe also in 4 and 7, or else also in 5 and 9. Playing 1 in any of those three combinations is a win for O. Programmatically, that would be (for the top row)
    if (board[2]>0) if (board[3]>0) score = 99;
So if you write a test for every possible row, column, and diagonal, combining the already played board with doing to see if it fills that
row/column/diagonal, then you can know if playing there is a win. That's rather tedious. However, because O plays are all negative, it's easier to add up the plays in each row/column/diagonal, and if we have two O plays in that line, the sum would be -4. We already know the square we are testing is empty, but we need to know that the candidate play is in that line. Some of these tests are easy, but most of them are messy. I usually use bit tests for this, but that turned out to be way too hard to explain. So we'll do them in three groups, the simple first:
    if (doing<4) { // in the top row..
      sum = board[1]+board[2]+board[3];
      if (sum == -4) score = 99;
      } // end of top row test
    else if (doing>6) { // in the bottom row..
      sum = board[7]+board[8]+board[9];
      if (sum == -4) score = 99;
      } // end of bottom row test
    else if (doing>3) if (doing<7) { // in the middle row (last test)..
      sum = board[4]+board[5]+board[6];
      if (sum == -4) score = 99;
      } // end of middle row test
To know if the candidate play is in a particular column, we can use the remainder (modulus) operator '%' because the remainder of doing/3 will be 1 in the first column, 2 in the middle column, and zero in the right column. Convince yourself this is true.
    if (doing%3 == 0) { // in the right column..
      sum = board[3]+board[6]+board[9];
      ...
    else if (doing%3 == 1) { // in the left column..
      sum = board[1]+board[4]+board[7];
      ...
    else if (doing%3 == 2) { // in the middle column..
      sum = board[2]+board[5]+board[8] == -4) score = 99;
      } // end of middle column test
You can use doing%4==1 for the down diagonal (I'll let you write it) but the up diagonal doesn't come out right that way, so the best you can do is logical-OR of three individual tests:
    if ((doing==3)||(doing==5)||(doing==7)) { // in the up diagonal..
      sum = board[3]+board[5]+board[7];


Then you want to know if playing there blocks X. If X played in the middle (square 5) and then in the bottom right corner, then O must block by playing the upper left corner, position 1. You know that, right? So basically you are going to run the same eight tests, but for equality to +2 (two Xs in that line) instead of -4, like this:

    // in each row/column/diagonal..
      if (sum == 2) score = score+22;
 
Maybe the row/column/diagonal is empty. If there are no Xs and no Os there, what would the sum of those three
cells be? Zero. You can also get zero from adding two Xs plus one O, but we already disallowed that (the candidate cannot test if the space is already filled). Here's the test line going into each sum:
    // in each row/column/diagonal..
      if (sum == 0) score++;
 
Then if a given row/column/diagonal is not empty (==0) and it's not a win or block or worthless (which you already checked) then it must have exactly one mark, either X (+1) or O (-2). So you compare each of the eight sums two more times to add +4 or +2 to the score. Can you do that?

Finally, if there is one-each X and O in the same row -- does this begin to sound familiar? Instead of the sum being -4 (to test for a win) or +2 (to test for a block), you now add a single X (+1) and O(-2) for a sum -1 (to test for a worthless play), eight tests. You can also see why I chose -2 for playing O: there's no way to add up any combination of these two numbers to get -1, except one each. But these don't add to the score, so we can ignore them.

How much of this do you think you can write code for? Try it.

Assuming that chose came out of the heuristic loop as a valid square -- don't forget to re-initialize chose and best before this for-loop -- playing O there should be the same as playing X from the user input. Did you get something like this?

if (chose==0) { // huh? this shouldn't happen..
  System.out.println("Something went wrong");
  break;}
board[chose] = -2; // mark O as having played this square
/// did O win? -- you already did this part, right?


OK, you should be able to put it all together, don't you think so? Try it! If you have trouble, that's OK, take a look at what I did, then try again. If you still can't make it work, examine your program line by line and ask yourself "Why is this different from Tom's?" If necessary, make it match until your program runs, then go back and unfix your differences one at a time until you know which ones broke it and which differences were don't-cares. I would suggest making a copy of your original version, then you can compare each difference side by side in separate windows.

Next: Subroutines & Recursion

<<Previous | ToC | Next >>

Revised: 2020 July 22