近期,必赢线路检测3003no1杨溢博士等在国际学术期刊《IEEE Transactions on Games》上发表了题为《The Complexities of Random-Turn Hex, Square, and Triangle Games》的论文。该期刊收录的论文主要涵盖了游戏理论(博弈论)、玩家对战策略及其算法实现,该期刊的影响因子是1.851。
该团队发表的论文研究了六连棋、正方形连棋和三角形连棋在随机轮走(每步都抛硬币决定谁下)的规则下,用计算机求解最佳落子点所需的时间复杂度。他们提出了基于连通性状态压缩的动态规划算法,证明了在边长为n的棋盘里,无论玩家给定哪个局面,该算法都可以在O(n9·cn)的时间内保证找到该局面下的最佳落子点,里面的常数c由棋盘的形状决定。他们计算得出了六连棋、正方形连棋和三角形连棋的c值都是一元多项式方程的根,它们保留3位小数后的结果分别是2.618、2.746和3.645。(撰稿:陈力、杨溢;审核:张海)