异步主变量分裂：优化博弈树并行搜索算法

博弈树并行搜索算法是一种在信息学竞赛中广泛应用的策略，特别是在解决复杂的博弈论问题时，它通过树形结构组织搜索过程。传统的PVSplit（主变量分裂）算法在ALPHA2BETA剪枝并行搜索中表现出色，因为它采用主变量搜索策略，能够有效地减少串行搜索中不必要的子树搜索，从而提高搜索效率，相较于其他方法如窗口分裂和直接树分解，它的加速比更高。 然而，PVSplit算法存在同步开销问题，主要体现在处理机间的通信延迟和处理机速度差异导致的等待时间。这些开销在处理机数量众多、性能各异的工作站机群中尤为显著，因为机群的异构性和高通信延时限制了其并行性能。针对这些问题，文章提出了异步主变量分裂算法（Asynchronous PVSplit, AsynPVSplit）。 异步PVSplit算法的关键在于打破原有的层次结构限制，允许主处理机在分配任务时不仅局限于同一层次，而是将已完成搜索的处理机分配给尚未完成的上一层子树，这样就消除了处理机之间的同步等待，使得调度更加灵活。算法的异步特性使其能够适应工作站机群的特性，更好地利用资源，减少处理机等待时间，提升并行度，从而提高并行搜索的效率。 作者李之棠和陈华民，分别作为工学博士和硕士研究生，他们的研究方向分别为计算机体系与结构和高性能计算，以及计算机网络，这表明他们在该领域有着深厚的理论基础和实践经验，他们的研究成果对于理解和优化博弈树并行搜索算法在实际应用中的性能具有重要意义。通过理论分析和实验验证，异步PVSplit算法有望在解决大型博弈问题时提供更高效的解决方案。