This applet plays a (not particularly good) game of Tic-Tac-Toe with a user. As you can see from the figures, it is possible for the player to beat the computer, unlike most other human versus computer versions of Tic-Tac-Toe which usually end in a tied game.
1. |
final static int moves[] = {4, 0, 2, 6, 8, 1, 3, 5, 7};
First we create an array named moves, which contains the given numbers. As it is declared final, the array can not change—i.e., it is a constant. This array determines which Tic-Tac-Toe square the computer will choose to take if neither player has a winning move. All of the possible moves are stored, in order of preference. |
2. |
static boolean won[] = new boolean[1 << 9];
static final int DONE = (1 << 9) -1;
Here two variables (one array and one int) are defined, both of which use the left shift operator for initialization. In both cases, this means that number 1 is shifted left 9 times (for the nine squares on the board), giving a result in binary of 1000000000 (1 followed by 9 zeros), which evaluates to 512 in decimal. Therefore, the array won consists of 512 Booleans (true/false values), and the int DONE is initialized to 512-1 or 511.
DONE could have been set explicitly to 511, but this approach keeps consistency with all the other places that need to identify separate squares. |
3. |
static void isWon(int pos) {
for (int i = 0 ; i < DONE ; i++) {
if ((i & pos) == pos) {
won[i] = true;
}
}
}
This section and the next use the 512 bits in won to keep track of all the possible winning combinations.
|
4. |
static {
isWon((1 << 0) | (1 << 1) | (1 << 2));
isWon((1 << 3) | (1 << 4) | (1 << 5));
isWon((1 << 6) | (1 << 7) | (1 << 8));
isWon((1 << 0) | (1 << 3) | (1 << 6));
isWon((1 << 1) | (1 << 4) | (1 << 7));
isWon((1 << 2) | (1 << 5) | (1 << 8));
isWon((1 << 0) | (1 << 4) | (1 << 8));
isWon((1 << 2) | (1 << 4) | (1 << 6));
}
There are eight possible ways to win, as shown above. Each box is numbered from 0 to 8, so if one player has boxes 0, 1, and 2, for example, they've won. The call to isWon sets up the won array.
For example, if one player has squares 0, 1 and 2, they have the entire top row for a win. We take the value of 1 followed by the number of zero's equal to the square number. So, the first isWon() call could instead read isWon(1 | 10 | 100);.The "|" means to combine the three numbers together, with a one in any position that any of the three contain a one, with a result that the line could alternatively have been rewritten as isWon(7); (7 being the decimal equivalent of 111 in binary). The isWon() method is passed each of these values encoding a win, goes through the 512 possible positions for each side, and marks which ones are winning positions. |
5. |
int best Move(int white, int black) {
int bestmove = -1;
loop:
for (int i = 0 ; i < 9 ; i++) {
Here the applet decides on its next move. There are nine boxes, so each has to be checked. The int i refers to the box we're checking, while bestmove is initialized to -1 to show that we haven't yet decided on the best possible move.
The white and black signify the computer and the player, respectively. They can't be referred to as X or O, as who goes first changes after each game. |
6. |
int mw = moves[i];
if (((white & (1 << mw)) == 0) && ((black & (1 << mw)) == 0)) {
The first line uses the moves array to get the best possible next move. The preferred position is the middle, then the top left, the top right, the bottom left, the bottom right, the top middle, the middle left, the middle right, and finally the bottom middle. The next line checks to see if this square is already taken. If so, there's no need to check it. |
7. |
int pw = white | (1 << mw);
if (won[pw]) {
// white wins, take it!
return mw;
}
The variable pw (possible white) is set for this move. Using the won array, the applet determines if this move would win the game for white; if so, the applet chooses it and ends the game. |
8. |
for (int mb = 0; mb < 9; mb++) {
if (((pw & (1 << mb)) == 0) && ((black & (1 << mb)) == 0)) {
int pb = black | (1 << mb);
If there's no easy white move to win, we want to check to see if there's an easy black move to win that the suggested white move doesn't block. This code loops through the possible black moves. |
9. |
if (won[pb]) {
// black wins, take another
continue loop;
}
If there's a possible black move to win, then we don't want to take the white move that we've been saving. The statement continue loop; returns the flow of control back up to the loop label and goes through the next iteration of the for loop checking for a better possible move. |
10. |
// Neither white nor black can win in one move, this will do.
if (bestmove == -1) {
bestmove = mw;
}
The code should only make it here if there are no possible moves that either white or black can make that would win the game. If this is true, we save the current candidate as bestmove. |
11. |
if (bestmove != -1) {
return bestmove;
}
If bestmove has been set, then that's the one to take. |
12. |
// If no move is totally satisfactory, try the first one that is open
for (int i = 0 ; i < 9 ; i++) {
int mw = moves[i];
if (((white & (1 << mw)) == 0) && ((black & (1 << mw)) == 0)) {
return mw;
}
}
If the applet hasn't found a good move yet, it'll just take the preferred empty square. |
13. |
// No more moves
return -1;
If no moves are available, the game has ended in a stalemate. |
14. |
boolean yourMove(int m) {
if ((m < 0) || (m > 8)) {
return false;
}
if (((black | white) & (1 << m)) != 0) {
return false;
}
black |= 1 << m;
return true;
}
This checks to see if the move that the user entered is valid. If a square lower than 0 or greater than 8 was picked, it's an invalid move. Or, if that square was already taken, it's also an invalid move. Otherwise, we set that square to indicate that it was taken by black and return that the move was valid. |
15. |
boolean myMove() {
if ((black | white) == DONE) {
return false;
}
int best = bestMove(white, black);
white |=1 << best;
return true;
}
Here's where the applet handles its move. If black or white is DONE, that means that there's a stalemate, so false is returned to show that there are no valid moves. Otherwise, we get the next move by calling bestMove, set white to show that that move has been taken, and return true. |
16. |
int status() {
if (won[white]) {
return WIN;
}
if (won[black]) {
return LOSE;
}
if ((black | white) == DONE) {
return STALEMATE;
}
return OK; }
A call to status() returns the game's status. If white has won, WIN is returned; if black has wone, LOSE is returned. If black or white is DONE,
STALEMATE is returned; otherwise, the game is in progress and the status is OK. |
17. |
Dimension d = size();
g.setColor(Color.black);
int xoff = d.width / 3;
int yoff = d.height / 3;
g.drawLine(xoff, 0, xoff, d.height);
g.drawLine(2*xoff, 0, 2*xoff,d.height);
g.drawLine(0, yoff, d.width, yoff);
g.drawLine(0, 2*yoff, d.width, 2*yoff);
The paint() method handles drawing the applet in the browser window. In this code, the applet gets the size of the applet area and divides it by three. Four lines are then drawn, dividing the area into thirds both horizontally and vertically. |
18. |
int i = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++, i++) {
if ((white & (1 << i)) !=0) {
g.drawImage(notImage, c*xoff + 1, r*yoff + 1, this);
}
else if ((black & (1 << i)) !=0) {
g.drawImage(crossImage, c*xoff + 1, r*yoff + 1, this);
}
}
}
In the remainder of the paint() method, the Xs and Os are drawn. The r loop counts rows and the c loop counts columns. In each square that white has claimed, an O is drawn, and in each square that black has claimed, an X is drawn. |
19. |
switch (status()) {
case WIN:
case LOSE:
case STALEMATE:
play(getCodeBase(), "audio/ return.au");
white = black = 0;
if (first) {
white |= 1 << (int)(Math. random() * 9);
}
first = !first;
repaint();
return true;
}
The mouseUp() method handles the main event check in this applet. If the game has already come to a conclusion and the user clicks the mouse in the playing area, a new game is started. Any result of status() other than OK causes a sound to play and white and black to be set to unplayed. If it's now white's (the applet's) turn to go first, white is set to a random square. Then, the variable first is reset to keep track of who will go first next time, and repaint() is called to clear the playing board. |
20. |
// Figure out the row/column
Dimension d = size();
int c = (x * 3) / d.width;
int r = (y * 3) / d.height;
if (yourMove(c + r * 3)) {
repaint();
If it's the user's turn to go first, the applet needs to handle their move. The placement of the mouseUp needs to be calculated and then checked for validity. If it's valid, the applet is repainted with the user's new X. |
21. |
switch (status()) {
case WIN:
play(getCodeBase(), "audio/ yahoo1.au");
break;
case LOSE:
play(getCodeBase(), "audio/ yahoo2.au");
break;
case STALEMATE:
break;
Now that the user has made their move, status() is once again checked. If the result is a win or loss, a sound congratulating the winner is played (the winning sound is much more enthusiastic than the losing sound). |
22. |
default:
if (myMove()) {
repaint();
In the default case, the game is still in progress, so the computer takes its turn by calling myMove() and repainting the window. |
23. |
switch (status()) {
case WIN:
play(getCodeBase(), "audio/ yahoo1.au");
break;
case LOSE:
play(getCodeBase(), "audio/ yahoo2.au");
break;
case STALEMATE:
break;
default:
play(getCodeBase(), "audio/ ding.au");
Now that the computer has taken its turn, it's time to check status() again. The only difference between this and the code above in step 21 is that here when the code falls into the default block, a sound plays to tell the user that it's now their turn.
|
