我参加了Programming Challenges并找到了 Yahtzee!我将简化的问题:
- 有13个评分类别
- 一个玩家有13个掷骰子(包括一个剧本)
- 每个卷必须适合不同的类别
- 目标是找到一场比赛的最高分(类别中滚动的最佳位置);score(play) 返回一个游戏的分数
蛮力找到最高游戏分数需要 13 分!(= 6,227,020,800) score() 调用。
我选择模拟退火以更快地找到接近最高分数的东西。虽然不是确定性的,但已经足够好了。我有一个 13 卷 5 骰子的列表,例如:
((1,2,3,4,5) #1
(1,2,6,3,4),#2
...
(1,4,3,2,2) #13
)
(1,5,6,7,2,3,4,8,9,10,13,12,11)
传递给 score()的剧本返回该剧本排列的分数。
如何选择一个好的“邻国”?对于随机重启,我可以简单地选择 nos 的随机排列。1-13,把它们放在一个向量中,然后给它们打分。在旅行商问题中,这是一个良好邻国的例子:
“某些特定排列的邻居是例如通过交换一对相邻城市而产生的排列。”
我对简单地交换两个随机向量位置有一种不好的感觉,如下所示:
(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one
但我没有证据,也不知道如何选择一个好的邻国。有人对如何选择好的邻国有任何想法吗?