五子棋ai软件排名-五子棋人工智能算法

博弈人工智能卡通人物，方法之一是：博弈树最大最小α-β剪枝搜索。

你是不是觉得这个名字牛逼，但是经过我的详细解读，你马上就会发现，也不过如此。

如何实现一个可以智能下五子棋的AI？ 自然的思考方式是让计算机尝试每一步的可能性，看看哪一步效果最好。 事实上，它是一种搜索方法，搜索所有接下来的可能性并选择最好的。 这就是博弈树搜索。

博弈树搜索

什么是博弈树搜索？ 博弈意味着互相战斗以采取最优策略。 例如，玩双陆棋时，你的下一步就是我的下一步。 这是一场相互的游戏。 假设棋盘的大小是10*10，即可以下100个点。 那么第一步可能是100，假设投注在A点，那么第二步除了A点还剩下99。有点可能。 假设投注在B点，那么第二步就有可能是除了B点之外的其余99个点。假设投注在C点…

你看，我上面的假设可以复制100次，而基于其中一个点，第二步可以复制99次，以此类推，形成一个树状结构：

好了，问题来了，有这么多的可能性，哪一步最好呢？ 这是下一步，极小极大搜索。

最大和最小搜索

对于一个棋局来说，判断它对我来说是优势还是劣势，是否可以用一个相对确定的数值来评价呢？ 答案是肯定的。 对于双陆棋，会计算当前的棋局并累积分数。 例如，如果 4 个棋子相连五子棋ai软件排名，则给出高分，因为你可以在下一步中获胜。 如果 3 个相连，则给出相对较低的分数五子棋ai软件排名，因为你可能不会获胜。 它会阻挡你，但分数会比只有 2 块连接在一起时得分更高。 这样的话，就会有如下的棋谱评级表：

# 棋型的评估分数
shape_score = [(50, (0, 1, 1, 0, 0)),
               (50, (0, 0, 1, 1, 0)),
               (200, (1, 1, 0, 1, 0)),
               (500, (0, 0, 1, 1, 1)),
               (500, (1, 1, 1, 0, 0)),
               (5000, (0, 1, 1, 1, 0)),
               (5000, (0, 1, 0, 1, 1, 0)),
               (5000, (0, 1, 1, 0, 1, 0)),
               (5000, (1, 1, 1, 0, 1)),
               (5000, (1, 1, 0, 1, 1)),
               (5000, (1, 0, 1, 1, 1)),
               (5000, (1, 1, 1, 1, 0)),
               (5000, (0, 1, 1, 1, 1)),
               (50000, (0, 1, 1, 1, 1, 0)),
               (99999999, (1, 1, 1, 1, 1))]

本文的示例是使用python代码实现的。 以上是我列出的一些常见的双陆棋形状。 1表示这里有棋子落下，0表示这里是空地，可以在这里进行下一步。 前面是对应的分数。

那么评价位置对应的分数就是统计所有匹配的棋谱的分数并相加。 这个分数的统计量称为评价函数，这个评价函数的质量非常重要。 以下算法都是固定的，适用于任何赌博游戏，但评估函数差异很大。

# 评估函数
def evaluation(is_ai):
    total_score = 0
    if is_ai:
        my_list = list1
        enemy_list = list2
    else:
        my_list = list2
        enemy_list = list1
    # 算自己的得分
    score_all_arr = []  # 得分形状的位置 用于计算如果有相交 得分翻倍
    my_score = 0
    for pt in my_list:
        m = pt[0]
        n = pt[1]
        my_score += cal_score(m, n, 0, 1, enemy_list, my_list, score_all_arr)
        my_score += cal_score(m, n, 1, 0, enemy_list, my_list, score_all_arr)
        my_score += cal_score(m, n, 1, 1, enemy_list, my_list, score_all_arr)
        my_score += cal_score(m, n, -1, 1, enemy_list, my_list, score_all_arr)
    #  算敌人的得分， 并减去
    score_all_arr_enemy = []
    enemy_score = 0
    for pt in enemy_list:
        m = pt[0]
        n = pt[1]
        enemy_score += cal_score(m, n, 0, 1, my_list, enemy_list, score_all_arr_enemy)
        enemy_score += cal_score(m, n, 1, 0, my_list, enemy_list, score_all_arr_enemy)
        enemy_score += cal_score(m, n, 1, 1, my_list, enemy_list, score_all_arr_enemy)
        enemy_score += cal_score(m, n, -1, 1, my_list, enemy_list, score_all_arr_enemy)
    total_score = my_score - enemy_score*ratio*0.1
    return total_score

AI移动的最佳方式是移动到某个点后计算该情况的得分，然后获得得分最大的点。 这不是最合适的点吗？ 太简单！ 这是最大搜索。

但别忘了，你只是考虑了一步。 搜索深度只有1，你没听说心机鬼老是考虑三步吗？ 也就是说，迈出这一步之后，你必须考虑对方接下来会做什么。 。 如果对方不傻的话，他肯定会到我分数最小的地步。 这个分数是相对于我而言的。 如果我的分数最小，那就是对手的最优策略。 这就是最小值搜索。

如果AI需要考虑3步，则意味着搜索深度为3，即搜索落点，3步后得分最大。 这将使您能够与会读三步国际象棋的老家伙战斗。

关于最大值和最小值的伪代码（注意是伪代码，不是本文例子的python代码）：

这里有递归，相信很容易理解。

int MinMax(int depth) { // 函数的评估都是以白方的角度来评估的
　if (SideToMove() == WHITE) {　// 白方是“最大”者 
　　return Max(depth); 
　} else {　　　　　　　　　　　// 黑方是“最小”者 
　　return Min(depth); 
　} 
} 　 
int Max(int depth) { 
　int best = -INFINITY; 
　if (depth  best) { 
　　　best = val; 
　　} 
　} 
　return best; 
} 　 
int Min(int depth) { 
　int best = INFINITY;　// 注意这里不同于“最大”算法 
　if (depth <= 0) { 
　　return Evaluate(); 
　} 
　GenerateLegalMoves(); 
　while (MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1); 
　　UnmakeMove(); 
　　if (val < best) { 　// 注意这里不同于“最大”算法 
　　　best = val; 
　　} 
　} 
　return best; 
} 

到了这一步，是不是感觉已经结束了呢？ 能和老家伙一决高下吗？ 这是错误的。 它忽略了一个很重要的问题，就是搜索的计算量。 如果你认为电脑是一台机器，CPU是Intel i7，它可以瞬间完成计算。 这种博弈树之所以被称为树，是因为它的分支数量呈指数级增长。 搜索深度3和搜索深度5的计算量相差不只是几倍。 这是指数差异的概念。 所以，虽然五子棋棋盘没有围棋那么大，但按照这种搜索所有可能性的方法来搜索，就会把计算机搞死。

于是聪明人对其进行了优化，这就是alpha-beta剪枝搜索。

α-β剪枝搜索

假设博弈树的搜索情况如下：

α是已知的最大值，β是已知的最小值。 由于我还没有搜索过，所以我不知道它的价值是什么。 为了安全起见，将其初始化为-∞和+∞。

当搜索D时，情况得分为5，（顺便说一句，这样的搜索是深度优先搜索，什么是深度优先搜索，可以百度一下），也就是说，如果你想寻找最大值，只能在(5,+∞)中找到。 同样，如果要寻找最小值，也只会在(-∞, 5)之间。

继续搜索。 当找到G后，F暂时等于6。F是求最大值，所以F不能小于6，B是求最小值。 已知B的最小值是(-∞, 5)，你的F不可能小于6，我为什么要搜索你的F后面的情况？ 这不是浪费时间吗，所以我果断点掉了F分支，不再搜索了。 这就是修剪。

对于另一侧已知的可能极限范围β也是如此。 当搜索是浪费时间时卡通人物，修剪并停止搜索。

这样就减少了很多不必要的搜索步骤，尤其是从一开始就找到最有可能的最大值和最小值，剪枝可以更快地完成。 如何首先尽快找到可能的最大值和最小值，稍后会讨论。 我们先打断一下，最大负值法。

负极大值法

上面的伪代码包括求最大值、最小值和两个函数。 事实上，他们都找到了自己的最大价值。 该各自的最大值就是该值。 他们都站在自己一边寻找最大价值。 对方的最大值在数值前面加负号对我来说就是最小值不是吗？ 虽然有点复杂，但我相信道理很容易理解。 这样做的好处是最大值和最小值写在函数中。 看代码：

# 负值极大算法搜索 alpha + beta剪枝
def negamax(is_ai, depth, alpha, beta):
    # 游戏是否结束 | | 探索的递归深度是否到边界
    if game_win(list1) or game_win(list2) or depth == 0:
        return evaluation(is_ai)
    blank_list = list(set(list_all).difference(set(list3)))
    order(blank_list)   # 搜索顺序排序  提高剪枝效率
    # 遍历每一个候选步
    for next_step in blank_list:
        global search_count
        search_count += 1
        # 如果要评估的位置没有相邻的子， 则不去评估  减少计算
        if not has_neightnor(next_step):
            continue
        if is_ai:
            list1.append(next_step)
        else:
            list2.append(next_step)
        list3.append(next_step)
        value = -negamax(not is_ai, depth - 1, -beta, -alpha)
        if is_ai:
            list1.remove(next_step)
        else:
            list2.remove(next_step)
        list3.remove(next_step)
        if value > alpha:
            print(str(value) + "alpha:" + str(alpha) + "beta:" + str(beta))
            print(list3)
            if depth == DEPTH:
                next_point[0] = next_step[0]
                next_point[1] = next_step[1]
            # alpha + beta剪枝点
            if value >= beta:
                global cut_count
                cut_count += 1
                return beta
            alpha = value
    return alpha

这里的实际代码可能不太容易理解。 上面的伪代码应该更好看，如下：

int negamax(GameState S, int depth, int alpha, int beta) {
    // 游戏是否结束 || 探索的递归深度是否到边界
    if ( gameover(S) || depth == 0 ) {
        return evaluation(S);
    }
    // 遍历每一个候选步
    foreach ( move in candidate list ) {
        S' = makemove(S);
        value = -negamax(S', depth - 1, -beta, -alpha);
        unmakemove(S') 
        if ( value > alpha ) {
            // alpha + beta剪枝点
            if ( value >= beta ) {
                return beta;
            }
            alpha = value;
        }
    }
    return alpha;
}

其他优化

好了，到这里基本上就结束了，但是根据五子棋的特点，还可以添加一些其他的优化，比如搜索的起点。 从上一步的点周围开始搜索，可以尽快找到一个比较大的最大值。 和相对较小的最小值，从而导致更快的修剪。 因为附近的点是最有可能的。 另外，为了减少计算量，我还去掉了各个方向上没有相邻细分的位置，因为这样的位置不太可能是有价值的位置。 当然，这种优化并不严谨，只是为了减少计算量。 。