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

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.

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:

where the type of the elements is "int[] TTTplays;

It is often convenient to do both steps in the same line:TTTplays = new int[10]; // or else TTTplays = new int[lxx]; // (lxx previously defined, >0)

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).int[] TTTplays = new int[10];

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

you get a second reference to the same array, so if you change the elements ofint[] theSame = TTTplays;

X-- anyway, that would be written in Java as "_{i}

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

Notice that we did not give a value toint[] TTTplays = new int[10];for (int nx=1;nx<10;nx++) TTTplays[nx] = nx;

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 "GameWgt[] TTTboard = new GameWgt[10];for (int nx=1;nx<10;nx++) TTTboard[nx] = new GameWgt();

You could also initialize these to their square number, but again (for only nine quares) that is easier to do in GameMaker.for (int nx=1;nx<10;nx++)TTTboard[nx] = myGame.FindListWgt("{sq" + nx + "}");

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

Then later on, after you have decided where to play O, perhaps in variavleint here = (vert>>6)*3+(horz>>6)+1;if (TTTplays[here] !=0) return false; // that square is takenTTTplays[here] = 1; // play X thereTTTboard[here].PutTextLn("X");

if (TTTplays[chose] !=0) return false; // that square is takenTTTplays[chose] = -2; // play O thereTTTboard[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.

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

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?

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.sum = TTTplays[1]+TTTplays[2]+TTTplays[3];

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 playfor (doing=1;doing<=9;doing++) { // try all available squaresif (TTTplays[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 `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)

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. Here is how I tested the first row:

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

You can useif (doing%3 == 1) { // in the left column..sum = board[1]+board[4]+board[7];...else ...

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