Gomoku game (human vs. computer)

In the last lesson, we discussed the Gomoku human vs. computer approach. In this lesson, we'll implement this approach while explaining the solution in detail. The following reiterates the requirements to convert the Gomoku human vs. human approach to the human vs. computer approach:

  1. The number of players is restricted to two; this is done to ensure that we have one human and one computer player to simplify the algorithm.

  2. The computer can randomly place its symbol in any valid board position.

  3. The computer should perform its turn by keeping in mind the following two points:

    1. The computer must prioritize placing its symbol where it has a winning chance.

    2. If that's not the case, then the computer must prioritize placing its symbol where it can block the opponent's win.

Implementation walkthrough

Restricting the number of players to two

Since we are restricting the number of players to two, there's no need for the NOP variable. Hence, the implementation of the init() and turnChange() functions have to be altered because both use the NOP variable.

Updated version of the init() function

In the previous version, the init() function asked for the number of players from the user and stored the value inside the NOP variable. Based on this variable, it asked the user for the names and symbols of said players. Since we'll only have one player in this version, all of this is unnecessary. The code snippet below highlights the changes made to the init() function:

Press + to interact
void init(char Board[][CAPACITY], int& dim, char pName[2][30], char pSym[], int& turn, int& winCount)
{
	cout << "Dimension: ";
	cin >> dim;
	cout << "Win Count: ";
	cin >> winCount;
	cout << "Enter player's name: ";
	cin >> pName[0];
    cout << "Enter player's symbol: ";
    cin >> pSym[0];
    
    pSym[1] = (pSym[0] == 'X' || pSym[0] == 'x') ? 'O' : 'X';
	
	for (int ri = 0; ri < dim; ri++)
	{
		for (int ci = 0; ci < dim; ci++)
		{
			Board[ri][ci] = '-';
		}
	}
	turn = rand() % 2;
}
Updated version of the turnChange() function

In the previous version, the modulus was taken by the number of players (NOP). However, in this case, we should take the modulus by 2, as shown below:

Press + to interact
void turnChange(int& turn)
{
	turn = (turn + 1) % 2;
}

Secondly, it'll be useful to create an enum to differentiate between the human and computer players. So, we declare the following before the function declarations:

enum TYPE{ HUMAN, COMPUTER };

Implementing the computer's move

For the computer's move, we have primarily two cases that we will implement in the HvsC function:

  1. The random case

  2. The winning case

The random case

In the random case, we need to generate a random number for both the row and the column (within the bounds of the board) and ensure that the selected position is valid (the isValid() function will come in handy here). The code snippet below shows how this can be done:

Press + to interact
do 
{
    ri = rand() % dim;
    ci = rand() % dim;
} while (!validInput(ri, ci, Board, dim));

AI Level 1: This approach is the most basic form of AI, where decisions are made by random.

Invalid points

Question

If the computer selects the wrong coordinates, do we need to print a message of invalid points?

Show Answer
The winning case

This case is not as straightforward as the previous one because we have to ensure all three of the following:

  1. If the computer can win by placing a symbol, it should make that move.

  2. Otherwise, the computer should place a symbol to block the opponent's win.

  3. The above two points should hold, even when the consecutive symbols are less than winCount - 1.

The computer must check all the valid positions of the board with respect to the first two conditions. Hence, for each valid position, we should do the following:

  1. Place the computer's/human's symbol temporarily on the board.

  2. Invoke the isWinHere() function and, if true is returned, we don't need to check for further moves; therefore, we return the function.

Before we head into the implementation of the winning case, we have to keep in mind that the Board parameter is of type const char[][], meaning that we can't place any symbol inside it. Therefore, the following code creates a copy of the Board in which we can place the symbol temporarily and invoke the isWinHere() function over it as well:

// creating an array for a new board
char T[CAPACITY][CAPACITY];
// copying the symbols from the board 'Board' to board 'T'
for (int r = 0; r < dim; r++)
{
    for (int c = 0; c < dim; c++)
    {
        T[r][c] = Board[r][c];
    }
}
Creating a copy of the board

Now, we can use the copy of the board stored inside T in our algorithms.

Implementation of the computer's winning move algorithm

Press + to interact
// Iterate over all positions in the board
for (int r = 0; r < dim; r++)
{
    for (int c = 0; c < dim; c++)
    {
        // If the position (r, c) is valid
        if (validInput(r, c, T, dim))
        {
            // Place computer's symbol
            T[r][c] = CS;
            // If the computer wins
            if (isWinHere(T, dim, WC, pSym, r, c))
            {
                // Remove computer's symbol from the board
                T[r][c] = '-';
                // Return the computer's move coordinates
                ri = r;
                ci = c;
                return;
            }
            else
            {
                // Remove computer's symbol from the board
                T[r][c] = '-';
            }
        }
    }
}

AI Level 2: This approach is a slightly advanced form of AI, where decisions are prioritized to benefit the computer.

Implementation of the human's winning move-blocking algorithm

Press + to interact
// Iterate over all positions in the board
for (int r = 0; r < dim; r++)
{
    for (int c = 0; c < dim; c++)
    {
        // If the position (r, c) is valid
        if (validInput(r, c, T, dim))
        {
            // Place human's symbol
            T[r][c] = HS;
            // If the human wins
            if (isWinHere(T, dim, WC, pSym, r, c))
            {
                // Remove human's symbol from the board
                T[r][c] = '-';
                // Return the human's move coordinates
                ri = r;
                ci = c;
                return;
            }
            else
            {
                // Remove human's symbol from the board
                T[r][c] = '-';
            }
        }
    }
}

AI Level 3: This approach is the most advanced form of AI, where decisions are not only prioritized to benefit the computer, but also to put the user at a disadvantageous position.

The outer loop iterates over all the rows in the board (from 0 to dim-1), and the inner loop iterates over all the columns in the board (from 0 to dim-1).

For each position (`r`,`c`) in the board, the code checks if the position is valid by calling `validInput(r, c, T, dim)`. If the position is valid, it places the human’s symbol (HS) in that position. Then, it checks if the human wins by calling `isWinHere(T, dim, WC, pSym, r, c)`. If the human wins, it returns the human’s move coordinates, which are stored in the variables `ri` and `ci`. If the human doesn’t win, the code removes the human’s symbol from the board by setting `T[r][c] = ‘-’`. This loop tries to simulate the human move and check if the human wins. If that's the case, it returns the coordinates of the winning move. Otherwise, it returns nothing.

It’s important to note that this code doesn’t guarantee that the human will win. Rather, it’s checking all the possible moves to check if the human would win in any of them.

Our algorithm for the computer's move selection is almost complete, with only one unresolved issue. Can you identify that issue? Does the computer only need to choose the coordinates when the winCount is equal to a specific number (for example, 5)? If this was the case, the human player could easily win, because the computer would place numbers randomly until the winCount would not be equal to the specific number.

To resolve this issue, we'll add one more loop for winCount that decrements the winCount until it is equal to 2. Hence, the computer will now perform computations for each winCount until 2 and choose the best winning move according to the requirements listed above.

Piecing it all together, we get the following code for the HvsC() function:

Press + to interact
void HvsC(const char Board[][CAPACITY], int& ri, int& ci, int dim, char pSym, int winCount, char CS, char HS)
{
    // creating an array for a new board
    char T[CAPACITY][CAPACITY];
    // copying the symbols from the board 'Board' to board 'T'
    for (int r = 0; r < dim; r++)
    {
        for (int c = 0; c < dim; c++)
        {
            T[r][c] = Board[r][c];
        }
    }
	for (int WC = winCount; WC > 1; WC--) {
        // Iterate over all positions in the board
        for (int r = 0; r < dim; r++)
        {
            for (int c = 0; c < dim; c++)
            {
                // If the position (r, c) is valid
                if (validInput(r, c, T, dim))
                {
                    // Place computer's symbol
                    T[r][c] = CS;
                    // If the computer wins
                    if (isWinHere(T, dim, WC, pSym, r, c))
                    {
                        // Remove computer's symbol from the board
                        T[r][c] = '-';
                        // Return the computer's move coordinates
                        ri = r;
                        ci = c;
                        return;
                    }
                    else
                    {
                        // Remove computer's symbol from the board
                        T[r][c] = '-';
                    }
                }
            }
        }
        // Iterate over all positions in the board
        for (int r = 0; r < dim; r++)
        {
            for (int c = 0; c < dim; c++)
            {
                // If the position (r, c) is valid
                if (validInput(r, c, T, dim))
                {
                    // Place human's symbol
                    T[r][c] = HS;
                    // If the human wins
                    if (isWinHere(T, dim, WC, pSym, r, c))
                    {
                        // Remove human's symbol from the board
                        T[r][c] = '-';
                        // Return the human's move coordinates
                        ri = r;
                        ci = c;
                        return;
                    }
                    else
                    {
                        // Remove human's symbol from the board
                        T[r][c] = '-';
                    }
                }
            }
        }
    }
    do {
        ri = rand() % dim;
        ci = rand() % dim;
    } while (!validInput(ri, ci, Board, dim));
}

Differentiating between the human's and computer's moves

Finally, all that is left for us is to invoke the logic for the human's and computer's moves separately inside the main() function, and our game is complete. Therefore, we add the following inside the do-while loop after printing the board:

Press + to interact
if (turn == HUMAN)
{
    do
    {
        userInput(ri, ci, pName[turn], pSym[turn]);
        if (!validInput(ri, ci, Board, dim))
        {
            cout << "Invalid Input" << endl;
        }
    } while (!validInput(ri, ci, Board, dim));
}
else
{
    cout << "Computer's turn..." << endl;
    sleep(3);
    HvsC(Board, ri, ci, dim, winCount, pSym[turn], pSym[COMPUTER], pSym[HUMAN]);
}

Complete implementation

#include <iostream>
#include <time.h>
#include <unistd.h>
#define CAPACITY 100
using namespace std;

enum TYPE{ HUMAN, COMPUTER };

void init(char Board[][CAPACITY], int& dim, char pName[2][30], char pSym[], int& turn, int& winCount)
{
	cout << "Dimension: ";
	cin >> dim;
	cout << "Win Count: ";
	cin >> winCount;

	cout << "Enter player's name: ";
	cin >> pName[0];
    cout << "Enter player's symbol: ";
    cin >> pSym[0];
    // pName[1] = (const char [30])"Computer";
    pSym[1] = (pSym[0] == 'X' || pSym[0] == 'x') ? 'O' : 'X';
	
	for (int ri = 0; ri < dim; ri++)
	{
		for (int ci = 0; ci < dim; ci++)
		{
			Board[ri][ci] = '-';
		}
	}
	turn = rand() % 2;
}
void printBoard(char Board[][CAPACITY], int  dim)
{
	system("clear");   
	for (int ri = 0; ri < dim; ri++)
	{
		for (int ci = 0; ci < dim; ci++)
		{
			cout << Board[ri][ci] << "   ";
		}
		cout << endl;
	}
}
void userInput(int& ri, int& ci, char pName[], char pSym)
{
	cout << pName << "'s Turn to place '" << pSym << " ' (ri, ci): " ;
	cin >> ri;
	cin >> ci;
	ri--;
	ci--;
}
bool validInput(int ri, int ci, const char Board[][CAPACITY], int dim)
{
	return ((ri >= 0 && ci >= 0) && (ri <= dim && ci <= dim) && Board[ri][ci] == '-');
}
void updateBoard(char Board[][CAPACITY], int  dim, int ri, int ci, char pSym)
{
	Board[ri][ci] = pSym;
}
bool horizontalCheck(char Board[][CAPACITY], int dim, int winCount, char pSym, int ri, int ci)
{
	if (ci + winCount - 1 >= dim)
		return false;
	for (int i = 0; i < winCount; i++)
	{
		if (Board[ri][ci + i] != pSym)
			return false;
	}
	return true;
}
bool verticalCheck(char Board[][CAPACITY], int dim, int winCount, char pSym, int ri, int ci)
{
	if (ri + winCount - 1 >= dim)
		return false;
	for (int i = 0; i < winCount; i++)
	{
		if (Board[ri + i][ci] != pSym)
			return false;
	}
	return true;
}
bool rightDiagonalCheck(char Board[][CAPACITY], int dim, int winCount, char pSym, int ri, int ci)
{
	if (ri + winCount - 1 >= dim)
		return false;
	for (int i = 0; i < winCount; i++)
	{
		if (Board[ri + i][ci + i] != pSym)
			return false;
	}
	return true;
}
bool leftDiagonalCheck(char Board[][CAPACITY], int dim, int winCount, char pSym, int ri, int ci)
{
	if (ci - (winCount - 1) < 0)
		return false;
	for (int i = 0; i < winCount; i++)
	{
		if (Board[ri + i][ci - i] != pSym)
			return false;
	}
	return true;

}
bool isWinHere(char Board[][CAPACITY], int  dim, int winCount, char pSym, int ri, int ci)
{
	bool horizontal = horizontalCheck(Board, dim, winCount, pSym, ri, ci);
	bool vertical = verticalCheck(Board, dim, winCount, pSym, ri, ci);
	bool leftDiagonal = leftDiagonalCheck(Board, dim, winCount, pSym, ri, ci);
	bool rightDiagnal = rightDiagonalCheck(Board, dim, winCount, pSym, ri, ci);
	return (horizontal || vertical || leftDiagonal || rightDiagnal);
}
bool isWin(char Board[][CAPACITY], int  dim, int winCount, char pSym)
{
	for (int ri = 0; ri < dim; ri++)
    {
        for (int ci = 0; ci < dim; ci++)
        {
            if (isWinHere(Board, dim, winCount, pSym, ri, ci))
                return true;
        }
    }

    return false;
}
bool isDraw(char Board[][CAPACITY], int dim)
{
	for (int ri = 0; ri < dim; ri++)
	{
		for (int ci = 0; ci < dim; ci++)
		{
			if (Board[ri][ci] == '-')
				return false;
		}
	}
	return true;
}
void turnChange(int& turn)
{
	turn = (turn + 1) % 2;
}

void HvsC(const char Board[][CAPACITY], int& ri, int& ci, int dim, char pSym, int winCount, char CS, char HS)
{
    // creating an array for a new board
    char T[CAPACITY][CAPACITY];
    // copying the symbols from the board 'Board' to board 'T'
    for (int r = 0; r < dim; r++)
    {
        for (int c = 0; c < dim; c++)
        {
            T[r][c] = Board[r][c];
        }
    }

	for (int WC = winCount; WC > 1; WC--) {
        // Iterate over all positions in the board
        for (int r = 0; r < dim; r++)
        {
            for (int c = 0; c < dim; c++)
            {
                // If the position (r, c) is valid
                if (validInput(r, c, T, dim))
                {
                    // Place computer's symbol
                    T[r][c] = CS;
                    // If the computer wins
                    if (isWinHere(T, dim, WC, pSym, r, c))
                    {
                        // Remove computer's symbol from the board
                        T[r][c] = '-';
                        // Return the computer's move coordinates
                        ri = r;
                        ci = c;
                        return;
                    }
                    else
                    {
                        // Remove computer's symbol from the board
                        T[r][c] = '-';
                    }
                }
            }
        }

        // Iterate over all positions in the board
        for (int r = 0; r < dim; r++)
        {
            for (int c = 0; c < dim; c++)
            {
                // If the position (r, c) is valid
                if (validInput(r, c, T, dim))
                {
                    // Place human's symbol
                    T[r][c] = HS;
                    // If the human wins
                    if (isWinHere(T, dim, WC, pSym, r, c))
                    {
                        // Remove human's symbol from the board
                        T[r][c] = '-';
                        // Return the human's move coordinates
                        ri = r;
                        ci = c;
                        return;
                    }
                    else
                    {
                        // Remove human's symbol from the board
                        T[r][c] = '-';
                    }
                }
            }
        }
    }

    do {
        ri = rand() % dim;
        ci = rand() % dim;
    } while (!validInput(ri, ci, Board, dim));
}

int main()
{
    cout <<"\n\n\t\t\tThe Game of Gomoku\n\n";
    cout <<"\n\n\t\t\t    Let's begin!\n\n"<<endl;
	srand(time(0));
	char choice;
	char Board[CAPACITY][CAPACITY];
	char pName[2][30] = {"Human", "Computer"}; 
				// "Human" will be replaced by the name of the player in init function
	char pSym[2];
    int turn, ri, ci, dim, winCount;
	bool gameOver = false;
	int winner = -1;

    cout <<"Initializing..."<<endl << endl;
	init(Board, dim, pName, pSym, turn, winCount);
	do
	{
		printBoard(Board, dim);
        if (turn == HUMAN)
        {
    		do
    		{
    			userInput(ri, ci, pName[turn], pSym[turn]);
    			if (!validInput(ri, ci, Board, dim))
    			{
    				cout << "Invalid Input" << endl;
    
    			}
    		} while (!validInput(ri, ci, Board, dim));
		}
		else
	    {
			cout << "Computer's turn..." << endl;
			sleep(3);
			HvsC(Board, ri, ci, dim, winCount, pSym[turn], pSym[COMPUTER], pSym[HUMAN]);
	    }
		
		updateBoard(Board, dim, ri, ci, pSym[turn]);
		printBoard(Board, dim);
		
		gameOver = isWin(Board, dim, winCount, pSym[turn]);
		if (gameOver)
			winner = turn;
		if (!isDraw(Board, dim))
			gameOver = true;
		if (!gameOver)
			turnChange(turn);
	} 
	while (!gameOver);
	cout << endl;
	if (winner == -1)
		cout << "Game Draw!" << endl;
	else
	{
		cout << pName[turn] << " has won!" << endl;
	}
    
	return 0;
}
Complete implementation of the human vs. computer Gomoku game