13
Javascript Games Tutorial #2: Awari
MarkKreitler (33)

Javascript Games Tutorial #2: Awari

Introduction

In this tutorial, we present a variation on the Ashanti game Awari. We have translated the BASIC game from David H. Ahl's 1978 book, "BASIC Computer Games -- Microcomputer Edition" into Javascript. This tutorial builds on the concepts discussed in Javascript Games Tutorial #1: GuessIt. It extends those ideas by introducing a game board and a computer opponent -- these will be the main focus of the tutorial.

The Rules

Before we begin presenting code, let's define the rules of the game.
The game is played on a board with 14 spaces: two rows of six small "bins", and two larger "bins", one on either side of the two rows (see the image below).

In this image, the green bins (the top row and the large bin on the left), belong to the computer, and the brown ones (bottom row and large bin on the right) belong to the human.

Each of the twelve small bins start with three tokens each. The large "scoring" areas are empty.

The human player moves first. You can select the tokens from any of the small bins in the bottom row. You then "sow" the tokens by dropping one into each bin, starting immediately to the right of the bin you chose and moving counterclockwise around the board. For example, if you drew the tokens in bin #4 and sowed them, this would be the result:

If the last token you sow falls into your scoring bin, you may immediately take another turn. You may only earn one extra move each turn, even if your last token lands in your scoring area during your extra move.

If the last token you sow falls in an empty small bin and there are tokens in the small bin opposite it, you may collect the tokens from both bins and move them into your scoring bin.

Once you have completed your move (or moves, if you earned a bonus turn), the computer will take its turn, following the same rules.

If, after any turn, all the small bins in either row are empty, the game ends and the winner is the player whose scoring area contains the most tokens. Ties are allowed.

Concepts

This tutorial will cover two topics:

  • Representing the game board
  • Creating a computer opponent

As with tutorial #1, we will present high-level topics here, and provide comments within the code itself with extra context and detail.

Representing the Board

The Awari board is really just a line with 14 elements that wraps around on itself:

Notice that we have started our numbering at 0, rather than 1. We'll explain why in a bit.

Each "bin" on the board holds exactly one piece of information: the number of tokens it contains.

So, to represent this board in Javascript, we need a data structure consisting of adjacent cells, each of which can hold a single number.

The "array" is the perfect fit.

In tutorial #1, we learned to define an array as follows:

var board[14];

It's a good convention to define "constants" (i.e., variables whose values never change) and then define your variable sizes in terms of these constants, rather than using the constants directly. So:

var BINS_PER_BOARD = 14;

var board[BINS_PER_BOARD];

This defines a linear list of cells. Recall from tutorial #1 that the first cell in the list has index '0':
board[0] = first cell in the list

We can read values from the array as follows:

var numTokensInCellFive = board[4];

and write them like this:

board[11] = 12; // puts 12 tokens in the twelfth cell

In general, we access the nth cell like this:
board[n - 1]

Keep these general array behaviors in mind as we discuss the functions that will manipulate the values on the board.

Manipulating the Board

To initialize the board for a new game, we could do this:

var STARTING_TOKEN_COUNT = 3; 	// 3 tokens per bin at game start

var setUpBoard = function() {
	for (var i=0; i<BINS_PER_BOARD; ++i) {
		if (i == PLAYER_SCORE_BIN || i == COMPUTER_SCORE_BIN) {
			board[i] = 0;
		}
		else {
			board[i] = STARTING_TOKEN_COUNT;
		}
	}
};

That's nice and simple, but we need a way to convey this configuration to the player. We can modify the 'print' function from tutorial #1 to facilitate display of an ASCII representation of the board.

var print = function(text, stayOnLine) {
	if (!text) text = "";
	if (!stayOnLine) text = text + "<br>";
	text = text.replace(/\s/g, "&nbsp");

	document.writeln(text);
	document.body.style.fontFamily = "monospace";
};

This new 'print' function has several key features. This line:

if (!text) text = "";

checks to see if the 'text' argument is invalid (the '!', or 'not' operator, reverses the truth value of whatever follows. If the text variable is invalid, it evaluates to false, and the 'not' operator will reverse this to true). If the text is invalid, we replace it with a valid, but empty, string.

This next line:

if (!stayOnLine) text = text + "<br>";

checks the value of the 'stayOnLine' argument. Here again, we use '!' to reverse the truth value of the argument. So, is 'stayOnLine' is false, we add the final "<br>" line break to the text, which will force the output down to the next line. Conversely, if 'stayOnLine' is true, then !stayOnLine is false, and we don't add any <br>. This means that the next call to print will start where the last one left off. We will use that to display our board in ASCII text.

This line:

text = text.replace(/\s/g, "&nbsp");

uses regular expressions (the text demarked with forward slashes /.../) to replace all whitespace characters (\s) globally (the trailing 'g') within the the string with html space characters (" "). We do this because, normally, web browsers purge whitespace as they see fit. This makes it difficult to display ASCII-art style drawings. This allows us to use "regular" spaces in code and have them render as HTML spaces on the web page.

Finally, we get to this line:

document.body.style.fontFamily = "monospace";

which tells the web page to render everything in a monospace font. Modern web fonts usually render different letters in different widths. This looks beautiful, but it makes it hard to align text when displaying console output. This line causes our text to render in a monospace style, in which all characters have the same width. This makes it easy to line up all our game board elements.

Armed with this modified print function, we can now display the game board with a couple of relatively simple functions:

var PLAYER_SCORE_BIN = 6;
var COMPUTER_SCORE_BIN = BINS_PER_BOARD - 1;
var BINS_PER_PLAYER = 6;

var drawBoard = function() {
	print("            COMPUTER'S BINS");

	print("   ", true);
	drawBins(COMPUTER);

	print("COMP                              YOUR");
	print("SCORE                             SCORE");

	if (board[COMPUTER_SCORE_BIN] < 10) {
		print("  " + board[COMPUTER_SCORE_BIN], true);
	}
	else {
		print(" " + board[COMPUTER_SCORE_BIN], true);
	}

	print("                              ", true);

	if (board[PLAYER_SCORE_BIN] < 10) {
		print ("  " + board[PLAYER_SCORE_BIN]);
	}
	else {
		print (" " + board[PLAYER_SCORE_BIN]);
	}

	print("   ", true);
	drawBins(PLAYER);
	print("    (1)  (2)  (3)  (4)  (5)  (6)");
	print("               YOUR BINS");

	print("");
;

var drawBins = function(startIndex) {
	var i = 0;

	for (i=0; i<BINS_PER_PLAYER; ++i) {
		var iBin = i + startIndex;

		if (startIndex === COMPUTER) {
			iBin = board.length - 2 - i;
		}

		var numTokens = board[iBin];

		if (numTokens < 10) {
		 	print ("  " + numTokens + " ", true);
		}
		else {
			print (" " + numTokens + " ", true);
		}
	}

	print();
};

Now that we can display the board, how do we make it change in reponse to player input?

Assume that we somehow obtain a number from 0-5 to identify the player bin from which to pull tokens to sow. Here is the algorithm that sows the tokens where startIndex is the bin from which we are drawing tokens and scoreBin is the index of the scoring bin for the current player (6 if it's the player's move and 13 if it's the computer's move):

var sowTokens = function(startIndex, scoreBin) {
	var i=0;
	var numTokens = board[startIndex]; // How many tokens in the selected bin?
	var doMoveAgain = false;
	var iBin = 0;

	// Remove tokens from the selected bins.
	board[startIndex] = 0;

	// Starting with the bin after the selected one,
	// loop numToken times...
	for (i=startIndex+1; i<startIndex+1 + numTokens; ++i) {
		// ...wrapping around if we went past the end of the board...
		iBin = i % BINS_PER_BOARD;

		// ...and adding 1 token to each space. 
		board[iBin] += 1;
	}

	// Find the bin across from our end point.
	var acrossBin = (BINS_PER_BOARD - 2) - iBin;

	// Did we place the last token on our score bin?
	if (iBin === scoreBin) {
		doMoveAgain = true;
	}
	// Did our last token land in an empty bin across from a non-empty bin?
	else if (board[iBin] === 1 && board[acrossBin] > 0) {
		// Yes -- so gather up the tokens from both bins...
		var capturedTokens = board[acrossBin] + board[iBin];
		board[acrossBin] = 0;
		board[iBin] = 0;

		// ...and pu them in our score bin.
		board[scoreBin] += capturedTokens;
	}

	return doMoveAgain;
};

There are a couple of lines that need further explanation.

First, this line:

iBin = i % BINS_PER_BOARD;

As the comment says, it's supposed to wrap around if we go past the end of the board. This works because the modulus operator (%) works as follows:

A % B = the remainder of A divided by B.

In our case, B is always BINS_PER_BOARD, or 14. Try plugging some numbers in to see how this works.

3 % 14 = 3
7 % 14 = 7
11 % 14 = 11
etc.

In fact, for any 'A' less than 14, we just get 'A' back.

At exactly 14, we get 0, because

14 / 14

has a remainder of 0.

Note that board[14 % 14] is the same as board[0] -- which returns us to the starting bin.

15 % 14 has a remainder of 1. So board[15 % 14] is the same as board[1]. In other words, we've wrapped back around to the second space.

Similary, 18 % 14 has a remainder of 4, which wraps us back to the 5th space.

And so on.

Then there's this line:

var acrossBin = (BINS_PER_BOARD - 2) - iBin;

This formula returns the index of the small bin across from any other small bin. For instance, the bin across from bin the player's second bin (which has index 1) is:

acrossBin = (14 - 2) - 1 = 11

With a quick glance at our diagrams above, we can see this is correct. Feel free to plug in more values to make sure you believe it.

Finally, notice that sowTokens() returns the value of doMoveAgain. If this is 'true', this indicates the last token fell in the appropriate scoring bin.

On the player's turn, let's assume that she presses a key from 1-6. We have to convert this text value to a number value and subtract one so it corresponds to the correct spaces in the array (0-5). We also have to ensure that the chosen bin contains some tokens. If all that is true, we then sow the tokens and watch out for the case in which the player earned a free move.

That routine will look something like this:

var isExtraMove = false;

var doPlayerMove = function(key) {
	// Use parseInt to convert the text value of the key
	// the user pressed into an integer value. Subtract 1
	// because the user pressed 1-6 to select from the first
	// six spaces, but these correspond to locations 0-5 in
	// the 'board' array.
	var binIndex = parseInt(key) - 1;

	// Check: if the chosen space is empty, report an invalid move.
	if (board[binIndex] === 0) {
		// TODO: report illegal move and try again.
	}
	// Call 'sowTokens'. This distributes the tokens around the board
	// and returns 'true' if the last token fell in the PLAYER_SCORE_BIN.
	// If that hapened (sowTokens returnd 'true') and we're not already
	// in the extra move phrase...
	else if (sowTokens(binIndex, PLAYER_SCORE_BIN) && !isExtraMove) {
		// ...check for game over...
		if (isGameOver()) {
			// TODO: tell the player the game is over.
		}
		else {
			// ...grant the player a second move.
			isExtraMove = true;

			// TODO: allow player to move again.
		}
	}
	// If the player is already taking an extra move, or if his move
	// didn't end in his score bin, go here:
	else {
		if (isGameOver()) {
			// TODO: tell the player the game is over.
		}
		else {
			// TODO: let the computer move.
		}
	}
};

Finally, we need to check to see if the game has ended. Recall that the end game condition is either row of small bins being empty. The check for that looks like this:

var isGameOver = function() {
	var i=0;
	var topTotal = 0;
	var bottomTotal = 0;

	for (i=0; i<BINS_PER_PLAYER; ++i) {
		topTotal += board[i + PLAYER_SCORE_BIN + 1];
		bottomTotal += board[i];
	}

	return topTotal === 0 || bottomTotal === 0;
};

Creating a Computer Opponent

In this section, we will outline how to make a computer opponent for the game. Our opponent will not do much thinking -- it will just make the play that earns the most points, given the current state of the board.

The simplest way to do that is to loop through the top row of small bins (from index 7 through 12), simulate a turn taken at each bin, and keep the best resulting board. The trick to this is using the same starting board configuration each time through the loop. This requires that we have a way to save the board, simulate a move, then restore the board:

var tryAllMoves = function() {
	saveCurrentBoard();
	for (int i=FIRST_COMPUTER_BIN; i<COMPUTER_SCORE_BIN; ++i) {
		if (board[i] > 0) {
		    if (sowTokens(i, COMPUTER_SCORE_BIN)) {
		        // TODO: go again, unless this is already a bonus move.
		    }
		}

		loadSavedBoard();
	}
}

Notice that we have to handle the case where the computer earns a bonus turn. This is tricky, because when this happens, we need to try all possible moves based on the new board configuration, then return to the original configuration and try the remaining possibilities. For example, suppose that we're trying all possible moves, and on move #3, the computer gets an extra turn. We then need to check all possible moves based on the board state after making move 3. Once we have tested those, we need to return back to the original configuration and try moves 4, 5, and 6:

In this diagram, all the moves in green represent moves simulated starting from the board's current configuration. The moves in black would be simulated using the state of the board after making move 3.

Ugh. This looks complicated. How are we going to use the new board configuration when simulating a bonus turn? How will we return to the old board configuration afterwards?

Fortunately, there's a clever way to do all this, but first we have to learn about variable scope.

Variable Scope and the Execution Stack

In everyday English, scope means, "extent or range," and broadly refers to the breadth of a region. It's much the same in computer jargon: "scope" refers to the region of a program over which a variable is accessible.

"Wait, what? Variables aren't accessible everywhere?"

Short answer: usually, no. We have been writing our programs in a very sloppy way, so far, putting all our variables in the "global scope", which is accessible everywhere, but this isn't great practice. It's good for us because it makes life easier, allowing us to focus on the fundamentals of programming, but soon, we'll develop better habits.

For now, though, we'll use a simple rule for scoping variables:

In a Javascript program, a variable is visible to anything within the same set of curly braces.

Here's an example:

{
	var valueOut = 5;

	var myFunc = function() {
		var valueIn = 3;

		console.log("Sum is " + (valueOut + valueIn));
	};

	var myOtherFunc = function() {
	    console.log("ValueOut: " + valueOut);
	    console.log("valueIn:  " + valueIn); // Error!	
	};
};

In this case, valueOut is visible everywhere, because everything is contained within that outer set of curly braces. The variable valueIn is visible only within the function myFunc, whose scope is defined by the curly braces wrapping its code. This means that myOtherFunc will throw an error because it's trying to access valueIn, which is defined outside its braces.

"But wait...isn't valueOut also defined outside the myOtherFunc's braces?"

Yes -- but myOtherFunc is contained within the same braces that contain valueOut, so valueOut is still visible to myOtherFunc -- they are both defined within the scopt of the outer braces. In contrast, valueIn is defined only within the scope of myFunc, and myOtherFunc is defined outside of myFunc's scope.

Now consider another example:

var myFunc2 = function() {
    var outVar = 3;

    for (var i=0; i<3; ++i) {
        var inVar = i + outVar;
        console.log("Value is " + inVar);
    }

    console.log("inVar = " + inVar); // Error!
};

The curly braces of the 'for' loop create a new local scope in which we define inVar. Therefore, inVar is available to any code inside those braces. Notice that the last console.log function is outside this scope, so trying to access inVar would be an error.

There is one final note to add to this entire discussion: you can think of all the code you write as being surrounded by a single set of invisible braces. This is known as the global scope, and variables defined in that scopre are visible everywhere in your program. So far, we have been defining everything in the global scope. As we mentioned above, that makes it easy to focus on learning programming fundamentals, but it's generally not a good idea, especially for larger programs.

OK, so now we know what scope is. Is that helpful?

By itself, not so much, but in conjunction with the concept of the execution stack, it's going to solve our problem.

So, what's the execution stack?

Without getting too technical, it's the program that runs our program. It performs two important functions: 1) it makes sure our code runs in the correct order, and 2) it reserves memory our program needs to run, as it is running.

#2 is the key for us: the execution stack is responsible for reserving the memory our program needs. More specifically, every time the stack executes one of our game functions, it reserves memory required by the variables in that function's scope. This is true even if it's executing a function inside of another function.

Consider this function:

var myFunc = function() {
    var value = 1;

    value = value + 1;

    if (value < 3) {
        // Call this function again.
        myFunc();
    }
};

Think through how this might work when we call it. First, the exectuion stack creates a new scope, and within that scope, it creates the variable value, which contains 1. Next, in adds 1 to value's contents, which become 2. Since the value is less than 3, the execution stack calls myFunc again.

At this point, you might be tempted to think that value already exists, so the next time we add 1 to it, it will increase to 3 and we will skip over the 'if', but that's not what happens. Each time the execution stack enters the if statement and calls myFunc, it creates a new scope, because this is a new call to the function. Within that scope is a new value variable that gets set to 1. That means it always executes the contents of the if clause. This leads to an endless cycle called infinite recursion. The word recurse refers to the process in which a function calls itself, as in myFunc above.

The important takeaway here is that each version of the function maintains its own local data, which is visible only to that version of the function.

With that knowledge, and these functions:

var copyBoard = function(srcBoard, destBoard) {
	destBoard.length = 0;
	for (var i=0; i<srcBoard.length; ++i) {
		destBoard.push(srcBoard[i]);
	}
};

var saveBoard = function(boardCopy) {
	var i=0;

	boardCopy.length = 0;
	for (i=0; i<board.length; ++i) {
		boardCopy.push(board[i]);
	}
};

var restoreBoard = function(boardCopy) {
	var i=0;

	for (i=0; i<board.length; ++i) {
		board[i] = boardCopy[i];
	}
}

we can now write the function that will act as the brain for our computer opponent:

var tryAllMoves = function(bestBoard) {
	// Find the best move from among the computer's six choices.
	var i = 0;
	var bestScore = -1;
	var bestBin = -1;
	var boardCopy = [];
	var newBestBoard = [];

	saveBoard(boardCopy);
			
	for (i=0; i<BINS_PER_PLAYER; ++i) {
		var iBin = PLAYER_SCORE_BIN + 1 + i;
		if (board[iBin] > 0) {

			if (sowTokens(iBin, COMPUTER_SCORE_BIN)) {
				if (!isExtraMove) {
					isExtraMove = true;
					tryAllMoves(newBestBoard);
					copyBoard(newBestBoard, board);
				}
			}

			if (board[COMPUTER_SCORE_BIN] > bestScore) {
				saveBoard(bestBoard);
				bestScore = board[COMPUTER_SCORE_BIN];
			}

			restoreBoard(boardCopy);
		}
	}
};

Here are the keys to understanding how it works:

1) It accepts a single argument called bestBoard. This is an array into which the best move will be copied.
2) It defines a local variable called boardCopy into which we copy the current board configuration.
3) It uses restoreBoard(boardCopy) to return the board to it's original configuration after every simulated run.
4) If sowTokens() returns 'true', meaning the computer earned an extra turn, it calls itself before restoring the board.

Think about #4 for a moment, then think about the last illustration with the green and black "Play #" diagram.

When the computer moves, it calls tryAllMoves. The program will start making simulated plays. These correspond to the green "Play #" entries above.

If the computer earns an extra turn, it will call tryAllMoves again. Since the board hasn't been restored for this pass through the loop, it will reflect the state of the board after the current simulated play. As the program starts to execute this second version of tryAllMoves (i.e., the black "Play #" entries above), it will save this modified board and start trying all the moves using it as the original state.

Once this second version of tryAllMoves has finished, it will copy its best result into the bestBoard array, then exit back into the first version of tryAllMoves. This takes us back to the lower, green "Play #" entries in the diagram. In terms of code, we come back at the 'copyBoard(newBestBoard, board)' command inside the if statement. This copies the best board from our free move back into the current board. The first version of tryAllMoves then tests this configuration to see if it's the best result, and if so, copies it into the bestBoard variable. Then it restores the board back to its original configuration and tries the next move.

Don't worry if this makes your brain hurt. Recursion is a difficult concept to grasp. Carefully stepping through a specific example can help.

But, believe it or not, that's all there is to our simple brain for Awari.

There isn't much else to the program, as you will see if you examine the source code.

One thing you'll notice if you play a few games is that your opponent will always choose exactly that same options, given a particular board configuration. Even if there are two plays that yield the identical amount of points, it will always pick the move closest to the player's starting goal.

Here's a challenge: see if you can figure out why tryAllMoves produces this behavior. Once you figure it out, see if you can modify it so that there's a chance it might pick a different move of equal worth.

You will also notice that your opponent isn't smart enough to protect itself. Specifically, if it has tokens across from an empty space, these tokens are subject to theft from the human player. Can you modify tryAllMoves to detect these vulnerabilities and avoid them?

Conclusion

That wraps up this tutorial. We hope this gives you some idea how to represent your game board as data inside your program, as well as how to make your program "play" a game. That subject -- which blurs into "game AI" (artificial intelligence) is broad and deep -- we've barely scratched the surface of the tip of the iceberg. But, hopefully, you have some idea this solution works, and how you might adapt it for other, similar games.

You are viewing a single comment. View All
1
shadowelite7 (0)

nice, now I don't have to worry about buying marbles for mancala