Chinook是一个玩棋盘游戏跳棋（也称为国际跳棋）的计算机程序。它由阿尔伯塔大学的一个团队开发，由计算机科学家Jonathan Schaeffer领导，旨在与人类跳棋最高水平竞争。1994年，它取得了历史性的里程碑，成为第一个在策略游戏中击败人类世界冠军并赢得世界锦标赛的计算机程序，击败了Marion Tinsley。2007年，Chinook团队宣布该程序已有效解决了跳棋问题，这意味着如果双方都完美发挥，游戏总是以平局告终。
Chinook的开发始于1989年，作为人工智能和博弈论的一个研究项目。该程序结合了搜索算法、评估函数和大量的开局库。它的成功建立在带有alpha-beta剪枝的极小极大搜索原理之上，这种技术使程序每秒能探索数百万个位置。该程序经过数年改进，在评估函数和搜索效率方面取得了显著提升。
世界锦标赛成就
Chinook最著名的成就是在1990年，它在美国国家跳棋锦标赛中获得第二名，从而获得了挑战世界冠军的资格，成为第一个获得人类世界冠军头衔资格的计算机。1992年，Chinook与Marion Tinsley进行了一场比赛，后者是当时的卫冕世界冠军，被广泛认为是有史以来最伟大的跳棋选手。比赛在40局后以平局告终，Tinsley保住了他的头衔。1994年，进行了复赛，但Tinsley因健康原因在六局后退出，Chinook被宣布为获胜者，使其成为第一个在棋盘游戏中持有世界冠军头衔的计算机程序。
在Tinsley退役后，Chinook于1995年对阵Don Lafferty卫冕成功，赢得了比赛。该程序继续参加人类锦标赛，但在1996赛季后最终退出比赛。
解决跳棋问题
2007年，Chinook团队在《科学》杂志上发表了一篇论文，宣布他们已解决了跳棋问题。这一解决方案涉及大规模计算工作，结合了逆向分析和搜索算法，以证明在完美发挥下游戏是平局。团队计算了所有最多10个棋子在棋盘上的位置数据库，这需要大约10^14次计算，并花费了超过18年的连续计算时间（使用分布式计算）。结果表明，从标准起始位置来看，跳棋在理论上是平局，这意味着如果双方都发挥最优，任何一方都无法强制获胜。
跳棋问题的解决是机器学习和游戏AI领域的一个里程碑式成就，因为它是当时解决的最大游戏，搜索空间约为5×10^20个可能位置。它展示了将搜索算法与大规模计算相结合的威力，并为人类在游戏中的专业知识的局限性提供了见解。
技术方法
Chinook的架构基于经典的游戏AI设计。它使用带有alpha-beta剪枝的深度优先搜索来评估位置，并采用了一个复杂的评估函数，考虑物质、机动性和位置优势。该程序还有一个大型开局库，包含数百万个来自专家对局的位置，以及一个通过逆向分析构建的残局数据库。残局数据库对解决过程至关重要，因为它使程序在游戏后期能够完美发挥。
在解决工作中，团队使用了一种称为“证明数搜索”的技术，将搜索引导到最可能是胜或负的位置。他们还使用分布式计算网络来处理残局数据库中的数十亿个位置。最终解决方案证明了跳棋是平局，但团队也表明，如果任一玩家犯错，另一方可以强制获胜。
遗产与影响
Chinook的成功对人工智能和游戏研究领域产生了重大影响。它启发了后续解决其他游戏的努力，如四子棋（1988年解决）以及后来的围棋，后者由AlphaGo等程序攻克。Chinook还为开发解决具有大状态空间的游戏的技术做出了贡献，其方法已应用于其他组合问题。
除了技术贡献外，Chinook还引发了关于人类与机器智能本质的哲学问题。该程序战胜人类世界冠军是后来国际象棋（1997年的深蓝）和围棋（2016年的AlphaGo）成就的先驱。今天，Chinook被铭记为一项开创性努力，展示了计算机掌握复杂策略游戏的潜力。
Chinook项目还促成了Fhourstones基准测试的开发，这是一种用于衡量搜索算法性能的测试。该程序的代码和数据库已供研究使用，其遗产继续影响着游戏AI系统的设计。