Creating Tic Tac Toe

We want to develop a game that will play tic tac toe so that we can implement a minimax search on it. However, before we can dig into the AI, we need to develop the game's engine. After our tic tac toe game is implemented completely, excluding the AI, we can develop the minimax search and related functionality. With that in mind, let's get started.

The Idea

I want to develop what will be, for the most part, a normal tic tac toe game. I would like to add some features, though. First, I want the game to be playable with either one or two players. In reality, this is choice between one or two human players. Second, if the user chooses to play against the computer, he should be able to play as either X or O. Third, regardless of which shape a player chooses, the X player should always go first. Finally, for a one-player game, the player needs to be able to select a skill level for the AI that will affect how well the computer plays against him. At the highest skill level, the computer should be unbeatable (or at least as unbeatable as you can be at tic tac toe).

The Artwork

In creating Tic Tac Toe , I've decided to do a good bit of the setup by placing symbols manually on the stage instead of by using attachMovie at run-time. In fact, I don't foresee using attachMovie at all in this game. I certainly could use it, but I figure there is little possibility of extending this game. I'm in no danger of wasting time building complex symbols that will need to be re-created later.

Six symbols are associated with Tic Tac Toe :

button . This symbol has been around since Chapter 5, "Arrays: Match 'Em Up and Sliders ." It's one of our standard buttons .
X . This movie clip contains the art for our X move.
O . This movie clip contains the art for our O move.
block . This movie clip contains instances of both X and O . The X instance is named x and the O instance is named o .
winbar . This movie clip contains a red line that is used to mark the winning move if someone wins the game.
board . This movie clip contains nine block instances, laid out in a 3 — 3 grid. Lines separate the blocks. This is the actual board that will be used to see the game in progress. The nine block instances are named b00 , b01 , b02 , b10 , b11 , b12 , b20 , b21 , and b22 . I chose these names because they easily correspond to a two-dimensional array.

On the stage, I have instantiated the board symbol one time and named the instance real_board . I have also instantiated the button symbol three times and named them button1 , button2 , and button3 .

That completes the initial artwork and symbol creation. Nothing has been exported for ActionScript because everything we need is already instantiated on the stage. That causes Flash to automatically export the symbols with the .swf.

The Design

Generally, when I'm developing a game with AI, I try to leave the AI logic portion until the end. There is no sense programming an AI to play a game that is not finished. If you do so, you'll end up going back and reworking the AI as game rules change and things are finalized. Even though the rules of tic tac toe are fixed, I'm going to leave the AI until the end. This makes testing the AI easier as well. It's hard to test an AI when the game the AI is to play has not been fully implemented.

The easiest thing to do is develop two-player tic tac toe game. That should be pretty easy for you by now. After implementing everything for a two-player game, we can deal with the AI for the one-player game. As usual, you can find files on the CD in the Chapter 10 directory for Tic Tac Toe in both implemented and unfinished form.

Game Engine Functions

As usual, we're going to use an initGame function to handle the game's initial setup.

 function initGame(){}

After initialization, two buttons are active. These buttons are labeled 1 plr and 2 plr. You use the first button to choose a single-player game, and you use the second button to choose a two-player game.

If the user clicks the first button, he should get a new pair of buttons that allow him to choose between being X or O. After choosing X or O, the user should be given a set of buttons from which to pick a skill level. The game begins after the user chooses the skill level. If the player has chosen X, he will be allowed to go first. If he has chosen O, the computer will make the first move.

If the user clicks the 2 plr button at the beginning, the game starts immediately. By clicking, the user can play as both X and O.

The following methods will be used to handle working through the setup buttons. The first, selectFirstPlayer , is called when the user clicks the 1 plr button.

 function selectFirstPlayer(){}

When the user chooses either X or O, the firstPlayerSelected function is called.

 function firstPlayerSelected(side){}

When the user chooses a skill level to play again, the selectSkill function is called.

 function selectSkill(skill){}

To begin a single-player game, startGame1plr is called.

 function startGame1plr(){}

To begin a two-player game, the startGame2plr function is called.

 function startGame2plr(){}

Both the startGame1plr and startGame2plr functions set up their individual settings and then call a generic startGame function, which contains functionality used to set up both kinds of games. This allows us to separate the one-player start game code from the two-player start game code but then have a third function to handle responsibilities shared by both one- and two-player games .

 function startGame(){}

When a player makes a move, we'll need to test to see if the game has just been won. We do this with the testForWin function.

 function testForWin(){}

The stopGame function ends the game if someone has won or if there is a tie. The single argument, winner , should be 1 for X wins, -1 for O wins, 0 for tie game, and undefined if the game is not yet over.

 function stopGame(winner){}

Move Execute Functions

Inside the board are the individual clips that contain both X and Y markers. These markers are made invisible in the initialization functions, but each has a function attached to its onRelease handler named makeMove . The makeMove function is responsible for responding to the user's clicks.

 function makeMove(){}

When a move has been chosen, either by the user from his click or from the computer AI, one of two functions is called. The first, makeXMove , is used to make a move for X. The second, makeOMove , is used to make a move for O.

 function makeXMove(mc){} function makeOMove(mc){}

When it's time for the computer to make a move, a single function named makeComputerMove is called. The makeComputerMove function checks the currently set skill level and then chooses between several different algorithms for a next move.

 function makeComputerMove(){}

The AI uses three functions: executeComputerMove , findGoodMove , and minimax . We'll discuss these later after the rest of the implementation has been completed.

 function executeComputerMove(tile){} function findGoodMove(){} function minimax(){}

That's all the functions we're going to need for Tic Tac Toe . From here, we're ready to begin the implementation.

The Implementation

Now that we have our functions laid out, it's time to start their implementation. Most of this should be pretty straightforward. You've seen it all before, but it never hurts to see more sample code. We begin with the engine functions.

Implementing the Game Engine Functions

The initialization, starting, and stopping of the game all come under the heading of game engine functions. We'll proceed through their implementation in the order in which they are called in the game.

The initGame Function

We call this function as our first line of code:

 initGame();

Now we define initGame as follows :

 function initGame(){      button3.enabled = false;      button3._visible = false;      feedback.text=" Please choose the number of human players. 1 Player    plays against the computer."

These two operations on button3 are used to disable and hide the button. We won't need button3 until we have a menu that needs three options. For us, that will be when we need to select a skill. We also need to give the user some instructions about what choice he needs to make. No matter how obvious a choice might seem to you, remember that as the developer, you have better insight into how the game works than anyone else. Your instincts about what a user will or will not understand are almost always the most suspect.

 turn = 0;

The turn variable keeps track of whether it's X's turn or O's. During a two-player game, turn alternates between 1 (for X) and -1 (for O). A turn value of 0 indicates that no game is currently being played .

 playerSide = 0;

The playerSide variable keeps track of which shape the player selected in a one-player game. If the player is playing X, playerSide is 1; if the player is playing O, playerSide is 0.

 playerCount = 0;

The playerCount variable keeps track of the difference between a one-player game and a two-player game. During a one-player game, playerCount is 1, and during a two-player game, playerCount is 2.

 button1.myText.text = "1 plr";      button2.myText.text = "2 plr";      button1.onRelease = selectFirstPlayer;      button2.onRelease = startGame2plr;

The first two buttons are given text and their onRelease handlers. Notice that button1 , which starts a one-player game, gets the selectFirstPlayer function as its handler. The second button, however, which starts a two-player game, goes right into the startGame2plr function. That's because in a two-player game, there is no need to choose the side (X or O) or the skill level.

Now we need to create an array to keep track of what's going on. We could use the existing board instance on the stage to hold this data, but I would rather not. If we use a small two-dimensional array to keep track of which squares contain which moves, this array will be very small. When it's time to develop our AI, we can let the AI's checks operate on a small array containing moves. That way, it does not have to mess with the real_board instance on the stage. After the AI operates on our little array ( board ) and chooses its move, we can execute the move on the real_board instance.

I want the game board ( real_board ) to be invisible until the user chooses a game.

 real_board._visible = false;

Finally, we must initialize the individual pieces inside the real_board . This is done in a nested for loop, as follows:

 for(var i=0;i<3;++i){           for(var j=0;j<3;++j){                real_board["b"+i+j].onRelease = makeMove;                real_board["b"+i+j].x._visible = false;                real_board["b"+i+j].o._visible = false;                real_board["b"+i+j].r=i;                real_board["b"+i+j].c=j;           }      }

Notice that we are attaching an onRelease handler to each element on the board. The handler we attach is the makeMove function. That means makeMove is called on whichever board unit (tile) the user clicks. We set both players' markers (X and O) to be invisible. Finally, we record the position of each tile by giving it two properties: r and c . The r property stands for row, and the c property stands for column. This information will be useful when it's time to make a move.

 }//close initGame

That concludes the initGame implementation, so we close the function with a curly brace .

The selectFirstPlayer Function

This function was called when the user clicked the 1 plr button. selectFirstPlayer needs to change the buttons around to let the user choose between playing as X and playing as O. That leads to the following implementation:

 function selectFirstPlayer(){      button1.onRelease = function(){firstPlayerSelected(1);}      button1.myText.text = "X";      button2.onRelease = function(){firstPlayerSelected(-1);}      button2.myText.text = "O";      feedback.text=" Please choose X or O.  X goes first." }

As you can see, we're changing the button text and the onRelease handler for each button. In both cases, we call firstPlayerSelected . If the user chooses to play as X, we use 1 as an argument; if the user chooses to play as O, we use -1 as the argument. We are using the feedback text field to give the user information about the choice he needs to make.

The firstPlayerSelected Function

This function is called when the user has selected X or O to play in a one-player game. If the user is to play X, our argument side is 1; if the user is to play O, side is -1. Next, the user must choose a skill level. I'm going to implement three skill levels in this version. That leads us to the following implementation:

 function firstPlayerSelected(side){      playerSide = side;      button1.onRelease = function(){selectSkill(1);}      button2.onRelease = function(){selectSkill(2);}      button3.onRelease = function(){selectSkill(3);}      button3.enabled = true;      button3._visible = true;      button1.myText.text = "skill 1";      button2.myText.text = "skill 2";      button3.myText.text = "skill 3";      feedback.text=" Please select a skill level." }

As you can see, we're changing the text and onRelease handler for the buttons. We're also enabling button3 and setting it up. When the user clicks a button, it will call selectSkill with the skill level (1, 2, or 3) as the argument.

The main thing to notice is the first line of the function: playerSide = side . This stores the side that the player uses in the playerSide variable, which is used later to make the correct moves for both the player and the computer.

The selectSkill Function

This function is called when the user chooses a skill level.

 function selectSkill(skill){      _this.skill = skill;      button1.onRelease = selectFirstPlayer;      button2.onRelease = startGame2plr;      button3.gotoAndStop("_up");      button3.enabled = false;      button3._visible = false;      button1.myText.text = "1 plr";      button2.myText.text = "2 plr";      feedback.text = "skill "+skill;      startGame1plr(); }

The first task we perform is storing the argument, skill , in the variable skill . I've used the this keyword because I want it to remain in the current timeline. The reason I had to specify a timeline at all is that skill is an argument to the function. As such, it is locally scoped to the function and will be deleted when the function ends. To preserve the variable, I have to give it a new scope.

Next, we reset the first two buttons so that they go back to their initial state, allowing the player to choose a one-player or two-player game. We then disable and hide button3 . Finally, we start the game with a call to startGame1plr .

The startGame1plr Function

This function is called to begin the single-player game. At this point, both the playerSide and skill variables have been set. All we need to do here is set a final variable called playerCount to 1. The playerCount variable keeps track of whether this is a one-player or two-player game.

 function startGame1plr(){      playerCount = 1;      startGame(); }

The function concludes with a call to startGame .

The startGame2plr Function

If the user had chosen to play a two-player game, the startGame2plr function would have been called. The implementation here is similar to startGame1plr except that we have to do a few extra things.

 function startGame2plr(){      feedback.text = "";      playerCount = 2;      playerSide = 1;      startGame(); }

The playerCount and playerSide variables would have been set if this was a one-player game, but because it's a two-player game, the functions that normally set those variables are not called. Instead, we need to set them here. The playerCount is 2 because it's a two-player game. The playerSide is set to 1. This is necessary because the user might have just played a one-player game as O, which would have set playerSide to -1.

The startGame Function

After one- and two-player games are initialized , they call the generic startGame function. This function's job is to set up the board and get things rolling. There are several things to do in this function, so I'm going to break it down step by step.

 function startGame(){

First we need to set the turn to 1 so that X goes first.

 turn = 1;

Then we need to make the board visible, if it's not already.

 real_board._visible = true;

Now we need to initialize the board array. Make sure that you don't confuse board with real_board . real_board is a movie clip instance on the stage that contains all the art to display the game. In contrast, the board object is a two-dimensional array where we're going to record moves.

 board = [[0,0,0],[0,0,0],[0,0,0]];

The board also contains a count of how many moves have been made. We need to set this to 0. When the moveCount property equals nine, that means that nine moves have been made and the game is over, even if there is no winner.

 board.moveCount = 0;

Then we need to loop through the real_board and make all the markers invisible. It's important to set up the onRelease handler for each one.

 for(var i=0;i<3;++i)           for(var j=0;j<3;++j){                real_board["b"+i+j].onRelease = makeMove;                real_board["b"+i+j].x._visible = false;                real_board["b"+i+j].o._visible = false;           }

Next, we need to make all the winbar movie clips invisible. The winbar movie clips draw the line across the winning set of three shapes on the real_board . When one side wins, the correct winbar is shown to mark the three in a row that won the game. Until the game has been won, all winbar s must remain invisible. There are eight possible ways to win, and the winbar for each is named winbar1 through winbar8 . We loop through these, making them invisible.

 for(var i=1;i<9;++i) real_board["winbar"+i]._visible = false;

Finally, we must deal with a special case. We've just set up our board so that the user can click on it and make moves. However, if the game is a single-player game and the user is playing as O, the computer needs to make a move before the user can make his first move. We test for this special case using playerCount and playerSide . The special case happens when playerCount is 1 and playerSide is -1.

 if(playerCount == 1 && playerSide==-1) makeComputerMove();

As you can see, we're making a call to makeComputerMove . As I outlined earlier, that function is the interface to the AI section. Everything necessary for choosing and making the move is encapsulated within makeComputerMove .

That concludes the startGame implementation, so we close the function.

 }//terminates startGame function

The testForWin Function

This function is called after a move is made. It takes no arguments but returns one of the following:

1. X has won.
-1. O has won.
0. Tie game. (All nine moves have been made.)
Undefined . Game is not yet complete.

There are several ways to test for a winner. We should give some consideration to these ways because the AI is going to call this function when the computer is deciding on moves to make. In fact, the computer might call testForWin several thousand times in some circumstances, so we should make sure it's efficient.

Before we break into the code, take a few minutes to think about how you might implement a test for win. Remember that board contains a 3 — 3 array with values of 0, 1, and -1. You'll need to test all eight winning combinations to see if either player gets three in a row.

I began by breaking the winning moves into three possibilities. The first possibility was that the [0][0] square had either a 1 or a -1 (X or O). The second was that the middle square [1][1] had either 1 or -1 in it. The third possibility was that the lower-right square [2][2] had either 1 or -1 in it. That resulted in the following implementation:

 function testForWin(){      if(board[0][0]){}      if(board[1][1]){}      if(board[2][2]){} }

For any possible win, your shape would have to be in one of these squares. For each case in which one of these squares is filled, we can then drill down and continue searching. If the square isn't filled, we don't need to check the lines that could connect to that square.

Now we need to fill out each of those if statements to continue the search for a win. In the first, we can test for wins across the top row, down the left column, and down the first diagonal (top left to bottom right). I'm doing this with three tests ”one for each case. We already know that the board[0][0] value is going to contain either 1 or -1, so from here, we can check to see whether the [0][0] square is the same as the other squares in each of our three cases. Consider the following addition to our function:

 function testForWin(){      if(board[0][0]){  if(board[0][0]==board[0][1] && board[0][1]==board[0][2])   return board[0][0];   if(board[0][0]==board[1][0] && board[1][0]==board[2][0])   return board[0][0];   if(board[0][0]==board[1][1] && board[1][1]==board[2][2])   return board[0][0];  }      if(board[1][1]){}      if(board[2][2]){} }

You should be able to see how this code checks for wins in the top row, left column, and first diagonal. From here, we can add similar sections to the remaining two if statements.

In the next if statement, we can check a middle row, middle column, and second diagonal win, as follows:

 if(board[1][1]){  if(board[1][0]==board[1][1] && board[1][1]==board[1][2])   return board[1][0];   if(board[0][1]==board[1][1] && board[1][1]==board[2][1])   return board[0][1];   if(board[0][2]==board[1][1] && board[1][1]==board[2][0])   return board[1][1];  }

Finally, we're ready for the final if statement, which checks the bottom row and right column wins:

 if(board[2][2]){  if(board[2][0]==board[2][1] && board[2][1]==board[2][2])   return board[2][0];   if(board[0][2]==board[1][2] && board[1][2]==board[2][2])   return board[0][2];  }

That handles checks for all eight winning combinations. If a winning move has been made, the value of 1 or -1 of the winning squares is returned. This effectively gives our testForWin function a return value of 1 when X wins and -1 when O wins.

Now we need to deal with the possibility of a tie. If the game is a tie because all nine moves have been made, we need to return 0. The number of moves made is stored as board.moveCount . We can test that against the maximum number of moves to check for a tie game, as follows:

 if(board.moveCount == 9) return 0;

Finally, if none of this has happened , we should return undefined to signal a game that is not yet over. However, if we neglect to return anything from our function, a return value of undefined is given to it implicitly. For that reason, we can go ahead and close our testForWin function now, and it should work perfectly .

The stopGame Function

After the player makes a move, we're going to call testForWin . The result of testForWin is going to be sent to the stopGame function as its 1 argument. The stopGame function stops the game if its argument is 1, -1, or 0 and gives an appropriate message to the feedback text field.

If stopGame is called with undefined as its last argument, it should do nothing because the game is not over. In this way, stopGame should probably be named testForStopGame or something similar because it's common for stopGame to be called when there is no winner and the game is not over.

The first thing we need to do is set up the feedback text field. I do this with a switch statement using the winner argument as follows:

 function stopGame(winner){      switch(winner){           case  undefined  : return;           case 0: feedback.text=" Tie Game!";break;           case 1: feedback.text=" X wins!";break;           case -1: feedback.text=" O wins!";break;      }

Notice what we're doing in the first case. If winner is undefined , we're returning from the function. That means nothing if this function executes unless there is a winner or tie game. That allows us to follow the previous switch statement with generic code that should be executed regardless of who won. Consider the following:

 playerCount = turn = playerSide = 0;

As you can see, we're setting playerCount , turn , and playerSide to 0. That will keep the game from playing until the user clicks one of the buttons to start a new game.

Note

You might be wondering how setting playerCount , turn , and playerSide to 0 can keep the game from continuing. The solution to this comes in the movement function that we have not yet implemented. Inside the makeMove function are tests of these variables to ensure that the proper logic can be used. If all three variables are 0, makeMove does nothing. This will be clear when we implement makeMove .

Now all that is left when the game ends is to make the proper winbar visible. I'm doing this with several if statements that use absolute value and addition, but there could be many possible solutions.

 if(Math.abs(board[0][0]+board[0][1]+board[0][2]) == 3)           real_board.winbar4._visible=true;      if(Math.abs(board[1][0]+board[1][1]+board[1][2]) == 3)           real_board.winbar5._visible=true;      if(Math.abs(board[2][0]+board[2][1]+board[2][2]) == 3)           real_board.winbar6._visible=true;      if(Math.abs(board[0][0]+board[1][0]+board[2][0]) == 3)           real_board.winbar1._visible=true;      if(Math.abs(board[0][1]+board[1][1]+board[2][1]) == 3)           real_board.winbar2._visible=true;      if(Math.abs(board[0][2]+board[1][2]+board[2][2]) == 3)           real_board.winbar3._visible=true;      if(Math.abs(board[0][0]+board[1][1]+board[2][2]) == 3)           real_board.winbar7._visible=true;      if(Math.abs(board[0][2]+board[1][1]+board[2][0]) == 3)           real_board.winbar8._visible=true;

That completes the stopGame implementation, so we can close the function.

Implementing the Movement Functions

The movement functions are composed of three separate functions. The first, makeMove , is a generic movement function that is called when the user clicks on a square. The second two functions, makeXMove and makeOMove , cause the move to be made on the board and test for a winning move. Let's begin with makeMove .

The makeMove Function

We've already attached the makeMove function to the onRelease handlers for all the tiles on the board. We begin by opening the function's definition:

 function makeMove(){

Because the makeMove function is attached to a handler, using this inside it refers to the square the user clicked. We can use this to make the correct move for the player.

First we test to see whether the player is playing X; if so, we make a move for X as follows:

 if(playerSide == 1) makeXMove(this);

Notice that we're calling makeXMove with this as the argument. That's because makeXMove is going to need a reference to the correct real_board square to make it visible.

Now we test to see whether the player is playing the O side. We could do this with an else because the player must be playing either X or O, but I've used an else if to be explicit:

 else if(playerSide == -1) makeOMove(this);

The player's move has been made. If it's a single-player game, we need to immediately make a computer move before the player has a chance to click another square. We first test to see if the game is a one-player game. If it is, we can use makeComputerMove .

 if(playerCount==1) makeComputerMove();

Next we need to put an else on the previous if statement. If this is not a one-player game, we're going to need to flip both the turn and playerSide variables. Therefore, the next move will be a move for the opposite side (X or O).

 else{turn = -turn; playerSide = -playerSide;}

That completes the makeMove function, so we can close it.

The makeXMove Function

When the player has chosen a move and he is playing as X, the makeXMove function is called. The single argument, mc , refers to the square that the user clicked. First we open the function:

 function makeXMove(mc){

Then we increment the move counter, which is attached to board .

 board.moveCount++;

We need to make the square show an X. The mc argument refers to a square on the board that has two child clips attached: one named x and one named o . We make the x child clip visible.

 mc.x._visible = true;

Now we must disable this square so that the user cannot click on it again.

 mc.onRelease = null;

We're storing our movement data in the board array. Because the move being made is for X, we set the board element to 1 as follows:

 board[mc.r][mc.c] = 1;

Notice how we're indexing the board array. The mc calls its properties r and c , which were initialized in initGame to indicate the row and column that the square represents in the board array. They recorded the 0 “2 index of the row and column for that particular square.

Finally, we need to test for a win. As I said earlier, we're going to give the return value from testForWin to the stopGame function. Both of these have been implemented already, so this should make sense.

 stopGame(testForWin());

That completes the makeXMove function, so we can close it.

The makeOMove Function

To implement makeOMove , we do the same thing that we did for X, but we change the values to reflect a move to O instead. Consider the following:

  function makeOMove(mc){  board.moveCount++;  mc.o._visible = true;  mc.onRelease = null;  board[mc.r][mc.c] = -1;  stopGame(testForWin()); }

Feel free to test the game now. The two-player version should be working and should look like Figure 10.12.

Figure 10.12: The two-player game works now.

Implementing the AI

Now that the base game engine is complete, we're ready to look at the AI. This is one of the most enjoyable parts of game development because AI programming tends to be a bit more creative than other forms of development. Even though our game uses a standard technique (minimax search) to solve the problem, our solution is not without some customizations that require creative thinking.

Skill Levels

The first thing we need to think about are the skill levels. I've added skill levels to this game so that we can explore a few different scenarios for how the computer can approach the same problem of how to choose a square. The techniques we'll see have drastically different results for how well the computer plays. Because some of the ways have better and worse results for the computer player, these correspond nicely to skill levels.

Tip	Skill levels for AIs don't always mean that you have to take multiple approaches to coding the AI. Often you can create one script that relies on variables whose ranges of values change based on the skill level.

Skill Level 1

The AI for skill level 1 should be pretty simplistic. A child who has a bit of skill at tic tac toe should be able to defeat it the majority of the time. Because we don't need something smart, I propose a simple solution.

At skill level 1, the computer will make a random move. That should ensure that this level is easy to beat and easy to implement.

Skill Level 2

Skill level 2 needs to be a little bit smarter , but not too smart. When a user is playing tic tac toe, the center square has a strategic advantage over other squares. The computer should move in the center square anytime it is available.

Further, the corners are better moves than the sides. The computer should play into the corners before it plays into the sides.

If we follow those two rules, the computer should have a decent shot at beating us.

Skill Level 3

At this skill level, the computer should play flawlessly. In tic tac toe, if both players play perfectly, the game ends in a tie every time. It is impossible for either X or O to win unless someone makes a mistake. Skill level 3 should never make mistakes. It should be undefeatable.

The makeComputerMove Function

The makeComputerMove function is called when the computer makes a move. It first chooses a move and then executes it on the board. We begin by opening the function.

 function makeComputerMove(){

Now we test to see if the skill level is 1.

 if(skill==1){

If it is, we create a do while loop that picks random moves until it finds one that has not been made. (We must keep the computer from trying to move in a square that's already played in.)

 do{                rr = getRandom(0,2);                rc = getRandom(0,2);           }while(board[rr][rc] != 0);

Caution

Make sure that you add the getRandom function from previous chapters to the end of your code. If you test the movie before you add this code, you will produce an infinite loop. Here is the code if you need it. Just be sure not to add it inside the current function:

 function getRandom(minimum, maximum){      return Math.floor(Math.random() * (maximum - minimum +1) + minimum); }

As you can see, rr and rc contain the indexes of the random move for skill level 1. We now package these together into an object named move . Later, we'll call executeComputerMove with this move object as an argument.

 move = {r:rr,c:rc};

That completes skill level 1, so we can close the if statement.

Skill level 2 needs to prefer the center to all other moves, followed by the corners. We can look through the moves in order of preference until we find one that is open. After we've found one, we create the move object with its indexes.

 else if(skill==2){           if(board[1][1]==0) move = {r:1,c:1};           else if(board[0][0]==0) move = {r:0,c:0};           else if(board[2][2]==0) move = {r:2,c:2};           else if(board[0][2]==0) move = {r:0,c:2};           else if(board[2][0]==0) move = {r:2,c:0};           else if(board[1][0]==0) move = {r:1,c:0};           else if(board[0][1]==0) move = {r:0,c:1};           else if(board[2][1]==0) move = {r:2,c:1};           else if(board[1][2]==0) move = {r:1,c:2};      }

As you can see, we're just stepping through the moves to find a vacant square. When we do find one, we set up the move object with the proper indexes.

Now it's time for skill level 3. There one is more complicated, so I've decided to completely encapsulate the skill level 3 behavior in a function called findGoodMove . This gives us the following:

 else if(skill==3){           move = findGoodMove();      }

As you might surmise from the preceding script, findGoodMove returns an object just like the other skill levels that can be stored in the move object.

At this point, we can assume that the move object contains a valid move and can now make the move. Before we execute the move, we need to get a reference to the real_board square that the computer wants. We know the index of the item, but now we need a reference to the real_board child clip that is associated with it. If you go review the names of the squares inside the real_board symbol, you find the names are conveniently constructed with the letter b plus a concatenation of the row and column numbers that correspond to the array, which result in the following:

 var tile = real_board["b"+move.r+move.c];

Now we have a tile reference that points to the proper square to click. We can execute the executeComputerMove function with our new tile as the argument.

 executeComputerMove(tile);

That completes the makeComputerMove function, so we can close it.

The executeComputerMove Function

You've just seen the call to executeComputerMove , which hands in a real_board square reference as the argument. To correctly make the move, we just need to check which side the player is playing and then make the opposite move. (If the player is playing X, we move O, and vice versa.) Consider the following:

 function executeComputerMove(tile){      if(playerSide==1) makeOMove(tile);      else if(playerSide==-1) makeXMove(tile); }

As you can see, it's just like I said. If the player is X (1) we call makeOMove . If the player is O (-1) we call makeXMove .

If you test your movie now, you'll see that skill levels 1 and 2 both work, although neither was difficult to defeat.

The findGoodMove Function

Now we're really getting down to it. The AI's interface and first two skill levels are complete. The AI can make moves at skill levels 1 and 2. Now it's time to implement skill level 3.

There are two functions we haven't implemented yet: findGoodMove and minimax . We're going to take a couple passes at them because I want to build them up one concept at a time. The first order of business is to implement the raw minimax search with no extra features.

The minimax function will return a move object for use in the executeComputerMove function, so for now we can implement findGoodMove to do nothing other than call minimax and return its result. In the future, we'll be adding some additional script to findGoodMove that will make our AI play faster, but we'll get to that later. Our initial implementation of findGoodMove is as follows:

 function findGoodMove(){      return minimax(); }

That's pretty easy. And, like I said, we'll be coming back and adding some stuff later. Let's move on to the heart of our AI: minimax .

The minimax Function

We're staring the monster square in the eyes, and it's time to make our move. We must implement a function that looks at every possible move in the game and finds the best move to make.

This is not going to be a simple function to develop, and you should be prepared to study it repeatedly over time to completely grasp it. In all honestly, you will probably not fully understand it until you have implemented it yourself at least once. After reading about this function, you might want to put the book down and try to reproduce it yourself. You'll know you really understand it when you can write it on your own.

Tip	If you decide to try implementing minimax on your own, just remember that you are creating a recursive function with no arguments that returns a move object. I have included a function in the "Testing" section that will help you debug your minimax function.

Our recursive minimax function is going to do all the work for any given node in the game tree. The function must perform several actions during each iteration. We need to look closely at exactly what those actions are. During each iteration, we need to pretend to make every possible move for the current turn. (Each turn has a maximum of nine possible moves.) We need to do the following for each possible move:

Evaluate each move to see if any is a winner.
If there is a winner or if the game is a tie, create a move object for the current move.
If the game is not yet over, recursively call the minimax function.
Undo the move we just pretended to make.
Check to see if the current move object contains a better move than our currently recorded best move. If the new move is better, change the best move to be the current move.
After you've tried every possible move for the current turn, return the best move.

This list is a bit dense and hard to follow, so let's go through it in detail.

Essentially , our minimax function uses a nested for loop to iterate over every possible move in the current turn. In other words, if the computer is about to make the first move of the game, there are nine possible moves it can make. We pretend to make each of these one at a time, and after pretending to make one, we perform steps 1 “5 on the board we've just created using our pretend move. If our pretend move caused either player to win, we create a move object for the current move we just pretended to make. If the game is finished in a tie, we also make a move object for the current move. However, if neither player has won and the game is not over yet, we call our minimax . That will, of course, cause our recursion and essentially cause the computer to look ahead at potential moves that come after the current move.

These recursive calls eventually return (when they hit base cases) and bubble back up the chain of recursive calls, and when they do, we assign a move object to their return value. After the recursive call, we undo the move we just pretended to make. Then we check to see if the move object for our current turn contains a better move than our currently recorded best move. If the new move is better than our old best move, we assign best move to be the current move.

After all possible moves for the current turn have been evaluated in this way by playing all potential moves hypothetically and continuing those moves until a game end is reached, we'll have a best move that represents the first move toward the optimal ending of the game. After we have this first step, we return the move object so that it can be executed.

That's the general idea of what needs to happen here. We're evaluating all our moves and returning the best move. You might be wondering how we determine the best move at any given time. You might also be wondering how the computer is going to make moves for both X and O while playing out the entire game for each move.

The computer looks for a best move for itself when it's playing O. However, after the recursion kicks in, the computer looks ahead toward future moves. At that point, the next move the computer needs to look at is a move for X because X's turn comes next. The computer must realize that X is trying to win, so it must assume that X will do its best to make good moves.

Each time the game tree grows deeper, the current move alternates between X and O. This whole search works by trying to find the best move for X when pretending to make X moves and trying to find the best move for O when O moves. The logic for finding a good move is the same no matter whose turn it is.

A win for X is represented by a value of infinity. Likewise, a win for O is represented by negative infinity. If we are looking for a best move for X, we're trying to maximize the value of the move (find a value of infinity, which means X has won.) When we're pretending to move for O, we're trying to minimize the value of the current move (find a value of negative infinity, which means O has won). This process of minimizing one turn and maximizing the next turn gives rise to the name of this technique: minimax .

That was a big chunk of theory, and you might be scratching your head a little bit. If so, then perhaps looking at the code will shed light on the situation. Let's go ahead and start adding some code to get minimax working.

We begin by opening the function:

 function minimax(){

Now we create a variable called bestMove , which will eventually hold an object indicating which move to make. We are going to do this by comparing the current best move's rank to the rank of the move that is currently being attempted. To make the comparison work the first time, we create an object, give it the property value , and set it equal to 0.

 var bestMove = {value:0};

Now we begin our nested loop. We need to iterate over the board to look at every possible move. Consider the following:

 for(var i=0;i<3;++i){           for(var j=0;j<3;++j){                if(board[i][j] == 0){

As you can see, this is a nested for loop with an if statement inside. The if tests to see whether the current move is available. If someone has already moved in this square, we don't need to look into it.

At this point, I want to close off all the statements we've opened so far and insert the return statement we've been talking about. The vital part of minimax is inside this if statement, so I want to make sure everything up until now makes sense. Consider our function so far:

 function minimax(){      var bestMove = {value:0};      for(var i=0;i<3;++i){           for(var j=0;j<3;++j){                if(board[i][j] == 0){                     //add the rest of the implementation here                }           }      }      return bestMove; }

Inside the unfinished part, we'll be setting bestMove equal to the best move possible this turn. At the end of the function, we return it. Now let's move inside that if statement to finish our implementation. First we need to create a temporary variable to hold the current move.

 var move;

Now we need to pretend to make the move. We do this by marking the board with the appropriate value (1 or -1). We don't need to actually make the move by calling makeXMove because we're only pretending to make the move. For our minimax purposes, we handle everything using board . We don't want to mess with real_board because all the steps we are going through now are hypothetical.

To make the correct move, we need to know if this is a move for X or for O. We can figure that out by using the moveCount variable that is attached to board . If moveCount is an even number, it's X's turn. If moveCount is odd, it's O's turn. We can use the modulus operator to determine whether the number is even or odd. Consider the following:

 if(board.moveCount%2==0)                          board[i][j] = 1;                     else board[i][j] = -1;

The previous script will make the appropriate move on the board. Now we must increment the moveCount so that future calls to minimax will have the proper moveCount .

 board.moveCount++;

At this point, we're ready for the heart of minimax . It's time for our base cases. As you know, if someone wins or if the game is a tie, we don't need to recurse anymore. Therefore, we first test to see if the move we just made has won the game.

 var someoneWon = testForWin();

If X has won, someoneWon will be 1. In that case, we set up a move object.

 if(someoneWon==1)                          move = {r:i,c:j,value:Infinity};

As you can see, our move object gets the for loop indexes to show the current move ( i and j ). Then we attach a third property to our move object: the value property. We'll use this later to figure out which of the current moves is the best. Because X has won, our value is Infinity .

Now we do the same for a win for O:

 else if(someoneWon==-1)                          move = {r:i,c:j,value:-Infinity};

Notice this time that because O has won, our move 's value is -Infinity .

Finally, we need to check for a tie. This is done, as usual, with the moveCount property.

 else if(board.moveCount==9)                          move = {r:i,c:j,value:0};

This time, our script is dealing with a tie game, so our value is set to 0.

Finally, we've tested for all three base cases, and it's time to recurse. If none of the above tests were true (neither player won, and moveCount is less than 9), we call minimax .

 else move = minimax();

Now we have to do something that you might find odd at first. Consider what's going to happen when the previous recursive call returns. The move that is returned from that call is going to contain r and c properties based on the final move that wins the game. But that is not the move we want to return. That future move should not be the move we make this turn. Instead, we know that the future move is going to win, so we make that move now. To do this, we change the values of move.r and move.c to reflect the current move. Keep in mind that we aren't affecting the value property of the move object.

 move.r=i;move.c=j;

That completes the heart of our recursive function. Now it's time to finish the work for this current move. We don't want the move we pretended to make to alter the other moves we're going to make later this turn (further iterations of our for loops ), so we need to unmake the move.

 board.moveCount-;                     board[i][j] = 0;

As you can see, we've decremented moveCount and reset the board element to 0. That unmakes our pretend move. All that's left to do is find out if our current move is better than the best move we've found so far.

We can check to see if our current move is better than our best move. This must happen in two parts because what's best for X is not what's best for O. In the same way that we choose which move to make (X or O), we're going to decide which move is best. As before, we do this with the modulus operator and the moveCount .

 if(board.moveCount%2==0){                          if(move.value >= bestMove.value){                               bestMove = move;                          }                     }

This script is the max part of minimax . It's testing whether the current move is a move for X. If it is, it's trying to maximize the value of the move. Therefore, if the current move ( move.value ) is greater than or equal to the best move ( bestMove.value ), we assign move to bestMove .

Now we do the same thing for a move of O, but we minimize instead, as follows:

 else{                          if(move.value <= bestMove.value){                               bestMove = move;                          }                     }

As you can see, this time we're using less than and equal to. That will make sure that our bestMove contains the most negative move possible. (We're looking for negative infinity.)

That completes the interior if statement just inside the for loops. I want to make sure you can look at this code as a block, so what follows is the complete minimax function. In the future, there will be improvements made, and the complete code listing at the end of the chapter contains those improvements. The script that follows does not contain improvements. It is the script we created earlier.

 function minimax(){      var bestMove = {value:0};      for(var i=0;i<3;++i){           for(var j=0;j<3;++j){                if(board[i][j] == 0){                     var move;                     if(board.moveCount%2==0)                          board[i][j] = 1;                     else board[i][j] = -1;                     board.moveCount++;                     var someoneWon = testForWin();                     if(someoneWon==1)                          move = {r:i,c:j,value:Infinity};                     else if(someoneWon==-1)                          move = {r:i,c:j,value:-Infinity};                     else if(board.moveCount==9)                          move = {r:i,c:j,value:0};                     else move = minimax();                          move.r=i;move.c=j;                     board.moveCount-;                     board[i][j] = 0;                     else if(board.moveCount%2==0){                          if(move.value >= bestMove.value){                               bestMove = move;                          }                     }                     else{                          if(move.value <= bestMove.value){                               bestMove = move;                          }                     }                }           }      }      return bestMove; }

The previous script is functional enough for you to be able to test a one-player game During testing, you might find some problems. When the computer makes its first move, the game pauses. If your computer is fast, this delay might not be very pronounced, but if your system is moderate or slow in speed, the pause could be large. In fact, you might receive a message informing you that the currently running script is taking a long time and asking whether you want to terminate it. This is shown in Figure 10.13.

Figure 10.13: If a script takes too long between frames , this dialog box appears asking if you want to terminate it.

The problem is that even though tic tac toe is a simple game, iterating through every possible move can take quite a long time. This pause can, on most systems, be far too long. This long pause is unacceptable, and we're going to have to find a way to speed things up. Fortunately, there are a couple things we can do.

Improving Efficiency

We're going to do two things to improve the efficiency of our AI. The first is to hardcode a few of the early moves so that our recursive function does not get called until the game is a few moves in. That will have a dramatic effect on how long our AI takes to choose its first couple moves. The second thing we're going to do involves removing some extra work that our minimax function is doing currently. Let's look at the hard coding first.

Hardcoding Early Moves

Our current minimax function iterates over the entire game tree. That allows our AI to play flawlessly, which is what we want. But the game tree, even for tic tac toe, is large. When the AI makes its first move, it has to iterate over hundreds of possible moves, which takes a great deal of time. However, after the game is a couple moves in, the minimax function has a much smaller game tree to iterate over, and things work fine. But consider this: If the player chooses to play as O, and the AI needs to make the first move of the game, it iterates over the entire game tree. The AI should choose the center square for its first move. Why are we iterating over the entire game tree if all we're going to do is move into the middle square? We're wasting time iterating over possible moves only to come back and move into the center square every time.

If we simply hardcoded this first move, the AI would instantly move into the middle square, freeing up valuable CPU cycles. Then the player would choose his first move. Finally, the AI would be ready to make its second move. The game tree, after two moves have been made, would be substantially smaller and faster to iterate over.

By preprogramming the first few moves of the game, our minimax function is spared a lot of needless work early in the game. I propose that our AI should have its first few moves hard-coded in. How would we do that? Fortunately, we're already set up for it. Inside the findGoodMove function, we're doing nothing but calling minimax . Now, instead of just instantly calling minimax , findGoodMove handles making the first few moves for the AI. When we're past those first few moves, findGoodMove can go back to calling minimax again.

The question now becomes this: How many moves should be hardcoded? Well, the further we try to hardcode, the harder it's going to be and the more logic it will take to program. The first move, of course, is obvious. If this is the first move of the game ( moveCount is 0), the AI will choose the middle square. Consider the following addition to findGoodMove :

 function findGoodMove(){  if(board.moveCount == 0) return {r:1,c:1};   else return minimax();  }

As you can see, we've introduced a bit of logic to handle the first move. If moveCount is 0, we simply return a move into the middle square (1,1). Now minimax will not be called until the AI is asked to make the third move of the game (O's second move).

Let's take it another step. If the player is playing X and he makes his first move, our AI will be called on to make the game's second move. The logic behind the second move is simple as well. If the player puts his X anywhere other than the center square, our AI's first move will be into the empty center square. However, if the player moved into the center on his first move, our AI can move into one of the corners. It doesn't really matter which corner he moves into at this point because the only move X has on the board is in the center square. Consider the following addition, which implements the second move of the game:

 function findGoodMove(){      if(board.moveCount == 0) return {r:1,c:1};  else if(board.moveCount ==1){   if(!board[1][1]) return {r:1,c:1};   else return {r:0,c:0};   }  else return minimax(); }

We've added an else if statement to handle the second move. If the center square is still open at this point, we move there. If it's not, (X moved there on his first turn), we move into the upper-left corner. This addition will save us loads of processing time, just like our previous addition did.

We're getting close to the end of what we'll want to hardcode, but I believe there is one more move we can make in this fashion.

If our AI is called on to make the third move of the game, we know we're playing O and that our first move would have been into the center square. That means that X's first move (the second move of the game) would have been into one of the outside squares. All we need to do to handle the third move logic is look for X's first move and then choose our next move based on that. Remember that we moved into the center square on our first move, so that one is already taken.

If the player moved into one of the corners, our AI should move into the opposite corner. If the player moved into one of the side squares, we should move into a corner on the opposite side of the board. Consider this final addition to findGoodMove :

 function findGoodMove(){      if(board.moveCount == 0) return {r:1,c:1};      else if(board.moveCount ==1){           if(!board[1][1]) return {r:1,c:1};           else return {r:0,c:0};      }  else if(board.moveCount ==2){   if(board[0][0]) return {r:2,c:2};   if(board[0][2]) return {r:2,c:0};   if(board[2][0]) return {r:0,c:2};   if(board[2][2]) return {r:0,c:0};   if(board[0][1]  board[1][0]) return {r:2,c:0};   if(board[1][2]  board[2][1]) return {r:0,c:0};   }  else return minimax(); }

As you can see, we're looking for X's first move and then choosing a move based on it.

At this point, we've hardcoded the first three moves into the AI. Now our minimax function will not be called until (at the earliest) the fourth move of the game. That dramatically reduces the size of the game tree and takes a lot of stress off the CPU in those early moves. In addition, the logic we've just coded will operate instantly, which will get rid of that nasty pause we have when minimax is first called.

Notice the way each hardcoded move becomes more complex as we go. The game's first move is one line of script, but each move after it has many lines more than the previous. If we attempted to code the next move (the fourth move in the game), our logic would become complex and difficult to write. At this point, we should go ahead and let minimax take over to find our move. With our reduced game tree, minimax will have no problem finding the best move in a short amount of time.

Removing Unnecessary minimax Calls

Our previous efficiency addition was pretty easy. We just hardcoded the first three moves of the game so that minimax wouldn't need to be called until our game was further along when the resulting game tree would be smaller and faster to iterate through.

The next step in improving our AI's speed is a little more complex. Our current minimax search is actually doing a good bit more work than it needs to. Look at Figure 10.14, which furthers the explanation.

Figure 10.14: Our AI is playing as O and is about to make a move.

In Figure 10.14, the player is playing as X and our AI is playing as O. As you can see, X has made three moves and O has made two. That means it's O's turn. There are four possible moves O can make at this point. Our current minimax function looks at all four moves. Any of those four that don't end the game are investigated by further recursive calls to minimax .

Notice that one of those four moves causes O to win. If one move allows O to win, why should we iterate over the entire game tree beneath this node? It should be enough to find that winning move and return it without investigating the other three moves, and more importantly, investigating all possible moves under those three moves.

The process of stopping our minimax function early because we're already found what we're looking for is called tree pruning . When possible, whole branches of our game tree can be removed (pruned) to avoid needless effort by minimax . The benefit can be quite large, so we should add tree pruning to our minimax function.

The idea is that we're going to want to watch during our testing for bestMove . If some value of move turns out to be infinity for an X move or negative infinity for an O move, we should break out of our current nested for loop. As I said, there is no point in looking for more moves on the same board when a winning move has been found.

The implementation is quite brief. We create a variable called prune as the first line in mini-max . We assign prune an initial value of false , indicating that we have not found a prune condition yet and we should proceed normally. Consider the following addition to minimax :

 function minimax(){  var prune = false;  var bestMove = {value:0};

Now we need to alter our nested for loops to stop when prune is true . That way, we can break out of the looping structure whenever a move that is good enough has been found. Consider the following alteration:

  for(var i=0;i<3&&!prune;++i){   for(var j=0;j<3&&!prune;++j){

As you can see, we're using a compound statement as our condition. We're looping until our index hits three, or until prune is true , whichever comes first.

Finally, we need to alter our checks for bestMove to include a test to see if we've found a winning move. If we have, we set prune to be true .

 else if(board.moveCount%2==0){                          if(move.value >= bestMove.value){                               bestMove = move;  if(bestMove.value == Infinity)   prune=true;  }                     }                     else{                          if(move.value <= bestMove.value){                               bestMove = move;  if(bestMove.value == -Infinity)   prune=true;  }                     }

As you can see, when we find a new bestMove , we check to see if the new move's value is a winning move for the current side (X or O). If it is, we set prune to be true . This causes our nested for loop to break out, bringing about the end of the function (return bestMove ) sooner. In addition to saving us some extra looping, we're also saving what would have been many recursive calls to minimax .

You might not think this pruning can make a substantial difference in terms of efficiency, but it does. In fact, our alteration cuts down the time that minimax takes to find a move by more than half.

At this point, Tic Tac Toe plays quickly. The AI takes a brief time to find the best move and, as you will see if you play it a few times on skill 3, it is undefeatable.

Tip

The tree pruning we're doing here is a simple version of what is called alpha/beta cutoff . Unfortunately, a discussion of alpha/beta cutoff is beyond this book, but I have included links in Appendix D, "Web Resources and Further Reading," to point you toward more information on the subject. Essentially, alpha/beta cutoff allows you to keep track of previous move values so that you can prune your tree when you find a move that is "good enough." What constitutes good enough is not always easy to decide. Sometimes the decision is based on trial and error, and other times it becomes more relaxed as your search takes longer and longer.

Testing

If you attempted to implement the minimax function yourself, you might have found it quite challenging. When your recursive function has a bug, finding it means digging through a stack of recursive calls, looking for the problem.

When I created this minimax implementation, I used the debugger, but I also supplemented it with my own function. Each time I entered minimax , I called a function named outputBoard .

The job of outputBoard was to trace the current state of board so that I could see exactly what the data looked like that minimax was about to operate on. I have included this helper function here for your convenience.

 function outputBoard(){      trace('depth: '+board.moveCount);      for(var i=0;i<3;++i){           mystring = "";           for(var j=0;j<3;++j){                if(board[i][j]==1) mystring += 'X';                else if(board[i][j]==-1) mystring += 'O';                else mystring += ' ';           }           trace(mystring);      } }

Complete Code Listing

What follows is a complete listing of the code for Tic Tac Toe . You can use this listing to see all the code in context. All the efficiency optimizations are in place.

 initGame(); function initGame(){      button3.enabled = false;      button3._visible = false;      feedback.text=" Please choose the number of human players. 1 Player    plays against the computer."      turn = 0;      playerSide = 0;      playerCount = 0;      button1.myText.text = "1 plr";      button2.myText.text = "2 plr";      button1.onRelease = selectFirstPlayer;      button2.onRelease = startGame2plr;      real_board._visible = false;      for(var i=0;i<3;++i){           for(var j=0;j<3;++j){                real_board["b"+i+j].onRelease = makeMove;                real_board["b"+i+j].x._visible = false;                real_board["b"+i+j].o._visible = false;                real_board["b"+i+j].r=i;                real_board["b"+i+j].c=j;           }      } } function selectFirstPlayer(){      button1.onRelease = function(){firstPlayerSelected(1);}      button1.myText.text = "X";      button2.onRelease = function(){firstPlayerSelected(-1);}      button2.myText.text = "O";      feedback.text=" Please choose X or O. X goes first." } function firstPlayerSelected(side){      playerSide = side;      button1.onRelease = function(){selectSkill(1);}      button2.onRelease = function(){selectSkill(2);}      button3.onRelease = function(){selectSkill(3);}      button3.enabled = true;      button3._visible = true;      button1.myText.text = "skill 1";      button2.myText.text = "skill 2";      button3.myText.text = "skill 3";      feedback.text=" Please select a skill level." } function selectSkill(skill){      this.skill = skill;      button1.onRelease = selectFirstPlayer;      button2.onRelease = startGame2plr;      button3.gotoAndStop("_up");      button3.enabled = false;      button3._visible = false;      button1.myText.text = "1 plr";      button2.myText.text = "2 plr";      feedback.text = "skill "+skill;      startGame1plr(); } function startGame1plr(){      playerCount = 1;      startGame(); } function startGame2plr(){      feedback.text = "";      playerCount = 2;      playerSide = 1;      startGame(); } function startGame(){      turn = 1;      real_board._visible = true;      board = [[0,0,0],[0,0,0],[0,0,0]];      board.moveCount = 0;      for(var i=0;i<3;++i)           for(var j=0;j<3;++j){                real_board["b"+i+j].onRelease = makeMove;                real_board["b"+i+j].x._visible = false;                real_board["b"+i+j].o._visible = false;           }      for(var i=1;i<9;++i) real_board["winbar"+i]._visible = false;      if(playerCount == 1 && playerSide==-1) makeComputerMove(); } function stopGame(winner){      switch(winner){           case  undefined  : return;           case 0: feedback.text=" Tie Game!";break;           case 1: feedback.text=" X wins!";break;           case -1: feedback.text=" O wins!";break;      }      playerCount = turn = playerSide = 0;      if(Math.abs(board[0][0]+board[0][1]+board[0][2]) == 3)           real_board.winbar4._visible=true;      if(Math.abs(board[1][0]+board[1][1]+board[1][2]) == 3)           real_board.winbar5._visible=true;      if(Math.abs(board[2][0]+board[2][1]+board[2][2]) == 3)           real_board.winbar6._visible=true;      if(Math.abs(board[0][0]+board[1][0]+board[2][0]) == 3)           real_board.winbar1._visible=true;      if(Math.abs(board[0][1]+board[1][1]+board[2][1]) == 3)           real_board.winbar2._visible=true;      if(Math.abs(board[0][2]+board[1][2]+board[2][2]) == 3)           real_board.winbar3._visible=true;      if(Math.abs(board[0][0]+board[1][1]+board[2][2]) == 3)           real_board.winbar7._visible=true;      if(Math.abs(board[0][2]+board[1][1]+board[2][0]) == 3)           real_board.winbar8._visible=true; } function makeMove(){      if(playerSide == 1) makeXMove(this);      else if(playerSide == -1) makeOMove(this);      if(playerCount==1) makeComputerMove();      else{turn = -turn; playerSide = -playerSide;} } function makeXMove(mc){      board.moveCount++;      mc.x._visible = true;      mc.onRelease = null;      board[mc.r][mc.c] = 1;      stopGame(testForWin()); } function makeOMove(mc){      board.moveCount++;      mc.o._visible = true;      mc.onRelease = null;      board[mc.r][mc.c] = -1;      stopGame(testForWin()); } function makeComputerMove(){      if(skill==1){           do{                rr = getRandom(0,2);                rc = getRandom(0,2);           }while(board[rr][rc] != 0);           move = {r:rr,c:rc};      }      else if(skill==2){           if(board[1][1]==0) move = {r:1,c:1};           else if(board[0][0]==0) move = {r:0,c:0};           else if(board[2][2]==0) move = {r:2,c:2};           else if(board[0][2]==0) move = {r:0,c:2};           else if(board[2][0]==0) move = {r:2,c:0};           else if(board[1][0]==0) move = {r:1,c:0};           else if(board[0][1]==0) move = {r:0,c:1};           else if(board[2][1]==0) move = {r:2,c:1};           else if(board[1][2]==0) move = {r:1,c:2};      }      else if(skill==3){           move = findGoodMove();      }      var tile = real_board["b"+move.r+move.c];      executeComputerMove(tile); } function executeComputerMove(tile){      if(playerSide==1) makeOMove(tile);      else if(playerSide==-1) makeXMove(tile); } function testForWin(){      if(board[0][0]){           if(board[0][0]==board[0][1] && board[0][1]==board[0][2])return board[0][0];           if(board[0][0]==board[1][0] && board[1][0]==board[2][0])return board[0][0];           if(board[0][0]==board[1][1] && board[1][1]==board[2][2])return board[0][0];      }      if(board[1][1]){           if(board[1][0]==board[1][1] && board[1][1]==board[1][2])return board[1][0];           if(board[0][1]==board[1][1] && board[1][1]==board[2][1])return board[0][1];           if(board[0][2]==board[1][1] && board[1][1]==board[2][0])return board[1][1];      }      if(board[2][2]){           if(board[2][0]==board[2][1] && board[2][1]==board[2][2])return board[2][0];           if(board[0][2]==board[1][2] && board[1][2]==board[2][2])return board[0][2];      }      if(board.moveCount == 9) return 0; } function findGoodMove(){      if(board.moveCount == 0) return {r:1,c:1};      else if(board.moveCount ==1){           if(!board[1][1]) return {r:1,c:1};           else return {r:0,c:0};      }      else if(board.moveCount ==2){           if(board[0][0]) return {r:2,c:2};           if(board[0][2]) return {r:2,c:0};           if(board[2][0]) return {r:0,c:2};           if(board[2][2]) return {r:0,c:0};           if(board[0][1]  board[1][0]) return {r:2,c:0};           if(board[1][2]  board[2][1]) return {r:0,c:0};      }      else return minimax(); } function minimax(){      outputBoard();      var prune = false;      var bestMove = {value:0};      for(var i=0;i<3&&!prune;++i){           for(var j=0;j<3&&!prune;++j){                if(board[i][j] == 0){                     var move;                     if(board.moveCount%2==0)                          board[i][j] = 1;                     else board[i][j] = -1;                     board.moveCount++;                     var someoneWon = testForWin();                     if(someoneWon==1)                          move = {r:i,c:j,value:Infinity};                     else if(someoneWon==-1)                          move = {r:i,c:j,value:-Infinity};                     else if(board.moveCount==9)                          move = {r:i,c:j,value:0};                     else move = minimax();                     move.r=i;move.c=j;                     board.moveCount-;                     board[i][j] = 0;                     if(board.moveCount%2==0){                          if(move.value >= bestMove.value){                               bestMove = move;                               if(bestMove.value == Infinity) prune=true                          }                     }                     else{                          if(move.value <= bestMove.value){                               bestMove = move;                               if(bestMove.value == -Infinity) prune=true                          }                     }                }           }      }      return bestMove; } function getRandom(minimum, maximum){      return Math.floor(Math.random() * (maximum - minimum +1) + minimum); } //uncomment this function for use in debugging the minimax function /* function outputBoard(){      trace('depth: '+board.moveCount);      for(var i=0;i<3;++i){           mystring = "";           for(var j=0;j<3;++j){                if(board[i][j]==1) mystring += 'X';                else if(board[i][j]==-1) mystring += 'O';                else mystring += ' ';           }           trace(mystring);      } } */