Programming Tic-Tac-Toe in Java


<<Previous | ToC | Next >>

ToC This Page

Game Strategy
Display
Arrays
Top-Down Design
O Heuristic


We have built a couple simple games without a lot of hard thinking about what the the game actually does. In Real programs, the algorithm, the logic of the game play, or how you get your rocket to land on Mars (and not go the other way), that's the hard part of programming. So 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.
 

Game Strategy

First, think about how you play the game with a pencil on paper. We'll keep this simple: somebody (a human) plays X, and the computer (initially, for this analysis, you the programmer) plays O. Suppose there's a partial game on, and it's your turnm and this is what you see -- OK, it's really X's turn, but we'll pretend:

You are playing "O", so where do you play? It's a no brainer, you play bottom left, because then you win. After the mechanics of the play, getting the user's choice, updating the board, when it's the computer's turn to play,

A. You want to look for three in a line, or more precisely, you want to look for an empty square that is in the same row, column, or diagonal with two other O's for a win.
In English, what do you tell the computer how to decide where to play? The computer is a step-by-step machine. What is your first step? Are you looking for an empty square? Which of our five principles would you use to find an empty square?

OK, you found an empty square, what next? Suppose you found Square 1, the top left corner. how many different directions do you need to look before you know whether you won or not? How do you decide which of those directions to try first?

OK, let's say your first choice is the top row. If O plays the top row, is that a win? How do you know?

Write down (in English) on a piece of paper, or else open a text editor, what you just now decided to tell the computer.
 

Now let's say one of those O's isn't there. Where do you play? Same place, because the two X's will be three in a row if you don't. So if A doesn't tell you where to play, then

B. You want to look for an empty square that is in the same row, column, or diagonal with two X's for a block.
Again in English, what do you tell the computer how to decide where to play if it sees those two X's and one O? Write it down.

Now write the same thing(s) in Java. Do you have any iteration? Do you know how to spell iteration in Java? How do you tell it where to start? How do you tell it when to stop?
 

Same board, take out all but the two corner plays, so this is what you see:

Where do you play? Obviously not in the empty square between them, that would never combine with the existing O to become part of a win, so it's a wasted move -- or worse, it gives the other player one more useful turn to win by. The upper left corner builds on the row that has the O, and it also starts the open left column, so there are several strategies we might look at, and give them different weights depending on how aggressive or defensive you want to be. Think about it while we focus on the mechanics of display.
 

Display

You already know how to put widgets on the screen. The squares are traditionally numbered from 1 to 9 starting at the top left corner, so we need one widget for each square to display its square number, or else "X" or "O" as played. I would set the font to "Large". Two long thin rectangles separating the rows, and another two separateing the columns. I started off thinking that we can have a separate (transparent) hit widget for each square on the game board, but I realized that would push some of the widgets off the bottom of the list, and it does not scoll. So instead I made the game board itself clickable, then carefully placed the separating lines on boundaries I could easily calculate (multiples of 64). Like the keystrokes in Pong all going through the ball, all my clicks go to the game board (be sure to make it clickable), and then I divided the horizontal and vertical components of the click location by 64 (same as shift right >>6) to get a cell number (vert>>6)*3+(horz>>6)+1.
 

Arrays

I build a linear array dimensioned 10 so that it holds all the board positions from 1 to 9. Now that I think about it, I don't believe I said anything about how to do arrays. In any programming language, an array is a numbered sequence of data, all the same type, usually some fixed size. Originally, back in Fortran days 60+ years ago, you told the compiler how big the array would be, but in Java that happens at runtime. The individual elements of the array are accessed by an (integer) index, one at a time, to either set the value of that element, or else to fetch the value out.

There are three parts to working with arrays: first you tell the compiler the name of the array and the data type of its elements. In Java that looks like this:

int[] TTTplays;
where the type of the elements is "int" and the "[]" tells the compiler that this is an array named "TTTplays". Then, before you can do anything else with this array, you must allocate memory space for it at least once:
TTTplays = new int[10]; // or else TTTplays = new int[lxx]; // (lxx previously defined, >0)
It is often convenient to do both steps in the same line:
int[] TTTplays = new int[10];
If you subsequently decide you need more or fewer elements (or for any reason at all) you can allocate another array. when you assign the array variable to the new allocation, the previous contents are lost, and eventually are "garbage collected" (made available for re-use).

Arrays in Java are Objects, with all the rights and priviledges thereto, which means you can have two variables pointing to the same object, so long as they are the same (or compatible) type. If you tell the computer

int[] theSame = TTTplays;
you get a second reference to the same array, so if you change the elements of TTTplays, you can fetch values out of theSame, and they will be the new values. Which brings me to the third part of working with arrays, which is putting values into the individual elements, or getting those values back out. You use an index -- sometimes called a subscript from the idea that arrays represent the mathematical concept of an indexed variable, which is written (in mathematics) as a capital letter with a tiny italic index variable hanging slightly below the line, like this:
Xi
-- anyway, that would be written in Java as "X[i]" and (in our case) a reference to the value of the third element in the TTTboard array would be TTTplays[4]. Like C, all Java arrays start with index 0, so if you want the squares in your TicTacToe play board to be numbered from 1 to 9, you need to allocate an array with ten elements in it and ignore the first (TTTplays[0]) element. You can use this reference on either side of the assignment operator, that is, you can put values in, and you can look at the current value. In reality, an array is a handy way to refer to a whole bunch of similar data with a single uniform reference, differing only by the index value, which might be the control variable in a for-loop.

In our case, we could declare and allocate our board array, and then preset it to (for example) the number of its position:

int[] TTTplays = new int[10];
for (int nx=1;nx<10;nx++) TTTplays[nx] = nx;
Notice that we did not give a value to TTTplays[0], which is left undefined. It may be safe in this case, but it's probably a bad policy in general. We could alternatively make an array of the individual widgets -- any type, remember? -- on the game board:
GameWgt[] TTTboard = new GameWgt[10];
for (int nx=1;nx<10;nx++) TTTboard[nx] = new GameWgt();
but then we'd need to go to all the trouble of defining the properties of each widget, which GameMaker does so much more easily for us. It would be easier (and less prone to errors) to create the nine board widgets in GameMaker, but give them carefully sequenced names "sq1" to "sq9" then let the game engine get their references for us:
for (int nx=1;nx<10;nx++)
  TTTboard[nx] = myGame.FindListWgt("{sq" + nx + "}");
You could also initialize these to their square number, but again (for only nine quares) that is easier to do in GameMaker.

Now, for instance, you might play the X moves into this array using the formula I gave above:

int here = (vert>>6)*3+(horz>>6)+1;
if (TTTplays[here] !=0) return false; // that square is taken
TTTplays[here] = 1; // play X there
TTTboard[here].PutTextLn("X");
Then later on, after you have decided where to play O, perhaps in variavle chose, you would have the computer play O like this:
if (TTTplays[chose] !=0) return false; // that square is taken
TTTplays[chose] = -2; // play O there
TTTboard[chose].PutTextLn("O");


There are two advantages to playing a -2 for the O moves. First, by being negative (to X's positive), you can do a simple sign test to know who played this square. Then, if you want to add up all the plays in a particular row, column, or diagonal, three X's adds up to +3, three O's adds up to -6, two of each adds up to +2 or -4, and one each adds up to -1. One simple sum tells you exactly how many of each player there are in any single row/column/diagonal. If you wanted to do that. You can get the same effect with both numbers positive, but it's harder to find two values that give you that property.
 

Top-Down Design

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


Even better, for a turns-based interaction with the computer, we can make the whole program event-driven, which means the computer does nothing at all (for us) until an event happens. The GameEngine is event-driven, and if we
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


The first time I put this game out for students to program, I tried to use bit arrays in a single int, which was impossibly hard to explain. People just copied the code, but had little or no understanding of what they were doing. That's gone now. No code for you to copy, you need to think about how the game needs to be played, and then write your own code to do that. If you get stuck, that's what we are here for, ask for help. We won't tell you what code to write, but we will help you to understand the problem so you can figure it out.

We don't need that outer loop at all. Each time the user clicks on the game board, that is their play, we get a ClickEvt method call with the coordinates of where they clicked. We just need to put an X there, then figure out where O should play. Then do it and get out. Maybe have another text widget that is hidden at the start, then when somebody wins, put up a congratulatory message. Does this make sense to you? Rewrite out high-level version of the program, but this time as a single ClickEvt method call.

How do you display the game board? You don't. GameEngine does that.

How do you figure out where to put the X? You don't. Well, not exactly. GameEngine gives you the coordinates of where the user clicked, and you divide that by the square size to get a row and column number, which is easily converted to a square number, then you put the user's X there.

Did X win? Check every row/column/diagonal and see. Remember, we discussed something like that at the front of this page. Now you get to do it.

Where should the computer play O? Go back and look at A (O wins) and B (X is blocked) above, can you do those two? If it's not one of them, can you think of any reason to play any other square? Can you describe why in plain English? Write it down. Then can you think how to say in Java what you already said in English? Is there an iteration? You know how to say that in Java, right? Is there a decision to be made, perhaps how many X's and O's there are in a given line, you know how to do conditionals in Java, right? Input? You already did that, when the user clicked. Output? that happend after you decide. What's left, variables and expression evaluation? You do that when you look in the TTTplays array to see how many X's and O's are there, right?

Think positive, "I can do this." Does O win when there are no other O's in this line? No? I didn't think so. Does O win when there is one other O in this line? How about when there are two? How can you tell the difference? You are smarter than the computer, you get to tell the computer the answer to that question.

What happens when you addup the current plays in row one?

sum = TTTplays[1]+TTTplays[2]+TTTplays[3];
What does that tell you about  how many O's there are in that row? Is playing in that row a good idea or a bad idea? How do you know? Think about it.
 

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 I did 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.

I used a for-loop to run through the board and test each square. Here is the stubbed-out version of the heuristic:

int doing, best = -1, chose = 0, score, sum;
  /// 4. Calculate O play
  for (doing=1;doing<=9;doing++) { // try all available squares
    if (TTTplays[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. Here is how I tested the first row:
    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 ...
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 == 1) { // in the left column..
      sum = board[1]+board[4]+board[7];
      ...
    else ...
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];


Can you do the rest? You need to think like a computer, so that you understand exactly what the computer will do with this code. Then you will know what to do for the other five lines. Try it. Program it up and step through in the debugger. Did it do what you thought it would? Do you now understand what it did do? This is important, you cannot tell the computer what to do and expect it to do what you wnat if you don't know what it will do with what you did tell it.

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.

Next Up: Some Game Ideas in Java

<<Previous | ToC | Next >>

Revised: 2020 August 3