parallel-processingtic-tac-toeminimax

Tic tac toe implementation using Minimax tree in Parallel


I am trying to find a source code for implementing Tic tac toe game using Minimax tree in parallel either in Java using Fork/Join or in C/C++ using pthread. I could find a lot of serial version of the game but not a parallel version.

I saw this question: How many threads are okay to use for tic-tac-toe using minimax? by @good_evening

but I couldn't find any source code. Any help is appreciated.


Solution

  • Here is a C++ implementation:

    Main Game File (main.cpp):

    // File: main.cpp
    
    #include <iostream>
    #include <vector>
    #include <thread>
    #include <limits>
    #include "Board.h"
    #include "Minimax.h"
    
    int main() {
        Board board;
        char currentPlayer = Board::PLAYER_O; // Human plays 'O', AI plays 'X'
    
        while (true) {
            board.printBoard();
    
            if (board.checkWin(Board::PLAYER_X)) {
                std::cout << "AI wins!" << std::endl;
                break;
            } else if (board.checkWin(Board::PLAYER_O)) {
                std::cout << "You win!" << std::endl;
                break;
            } else if (board.isFull()) {
                std::cout << "It's a draw!" << std::endl;
                break;
            }
    
            if (currentPlayer == Board::PLAYER_O) {
                // Human's turn
                int x, y;
                std::cout << "Enter your move (row[0-2] and column[0-2]): ";
                std::cin >> x >> y;
                if (x < 0 || x > 2 || y < 0 || y > 2 || !board.makeMove(x, y, Board::PLAYER_O)) {
                    std::cout << "Invalid move! Try again." << std::endl;
                    continue;
                }
                currentPlayer = Board::PLAYER_X;
            } else {
                // AI's turn
                std::cout << "AI is thinking..." << std::endl;
    
                std::vector<std::pair<int, int>> moves = board.getAvailableMoves();
                int bestScore = std::numeric_limits<int>::min();
                std::pair<int, int> bestMove;
                std::vector<std::thread> threads;
                std::vector<int> scores(moves.size());
    
                for (size_t i = 0; i < moves.size(); ++i) {
                    threads.emplace_back([&, i]() {
                        Board newBoard = board;
                        newBoard.makeMove(moves[i].first, moves[i].second, Board::PLAYER_X);
                        scores[i] = minimax(newBoard, false, Board::PLAYER_X, Board::PLAYER_O);
                    });
                }
    
                for (auto& thread : threads) {
                    thread.join();
                }
    
                for (size_t i = 0; i < scores.size(); ++i) {
                    if (scores[i] > bestScore) {
                        bestScore = scores[i];
                        bestMove = moves[i];
                    }
                }
    
                board.makeMove(bestMove.first, bestMove.second, Board::PLAYER_X);
                std::cout << "AI played: " << bestMove.first << "," << bestMove.second << std::endl;
    
                currentPlayer = Board::PLAYER_O;
            }
        }
    
        board.printBoard();
        return 0;
    }
    
    

    Now let's develop board.h

    // File: Board.h
    
    #ifndef BOARD_H
    #define BOARD_H
    
    #include <vector>
    
    class Board {
    public:
        Board();
        void printBoard();
        bool makeMove(int x, int y, char player);
        void undoMove(int x, int y);
        bool checkWin(char player);
        bool isFull();
        std::vector<std::pair<int, int>> getAvailableMoves();
        char getCell(int x, int y);
    
        static const char EMPTY = ' ';
        static const char PLAYER_X = 'X'; // AI
        static const char PLAYER_O = 'O'; // Human
    
    private:
        char board[3][3];
    };
    
    #endif
    
    

    and board.cpp would be

    // File: Board.cpp
    
    #include "Board.h"
    #include <iostream>
    
    Board::Board() {
        // Initialize the board with empty cells
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                board[i][j] = EMPTY;
    }
    
    void Board::printBoard() {
        std::cout << "Board:" << std::endl;
        for (int i = 0; i < 3; ++i) {
            for(int j=0; j<3; ++j) {
                std::cout << board[i][j];
                if(j < 2) std::cout << "|";
            }
            std::cout << std::endl;
            if(i < 2) std::cout << "-----" << std::endl;
        }
    }
    
    bool Board::makeMove(int x, int y, char player) {
        if (board[x][y] == EMPTY) {
            board[x][y] = player;
            return true;
        }
        return false;
    }
    
    void Board::undoMove(int x, int y) {
        board[x][y] = EMPTY;
    }
    
    bool Board::checkWin(char player) {
        // Check rows, columns, and diagonals
        for(int i=0; i<3; ++i) {
            if(board[i][0]==player && board[i][1]==player && board[i][2]==player)
                return true;
            if(board[0][i]==player && board[1][i]==player && board[2][i]==player)
                return true;
        }
        if(board[0][0]==player && board[1][1]==player && board[2][2]==player)
            return true;
        if(board[0][2]==player && board[1][1]==player && board[2][0]==player)
            return true;
        return false;
    }
    
    bool Board::isFull() {
        for(int i=0;i<3;++i)
            for(int j=0;j<3;++j)
                if(board[i][j]==EMPTY)
                    return false;
        return true;
    }
    
    std::vector<std::pair<int, int>> Board::getAvailableMoves() {
        std::vector<std::pair<int, int>> moves;
        for(int i=0;i<3;++i)
            for(int j=0;j<3;++j)
                if(board[i][j]==EMPTY)
                    moves.emplace_back(i, j);
        return moves;
    }
    
    char Board::getCell(int x, int y) {
        return board[x][y];
    }
    
    

    Minimax Algorithm (Minimax.h and Minimax.cpp):

    Minimax.h:

    // File: Minimax.h
    
    #ifndef MINIMAX_H
    #define MINIMAX_H
    
    #include "Board.h"
    
    int minimax(Board& board, bool isMaximizing, char aiPlayer, char humanPlayer);
    
    #endif
    

    Minimax.cpp:

    // File: Minimax.cpp
    
    #include "Minimax.h"
    #include <vector>
    #include <limits>
    
    int minimax(Board& board, bool isMaximizing, char aiPlayer, char humanPlayer) {
        if (board.checkWin(aiPlayer))
            return 10;
        else if (board.checkWin(humanPlayer))
            return -10;
        else if (board.isFull())
            return 0;
    
        std::vector<std::pair<int, int>> moves = board.getAvailableMoves();
        int bestScore = isMaximizing ? std::numeric_limits<int>::min() : std::numeric_limits<int>::max();
    
        for (auto move : moves) {
            board.makeMove(move.first, move.second, isMaximizing ? aiPlayer : humanPlayer);
            int score = minimax(board, !isMaximizing, aiPlayer, humanPlayer);
            board.undoMove(move.first, move.second);
    
            if (isMaximizing)
                bestScore = std::max(bestScore, score);
            else
                bestScore = std::min(bestScore, score);
        }
    
        return bestScore;
    }
    
    

    compiling command:

    g++ -std=c++11 main.cpp Board.cpp Minimax.cpp -o TicTacToe -pthread
    

    The -pthread flag is necessary for threading support.

    Run the Game:

    ./TicTacToe