Edit: 此问题与What is the optimal algorithm for the game 2048?不重复
-
那个问题问'what is the best way to win the game?'
-
这个问题问'how can we work out the complexity of the game?'
他们是完全不同的问题 . 我对进入“赢”状态需要采取哪些步骤感兴趣 - 我有兴趣了解是否可以计算出可能的步骤总数 .
我一直在阅读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
在这一点上，我想我会在这里等待一段时间来运行......
所以我的问题是 - 我将如何开始编写这种算法 - 什么策略最适合计算游戏的复杂性？
我在2048和国际象棋之间看到的最大区别是，当添加新的牌时，程序可以在2到4之间随机选择 - 这似乎增加了大量额外的可能移动 .
最终，我希望程序输出一个数字，显示游戏中可能的排列数量 . 这可能吗？！
1 回答
让我们确定有多少可能的电路板配置 .
每个图块可以为空，也可以包含2,4,8，...，512或1024图块 .
每块瓷砖有12种可能性 . 有16块瓷砖，所以我们得到1612 = 248种可能的电路板状态 - 这很可能包括一些无法接入的电路板状态 .
假设我们可以将所有这些存储在内存中，我们可以从所有电路板状态向后工作，这将在下一步中生成2048磁贴，执行一定量的工作以将可达的电路板状态相互链接，这应该给我们一个概率每个州最好的举动 .
为了将所有位存储在存储器中，假设我们需要每个块4位，即64位=每个板状态8个字节 .
然后，248个板状态将需要8 * 248 = 2251799813685248字节= 2048 TB（更不用说增加开销以跟踪最佳板） . 这有点超出了现在的台式电脑，尽管可能会巧妙地限制在任何给定时间所需的电路板数量，以便达到适合3 TB硬盘驱动器的功能，或者可能甚至在RAM中 .
供参考，chess has an upper bound of 2155 possible positions .
如果我们从一开始就实际计算每一个可能的移动（以类似于_1010743的方式），我们就会获得大量的数字 .
这不是确切的数字，而是对上限的粗略估计 .
让我们做一些假设:(这绝对不是真的，但为了简单起见）
总共有15个空心方块
你总是有4个动作（左，右，上，下）
一旦板上所有瓷砖的总和达到2048，将获得单个2048的最小组合数量（因此，如果放置2使得总和为2048，则组合将为2 - > 4 - > 8 - > 16 - > ...... - > 2048，即进行10次移动）
A 2将永远被放置，永远不会是4 - 算法不会假设这一点，但是，为了计算上限，我们将 .
我们不会考虑在此过程中可能会产生重复的电路板这一事实 .
要达到2048，需要放置2048/2 = 1024个磁贴 .
你从2个随机放置的瓷砖开始，然后重复移动并放置另一个瓷砖，所以大约有1022'转'（转弯包括移动和瓷砖放置），直到我们得到2048的总和，然后是另外10回合得到2048瓦 .
在每个回合中，我们有4个移动，并且可以有两个瓦片中的一个放置在15个位置中的一个（30种可能性）中，因此4 * 30 = 120种可能性 .
这总共会给我们1201032个可能的状态 .
如果我们假设一个4总是放置，我们得到120519个状态 .
计算确切的数字可能涉及在所有这些状态下工作，这实际上是不可行的 .