10

编辑：这个问题不重复What is the best algorithm for the game 2048?

  • 这个问题问'赢得比赛的最佳方式是什么？
  • 这个问题问“我们如何才能计算出游戏的复杂性？”

它们是完全不同的问题。我对走向“胜利”状态需要哪些步骤不感兴趣——我有兴趣找出是否可以计算可能步骤的总数。

我一直在阅读这个关于游戏2048的问题，其中讨论了创建能够在游戏中表现良好的算法的策略。

接受的答案提到：

游戏是一个离散状态空间，完美信息，象棋一样的回合制游戏

这让我想到了它的复杂性。对于像国际象棋这样的确定性游戏，它可能（理论上）计算出所有可能导致获胜状态的移动并向后工作，选择持续导致该结果的最佳移动。我知道这会导致大量可能的移动（在宇宙中的原子数量范围内）.. 但是 2048 或多或少复杂？

伪代码：

for the current arrangement of tiles
    - work out the possible moves
    - work out what the board will look like if the program adds a 2 to the board
    - work out what the board will look like if the program adds a 4 to the board
    - move on to working out the possible moves for the new state

在这一点上，我想我会在这里等待一段时间运行......

所以我的问题是——我将如何开始编写这个算法——哪种策略最适合计算游戏的复杂性？

我在 2048 和国际象棋之间看到的最大区别是，程序可以在添加新棋子时在 2 到 4 之间随机选择——这似乎增加了大量额外的可能移动。

最终，我希望程序输出一个数字，显示游戏中可能的排列数量。这可能吗？！

4

1 回答 1

8

让我们确定有多少种可能的电路板配置。

每个瓦片可以是空的，也可以包含 2、4、8、...、512 或 1024 瓦片。

这是每个图块 12 种可能性。有 16 个图块，所以我们得到 16 12 = 2 48种可能的棋盘状态——这很可能包括一些无法到达的棋盘状态。

假设我们可以将所有这些都存储在内存中，我们可以从所有棋盘状态向后工作，这些棋盘状态将在下一步生成 2048 个图块，做大量工作以将可到达棋盘状态相互关联，这应该给我们一个概率每个州的最佳移动。

要将所有位存储在内存中，假设我们需要每个图块 4 位，即每个板状态 64 位 = 8 个字节。

2 48 个电路板状态将需要 8*2 48 = 2251799813685248 字节 = 2048 TB（更不用说为跟踪最佳电路板而增加的开销）。这有点超出了当今台式计算机所具备的能力，尽管可以巧妙地限制在任何给定时间所需的板数量，以便减少到适合 3 TB 硬盘驱动器的东西，或者也许即使在 RAM 中。

作为参考，国际象棋有 2 155 个可能位置的上限。

如果我们从一开始就实际计算每一个可能的移动（以类似广度优先搜索的方式），我们会得到一个巨大的数字。

这不是确切的数字，而是对上限的粗略估计。

让我们做一些假设：（这绝对不总是正确的，但是，为了简单起见）

  • 总有 15 个空方格

  • 你总是有 4 个动作（左、右、上、下）

  • 一旦棋盘上所有棋子的总和达到 2048，将需要最少的组合数才能获得单个 2048（因此，如果放置 2 使总和为 2048，则组合将为 2 -> 4 -> 8 - > 16 -> ... -> 2048，即走 10 步）

  • 总是会放置 2，而不是 4 - 算法不会假设这一点，但是，为了计算上限，我们会这样做。

  • 我们不会考虑在此过程中可能会产生重复板的事实。

要达到 2048，需要放置 2048 / 2 = 1024 个图块。

您从 2 个随机放置的瓷砖开始，然后反复移动并放置另一个瓷砖，所以大约有 1022 个“回合”（一个回合由移动和放置一个瓷砖组成）直到我们得到 2048 的总和，然后有再转 10 圈得到 2048 格。

在每一轮中，我们有 4 个移动，并且可以在 15 个位置之一（30 种可能性）中放置两个瓷砖之一，所以这是 4*30 = 120 种可能性。

这总共会给我们 120 1032个可能的状态。

如果我们假设总是放置一个 4，我们得到 120 519个状态。

计算确切的数字可能会涉及到所有这些状态，这实际上是不可行的。

于 2014-03-19T15:21:32.630 回答