<<Previous | ToC
| Next >>

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 whatwhile (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,

We also need to initialize the board to all zeroes:int[] board = new int[10];boolean Xwon = false, Owon = false, cats = false;

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 variablefor (int nx=1;nx<=9;nx++) board[nx] = 0;

/// 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 winnerif (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.

I would put these eight lines after the user has input his play ("if (board[1]>0) if (board[2]>0) if (board[3]>0) Xwon = true; // top rowif (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

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:

We also need to initialize it to zero before we draw the board:int[] board = new int[10];int doing;boolean Xwon = false, Owon = false, cats = false;

Inside the inner loop we will increment doing to the next board cell, then test that cell:doing = 0;for (int ro=1;ro<=3;ro++) { // do three rows..

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 rowsSystem.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

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 "board[1] = 1; // play X in top left cornerboard[5] = -2; // play O in middle...

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 playSystem.out.print("Your play: ");while (true) {doing = Zystem.ReadInt();if (doing>9) doing = 0; // so a single test catches all off-board playsif (doing<1) break; // invalid input, user wants outif (board[doing] == 0) { // valid play..board[doing]++; // mark X as having played this squarebreak;}System.out.print("Taken! "); // ..then go back for another input} // end of input loopif (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` :-)`

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 playfor (doing=1;doing<=9;doing++) { // try all available squaresif (board[doing] !=0) continue; // already played, go to next squarescore = 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

So if you write a test for every possible row, column, and diagonal, combining the already playedif (board[2]>0) if (board[3]>0) score = 99;

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:

To know if the candidate play is in a particular column, we can use the remainder (if (doing<4) { // in the top row..sum = board[1]+board[2]+board[3];if (sum == -4) score = 99;} // end of top row testelse if (doing>6) { // in the bottom row..sum = board[7]+board[8]+board[9];if (sum == -4) score = 99;} // end of bottom row testelse 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

You can useif (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

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