fin*_*ook 9 algorithm logic artificial-intelligence game-theory
编辑:这个问题不是重复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个瓦片,所以我们得到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次移动)
A 2总是会被放置,永远不会是4 - 算法不会假设这个,但是,为了计算上限,我们会.
我们不会考虑在此过程中可能会产生重复的电路板这一事实.
要达到2048,需要放置2048/2 = 1024个磁贴.
你从2个随机放置的瓷砖开始,然后重复移动并放置另一个瓷砖,所以大约有1022'转弯'(转弯包括移动和瓷砖放置),直到我们得到2048的总和,然后是另外10回合得到2048瓦.
在每个回合中,我们有4个移动,并且可以有两个瓦片中的一个放置在15个位置中的一个(30种可能性)中,因此4*30 = 120种可能性.
这总共会给我们120个1032个可能的状态.
如果我们假设一个4将总是被放置,我们得到120 519个状态.
计算确切数字可能涉及在所有这些状态下工作,这实际上是不可行的.