Six-Trix
Aqualines
CycleMan
Domino Dilemma
Rhumb Line

All Games...
Six-Trix on flash!
CycleMan
PacHoney Bear

CycleMan
Cram
SuperNim
Abracadabra
Javanoid
Basketball

 
 
 
 
 
 
 
 

How to make a logical game on Flash. Part 3

This is the Chapter 11 from our book "The Flash 8 Game Developing Handbook", ISBN 1-931769-47-8. CD-ROM included. You can buy this book from us for $30 only.

Listing 11.11 contains the rel function that is called from the onRelease event handlers attached to every piece. If the piece that passed its coordinates to rel is marked, the function should remove the mark from the piece. In other words, it should remove the mark clip attached to the piece and set marked[y][x] to zero. The mark clip can be accessed using its full name eval('square'+x+y+'.piece.mark').removeMovieClip(). Here 'square'+x+y is the name of the square on the board. Appending the '.piece' string to this name gives you the name of the piece on this square. If you append '.mark' to the result, you'll get access to the instance of the mark clip attached to the piece. When you know the name of an object, you can call the eval function to obtain a reference to the object and use its methods and properties.
If the gamer clicked an unmarked piece, the function should mark it by attaching an instance of the mark clip to the piece. However, the function should first check for marked pieces in the other rows. If the check is successful, the function gets a reference to the instance of the piece: name=eval('square'+x+y+'.piece'). Then it uses the name reference to get a reference to the instance of the mark clip attached to the piece: name=eval('name.mark'). You might be surprised, but this code, where the name reference is inside a string, works correctly.
Generally speaking, when you attach a piece to a square and a mark to a piece, you don't need to set their coordinates to zeroes because these are default values. However, you can test this code, for example, by setting the _x property of the mark clip to ten: name._x=10. You'll see that the marks on the pieces moved ten pixels to the right.
Listing 11.12. The userMove function

// the user's move
// this function is called when the btOK button is clicked
function userMove()
{ var flag=0;

  // If this is the computer's move, exit the function.
  if (mymove) return;
  // removing all the marked pieces
  for (var i=0; i < 3; i++)
   for (var j=0; j < i+3; j++)
    if (marked[i][j])
     { showPiece(0,j,i);
       // setting an indication that at least one piece was removed
       flag=1;
     }
  // If there were no move, nothing happens.
  if (flag)
   { if (!numpieces)
      // There are no pieces left. The game is over.
      { // You win!
        showResult(2);
        // Game over
        showGameOver(1);
        return;
      }
     // It is the computer's move now
     mymove=1;
     // The thinking function will start in 0.1 second
     // It will display "Thinking..."
     gameact.onEnterFrame=thinking;
     waittime=getTimer()+100;
   }
}

After the gamer marks pieces to be removed, he or she clicks the btOK button. However, some people can click this button needlessly, just for fun. The userMove function (Listing 11.12) foresees both situations. While removing the marked pieces in the loop, the function sets the flag variable indicating whether at least one piece was removed. Then it examines the indicator. If no pieces were removed, the function does nothing. Otherwise it checks whether the game is over by analyzing the numpieces variable. If the variable is equal to zero, the gamer has won. Otherwise it is the computer's turn to make a move. The function calls the thinking function which calls the computerMove function. Both calls are made after delays, so that the Thinking: text isn't displayed simultaneously with disappearance of the piece.

11.4. Computing and Making Moves

To be able to play with your program, you only need to implement the last two functions: computerMove that makes a move and an auxiliary function, isWin, that determines whether a given move is winning. The latter function will analyze the position after the move. This function is the most important though very small. Without it, the program would make random pointless moves. Interaction between these two functions is the following: The computerMove function skims through all possible moves in the current position. It passes the resulting positions to the isWin function asking it whether the position is winning. If isWin answers: "Yes", the computerMove function makes the move and allows the gamer to make his or hers. If no winning move is found, the anyMove function that makes a random move is called.
In which form is the position passed to the isWin function? Only three variables are necessary for describing a position: they should store the numbers of pieces in each row. Indeed, the locations of the pieces in the columns are insignificant. For the sake of convenience, these variables are combined in an array though working with indexed variables is slower than with scalar ones.
Before I show you the isWin function, I should digress. This function calls itself, and there weren't such functions in this book so far.

11.4.1. Recursive Functions

Recursive functions call themselves either directly, in their bodies, or indirectly, via chains of calls to other functions. In any case, you enter a recursive function before you exit it.
At the dawn of computer technology, not all high-level programming languages included recursive functions. ActionScript does, but it limits the recursion depth to 256 levels. At the 256th level, the interpreter suspects that the recursion is infinite, and stops execution. For this project, 256 levels are enough because there will never be more than 12 moves in the game. You'll never go deeper than the 12th level. In addition, the 15-second time limit will be exhausted before the recursion limit is reached.
When describing recursive functions, many authors use computation of a factorial as an example. (A factorial is a product of all natural numbers from 1 to N: N!=1 2 : N). It is easy to implement a factorial using a simple loop. However, not all of recursive functions can be rewritten as loops. In ActionScript, factorial computation looks as follows:

function fact(n)
{ if (n < 2) return 1;
  return n*fact(n-1);
}

Surprisingly, it works very quickly even if you specify

trace(fact(100));

If you specify a greater value, say, 255, the result will be Infinity. If you specify

trace(fact(256));

you'll see the following message in the Output window:
256 levels of recursion were exceeded in one action list.
This is probably an infinite loop.
Further execution of actions has been disabled in this movie.
I mentioned this situation earlier.
Consider an example of how this function works. Let n be three. If you put trace(n); at the beginning of the function, you'll see the following output:

3
2
1
6

The last line, 6, is the result of computation. At the first call, the fact function "sees" that n isn't less than two and executes the 3*fact(2) statement. The second call is made with the 2 argument, so the 2*fact(1) is executed. At the third level of recursion, the function doesn't need to call itself and returns one. However, it returns this value to itself, to the previous level, rather than to the main program. At this level, the 2*fact(1) expression turns into 2*1 and is computed. The result, which is two, is returned to the upper level. The 3*fact(2) expression becomes 3*2 and is computed. The result is passed to the trace function that displays it.
This might seem too complicated. The human brain cannot think recursively, and it often fails to remember the return point if the recursion level is three or greater. As for the computer processor, it manages recursion easily and doesn't have a headache.
Let's now return to the project and apply recursion to the search of the best move. The isWin function takes a game position as a parameter and returns one if the position is wining or zero otherwise. To do this, isWin declares a local array to store the position. Like other local variables, the array belongs to the current instance of isWin. before the function returns control (to itself), the memory allocated for its local variables in freed up. The execution will continue with local variables of the outer instance of isWin which called its copy. Of course, the code of the isWin function isn't duplicated, but new memory is only allocated for local variables.
After isWin receives the current position from itself of from the computerMove function, it skims through all possible moves in this position and obtains the positions that emerge after the moves. It calls itself repeatedly passing itself the obtained positions. As a result, a called copy of isWin analyzes the position stored in the local array of the calling copy of this function. Suppose isWin makes a move, calls itself passing its local array to the called copy, and receives 1. What is the conclusion? Is the position in the array winning? Nothing of the kind. Surprised? I'll explain this. When isWin receives a position, it makes the moves for the opponent of the caller copy. For the opponent to win, he or she should have a winning move in the position. If there is at least one winning move (the called isWin function returned one), the position passed to the current copy of isWin is losing. Well, when is a position passed to isWin winning? When it receives zeroes from all copies of it called during skimming through all the possible moves. Such a situation indicates that all the moves in the received position are losing, and, therefore, the caller of the current copy of isWin made a winning move. Ooh! The code, however, is quite elegant: a function ten statements long beats a person in a logical game! In this project, a simple game is implemented, but the function does its job well in any case. This is the power of recursion!
To continue the theoretical digression, I'll tell you that you don't need to pass the array with a position as an argument. All instances of the isWin function can work with the same global array. With such an approach, isWin should undo the move it made before it returns. It is necessary to restore the position that existed at the moment when the function was called. In each particular game, you should choose the quickest approach. For example, when moves are computed quickly, and the array with a position is large, the second variant is the best.
If you represent a game as a tree of moves in which nodes correspond to positions, the root node will correspond to the initial position. A few branches (moves) are incident from this zero-level node to first-level nodes in which the other player can make moves. Other branches are incident from the first-level nodes to second-level nodes, and so on. At a certain level, some nodes don't have incident branches. These nodes correspond to end positions (the board is empty). The isWin function starts the tree traverse from the root node and walks as deep as possible, up to the end node. Then it steps back and walks along another branch up to the end. This sort of traverse is called depth-first search. Chess programs are based on the same principles. When traversing the game tree, the function doesn't visit all the nodes, that is, doesn't analyze all the positions. If it finds a winning move in a position, it doesn't consider the other moves in this position. It steps back and sees whether the opponent has a counter-move. With such a method, isWin estimates the positions, and the estimate gradually moves to the initial position. Finally, when the initial position is estimated, the function completes its work. The estimates for positions on deeper levels are stored in local variables of corresponding instances of the isWin function. I could write this function in a non-recursive form, but this would be much more complicated.

11.4.2. The computerMove and isWin Functions

These are the last and the most complicated fragments of code in this book.
Listing 11.13. The computerMove function

// the computer's move
function computerMove()
{ // waiting for a specified time interval
  if (getTimer() < waittime) return;
  // deleting the wait method of the gameact clip
  delete gameact.onEnterFrame;
  
  // skimming through the variants of the computer's moves
  var i,j,k,res,nump,rows=new Array(0,0,0),rows1=new Array(0,0,0);
  // assigning the rows and rows1 arrays the numbers of the pieces
  // in the rows
  for (i=0; i < 3; i++)
   { for (j=0; j < i+3; j++)
      rows[i]+=board[i][j];
     rows1[i]=rows[i];
   }
  // Skimming through the computer moves in the current position
  // starting from the lowest row because there can be more pieces there
  for (i=2; i >= 0; i--)
   { // skimming over empty rows
     if (!rows[i]) continue;
     // making all possible moves in the ith row
     for (j=0; j < rows[i]; j++)
      { // A move: leaving j pieces in the ith row
        rows1[i]=j;
        // estimating the move
        res=isWin(rows1);
        // if the move is winning, the opponent will lose
        if (res == 1)
         { showResult(1);
           // making this winning move
           // i.e., removing rows[i]-j pieces from the ith row
           nump=rows[i]-j;
           // removing the pieces from the board
           for (k=0; k < i+3; k++)
            if (nump && board[i][k])
             { showPiece(0,k,i);
               --nump;
             }
           // it is now the gamer's turn
           mymove=0;
           // hiding the "Thinking..." text
           showThinking(0);
           // if there are no more pieces, the game is over
           if (!numpieces) showGameOver(1);
           return;
         }
      }
     // restoring the number of pieces in the ith row
     rows1[i]=rows[i];
   }
  // A winning move wasn't found. Making a random move
  anyMove();
}

When preparing to skimming through moves, the computerMove function (Listing 11.13) creates two arrays, rows and rows1, and assigns their elements the numbers of pieces in the rows on the board: the zero elements of both arrays get the number of pieces in the top row, the first elements get the number in the middle row, and the second elements get the number in the bottom row:

for (i=0; i < 3; i++)
   { for (j=0; j < i+3; j++)
      rows[i]+=board[i][j];
     rows1[i]=rows[i];
   }

The rows array will be used to make moves and pass the resulting positions to the isWin function, and the rows1 array will be used to undo losing moves. The external loop iterates through the ith row moving from the bottom to top to remove as many pieces as possible and have more chances to find a winning move quickly:

for (i=2; i >= 0; i--)
   { // skimming over empty rows
     if (!rows[i]) continue;

The internal loop changes the j loop counter from zero to rows[i] which is the number of pieces in the ith row. During each iteration, all possible moves are made. That is, the code first leaves no pieces, then it leaves one piece, then two, and so on up to rows[i] 1 pieces:

for (j=0; j < rows[i]; j++)
 { // A move: leaving j pieces in the ith row
   rows1[i]=j;

Then the res variable is assigned an estimate of the position after the next move is made:

res=isWin(rows1);

If res is equal to one, the computer won, and the You lose message is displayed:
showResult(1);
The computer should make this winning move then. To do this, the function assigns the nump (number of pieces) variable the number of pieces in the ith row:

nump=rows[i]-j;

In a loop, the function finds squares with pieces in the ith row and removes the pieces until the nump variable becomes equal to zero:

for (k=0; k < i+3; k++)
 if (nump && board[i][k])
  { showPiece(0,k,i);
    --nump;
  }

If no pieces are left after this move, the game is over. Otherwise its the gamer's turn, and the computerMove function returns control.
If the function tried all possible moves in the ith row, but failed to find a winning move, it restores the number of the pieces in this row and goes to the next row:

rows1[i]=rows[i];

If the loop for i terminated naturally, this means the current position is loosing, and the anyMove function should be called to make a random move:
anyMove();
That's all about the computerMove function. Consider the isWin function (Listing 11.14). In fact, it executes almost the same code to skim through possible moves, but it simply returns zero instead of making a winning move.
Listing 11.14. The isWin function

// returns an estimate of the move that led to the current position
// 0 - the move was losing
// 1 - the move was winning
function isWin(rows)
{ var i,j,res,
   rows1=new Array(rows[0],rows[1],rows[2]);

   for (i=2; i >= 0; i--)
   { // skimming over empty rows
     if (!rows1[i]) continue;
     // Making the opponent's moves in the ith row
     for (j=0; j < rows[i]; j++)
      { // A move: leaving j pieces in the ith row
        rows1[i]=j;
        // estimating the move
        res=isWin(rows1);
        // If the opponent's move is winning, the move that led to the 
        // current position, was losing
        if (res == 1) return 0;
      }
     // restoring the number of pieces in the ith row
     rows1[i]=rows[i];
   }
  // If the opponent's all moves are losing,
  // the move that led to the current position, was winning
  return 1;
}

If you are attentive enough, you noticed that the following two statements:

res=isWin(rows1);
if (res == 1) return 0;

can be replaced with one:

if (isWin(rows1)) return 0;

This will speed up the execution a little. (By the way, if you used scalar variables instead of arrays in isWin function, the gain in performance would be even greater. However, don't do this in games where many moves are skimmed through.) This is true, but you should change this function to allow people play and have fun. In the current version, if the gamer carefully makes a move other than winning, he or she will get the You lose message immediately: the program will warn them that it is pointless to play further. Only when the gamer clicks the Comp. begins button, the computer doesn't skim through moves, but makes a random move. If it computed the best first move, the gamer would always lose without making a single move. Like 80% of similar positions, the initial position is winning. However, only one move is winning: you should remove two pieces from the upper row. You'll see this after you play with the project in the nim.fla and nim.as files located in the Example\Chapter 11 folder. You'll notice that computing moves takes a certain amount of time (about a few seconds) depending on the performance of your computer. I believe you have the quickest processor.

<<Prev.   Next>>