五子棋棋力提升计划(2) 深度搜索

Ray

在课堂上我们的五子棋程序有最基本的棋型判断，但是并不具有“前瞻性”。我们可以利用Minimax算法来解决这一问题。该算法基于当前状态推测对我方最有利而对方最不利的落子点位，同时假设对方会在对对方最有利而对我方最不利的点位落子。α-β剪枝搜索是Minimax算法的一个优化。
下面是实现上述逻辑的伪代码：

# Minimax算法框架：
# - 最大化己方收益，最小化对方收益
# - 通过深度搜索模拟未来几步的可能走法
# - alpha表示己方保证的最低分，beta表示对方保证的最高分
# - 当alpha >= beta时，可以剪枝停止搜索该分支
def recursive_search(board,turn,depth,a,b):
    if depth<=0: 
        return 静态评估棋盘的价值
    生成有价值的下一招候选集合(取决于你怎么判断有价值，可以将所有空白点位设为下一招，也可以将有邻居的空白点位设为下一招，或者别的方法也行)
    for 下一招 in 下一招候选集合:
        取出下一招的x,y
        board[y][x]=turn #假设这一步是己方下，注意此处的己方可能是我方，也可能是对方，会交替更换
        score=-self.recursive_search(board,对方的turn(交替落子方),depth-1,-b,-a) #深度搜索，score由静态评估棋盘的价值一层层传递上来
        board[y][x]=0 #深度搜索后重置
        if score>a:
            a=score #a是此前最好的评分，但是现在被更新了
            认为(x,y)是局部最优解
            if a>=b:
                break
        更新当前最优解为(x,y)
    return a

在实现这一算法后，棋力将有很大提升。

Ray

如果可以判断双三、三四、双四等棋型，同时加以4层搜索，即可做杀。6层的做杀很隐蔽。楼主第一届参赛程序的搜索只有6层

脆脆大奶酪

大佬a和b这两个参数的含义有点没看懂啊，什么叫“保证”的最高/最低分？

Ray

脆脆大奶酪 发表于 8-1-2025 03:51
大佬a和b这两个参数的含义有点没看懂啊，什么叫“保证”的最高/最低分？

a是我觉得我是 b是不要你觉得 要我觉得

脆脆大奶酪

Ray 发表于 8-3-2025 13:12
a是我觉得我是 b是不要你觉得 要我觉得

连夜研读链接里的文章终于理解了。
以防有同学和我一样第一眼没看懂，先从minimax搜索讲讲我的理解：
minimax的原理是始终从我方视角来评估当前局面分数，同时假设对手总能做出最优（即对我方最不利而对对方最有利）的决策。
那么很自然地，我方应该选择分数最高的，而对方则会选择分数最低的（注意此处的“分数”均指对我方而言局面的好坏，因此对对方最有利的选择就是分数最低的）
简单做了张决策树示意图：

假设我方执白，红色的×表示下一步可能走的位置（其实理论上棋盘上每个空位都能走，这里为了简化人为挑了几个看起来好一点的走法）
箭头指向的是走出某一步后的局面，此时轮到另一方走棋，红色的×同样表示再下一步可能走的位置
这里我假定是搜索三层，所以第三层箭头指向的叶子节点就直接用局面的静态分值代替了（具体分值自己瞎脑补的，仅作示意）
可以看到图中每层的节点分为两类：轮到我方走棋和轮到对方走棋。轮到我方走棋的节点分值即为子节点分值的最大值，反之则为最小值，这样从下往上推出了根节点得分。
这里要注意这个根节点的得分并非是真正的“最优解”，而是在最坏情况下（即对手始终做出了最合适的选择）我方能获得的最高分，换言之，这个得分只是个“下限”，在走完这步后完全有可能因为对手的应对失误而最终获得更高的局面分数。
理解不一定完全准确，希望可以给同样的初学者提供一些思路

Ray

脆脆大奶酪 发表于 8-11-2025 02:34
连夜研读链接里的文章终于理解了。
以防有同学和我一样第一眼没看懂，先从minimax搜索讲讲我的理解：
min ...

主播图文并茂的理解非常深刻！需要注意的是，这个算法有一个短视的局限性，即假设对方认为的好与坏和你认为的好与坏相同。这一点在连续活三/连续冲四时是成立的（不堵就死了），但是在前期评估棋盘时就会显得乏力。因此，我们可以考虑使用特判来区分“前期” “中期”和“杀招”，进行分治。这一想法是比较自然的

Ray

ab搜索就是在minimax搜索的基础上，记录了到此为止我方可以保证最好的评分&到此为止对方可以得到的最好的评分，并将相对差/没有吸引力的分支剪除。