求解奇偶博弈最优策略的新型算法

"这篇论文探讨了奇偶博弈的最优策略求解算法，主要关注的是在简单随机对策中的问题。文章作者提出了一种新的算法来确定这类游戏中的最优期望收益，尤其是在有概率移动和可达性胜利条件的情况下。简单随机游戏是由A.Condon深入研究的类型，它们在理论计算机科学中扮演着重要角色，例如在奇偶博弈和μ演算模型检查等领域都有应用。求解简单随机游戏是否能在多项式时间内完成是一个未解的开放性问题。 该算法的核心是将搜索空间看作超立方体[0，1]^N的子集，并将其划分为凸子区域，利用线性优化技术在每个子区域中进行操作。通过在这些子区域间逐步转换，算法能够找到包含最佳支付的区域。尽管子区域总数呈指数增长，但在实际运行中，算法通常只需访问少量子区域就能找到解决方案。这种方法可能为理解和解决简单随机游戏以及其他等价问题的算法复杂性提供新的视角。 文章首先介绍了在计算机科学中，图形游戏作为一种工具常用于表示和解决各种问题，如系统验证、控制合成和交替自动机理论。关键挑战在于找到有效算法来决定哪一方有获胜策略。奇偶博弈，一种具有特定获胜条件的博弈，长期以来一直是研究的重点，尤其是关于是否能以多项式时间复杂度解决此类游戏的问题。 这篇论文提出了一个用于求解奇偶博弈最优策略的新算法，该算法具有实际应用潜力，并可能为解决相关复杂问题提供新的思路。通过深入研究和实验，有望进一步理解这类游戏的算法复杂性和效率边界。"