如何计算游戏2048的复杂度？

Question

编辑：这个问题不是重复什么是游戏2048的最优算法？

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

这让我想到了它的复杂性。对于像国际象棋这样的确定性游戏，它有可能（在理论上）计算出所有导致胜利状态的可能的走法，并向后工作，选择保持导致结果的最佳走法。我知道这导致了大量可能的移动（在宇宙中原子数量范围内的东西）…但2048年是不是比较复杂？

PsudoCode：

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

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

Answer 1

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

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

这是12个可能性每瓷砖。有16个瓦片，因此我们得到16¹²=2⁴⁸可能的板状态--这很可能包括一些不可达的状态。

2⁴⁸板状态则需要8*2⁴⁸=2251799813685248html" target="_blank">字节=2048 TB（更不用说为跟踪最佳板而增加的开销）。这有点超出了目前台式计算机的水平，尽管在任何给定时间都可以巧妙地限制所需的电路板数量，以获得适合于例如3 TB硬盘驱动器或甚至是RAM的电路板。

作为参考，国际象棋有一个2¹⁵⁵可能位置的上界。

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

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

>

始终有15个打开的方块

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

一旦板上所有瓷砖的总和达到2048，将需要最少的组合数来获得单个2048（因此，如果放置2使和2048，则组合将是2->4->8->16->...->2048，即采取10步）

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

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

要达到2048，需要放置2048/2=1024个瓦片。

计算确切的数字可能需要我们通过所有这些州，这是不可行的。