Hex-Game [Project]

Hex Game: A C++ Masterpiece

Hex is an exciting strategy game where the objective is to form a continuous path connecting opposite sides of a hexagonal board. The code not only allows you to play the game but also pits you against a Monte Carlo-based AI designed to give you a tough challenge.

The code is available on GitHub: Hex-Game.

---

Understanding the Game of Hex

The Rules

1. Players: The game is played between two players, Black and White. Black always starts first.
2. Objective: Connect the opposite sides of the board corresponding to your color. Black aims to connect the left and right sides, while White connects the top and bottom.
3. Moves: Players take turns placing pieces on the hexagonal grid. Once a piece is placed, it cannot be moved or removed.
4. Winning: A player wins by forming an unbroken chain of their pieces that connects their target sides.

Hexagonal Board

The board is represented using a 2D grid. Each cell can be one of three states:

• +: Empty
• B: Occupied by Black
• W: Occupied by White

Input Format

Players enter their moves in the format y x (row and column), making it simple and intuitive.

---

Features of the Code

AI Implementation

The AI leverages Monte Carlo simulations to determine the best move. It evaluates the probability of winning by simulating 1000 random games for each possible move, picking the one with the highest success rate.

Key Concepts

1. Breadth-First Search (BFS): Used to determine if a player has formed a continuous path connecting their target sides.
2. Monte Carlo Simulation: Randomized simulations help the AI predict which moves are most likely to lead to a win.
3. Dynamic Board: The board size is adjustable, making the game versatile and challenging for different levels of players.

---

How the Code Works

Board Representation

The Board class handles all operations related to the board:

• Initialization: Creates a grid filled with + to represent empty cells.
• Placement: Ensures valid moves by checking if the selected cell is within bounds and unoccupied.
• Win Detection: Uses BFS to check if a player has connected their target sides.
• Printing: Displays the board in a visually appealing format with proper indentation for the hexagonal structure.

AI Mechanics

The AI class performs the following:

1. Generate Moves: Finds all empty spots on the board.
2. Simulate Games: For each empty spot, the AI simulates multiple games to estimate the win probability.
3. Select Best Move: Chooses the move with the highest success rate from the simulations.

Game Flow

The Game class orchestrates the gameplay:

1. Setup: Prompts the user for board size and player choice.
2. Turn Handling: Alternates turns between the player and the AI.
3. Victory Check: Determines if a move results in a win for either side.

---

Installation and Running the Code

Clone the Repository

git clone https://github.com/paulrounak/Hex-Game.git

Compile and Run

Navigate to the project directory, compile the code, and run it:

cd Hex-Game
g++ main.cpp -o hex_game
./hex_game

Instructions to Play

1. Enter the board size (e.g., 11 for an 11x11 grid).
2. Choose your side (b for Black or w for White). Black always starts first.
3. Place your pieces by entering coordinates in the format y x.
4. Watch the AI make its moves and try to outsmart it!

---

Code Highlights

BFS for Win Detection

The BFS algorithm checks if a player has formed a path between their target sides:

void Board::bfsSearch(vector<pair<int, int>> &start, vector<bool> &condition)
{
    if (!start.empty())
    {
        int x = start[0].first;
        int y = start[0].second;
        char side = board[x][y];

        vector<vector<bool>> visited(size, vector<bool>(size));
        queue<pair<int, int>> trace;

        for (const auto &itr : start)
        {
            trace.push(itr);
            visited[itr.first][itr.second] = true;
        }

        while (!trace.empty())
        {
            auto top = trace.front();
            borders(top.first, top.second, condition, side);
            trace.pop();

            for (auto &i : direction)
            {
                int xCursor = top.first + i[0];
                int yCursor = top.second + i[1];
                if (inBoard(xCursor, yCursor) && board[xCursor][yCursor] == side && !visited[xCursor][yCursor])
                {
                    visited[xCursor][yCursor] = true;
                    trace.emplace(xCursor, yCursor);
                }
            }
        }
    }
}

Monte Carlo Simulation

This part of the code calculates the best move by simulating 1000 random games:

pair<int, int> AI::next(Board &board, Player p)
{
    auto blank = board.getEmpty();
    double bestMove = 0;
    pair<int, int> move = blank[0];

    for (auto &i : blank)
    {
        int x = i.first;
        int y = i.second;
        board.place(x, y, p);

        double moveValue = getWins(board, p);
        if (moveValue > bestMove)
        {
            move = i;
            bestMove = moveValue;
        }

        board.badMove(x, y);
    }
    return move;
}

---

Closing Thoughts

This implementation of Hex in C++ is both a fun and intellectually stimulating project. It showcases how algorithms like BFS and Monte Carlo simulations can be applied to create an AI opponent capable of strategic gameplay. Whether you’re a developer looking to learn or a player seeking a challenge, this game is sure to captivate you.

Why not give it a try and see if you can outsmart the AI?