algorithm - 生成具有等同于洗牌的随机性的可获胜单人纸牌游戏

Question

如果给定:

1. 一个好的洗牌算法(一个好的随机源加上一个洗牌方法不受任何可能导致结果偏差的常见陷阱的影响)
2. 一个魔法函数WINNABLE(D)，它获取洗牌后的牌组，如果牌组 D 可以通过某些播放顺序获胜，则返回 True，如果不可避免地导致一个失败的位置。

然后可以通过使用 (1) 生成大量起始套牌然后使用 (2) 将它们过滤到可获胜的组来生成一组“分布良好”的可获胜单人纸牌交易。当您试图避免微妙的选择偏差影响您的结果时，这种随机生成可能性并从中挑选的方法始终是一个很好的起点。

问题是 (2) 很难(可能是 NP-hard，具体取决于游戏)，甚至它的近似值在计算上也很昂贵(如果你在 iPad 上，比如说)。然而，更便宜的算法，例如从获胜位置开始并进行随机“未移动”以将游戏逆转回起点，可能会偏向于很难量化或避免的特定牌组洗牌。

在生成像这样的可获胜游戏方面是否有任何有趣的算法或研究？

Answer 1

由于单人纸牌游戏差异很大，因此很难在这种普遍性水平上进行推理。为了集中我们的想法，让我们举一个特殊的例子:四十大盗。这是一款双包游戏，从空地开始，逐步建立王牌；一个空的废物堆；以及十张预先发牌的牌堆，每堆四张牌。废物堆和布局堆的顶牌暴露。在每一步中，您可以:

1. 将暴露的卡片移到其在基础中的合法位置，不用担心后退;
2. 将一张暴露的牌移到布局中的一堆上，只有在以下情况下才合法在同一花色中向下 build ；
3. 将一张暴露的卡片移到一个空的布局槽中；
4. 从存货区发一张牌到垃圾区顶部。

初学者按照规定的顺序演奏这些选项。 (我玩的实现实际上有一个提示按钮，可以建议相应的行动。)我估计只有不到十分之一的交易可以通过该策略赢得，而实际赢得的交易比例约为三分之一。

现在，如果您通过随机未着手生成可赢的交易，则存在难以量化的偏差；我不同意这一点。不过，我认为，在碰巧可以赢得的交易中，交易往往比平均水平更难，几乎没有交易可以通过初学者的策略赢得。

但是，您可以有意地使未着手非随机。如果您以与初学者策略相反的顺序选择取消移动，您将获得初学者策略起作用的交易:例如如果只是作为最后的手段，您不从基础转移到废物，那么只要有可能，从废物转移到基础总是正确的。