炸弹人Minimax

我正在开发炸弹人游戏的克隆,我正在尝试不同types的人工智能。 首先,我用A *search状态空间,现在我想用Minimaxalgorithm尝试不同的方法。 我的问题是,每一个minimax文章我发现假设球员交替。 但在炸弹人中,每个玩家同时采取一些行动。 我认为我可以为一个游戏刻度生成所有可能的状态,但是有四个玩家和五个基本动作(四个动作和一个炸弹的地方),它在游戏树的第一级给出5 ^ 4个状态。 这个价值会随着每一个下一个水平呈指数上升。 我错过了什么吗? 有什么办法来实现它,或者我应该使用完全不同的algorithm? 感谢您的任何建议

像轰炸机一样的实时战略游戏与AI有困难的时候。 你想要它是聪明的,但同时它不可能是完美的。

如果AI是完美的,你的玩家会感到沮丧。 要么因为他们总是失败,要么你得到.3帧每秒。

如果它不够聪明,你的玩家会觉得无聊。

我的建议是有两个AIfunction,一个决定AI去哪里,另一个决定什么时候放下炸弹。 你可以使用诸如运动预测之类的东西来确定一个敌人是否正朝着当前位置投掷炸弹时危险的地点移动。

根据难度,您可以修改这些function来提高或降低难度。

正如你所注意到的,炸弹人太复杂了,不能被模拟为回合制游戏。 推断任何可能的自己的决定加上每一个其他球员的每一个可能的决定只是没有工作。

相反,你应该使用更具战略性的方法。

你应该问自己:一个人类玩家如何在玩炸弹人的同时作出决定? 通常,玩家应该遵循四个基本的优先事项:

  1. 避免爆炸的地方
  2. 放置炸弹,让其他人无法避开爆炸区域
  3. 收集通电
  4. 放置炸弹炸毁岩石

首先可以通过创建一个“危险地图”来实现。 当放置炸弹时,所有被其覆盖的瓷砖都应该被标记为“危险的”。 炸弹爆炸越早(牢记连锁反应!),危险程度越高。 每当AI发现它在高危地区时,它应该离开。 当绘制一条path(无论出于何种原因)时,应该避免使用高危险级别的域(可以通过人为地为它们添加更高的path成本来实现)。

危险地图的计算可以进一步加强,以保护AI从愚蠢的决定(如进入其他玩家很难逃离的区域)。

这应该已经创造了一个合理的防守AI。 那么进攻呢?

当人工智能认为现在合理安全时,应该计划进攻性的演习:应该考虑如何通过放置炸弹来增加其他玩家的危险地图。 在select放置炸弹的地点时,应该select靠近的地点,这样就不必移动太远。 当由此产生的危险地图不允许合理的逃生路线时,也应该忽略炸弹的位置。

我认为我可以为一个游戏刻度生成所有可能的状态,但是有四个玩家和五个基本动作(四个动作和一个炸弹的地方),它会在游戏树的第一级给出5 ^ 4个状态。

正确! 你需要search所有5 ^ 4(甚至6 ^ 4,因为你可以走4个方向,停止和“放炸弹”? 但是,当玩家已经决定移动时,需要一些时间才能执行移动(例如10个游戏)。 在此期间,可能性会减less。

这个价值会随着下一个水平成倍地提高。 我错过了什么吗? 有什么办法来实现它,或者我应该使用完全不同的algorithm?

您可以使用哈希表只计算一次相同的游戏状态“子树”。 想象一下,玩家A上下走动,而所有其他玩家“等待”,最终都会处于相同的游戏状态。 这与“左 – 右”或“右 – 左”相同。 另外,“左上”和“左上”的结果也是相同的状态。 使用哈希表,您可以“重新使用”已计算的游戏状态的计算得分。 这会降低增长速度。 在math上,它减less了指数增长函数的基数。 要想知道降低复杂程度有多less,让我们看看如果玩家可能只是向上/向下/向左/向右/停止移动,那么只有一个玩家可以相对于地图上的可达位置(=不同的游戏状态) 。

深度1:5移动,5个不同的状态,5个额外的状态recursion

深度2:25移动,13个不同的状态,这个recursion有8个附加状态

深度3:6125移动,25个不同的状态,12递增的状态

为了可视化,请回答自己:地图上的哪些字段可以通过一个移动,两个移动,三个移动来达到。 答案是:距离开始位置的最大距离= 1,2或3的所有字段。

当使用HashTable时,你只需要评估每个可到达的游戏状态(在我们的例子25的深度3)一次。 而没有HashTable你需要多次评估它们,这将意味着6125个评估,而不是25个在深度级别3.最好的:一旦你计算了一个HashTable条目,你可以在以后的时间步骤重新使用它…

你也可以使用增量深化和alpha-beta修剪“剪切”的子树,这是不值得深入search的。 对于象棋,这将search到的节点数量减less到大约1%。 一个简短的alpha-beta修剪介绍可以在这里find一个video: http : //www.teachingtree.co/cs/watch? concept_name=Alpha-beta+Pruning

进一步研究的好开始是http://chessprogramming.wikispaces.com/Search 。 该页面与国际象棋相关,但search和优化algorithm是相当的。

另一个(但是复杂的)人工智能algorithm – 比较适合游戏 – 是“时间差分学习”。

问候

斯特凡

PS:如果你减less了可能的游戏状态的数量(例如地图尺寸非常小,每个玩家只有一颗炸弹,没有别的),那么就有机会预先计算所有游戏状态的评估。

– 编辑 –

您也可以使用离线计算的极小极小计算结果来训练神经元networking。 或者你可以使用它们来评估/比较手工执行的策略。 例如,你可以实现一些建议的“个性”和一些启发式,在哪种情况下哪种策略是好的。 所以你应该“分类”情况(比如游戏状态)。 这也可以通过神经元networking来处理:训练一个神经元networking,以预测在当前情况下哪一种手工编码的策略发挥最好并执行它。 这应该为真实游戏产生非常好的实时决策。 比在其他情况下可以实现的低深度限制search要好得多,因为离线计算需要多长时间(游戏之前)并不重要。

– 编辑#2 –

如果你只是每1秒重新计算一次最好的移动次数,那么你也可以试着做更高级的移动。 这是什么意思? 你知道你可以在1秒内做多less动作。 所以你可以列出一个可到达的位置列表(例如,如果这将是1秒内3次移动,你将有25个可到达的位置)。 那么你可以像这样计划:去“位置x并放置炸弹”。 正如其他人所建议的,你可以创建一个“危险”的地图,用于路由algorithm(如何去位置x?哪个path应该是首选的[在大多数情况下有一些可能的变化])。 与较大的HashTable相比,这不会占用更多的内存,但会产生不太理想的结果。 但是由于使用较less的内存,caching效果会更好(更好地使用L1 / L2内存caching)。

另外:你可以做预先search,只包含每个玩家的移动,以找出导致失去的变化。 因此,把所有其他玩家从游戏中取出…存储每个玩家可以select的组合,而不会丢失。 如果只有松动的动作,寻找玩家活着的时间最长的移动组合。 要存储/处理这种树结构,你应该使用一个索引指针这样的数组:

class Gamestate { int value; int bestmove; int moves[5]; }; #define MAX 1000000 Gamestate[MAX] tree; int rootindex = 0; int nextfree = 1; 

每个状态都有一个评价“价值”,并通过将移动[0]中的数组索引存储在“树”中来移动(0 =停止,1 =向上,2 =向右,3 =向下,4 =向左) ]移动[4]。 以recursion方式构建您的树,可能看起来像这样:

 const int dx[5] = { 0, 0, 1, 0, -1 }; const int dy[5] = { 0, -1, 0, 1, 0 }; int search(int x, int y, int current_state, int depth_left) { // TODO: simulate bombs here... if (died) return RESULT_DEAD; if (depth_left == 0) { return estimate_result(); } int bestresult = RESULT_DEAD; for(int m=0; m<5; ++m) { int nx = x + dx[m]; int ny = y + dy[m]; if (m == 0 || is_map_free(nx,ny)) { int newstateindex = nextfree; tree[current_state].move[m] = newstateindex ; ++nextfree; if (newstateindex >= MAX) { // ERROR-MESSAGE!!! } do_move(m, &undodata); int result = search(nx, ny, newstateindex, depth_left-1); undo_move(undodata); if (result == RESULT_DEAD) { tree[current_state].move[m] = -1; // cut subtree... } if (result > bestresult) { bestresult = result; tree[current_state].bestmove = m; } } } return bestresult; } 

这种树结构要快得多,因为dynamic分配内存真的很慢! 但是,存储search树也是非常缓慢的…所以这更多的是一个灵感。

能想象大家轮stream吗?

从技术上讲,在底层系统中,它们实际上是这样做的,但是由于事物是交错叠加的,它们似乎是同时运行的。

另外请记住,你不必在每一帧animation之后运行AI。 许多成功的休闲游戏每秒只运行一次AIalgorithm,为AI控制的角色提供他们应该去的地方或者应该做什么的信息,然后用这些信息来控制AI角色在其他框架。