我实施了一个谜题 15,供人们在线竞争。我当前的随机发生器通过从良好的配置开始并移动瓷砖 100 次移动(任意数)来工作
一切都很好,但是,偶尔洗牌太容易了,只需要几个动作就可以解决难题,因此对于一些人以更高的速度获得更好的分数来说,这个游戏真的很不公平。
什么是随机化初始配置的好方法,所以它不是“太容易”?
我实施了一个谜题 15,供人们在线竞争。我当前的随机发生器通过从良好的配置开始并移动瓷砖 100 次移动(任意数)来工作
一切都很好,但是,偶尔洗牌太容易了,只需要几个动作就可以解决难题,因此对于一些人以更高的速度获得更好的分数来说,这个游戏真的很不公平。
什么是随机化初始配置的好方法,所以它不是“太容易”?
您可以生成一个完全随机的配置(即可解),然后使用一些求解器来确定最佳的移动顺序。如果序列对您来说足够长,很好,否则生成新配置并重复。
更新和详细信息
维基百科上有一篇关于 15 谜题的文章,以及它何时(和不可)可解。简而言之,如果空方块位于右下角,那么当且仅当反转数(反转是序列中两个元素的交换,不一定是相邻元素)相对于目标排列是偶数。
然后,您可以通过进行偶数次反转轻松生成可解的起始状态,这可能会比通过常规移动更快地导致不太容易解决的状态,并且可以保证它将保持可解。
实际上,您不需要使用我上面提到的搜索算法,而是可以使用的启发式算法。这样的人总是低估永远不会高估解决难题所需的移动数量,即你可以保证它不会像启发式告诉你的那样减少移动。
一个好的启发式是每个数字到其目标位置的曼哈顿距离之和。
概括
简而言之,用于生成起始位置的可能(非常简单)算法可能如下所示:
1: current_state <- goal_state
2: swap two arbitrary (randomly selected) pieces
3: swap two arbitrary (randomly selected) pieces again (to ensure solvability)
4: h <- heuristic(current_state)
5: if h > desired threshold
6: return current_state
7: else
8: go to 2.
要绝对确定一个状态有多困难,您需要使用一些求解器找到最佳解决方案。启发式只会给你一个估计。
我会这样做
在随机方向进行有效转弯
因此,您必须跟踪间隙的位置并生成随机方向(N,E,S,W)
并进行移动。我想这部分你也做过。
计算展示位置的随机性
因此,根据数组的顺序计算一些系数。因此,有序(已解决)的解决方案将具有低值,而随机将具有高值。然而,系数的方程是一个反复试验的问题。这里有一些想法使用什么:
平均价值差的总和及其邻居
1 2 4
3 6 5
9 8 7
coeff(6)= (|6-3|+|6-5|+|6-2|+|6-8|)/4
coeff=coeff(1)+coeff(2)+...coeff(15)
与有序数组的绝对距离
您可以将更多方法组合在一起。您可以将其划分为单独的行和列,然后将子系数组合在一起。
来自 #3 的循环 #2 单位系数足够高(阈值)
门槛也可以用来改变难度。