Atoms Game. Tutorial two – doing computer moves

In the first tutorial, I created the Atoms board and wrote code to let the player enter their move. In this tutorial, I’ll add the computer player and also code to handle chain reactions.

Remember when you add one to any cell, if that cell reaches four then all adjacent cells horizontally and vertically have one added. These cells can change ownership and this is what wins or loses you the game. When there are none of your cells left or your opponents then the game finishes. Also because this happens during chain reactions which can rumble on for a long time, it’s important to do the check every time an adjacent cell changes ownership.

Computer player Strategy

Once a move has been decided, playing it is simple but what is the strategy for deciding where to play? I decided that I’d make this work in two different ways.

  1. Before the board has a certain number of computer owned cells, just pick a random empty spot.  An initial value that I used was 32. I call this the threshold.
  2. After the threshold has been reached. Find computer owned cells next to a player owned cell and play on those. Build up a computer owned cell until it reaches four and captures the adjacent player cell.

To make this work, I need to create some helper functions. These are

  • FindEmptyCell – Finds the coordinates of an empty cell.
  • CountCells – Check to see if we have reached the threshold.
  • IsGameOver. Count the cells owned by the player and the computer player. If either is 0 then the game is over. Note though don’t call this until five moves have been played!
  • FindComputerCellNearPlayer returns x and y coordinates next to a player cell.
  • NearPlayer. Returns 1 if the piece is next to a player piece.

Each function is short and does one thing. This is a good programming practise. Some of the functions need helper functions of their own. For example NearPlayer calls IsPlayerPiece which returns 1 if the specified cell contains a player piece. It also calls IsOnBoard, a function that returns 1 if the specified coordinates are both within the range 0..BOARDSIZE-1.

Returning multiple values from a function

There are two ways to do this. One is to create a struct and populate it. I never like doing that as it’s a bit clunky and I haven’t explained what a struct is. The other is a bit more complicated because it uses pointers. I’ve not discussed pointers yet either. A pointer is a variable that holds the address of another variable. You declare it like this.

int * pointer_variable;

as in

int * x;

and to refer to the integer you use *x as in *x =0; This assigns 0  to the variable that x points to.

In int * x, x is a pointer to an int variable. In the example below (FindEmptyCell) the parameters passed into the function are the addresses of two variables. In the first three lines of PlayComputerMove, you can see two int variables x and y declared. Then in the call to FindEmptyCell the addresses of x and y are actually passed in. This is what &x and &y means.

The actual addresses are somewhere in memory but its not important exactly where they are. By telling FindEmptyCell where they are, it makes it possible to update the actual int variables and that’s what *x = and *y = does.

In my functions I use this to get the value of multiple parameters back. Here is an example with the function FindEmptyCell which is called from PlayComputerMove.

int FindEmptyCell(int* x, int* y) {
	int tries = 0;
	do {
		tries++;
		*x = rand() % BOARDSIZE;
		*y = rand() % BOARDSIZE;
		if (tries == MAXTRIES)
		{
			return 0;
		}
	} while (board[*x][*y] == 0);
	return 1;
}

void PlayComputerMove() {
	int x, y;
	if (CountCells() < THRESHOLD) {
		if (FindEmptyCell(&x, &y)) {
			PlayMove(x, y, 0);
		}
		else
		{
			FindComputerCellNearPlayer(&x, &y);
		}
	}
	else {
        // To be done
        }
}

This tries up to 1000 times (I used the #define MAXTRIES to specify this- feel free to try different values) to pick random coordinates on the board (anywhere from 0..BOARDSIZE-1). The stdlib function rand() returns a random value between 0 and RAND_MAX. RAND_MAX is a system specified value but is guaranteed to be at least 32767. On Windows, it is 32767.

The % BOARDSIZE does a modulus 8 calculation. It’s the same as clock arithmetic which is modulus 24. In clock arithmetic If you add 1 to 23:00 it becomes 00:00 as 24 wraps round to 0. Using % BOARDSIZE this way brings the random number into the range 0..7.

Normally you cannot return values from a function except by the return statement. Here though we have passed in the address of x and y. This is a bit naughty because x and y in the PlayComputerMove() function are ints but inside FindEmptyCell they are pointers to ints. So the effect of the line *x = rand() % BOARDSIZE; is to put a random value in the range 0..7 into the int x in the calling function which is PlayComputerMove.

Technically the line if (FindEmptyCell(&x, &y)) in PlayComputerMove does two things. It checks that the return value is 1 meaning it found an empty cell and it populates x and y with the coordinates of the empty cell.  The FindEmptyCell will always put values in x and y even if it can’t find an empty cell. It will try MAXTRIES times and the values left in x and y are the values from the last attempt. If the FindEmptyCell return 0 then it means it couldn’t find an empty cell and the PlayComputerMove then calls FindComputerCellNearPlayer..

Finding a Computer owned cell next to a player owned cell

This is the function FindComputerCellNearPlayer.

int FindComputerCellNearPlayer(int* x, int* y) {
	int tries = 0;
	do {
		if (!FindComputerCell(x, y))
			return 0; // Failed to find anywhere...
		if (NearPlayer(*x, *y)) {
			return 1;
		}
		tries++;
	} while (tries < MAXTRIES);
	return 0;
}

You might find it confusing that it calls FindComputerCell with x and y parameters but then calls NearPlayer with *x and * y. Why is this?

With FindComputerCell we want the x,y coordinates to be updated if it succeeds. Because we are in FindComputerCellNearPlayer which itself will update the coordinates we can use the x and y pointers directly, With NearPlayer though we only want to know if the coordinates are near a player owned cell. So it doesn’t need to update the coordinates like FindComputerCell does. So we pass in the actual int values of the external x and y which are obtained from *x and *y.

Making a Move and Explode

The function Explode handles incrementing the board cell value, setting the cell owner to whoever made the move and then checking to see if a chain reaction occurred. It does this recursively by calling Explode for all of the adjacent horizontal and vertical pieces. The first line in Explode checks that the supplied coordinates are on the board by calling IsOnBoard. If you exploded a cell at 0,0 then it would call Explode on -1,0,  0,-1, 0,1 and 1,0. Only the last two coordinates are of valid cells. You cannot access board[-1.0]. It will crash!

void Explode(int x, int y, int owner) {
	if (!IsOnBoard(x, y)) return;
	board[x][y]++;
	playerCell[x][y] = owner;
	if (board[x][y] == 4) {
		board[x][y] = 0;
		Explode(x - 1, y, owner);
		Explode(x + 1, y, owner);
		Explode(x, y - 1, owner);
		Explode(x, y + 1, owner);
	}
}

Notable in this is the statemen board[x][y]++ which adds one to board[x][y].

Checking the game has finished

This is done by calling IsGameOver() after each move. The best place to call this is in the main while(1) loop. If it is true (i.e. has a non-zero value) then it does a break to exit that loop. I used a global variable gameOver which is set in the function IsGameOver. It sets gameOver to 1 if the player won, or 2 if the computer won. We only use this variable to indicate who won.

Other changes

I added #defines for the playerCell values. 0 = UNOWNED, 1= PLAYEROWNED and 2 = COMPUTEROWNED.  This makes the logic a bit clearer. Also the computer player picks random empty locations for the first five turns and then with a 30% chance of picking an empty cell after that. Otherwise it looks for a Computer owned cell next to a player owned cell.

Also I moved the player input code into a separate GetPlayerMove function which calls PlayMove if you input valid coordinates. This function returns 0 if the player hit an escape key (or Q/q), and 1 if the player entered a valid move. I intend to move the escape checks into a function as its called in three places. I’ll do that with tutorial three.

Source Code

All the changes have grown the file to 275 lines long. I’ve uploaded this file (atoms2.c) to GitHub. Note, it hasn’t been extensively tested and there is currently one bug where the Computer player seems to own one or more of the Player cells. This is noticeable when you try to add an atom to a player cell and the program says you can’t do this on a computer owned cell. It’s there to prevent you adding one to a computer owned cell but has this bug.

(Visited 3 times, 1 visits today)