2048⼩游戏最佳算法C语⾔,2048游戏的最佳算法是什么？我使⽤Expectimax优化开发了2048 AI ，⽽不是@ovolve算法使⽤的minimax搜索。AI会简单地对所有可能的移动执⾏最⼤化，然后对所有可能的图块⽣成进⾏期望(通过图块的概率加权，即4的概率为10％，2的概率为90％)。据我所知，不可能修剪Expectimax优化(除去删除极不可能的分⽀)，因此使⽤的算法是经过仔细优化的蛮⼒搜索。
性能
AI的默认配置(最⼤搜索深度为8)从10ms到200ms的任何时间执⾏移动，具体取决于电路板位置的复杂程度。在测试中，⼈⼯智能在整个游戏过程中的平均移动速率为每秒5-10次移动。如果将搜索深度限制为6个动作，则AI可以轻松地每秒执⾏20个以上的动作，这使您可以进⾏⼀些有趣的观看。
为了评估AI的得分表现，我运⾏了AI 100次(通过遥控器连接到浏览器游戏)。对于每个图块，以下是该图块⾄少获得⼀次的游戏⽐例：
2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%
最低分数为124024；AI的最⾼得分是794076。中位数是387222。AI从未失败过获得2048个图块(因此，即使每100场游戏中有⼀次它也不会输掉游戏)；实际上，它在每次运⾏中⾄少获得了8192个磁贴！
这是最佳运⾏的屏幕截图：
32768瓷砖，得分794076
该游戏在96分钟内进⾏了27830次移动，或平均每秒4.8次移动。
实作
我的⽅法将整个电路板(16个条⽬)编码为单个64位整数(其中，图块为四位，即4位块)。在64位计算机上，这使整个电路板可以在单个计算机寄存器中传递。
位移操作⽤于提取单独的⾏和列。单个⾏或列是16位数量，因此⼤⼩为65536的表可以编码对单个⾏或列进⾏操作的转换。例如，将移动作为4个查询实现到预先计算的“移动效果表”中，该表描述了每个移动如何影响单个⾏或⼀列(例如，“向右移动”表包含条⽬“ 1122-> 0023”，该条⽬描述了当向右移动时，⾏[2,2,4,4]变为⾏[0,0,4,8]。
还可以使⽤表查来进⾏计分。这些表包含在所有可能的⾏/列上计算的启发式分数，并且⼀块⽊板的结果分数就是每个⾏和列中表值的总和。
这种棋盘表⽰形式以及⽤于移动和得分的表格查⽅法，使AI可以在短时间内搜索⼤量游戏状态(在我的2011年中期笔记本电脑的⼀个核⼼上每秒可搜索超过10,000,000个游戏状态)。
Expectimax搜索本⾝被编码为递归搜索，它在“期望”步骤(测试所有可能的⽡⽚⽣成位置和值，并通过每种可能性的概率加权其优化得分)和“最⼤化”步骤(测试所有可能的移动)之间交替并选择得分最⾼的那个)。当树搜索看到先前看到的位置(使⽤转置表)，达到预定义的深度限制或达到极不可能的板状态(例如，通过获取6个“ 4”图块达到该状态)时，树搜索终⽌从起始位置开始连续排成⼀⾏)。典型的搜索深度是4-8步。
启发式
⼏种启发式⽅法⽤于将优化算法引向有利位置。启发式算法的精确选择对算法的性能有很⼤的影响。权衡各种启发式⽅法并将其组合到位置分数中，该分数确定给定板位置的“好”程度。然后，优化搜索将旨在使所有可能的董事会职位的平均分数最⼤化。如游戏所⽰，实际得分不⽤于计算棋盘得分，因为它过于权重⽽⽆法合并砖块(延迟合并可能产⽣巨⼤收益)。
最初，我使⽤了两种⾮常简单的启发式⽅法，分别为开放正⽅形和在边缘具有较⼤值的对象授予“奖励”。这些启发式⽅法的效果⾮常好，经常达到16384，但从未达到32768。c语言编程小游戏
PetrMorávek(@xificurk)采⽤了我的AI，并添加了两个新的启发式⽅法。第⼀种启发式⽅法是对具有⾮单调的⾏和列的⾏列进⾏惩罚，该⾏和列随等级的增加⽽增加，以确保数量较少的⾮单调⾏不会严重影响得分，但是数量较⼤的⾮单调⾏将严重损害得分。第⼆种启发式⽅法计算了除开放空间之外的潜在合并数(相邻的相等值)。这两种启发式算法将算法推向单调板(更易于合并)，并推向具有⼤量合并的板位置(⿎励它在可能的情况下对齐合并以产⽣更⼤的效果)。
此外，Petr还使⽤“元优化”策略(使⽤称为CMA-ES的算法)对启发式权重进⾏了优化，其中权重本⾝已进⾏调整以获得最⾼的平均得分。
这些变化的影响极为显着。该算法从⼤约13％的时间达到16384⽡⽚到90％的时间达到了它，并且算法在1/3的时间开始达到32768(⽽旧的启发式算法从未产⽣过32768⽡⽚) 。
我相信启发式⽅法仍有改进的空间。该算法肯定还不是“最优”的，但是我觉得它已经接近了。
⼈⼯智能在超过三分之⼀的游戏中获得了32768⽡，这是⼀个巨⼤的⾥程碑。听到有⼈在正式游戏中获得32768的成绩(即未使⽤savestates或undo等⼯具)，我会感到惊讶。我认为65536磁贴触⼿可及！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。