编辑:这个问题不是重复的什么是游戏2048的最佳算法?
- 这个问题问的是"赢得比赛的最佳方式是什么?"' 这个问题问的是"我们如何计算出游戏的复杂性?"'
它们是完全不同的问题。我对需要采取哪些步骤才能走向"获胜"状态不感兴趣——我感兴趣的是找出是否可以计算出可能步骤的总数。
我一直在阅读这个关于游戏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之间随机选择——这似乎增加了大量额外的可能移动。
最后，我希望程序输出一个数字，显示游戏中可能排列的数量。这可能吗?!
让我们来确定有多少种可能的板配置。
每个贴图可以是空的，或者包含2,4,8，…
每个贴图有12种可能。有16个贴图，所以我们得到1612 = 248可能的棋盘状态——这很可能包括一些无法到达的。
假设我们可以将所有这些都存储在内存中，我们可以从所有的棋盘状态往回算，在下一步移动中生成2048个贴图，做恒定的工作将可到达的棋盘状态彼此连接起来，这应该给我们每个状态的概率最佳移动。
要将所有位存储在内存中，假设我们需要每个tile 4位，即64位=每个board状态8字节。
248板状态将需要8*248 = 2251799813685248字节= 2048 TB(更不用说跟踪最佳板所增加的开销)。这比现在的台式电脑所拥有的要多一点，尽管有可能在任何给定的时间巧妙地限制所需的主板数量，以减少到适合的东西，比如说，3tb的硬盘驱动器，或者甚至是RAM。
作为参考，象棋的上界为2155可能的位置。
如果我们从一开始就计算每一个可能的移动(以宽度优先的搜索方式)，我们会得到一个巨大的数字。
这不是确切的数字，而是对上限的粗略估计。
让我们做一些假设:(这肯定不总是正确的，但是，为了简单起见)
-
总是有15个开放的方块
-
你总是有4次移动(左，右，上，下)
-
一旦棋盘上所有瓷砖的总和达到2048，它将需要最小数量的组合来获得单个2048(所以，如果放置2使总和为2048，组合将是2 -> 4 -> 8 -> 16 ->…-> 2048，即移动10步)
-
a2总是会被放置，而不是4——算法不会这样假设，但是，为了计算上界，我们会这样做。
-
我们不会考虑在这个过程中可能会产生重复的电路板。
要达到2048，需要放置2048/2 = 1024个贴图。
你从2个随机放置的贴图开始，然后重复移动并放置另一个贴图，所以大约有1022个"回合"(一个回合包括移动和放置贴图)，直到我们得到2048个，然后还有另外10个回合获得2048个贴图。
在每个回合中，我们有4次移动，并且可以在15个位置(30种可能性)中的一个位置放置两个瓷砖中的一个，所以这是4*30 = 120种可能性。
这总共会给我们1201032可能的状态。
如果我们假设4总是被放置，我们得到120519状态。
计算确切的数字可能需要我们遍历所有这些状态，这是不可行的。