如何制定2048年游戏的复杂性？
编辑：这个问题不是什么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，...，512或1024个图块。
每瓦有12种可能性。 有16个图块，所以我们得到1612 = 248个可能的图板状态 - 这很可能包括几个不可触摸的状态。
假设我们可以将所有这些存储在内存中，我们可以从所有板状态向后工作，在下一步移动时产生2048个瓦片，做可持续的工作以将可达到的板状态彼此链接，这应该给我们一个概率每个州的最佳举措。
为了将所有位存储在内存中，假设我们需要每块瓷砖4位，即每个电路板状态64位= 8个字节。
然后，248个主板状态将需要8 * 248 = 2251799813685248个字节= 2048 TB（更不用说追加最佳主板的额外开销）。 虽然有可能巧妙地限制在任何特定时间需要的电路板数量，以便找到适合的产品，比如3TB硬盘驱动器，或者可能即使在RAM中。
作为参考，国际象棋上限为2155个可能的位置。
如果我们从一开始就真正计算出每一个可能的举措（以广度优先的搜索方式），我们会得到大量的数据。
这不是确切的数字，而是对上限的粗略估计。
让我们来做一些假设:(这肯定不总是正确的，但为了简单起见）
总是有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个可能性。
这总共会给我们1201032个可能的状态。
如果我们假设一个4总是被放置，我们会得到120519个状态。
计算确切的数字可能涉及到通过所有这些国家的工作方式，这将不会真正可行。
链接地址: http://www.djcxy.com/p/6839.html上一篇: How to work out the complexity of the game 2048?
下一篇: Map Tiling Algorithm