javascript - 在锦标赛中获胜的最佳算法(演示 2 人游戏)

Question

背景

我遇到了 this problem来自已完成的 CodeForces 竞赛。这个问题叫做“关于树的简单问题”。

Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it.

On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left.

Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

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

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

问题

解决这个问题的有效算法是什么？

我对用 C++(可以在 CodeForces 网站上测试)或用 Javascript(允许我在游戏中添加 AI)的答案感兴趣

我尝试过的

问题可以通过选择一个阈值级别 T 并回答“piegirl 能保证得到一个小于或等于 T 的值吗？”这个问题来简化。如果我们能解决这个更简单的问题，那么我们就可以使用二分法找到 T 的最小值，这将是原始问题的答案。

简化后的问题相当于一个有 Blob 的游戏:

规则:

1. 这是一款双人游戏，游戏的目的是将所有的 Blob 拼成一个与你的颜色相同的巨大 Blob 。
2. 玩家轮流组合 blob。
3. 您可以组合两个相邻的大小相同的 Blob 。如果两个 Blob 中的任何一个是你的颜色，那么最终的颜色就是你的颜色。

我做了这个游戏的演示here尝试了解该策略。

目前感觉是这样的:

1. 用你的颜色做大 Blob 很好
2. 经常有陷阱，其中有一个子谜题，谁先动就会输
3. 走最后一步的玩家只需要让最上面的两个子谜题之一有自己的颜色，而另一个玩家需要让两个子谜题都有自己的颜色
4. 通常有一些区域可以进行一些等待 Action ，这些 Action 不会影响子谜题的最终颜色。

我认为一个简单的 minimax 前瞻(例如，使用一个评估函数对大 blob 的得分更高)在实践中可能会很好地工作，但我觉得应该有一个更好的算法来最优地解决这个问题。

有人有任何进一步的想法吗？

更新

我在演示中添加了一个 minimax 求解器(单击 FindBest 让计算机走一步)。这适用于深度达 4，以毫秒解决，但需要很长时间来思考深度 5 及以上。我可以通过保存之前看到的位置的结果来稍微加快这一速度，但即使有了这种改进，它仍然会有一个巨大的状态空间可供探索。

Answer 1

这不是一个完整的答案，但对于评论来说太长了。

让我们称玩家为蓝色和红色。对于给定的树，在最佳游戏下有四种获胜的可能性:总是蓝色(B)，总是红色(R)，总是第一个玩家(1 )，总是第二个玩家 (2)。如果子树的叶子数为奇数(即移动次数为偶数)，我们将子树称为 Even，如果叶子数为偶数(即移动次数为奇数)，则称为 Odd。

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

子树的三种定性不同的可能性是 Even--Even、Even--Odd(对称地，Odd--Even)和 Odd--Odd。让我们对称地假设蓝色先出牌。

连--连

蓝色最先播放，最后播放。如果有一个 B 或 1 子树，那么 Blue 在其中下棋获胜。 Blue 对子树的后续选择与 Red 的操作相呼应。如果两个子树都是 R 或 2，则红色通过呼应蓝色的子树选择获胜。

Missing cases: none

奇--奇

蓝色最先播放，最后播放。如果有一个 B 或 2 子树，那么 Blue 通过在另一个子树中下棋并在 Red 下棋时停在那里而获胜。如果两个子树都是 R，则 Red 通过在两个子树中强制交替来获胜。

Missing cases: R1 (= 1R), 11

偶--奇

蓝色先玩，红色最后玩。如果奇数子树是 R 或 2，那么只要蓝色停止，红色就会通过在偶数子树中停滞而获胜。如果偶数子树是 B 或 2，奇数子树是 B 或 1，则蓝色获胜在奇数子树中播放并响应红色在同一子树中的后续播放。

Missing cases: RB, R1, 1B, 11

评论

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