# 五子棋AI程式碼
## 簡介
這段 C++ 程式碼是用來實現 五子棋（Gomoku） 遊戲，其中一方玩家用 'O' 代表，另一方 AI 用 'X' 代表。程式使用了像是 Minimax 算法、Alpha-Beta 剪枝、執行緒分工等技術來提升 AI 的決策效率。
## 程式結構概覽
1.Minimax 演算法：
* AI 使用 Minimax 演算法來評估可能的步驟，通過遞歸模擬 AI 和玩家的移動。

* AI 嘗試最大化自己的得分，同時最小化玩家贏得比賽的機會。

2.評分函數：

* evaluateSinglePosition 函數用來評估某一位置的得分，根據連續的棋子數量和開放式的可能性（即是否可以與相鄰的空位連接）來進行計算。

* 根據不同的情況（例如連成一行五子、準備四子或三子等）給予不同的啟發式評分。

3.Alpha-Beta 剪枝：

* 為了提升效率，程式使用 Alpha-Beta 剪枝，這樣可以減少需要遍歷的搜尋樹節點數量，只保留對結果有可能影響的分支。

4.多執行緒：

* 程式使用多執行緒技術，將可能的移動評估分為多個任務並行處理，這樣可以加速 AI 做決策的速度。

5.棋盤表示：

* 棋盤使用一個 2D 字元陣列表示，並且為了在 Minimax 搜尋過程中並行計算，維護多個棋盤副本來評估不同的狀態。
## Code

#include<bits/stdc++.h>
using namespace std;
#define mkp make_pair
typedef pair<int,int> Position;
 
constexpr int SIZE = 15;
constexpr char EMPTY = '.';
constexpr char PLAYER = 'O';
constexpr char AI = 'X';
typedef long long ll;
 
template<typename T>
using V = vector<T>;
int dx[8] = {1,-1,1,-1,0,0,-1,1};
int dy[8] = {0,0,1,-1,1,-1,1,-1};
 
const int threadCount = 8;
 
struct Game {
    V<V<char>> board;
    V<V<V<char>>> boardCopy;
    int turnCount;
 
    ll callCount;
    clock_t startTime;
 
    int minX, maxX;
    int minY, maxY;
    int playerValue(char c) {
        return (c == PLAYER ? 2 : -1);
    }
 
    ll evaluateSinglePosition(int x, int y, int id) {
        auto &brd = (id == -1 ? board : boardCopy[id]);
        assert(brd[x][y] != EMPTY);
        auto isAdjacentEmpty = [&](int x, int y) {
            return isWithinBoard(x, y) && brd[x][y] == EMPTY;
        };
 
        ll sum = 0;
        ll K[5] = {(ll)1e7, (ll)1e5, (ll)1e3, 10, 1};
        ll factor = playerValue(brd[x][y]);
 
        for(int dir = 0; dir < 8; dir += 2) {
            int cnt1 = countConsecutiveStones(brd[x][y], dir, x, y, id);
            int cnt2 = countConsecutiveStones(brd[x][y], dir + 1, x, y, id);
            int islive1 = isAdjacentEmpty(x + (cnt1 + 1) * dx[dir], y + (cnt1 + 1) * dy[dir]);
            int islive2 = isAdjacentEmpty(x + (cnt2 + 1) * dx[dir + 1], y + (cnt2 + 1) * dy[dir + 1]);
            int total = cnt1 + cnt2 + 1;
            
            if(total == 5) sum += K[0]; 
 
            if(total == 4 && islive1 && islive2)
                sum += K[1];
            else if(total == 4 && (islive1 || islive2))
                sum += K[2];
 
            if(total == 3 && islive1 && islive2) 
                sum += K[2];
            else if(total == 3 && (islive1 || islive2))
                sum += K[3];
 
            if(total == 2 && islive1 && islive2)
                sum += K[3];
            else if(total == 2 && (islive1 || islive2))
                sum += K[4];
 
            if(total == 1 && islive1 && islive2)
                sum += K[4];
        }
        return sum * factor;
    }
 
    ll evaluateBoard() {
        ll sum = 0;
        for(int x = 0; x < SIZE; ++x)
            for(int y = 0; y < SIZE; ++y) {
                if(board[x][y] == EMPTY) continue;
                sum += evaluateSinglePosition(x, y, -1);
            }
        return sum;
    }
 
    void placeStone(char player, int x, int y, int id) {
        assert(isValidMove(x, y, id));
        boardCopy[id][x][y] = player;
    };
    void removeStone(int x, int y, int id) {
        boardCopy[id][x][y] = EMPTY;
    }
    // 1 player, 0 AI
    ll minimaxSearch(char player, int depth, ll val, int id, ll alpha=-1e18, ll beta=1e18) {
        callCount++;
        if(depth == 0) {
            return val;
        }
        if(player == PLAYER) {
            for(int x = minX; x <= maxX; ++x) {
                for(int y = minY; y <= maxY; ++y) {
                    if(boardCopy[id][x][y] != EMPTY) continue;
                    placeStone(player, x, y, id);
                    alpha = max(alpha, minimaxSearch(AI, depth - 1, val + evaluateSinglePosition(x, y, id), id, alpha, beta));
                    removeStone(x, y, id);
                    if(alpha >= beta) break;
                }
                if(alpha >= beta) break;
            }
            return alpha;
        }
        if(player == AI) {
            for(int x = minX; x <= maxX; ++x) {
                for(int y = minY; y <= maxY; ++y) {
                    if(boardCopy[id][x][y] != EMPTY) continue;
                    placeStone(player, x, y, id);
                    beta = min(beta, minimaxSearch(PLAYER, depth - 1, val + evaluateSinglePosition(x, y, id), id, alpha, beta));
                    removeStone(x, y, id);
                    if(alpha >= beta) break;
                }
                if(alpha >= beta) break;
            }
            return beta;
        }
        return -1;
    }
 
    int countConsecutiveStones(char player, int dir, int x, int y, int id) {
        auto& brd = (id == -1 ? board : boardCopy[id]);
        int nx = x + dx[dir];   
        int ny = y + dy[dir];
        int cnt = 0;
        while(isWithinBoard(nx, ny) && brd[nx][ny] == player) {
            ++cnt;
            nx += dx[dir];
            ny += dy[dir];
        }
        return cnt;
    }
 
    bool isWithinBoard(int x, int y) {
        return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
    }
    bool isWinningMove(char player, int x, int y) {
        auto _countConsecutive = [&](int dir, int x, int y) {
            return countConsecutiveStones(player, dir, x, y, -1);
        };
        for(int dir = 0; dir < 8; dir += 2) {
            if(_countConsecutive(dir, x, y) + _countConsecutive(dir + 1, x, y) + 1 >= 5) return true;
        }
        return false;
    }
    bool isValidMove(int x, int y) {
        return board[x][y] == EMPTY;
    }
    bool isValidMove(int x, int y, int id) {
        return boardCopy[id][x][y] == EMPTY;
    }
    int processMove(char player, int x, int y) {
        if(!isValidMove(x, y)) { return -1; }
        board[x][y] = player;
        if(isWinningMove(player, x, y)) return 2;
        return 1;
    }
 
    void printBoard() {
        for(int x = 0; x <= SIZE; ++x)
            cout << setw(3) << x;
        cout << '\n';
 
        for(int y = SIZE - 1; y >= 0; --y) {
            cout << setw(3) << y + 1;
            for(int x = 0; x < SIZE; ++x)
                cout << setw(3) << board[x][y];
            cout << '\n';
        }
        cout << '\n';
    }
 
    int playRound() {
        turnCount++;
        printBoard();
        char player = (turnCount % 2 ? PLAYER : AI);
 
        int x, y;
        auto input = [&]() {
            cout << "Player " << turnCount % 2  << ' ' << '\n';
            cout << "Put at (x,y): ";
            cin >> x >> y;
            --x, --y;
        };
 
        input();
        int res = processMove(player, x, y);
        while(res == -1) {
            cout << "Invalid move\n";
            input();
            res = processMove(player, x, y);
        }
        if(res == 2)  {
            cout << "Player " << turnCount % 2 << " wins!\n";
            return 0;
        }
 
        turnCount++;
        ll originalValue = evaluateBoard();
        callCount = 0;
        startTime = clock();
 
        minX = minY = 1e9;
        maxX = maxY = -1e9;
        auto updateBoardBounds = [&]() {
            for(int x = 0; x < SIZE; ++x) {
                for(int y = 0; y < SIZE; ++y) {
                    if(board[x][y] == EMPTY) continue;
                    minX = min(minX, x);
                    minY = min(minY, y);
                    maxX = max(maxX, x);
                    maxY = max(maxY, y);
                }
            }
            maxX = min(SIZE - 1, maxX + 3);
            minX = max(0, minX - 3);
            minY = max(0, minY - 3);
            maxY = min(SIZE - 1, maxY + 3);
        };
        updateBoardBounds();
 
        for(auto &i : boardCopy)
            i = board;
 
        vector<Position> validMoves;
        auto identifyValidMoves = [&]() {
            for(int x = minX; x <= maxX; ++x) {
                for(int y = minY; y <= maxY; ++y) {
                    if(board[x][y] != EMPTY) continue;
                    validMoves.push_back(mkp(x, y));
                }
            }
        };
 
        identifyValidMoves();
 
        vector<vector<Position>> dividedTasks(threadCount);
        auto divideTasks = [&]() {
            int taskSize = (validMoves.size() + threadCount - 1) / threadCount;
            for(int i = 0; i < threadCount; ++i) {
                dividedTasks[i] = 
                    vector<Position>(validMoves.begin() + i * taskSize, 
                                     validMoves.begin() + min((i + 1) * taskSize, (int)validMoves.size()));
            }
        };
        divideTasks();
 
        vector<array<ll, 3>> results;
        auto evaluateMoveOptions = [&](int id) {
            ll minValue = 1e18;
            int bestX, bestY;
            for(auto &[x, y] : dividedTasks[id]) {
                placeStone(AI, x, y, id);
                ll val = minimaxSearch(PLAYER, 3, originalValue + evaluateSinglePosition(x, y, id), id);
                if(val < minValue) {
                    minValue = val;
                    bestX = x;
                    bestY = y;
                }
                removeStone(x, y, id);
            }
            results.push_back(array<ll, 3>{minValue, bestX, bestY});
        };
 
        vector<thread> threads;
        for(int i = 0; i < threadCount; ++i) {
            threads.push_back(thread(evaluateMoveOptions, i));
        }
 
        for(auto &th : threads) {
            th.join();
        }
        
        auto findBestMove = [&]() {
            ll minValue = 1e18;
            int bestX, bestY;
            for(auto &[val, x, y] : results) {
                if(val < minValue) {
                    minValue = val;
                    bestX = x;
                    bestY = y;
                }        
            }
            return mkp(bestX, bestY);
        };
 
        auto [bestX, bestY] = findBestMove();
        system("cls");
        cout << "Call Count: " << callCount << '\n';
        cout << "Time Used: " << (1.0L * clock() - startTime) / threadCount / CLOCKS_PER_SEC << '\n';
        
        res = processMove(AI, bestX, bestY);
        if(res == 2) {
            cout << "Player " << turnCount % 2 << " wins!\n";
            return 0;
        }
 
        return 1;
    }
 
    Game() {
        board.assign(SIZE, V<char>(SIZE, EMPTY));
        boardCopy.assign(threadCount, V<V<char>>());
        turnCount = 0;
    }    
};
 
int main() {
    Game game;
 
    while(game.playRound()) {};
    game.printBoard();
}