设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

对弈类游戏的人工智能(3)--博弈树优化

来源:未知 编辑:admin 时间:2019-05-31

  对弈类游戏的智能算法, 网上资料颇多, 大同小异. 然而书上得来终觉浅, 绝知此事要躬行. 结合了自己的工程实践, 简单汇总整理下. 一方面是对当年的经典表达敬意, 另一方面, 也想对自己当年的游戏编程人生做下回顾.

  这篇博文回归到博弈树这边, 具体阐述下博弈树的优化手段, 为了游戏性添加的合理技巧.

  博弈树本质是极大极小的求解过程, 而alpha+beta剪枝则加速该求解过程.

  通过人工演算和模拟, 整个博弈过程, 成功地减少了3个节点的计算量的, 效果一般.

  这个过程, 我们是否有优化的余地呢? 让我们调整下,节点S1和S2的搜索顺序.

  与调整顺序之前相比, 其alpha+beta剪枝的效果提升, 砍去了一个大分支, 减少了4个节点的计算量.

  从这个例子中, 我们可以清晰的看到, 对于博弈树而言, 其alpha+beta的剪枝效果, 和搜索顺序是有一定关系的. 简单的总结:alpha+beta效果, 对搜素的顺序敏感.

  于是我们找到了一个优化方向: 调整可行步的顺序, 并优先搜索预期高的分支. 该技巧命名为:启发搜索.常有人借助历史值, killer步来构造启发函数.

  当然该过程是有一定代价的, 在alpha+beta剪枝效果提升和排序损耗需要均衡和折中. 一般采用计算简单的预估函数即可.

  让我们回到黑白棋AI, 我们可以简单选定, 预估函数等同于位置表, 即P(x, y) = Map(x, y). (Map 为 黑白棋棋面的位置重要度矩阵), 效果斐然.

  搞过ACM的人, 都知道DP求解的一种方式:记忆化搜索. 本质就是把中间状态保存, 减少重复搜索的一种技巧.

  1). 游戏局面S本身占用空间大, 而且需要保存的状态S集合多, 因此需要一个转换函数F(S) = key, (key为不长二进制串, 或一个很大的整数)

  2). 转换后的key, 一一对应了某个具体局面S (冲突率很低可忽略, 或不存在)

  让我们以黑白棋来做个例子, 局面转换为矩阵(0: 空白, 1: 黑棋, 2:白棋), 扁平化为字符串, 在借助强有力的Hash函数来转化.

  和记忆化搜索相比, 置换表对应的局面是,只是中间的预测节点, 因此该状态除了本身和游戏局面相关, 还和当前的搜索深度有关.

  启发搜索和置换表, 两者都是很好的思路, 前者通过调整搜索顺序来加速剪枝效果. 后者通过空间换时间. 总而言之, 这些都是博弈树上很常见的优化手段. 当然在具体游戏中, 需要权衡和评估. 下一篇讲讲出于游戏性的考虑, 如何进行优化和策略选择.

  如果你觉得这篇文章对你有帮助, 请小小打赏下. 其实我想试试, 看看写博客能否给自己带来一点小小的收益. 无论多少, 都是对楼主一种由衷的肯定.

本文链接:http://mzi-ads.com/boyishusousuo/527.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top