背景
我从一个完整的CodeForces竞赛中碰到this problem。该问题称为“关于树木的简单问题”。
树的大小最多为250个节点。
竞赛中没有人解决了这个问题。
题
什么是解决此问题的有效算法?
我会对C++(可在CodeForces网站上进行测试)或Javascript(可让我向游戏中添加AI)的答案感兴趣。
我尝试过的
通过选择阈值水平T并回答问题“馅饼女孩可以保证得到小于或等于T的值吗?”,可以简化问题。
如果我们可以解决这个较简单的问题,则可以使用二等分法找到T的最小值,这将是原始问题的答案。
简化的问题等同于带有 Blob 的游戏:
规则:
我对该游戏here进行了演示,以尝试了解该策略。
到目前为止,感觉像:
我认为简单的minimax前瞻(例如,具有较高的大 Blob 得分的评估函数)在实践中可能会很好地工作,但是感觉应该有一个甚至更好的算法可以最佳地解决这一问题。
任何人还有其他想法吗?
更新
我在演示中添加了一个minimax解算器(单击FindBest使计算机移动)。
对于深度达4的深度(以毫秒为单位)求解,此方法工作正常,但是对于深度5及以上的深度进行思考需要花费一些时间。通过保存以前看过的职位的结果,我可以稍微加快一点,但是即使有了这一改进,它仍然有巨大的状态空间可供探索。
最佳答案
这不是一个完整的答案,但是评论太长了。
我们将玩家称为“蓝色”和“红色”。对于给定的树,在最佳游戏中获胜的人有四种可能性:永远是蓝色(B
),永远是红色(R
),永远是第一人(1
),永远是第二人(2
)。我们称子树为偶数,即使它的叶子数为奇数(即移动的偶数),也称其为奇数,如果它的叶子数为偶数(即移动的奇数)。
以下是缺少几个案例的案例分析。它对于优化minimax搜索仍然可能有用。
子树在质量上存在三种不同的可能性,即偶数-偶数,偶数-奇数(对称地,奇数-偶数)和奇数-奇数。让我们对称地假设Blue首先出现。
偶甚至
蓝色首先播放,最后播放。如果存在B
或1
子树,那么Blue将通过在其中赢得胜利。蓝色随后选择的子树呼应了红色的戏剧。如果两个子树都是R
或2
,那么红色将通过呼应蓝色子树的选择而获胜。
Missing cases: none
奇数-奇数
蓝色首先播放,最后播放。如果存在
B
或2
子树,则Blue会通过在另一个中玩并在Red出现时停在那里而获胜。如果两个子树都是R
,则Red通过强制两个子树中的交替来获胜。Missing cases: R1 (= 1R), 11
偶数-奇数
蓝色首先播放,红色最后播放。如果奇数子树是
R
或2
,那么只要Blue这样做,Red就会通过停在偶数子树中而获胜。如果偶数子树是B
或2
,而奇数子树是B
或1
,那么蓝色将通过在奇数子树中播放并响应红色在同一子树中的后续游戏来获胜。Missing cases: RB, R1, 1B, 11
评论
有问题的情况似乎是一种情况,其中一个玩家强制另一个玩家在子树中连续移动两次。从比赛参数看来,在任意移动之后有足够的时间确定赢/输,但是案例分析变得很长,比我现在耐心的要更长。