Visual Basic 2010国际象棋递归搜索中List复用的性能优化技术问询

Hey，针对你在VB2010象棋程序递归搜索里遇到的List复用和性能问题，我有几个实用的解决方案，尤其是能让你复用同一个List同时保证递归前后状态一致的方法，一起来看看：

核心思路：记录List初始长度，递归后截断恢复 #

频繁新建List会导致大量内存分配和GC压力，这正是你程序变慢的原因。我们可以复用同一个List，在递归调用前记录List的当前长度，递归返回后把List截断回初始长度，这样就模拟了ByVal按值传递的效果，同时完全避免了新建List的开销。

具体代码修改步骤 #

首先，你需要调整calculate_all_moves的实现：原来的代码是返回新List并赋值给all_moves_list，这会丢失原List的引用，无法后续恢复。请把它改成直接往传入的List中添加当前局面的合法走法（比如改成Sub过程，或者让函数在现有List基础上追加元素）。

然后修改你的递归过程：

Sub recurvive_search(ByVal the_board(,) As theboardclass, ByVal depth As Integer, ByRef depth_count() As Integer, ByVal whosgo__ As Integer, ByRef all_moves_list As List(Of A_Move))
    If depth = 3 Then
        depth_count(4) += 1
    Else
        ' 1. 记录递归前List的初始长度
        Dim initialListCount As Integer = all_moves_list.Count
        
        ' 2. 计算当前局面的所有走法，直接添加到现有List中（已调整calculate_all_moves逻辑）
        calculate_all_moves(the_board, whosgo__, all_moves_list)
        
        ' 3. 遍历本次新增的走法（从初始长度到List末尾）
        For i As Integer = initialListCount To all_moves_list.Count - 1
            Dim currentMove As A_Move = all_moves_list(i)
            If Not IsNothing(currentMove.sym_of_moving_piece) Then
                depth_count(depth) += 1
                ' 执行走法，更新棋盘
                the_board = Me.change_board(the_board, the_board(currentMove.From_x, currentMove.From_Y).getsym, the_board(currentMove.From_x, currentMove.From_Y).getteam, currentMove.New_x, currentMove.New_Y, currentMove.From_x, currentMove.From_Y)
                ' 切换玩家
                whosgo__ = switchgoes(whosgo__)
                
                ' 递归调用，传递同一个List
                recurvive_search(the_board, depth + 1, depth_count, whosgo__, all_moves_list)
                
                ' 恢复玩家和棋盘状态
                whosgo__ = switchgoes(whosgo__)
                the_board = Me.undo_move(the_board, currentMove)
            End If
        Next
        
        ' 4. 递归返回后，移除本次添加的所有走法，恢复List到初始状态
        all_moves_list.RemoveRange(initialListCount, all_moves_list.Count - initialListCount)
    End If
End Sub

为什么这个方法高效？ #

• 避免内存分配：全程复用同一个List，没有频繁的New List操作，大幅减少GC的工作负担。
• 批量操作更高效：RemoveRange是批量移除元素的方法，比逐个移除元素的性能高很多，对List的整体性能影响极小。

额外性能优化建议 #

1. 预先设置List的Capacity：在初始化all_moves_list时，设置一个足够大的初始容量（比如国际象棋单次最多可能有200+种合法走法），避免List在添加元素时频繁扩容：

   Dim all_moves_list As New List(Of A_Move)(256) ' 设置初始容量为256
   

2. 检查calculate_all_moves的效率：确保这个方法本身没有冗余计算，比如重复遍历棋盘、不必要的对象创建等，这也是递归性能的关键环节。

内容的提问来源于stack exchange，提问作者lewis peck