背景

我从一个完整的CodeForces竞赛中碰到this problem。该问题称为“关于树木的简单问题”。



树的大小最多为250个节点。

竞赛中没有人解决了这个问题。



什么是解决此问题的有效算法?

我会对C++(可在CodeForces网站上进行测试)或Javascript(可让我向游戏中添加AI)的答案感兴趣。

我尝试过的

通过选择阈值水平T并回答问题“馅饼女孩可以保证得到小于或等于T的值吗?”,可以简化问题。
如果我们可以解决这个较简单的问题,则可以使用二等分法找到T的最小值,这将是原始问题的答案。

简化的问题等同于带有 Blob 的游戏:

规则:

  • 这是一个两人游戏,游戏的目的是将所有 Blob 连接在一起,以制成您唯一的巨型 Blob 。
  • 玩家轮流合并blob。
  • 您可以合并两个相同大小的相邻Blob。如果两个 Blob 中的任何一个是您的颜色,则最终颜色将是您的颜色。

  • 我对该游戏here进行了演示,以尝试了解该策略。

    到目前为止,感觉像:
  • 可以使您的颜色成为大 Blob
  • 通常存在陷阱,其中存在一个子谜题,谁先采取行动,谁就会输掉
  • 采取最后行动的玩家只需要使前两个子谜题之一具有颜色,而另一个玩家则需要使两个子谜题中都有其颜色
  • 通常,可以进行许多等待 Action 的区域不会影响子拼图的最终颜色。

  • 我认为简单的minimax前瞻(例如,具有较高的大 Blob 得分的评估函数)在实践中可能会很好地工作,但是感觉应该有一个甚至更好的算法可以最佳地解决这一问题。

    任何人还有其他想法吗?

    更新

    我在演示中添加了一个minimax解算器(单击FindBest使计算机移动)。
    对于深度达4的深度(以毫秒为单位)求解,此方法工作正常,但是对于深度5及以上的深度进行思考需要花费一些时间。通过保存以前看过的职位的结果,我可以稍微加快一点,但是即使有了这一改进,它仍然有巨大的状态空间可供探索。

    最佳答案

    这不是一个完整的答案,但是评论太长了。

    我们将玩家称为“蓝色”和“红色”。对于给定的树,在最佳游戏中获胜的人有四种可能性:永远是蓝色(B),永远是红色(R),永远是第一人(1),永远是第二人(2)。我们称子树为偶数,即使它的叶子数为奇数(即移动的偶数),也称其为奇数,如果它的叶子数为偶数(即移动的奇数)。

    以下是缺少几个案例的案例分析。它对于优化minimax搜索仍然可能有用。

    子树在质量上存在三种不同的可能性,即偶数-偶数,偶数-奇数(对称地,奇数-偶数)和奇数-奇数。让我们对称地假设Blue首先出现。

    偶甚至

    蓝色首先播放,最后播放。如果存在B1子树,那么Blue将通过在其中赢得胜利。蓝色随后选择的子树呼应了红色的戏剧。如果两个子树都是R2,那么红色将通过呼应蓝色子树的选择而获胜。

    Missing cases: none
    

    奇数-奇数

    蓝色首先播放,最后播放。如果存在B2子树,则Blue会通过在另一个中玩并在Red出现时停在那里而获胜。如果两个子树都是R,则Red通过强制两个子树中的交替来获胜。
    Missing cases: R1 (= 1R), 11
    

    偶数-奇数

    蓝色首先播放,红色最后播放。如果奇数子树是R2,那么只要Blue这样做,Red就会通过停在偶数子树中而获胜。如果偶数子树是B2,而奇数子树是B1,那么蓝色将通过在奇数子树中播放并响应红色在同一子树中的后续游戏来获胜。
    Missing cases: RB, R1, 1B, 11
    

    评论

    有问题的情况似乎是一种情况,其中一个玩家强制另一个玩家在子树中连续移动两次。从比赛参数看来,在任意移动之后有足够的时间确定赢/输,但是案例分析变得很长,比我现在耐心的要更长。

    07-24 09:54
    查看更多