五子棋 ai 剪枝c++

剪枝是五子棋 AI 中非常重要的一部分，能够有效地减少搜索空间，提高搜索效率。下面是一个简单的五子棋 AI 剪枝的 C++ 代码示例：

#include <bits/stdc++.h>
using namespace std;

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

int a[MAXN][MAXN];
int val[2][MAXN][MAXN];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int max_value(int depth, int alpha, int beta);
int min_value(int depth, int alpha, int beta);

int get_score(int x, int y, int player) {
    int score = 0;
    for (int i = 0; i < 8; i++) {
        int cnt = 0, flag1 = 0, flag2 = 0;
        int tx = x, ty = y;
        while (a[tx][ty] == player || a[tx][ty] == 0) {
            if (a[tx][ty] == player) {
                cnt++;
            } else {
                if (!flag1) flag1 = 1;
                else break;
            }
            tx += dx[i], ty += dy[i];
        }
        tx = x - dx[i], ty = y - dy[i];
        while (a[tx][ty] == player || a[tx][ty] == 0) {
            if (a[tx][ty] == player) {
                cnt++;
            } else {
                if (!flag2) flag2 = 1;
                else break;
            }
            tx -= dx[i], ty -= dy[i];
        }
        cnt--;
        if (cnt < 4) continue;
        if (flag1 && flag2) score += val[player - 1][x][y][i][cnt];
        else if (flag1 || flag2) score += val[player - 1][x][y][i][cnt] / 2;
        else score += val[player - 1][x][y][i][cnt] / 4;
    }
    return score;
}

int max_value(int depth, int alpha, int beta) {
    if (depth == 0) return get_score(0, 0, 2) - get_score(0, 0, 1);
    int val = -INF;
    vector<pair<int, int>> v;
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 10; j++) {
            if (a[i][j] == 0) {
                a[i][j] = 2;
                int tmp = min_value(depth - 1, alpha, beta);
                a[i][j] = 0;
                if (tmp > val) {
                    val = tmp;
                    v.clear();
                    v.push_back(make_pair(i, j));
                } else if (tmp == val) {
                    v.push_back(make_pair(i, j));
                }
                if (val >= beta) {
                    return val;
                }
                alpha = max(alpha, val);
            }
        }
    }
    return val;
}

int min_value(int depth, int alpha, int beta) {
    if (depth == 0) return get_score(0, 0, 2) - get_score(0, 0, 1);
    int val = INF;
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 10; j++) {
            if (a[i][j] == 0) {
                a[i][j] = 1;
                val = min(val, max_value(depth - 1, alpha, beta));
                a[i][j] = 0;
                if (val <= alpha) {
                    return val;
                }
                beta = min(beta, val);
            }
        }
    }
    return val;
}

int main() {
    // 初始化权值表
    memset(val, 0, sizeof(val));
    for (int k = 0; k < 2; k++) {
        for (int i = 1; i <= 10; i++) {
            for (int j = 1; j <= 10; j++) {
                for (int d = 0; d < 8; d++) {
                    for (int len = 5; len >= 1; len--) {
                        int cnt1 = 0, cnt2 = 0;
                        int tx = i, ty = j;
                        while (a[tx][ty] == k + 1 || a[tx][ty] == 0) {
                            if (a[tx][ty] == k + 1) {
                                cnt1++;
                            } else if (a[tx][ty] == 0) {
                                cnt2++;
                            }
                            tx += dx[d], ty += dy[d];
                        }
                        tx = i - dx[d], ty = j - dy[d];
                        while (a[tx][ty] == k + 1 || a[tx][ty] == 0) {
                            if (a[tx][ty] == k + 1) {
                                cnt1++;
                            } else if (a[tx][ty] == 0) {
                                cnt2++;
                            }
                            tx -= dx[d], ty -= dy[d];
                        }
                        cnt1--;
                        if (cnt1 + cnt2 < len) continue;
                        if (cnt1 >= len) {
                            val[k][i][j][d][len]++;
                        } else {
                            val[k][i][j][d][cnt1] += cnt2;
                        }
                    }
                }
            }
        }
    }
    // 进行搜索
    int depth = 2;
    vector<pair<int, int>> v;
    max_value(depth, -INF, INF);
    for (auto p : v) {
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}

在这个例子中，我们使用了 Alpha-Beta 剪枝算法来提高搜索效率，同时还使用了启发式搜索来评估棋盘局面的得分。具体来说，我们使用了一个预先计算好的权值表，根据当前棋盘局面和棋手来计算出对应的得分，然后在搜索时选择能够得到最高得分的走法。