用c++实现alphabeta剪枝算法的五子棋

以下是一个简单的C++代码实现Alpha-Beta剪枝算法的五子棋。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 15;
const int INF = 0x3f3f3f3f;

// 棋盘
int board[MAXN][MAXN];

// 玩家
int player;

// 判断胜负
bool isWin(int x, int y, int color)
{
    // 横向
    int cnt = 0;
    for (int i = y - 4; i <= y + 4; i++)
    {
        if (i < 0 || i >= MAXN) continue;
        if (board[x][i] == color) cnt++;
        else cnt = 0;
        if (cnt == 5) return true;
    }
    // 纵向
    cnt = 0;
    for (int i = x - 4; i <= x + 4; i++)
    {
        if (i < 0 || i >= MAXN) continue;
        if (board[i][y] == color) cnt++;
        else cnt = 0;
        if (cnt == 5) return true;
    }
    // 左上到右下
    cnt = 0;
    for (int i = -4; i <= 4; i++)
    {
        int rx = x + i, ry = y + i;
        if (rx < 0 || rx >= MAXN || ry < 0 || ry >= MAXN) continue;
        if (board[rx][ry] == color) cnt++;
        else cnt = 0;
        if (cnt == 5) return true;
    }
    // 右上到左下
    cnt = 0;
    for (int i = -4; i <= 4; i++)
    {
        int rx = x + i, ry = y - i;
        if (rx < 0 || rx >= MAXN || ry < 0 || ry >= MAXN) continue;
        if (board[rx][ry] == color) cnt++;
        else cnt = 0;
        if (cnt == 5) return true;
    }
    return false;
}

// Alpha-Beta剪枝
int AlphaBeta(int depth, int alpha, int beta)
{
    if (depth == 0) return 0;
    if (isWin(0, 0, player)) return -INF;
    if (isWin(0, 0, -player)) return INF;

    // 最优解
    int maxScore = -INF;

    // 所有可下的点
    vector<pair<int, int>> points;
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            if (board[i][j] == 0)
                points.push_back(make_pair(i, j));

    // 按估价函数排序
    sort(points.begin(), points.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        int ax = a.first, ay = a.second;
        int bx = b.first, by = b.second;
        int as = 0, bs = 0;
        for (int i = ax - 2; i <= ax + 2; i++)
        {
            if (i < 0 || i >= MAXN) continue;
            for (int j = ay - 2; j <= ay + 2; j++)
            {
                if (j < 0 || j >= MAXN) continue;
                if (board[i][j] == player) as++;
                else if (board[i][j] == -player) as -= 2;
            }
        }
        for (int i = bx - 2; i <= bx + 2; i++)
        {
            if (i < 0 || i >= MAXN) continue;
            for (int j = by - 2; j <= by + 2; j++)
            {
                if (j < 0 || j >= MAXN) continue;
                if (board[i][j] == player) bs++;
                else if (board[i][j] == -player) bs -= 2;
            }
        }
        return as > bs;
    });

    for (const auto& p : points)
    {
        int x = p.first, y = p.second;
        board[x][y] = player;
        int score = -AlphaBeta(depth - 1, -beta, -alpha);
        board[x][y] = 0;
        maxScore = max(maxScore, score);
        alpha = max(alpha, score);
        if (alpha >= beta) return maxScore;
    }

    return maxScore;
}

// AI下棋
void AIPlay()
{
    int maxScore = -INF;
    int px = -1, py = -1;

    // 所有可下的点
    vector<pair<int, int>> points;
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            if (board[i][j] == 0)
                points.push_back(make_pair(i, j));

    for (const auto& p : points)
    {
        int x = p.first, y = p.second;
        board[x][y] = player;
        int score = -AlphaBeta(2, -INF, INF);
        board[x][y] = 0;
        if (score > maxScore)
        {
            maxScore = score;
            px = x;
            py = y;
        }
    }

    board[px][py] = player;
    cout << "AI下棋: " << px << ", " << py << endl;
}

// 人类下棋
void HumanPlay()
{
    int x, y;
    cout << "请输入下棋位置(x, y): ";
    cin >> x >> y;
    while (board[x][y] != 0)
    {
        cout << "该位置已被占用，请重新输入(x, y): ";
        cin >> x >> y;
    }
    board[x][y] = -player;
}

// 初始化
void Init()
{
    // 初始化棋盘
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            board[i][j] = 0;

    // 随机玩家
    player = (rand() % 2 == 0) ? 1 : -1;
}

// 显示棋盘
void ShowBoard()
{
    cout << "  ";
    for (int i = 0; i < MAXN; i++)
        cout << i << " ";
    cout << endl;
    for (int i = 0; i < MAXN; i++)
    {
        cout << i << " ";
        for (int j = 0; j < MAXN; j++)
        {
            if (board[i][j] == 0) cout << "+ ";
            else if (board[i][j] == 1) cout << "O ";
            else cout << "X ";
        }
        cout << endl;
    }
}

int main()
{
    // 初始化
    Init();

    // 游戏循环
    while (true)
    {
        ShowBoard();
        if (isWin(0, 0, player))
        {
            cout << "AI胜利!" << endl;
            break;
        }
        if (isWin(0, 0, -player))
        {
            cout << "人类胜利!" << endl;
            break;
        }
        if (player == 1) AIPlay();
        else HumanPlay();
        player = -player;
    }

    return 0;
}

该代码使用Alpha-Beta剪枝算法实现了一个简单的五子棋AI。其中，isWin()函数用于判断胜负，AlphaBeta()函数用于计算最优解，AIPlay()函数用于让AI下棋，HumanPlay()函数用于让人类下棋，Init()函数用于初始化游戏，ShowBoard()函数用于显示棋盘。在游戏循环中，如果有一方胜利，就退出循环。