用c++实现alphabeta算法五子棋

下面是使用C++实现Alpha-Beta剪枝算法的五子棋程序：

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

const int MAXN = 15; // 棋盘大小
const int INF = 0x3f3f3f3f; // 无穷大
const int DX[4] = {1, 0, 1, -1}; // x方向偏移量
const int DY[4] = {0, 1, 1, 1}; // y方向偏移量

int chess[MAXN][MAXN]; // 棋盘
int depth; // 搜索深度
int best_x, best_y; // 最优解坐标

// 判断(x, y)是否越界
bool valid(int x, int y)
{
    return (x >= 0 && y >= 0 && x < MAXN && y < MAXN);
}

// 判断是否有五子连珠
bool win(int x, int y, int color)
{
    for (int i = 0; i < 4; i++)
    {
        int cnt = 1;
        for (int j = 1; j < 5; j++)
        {
            int nx = x + j * DX[i], ny = y + j * DY[i];
            if (valid(nx, ny) && chess[nx][ny] == color) cnt++;
            else break;
        }
        for (int j = 1; j < 5; j++)
        {
            int nx = x - j * DX[i], ny = y - j * DY[i];
            if (valid(nx, ny) && chess[nx][ny] == color) cnt++;
            else break;
        }
        if (cnt >= 5) return true;
    }
    return false;
}

// 估价函数
int evaluate(int color)
{
    int res = 0;
    for (int x = 0; x < MAXN; x++)
    {
        for (int y = 0; y < MAXN; y++)
        {
            if (chess[x][y] == color) res++;
            else if (chess[x][y] == 3 - color) res--;
        }
    }
    return res;
}

// Alpha-Beta剪枝搜索
int alphabeta(int depth, int alpha, int beta, int color)
{
    if (depth == 0) return evaluate(color);
    int max_val = -INF;
    for (int x = 0; x < MAXN; x++)
    {
        for (int y = 0; y < MAXN; y++)
        {
            if (chess[x][y] != 0) continue;
            chess[x][y] = color;
            if (win(x, y, color))
            {
                chess[x][y] = 0;
                return INF; // 电脑赢了
            }
            int val = -alphabeta(depth - 1, -beta, -alpha, 3 - color);
            chess[x][y] = 0;
            if (val > max_val)
            {
                max_val = val;
                if (depth == ::depth) // 更新最优解坐标
                {
                    best_x = x;
                    best_y = y;
                }
                if (val > alpha) alpha = val;
                if (alpha >= beta) return alpha;
            }
        }
    }
    return max_val;
}

int main()
{
    memset(chess, 0, sizeof(chess));
    int color = 1; // 电脑执黑先手
    cout << "请输入搜索深度：";
    cin >> depth;
    while (true)
    {
        if (color == 1) // 电脑下棋
        {
            alphabeta(depth, -INF, INF, color);
            cout << "电脑下棋(" << best_x << ", " << best_y << ")" << endl;
            chess[best_x][best_y] = color;
            if (win(best_x, best_y, color))
            {
                cout << "电脑赢了！" << endl;
                break;
            }
            color = 3 - color;
        }
        else // 玩家下棋
        {
            int x, y;
            cout << "请输入落子坐标(x, y)：";
            cin >> x >> y;
            if (valid(x, y) && chess[x][y] == 0)
            {
                chess[x][y] = color;
                if (win(x, y, color))
                {
                    cout << "玩家赢了！" << endl;
                    break;
                }
                color = 3 - color;
            }
            else
            {
                cout << "无效坐标，请重新输入！" << endl;
            }
        }
    }
    return 0;
}

程序中，使用Alpha-Beta剪枝算法实现了电脑下棋的决策过程，evaluate函数用来评估当前棋盘状态，win函数用来判断是否有五子连珠。在主函数中，先输入搜索深度，然后交替进行电脑和玩家的下棋，直到有一方获胜。