一组计算机科学家第一次解决了近一个世纪以来困扰着研究人员的博弈情况。该情况叫做上校棋局,自其1921年创立之初就被用来分析竞选的潜在可能结果,以及其他类似的两党相争问题。直到现在,由于缺乏明确方法,仍然只有有限应用。
由UMD领导的团队研发出一种算法,能够解决上校棋局。其中一个显著的成就在于,算法能够给政治策略家、企业领导和其他决策制定角色提供一种强大的新工具来做出明确选择。
「我们的算法能够为任何竞争者针对某个机会计算最好的资源投资策略,」Mohammad Hajiaghayi说道,他是UMD计算机科学的Jack and Rita G.Minker助理教授,并领导该项目。「只要我们给定某个场景的有效数据,我们就能用我们的算法为不同领导者找出最佳策略,比如政治候选人、体育团队、公司和军事领导。」
上校棋局要求两个竞争者互相竞争,并要求每个人做出如何部署有限资源的困难决策。在最简单的情况下,每个竞争者会分配有限数量的资源,或者军队前往战场,玩家必须在毫不知悉对手策略的情况完成这一切。当玩家在某个战场上分配的军队比对手多时就赢得了该战场,谁赢得的战场多谁就获胜。
这个游戏能够延展到真实世界的情况,比如美国的总统大选。在这种情况下,每个竞选人就是一个玩家,资源就是竞选团、时间和资金,这就是那些部队,而每一个州就是一个战场。游戏也能应用于常见的消费产品竞争,比如在苹果iPhone和谷歌安卓手机产品之间正在进行的竞争。
「从总统竞选到市场决策,对注意力和忠诚度的竞争是日常生活的一部分。然而个体对这种竞争的回应行为尚未完全理解。」Hajiaghayi说道,他在UMIACS举办了一次联合会议。「我们发现这样的策略行为是能够计算处理的。给定一种竞争描述,我们就能够决定哪种策略能够为给定选手最大化结果。」
虽然上校棋局的规则非常简单,玩家能够采用的潜在策略几乎是无限的,这取决于战场的数量和每个玩家的总资源。Hajiaghayi和他的同事们研究出来的策略并不是让某位玩家打败另一玩家,而是一种平衡,这种平衡让玩家们都能够根据对手的策略最优部署自己的策略。
大量不同的可能策略就是找到该游戏计算式解决方法的关键障碍。Hajiaghayi和他的团队通过限制可能策略的总数量,只给出屈指可数的代表性答案解决了这个问题。
「我们发现玩家的策略可以精确地由少量的可能性策略代表,」Hajiaghayi说道:「这是个更通用的方法,但作为概念验证非常有效。很多其他方法都试图解决精确场景的布洛特对策,但我们是第一个用一种更通用的方法并解决了这个理论的。」 这一方法使团队能够发明出一个概括性算法,该算法能够用于特定场景,比如2016总统大选。
「我们的算法只能用于两个竞争者,所以需要等到大选时来进行试验,」Saeed Seddighin说道,他是UMD计算机科学的硕士生,并将团队研究成果展现在AAAI大会上。「如果我们知道给定的一个州在之前大选上的投票跟每一个竞选者在该州进行投资的资源情况的关系,那么我们就能利用今年大选的投资数据来预测每个竞选者是否在全国范围内采用的最佳策略。」
这项研究,「从决斗到战场:计算上校棋局和其他游戏的平衡,」AmirMahdi Ahmadinejad,Sina Dehghani,MohammadTaghi Hajiaghayi,Brendan Lucier,Hamid Mahini及Saeed Seddighin所著,于2016年2月15日发表于AAAI大会。 该研究由国家科学基金会和DARPA以及谷歌赞助。本文内容不代表以上各组织观念。
本文选自sciencedaily,来源马里兰大学。机器之心编译出品,编译:柒少