为游戏'接近'找到最佳/足够好的策略和人工智能？

Question

'接近'是一个类似于黑白棋，围棋和风险的领土统治战略游戏。两个玩家，使用10x12六角形网格。游戏发明者Brian Cable在2007年。

似乎是一个值得讨论的游戏a）优化算法然后b）如何构建AI。
由于随机性因素和疯狂的分支因子（20^120），策略将是概率性的或基于启发式的。 因此，客观地比较是很难的。 每回合最多5秒的计算时间限制似乎是合理的=>这排除了所有暴力尝试。（玩游戏的AI上专家的水平来感受 - 它基于一些简单的规则十分出色）

游戏：Flash version here，iPhone version iProximity here和许多副本在网络上其他地方 规则：here

对象：在所有瓷砖放置完毕后控制大多数军队。你从一个空的木板开始。每回合你收到一个随机编号的瓦片（值在1到20军）放置在任何空置的电路板空间。如果此贴砖与任何ALLY贴砖相邻，则会加强每个贴砖的防御+1（最高可达20）。如果它与任何ENEMY牌相邻，如果其号码高于敌方牌上的号码，则会控制它们。

关于策略的思考：以下是一些初步想法;设置电脑AI专家可能会教导很多：

1. 尽量减少你的周边似乎是一个很好的策略，以防止翻转和减少最坏情况下的损伤
2. 像围棋，留孔内的形成是致命的，只有更多的六角网格，因为你可以在一次移动中失去多达6个方格的军队
3. 低编号的瓷砖是一种责任，所以把它们放置在远离你的主要领土，靠近电路板边缘并散落的地方。你也可以使用低编号的瓦片来堵住你阵型的洞，或者在对手不会打扰攻击的周界上进行小幅度增益。
4. 由于它们相互加强，并且还减少了边界，所以三个三角形的形成是强的。每个瓦片可以翻转至多6次，即当其邻居瓦片被占用时。地层的控制可以来回流动。有时候你会失去一部分阵型并堵住任何漏洞，导致该部分棋盘“死亡”并锁定在你的领土内/防止进一步的损失。
5. 低编号的瓷砖是显而易见但价值低的负债，但编号较高的瓷砖如果翻转（这更难）会是更大的负债。一次20军瓦片的幸运玩法可能导致200的挥杆（从+100到-100军队）。所以拼贴放置会有攻击和防御两方面的考虑。

评论1,2,4似乎类似于一个极小极小战略，我们尽量减少最大的预期可能损失（通过一些概率考虑值的修正，对手可以从1..20得到，即一个结构可以只有被ß= 20瓦翻转才是'几乎坚不可摧'。） 我不清楚评论3,5,6对最佳策略的影响。 对Go，Chess or Othello玩家的评论感兴趣。

（续集ProximityHD for XBox Live, allows 4-player -cooperative or -competitive local multiplayer增加分支因素，因为你现在在你的手牌5在任何给定的时间，而你只能起到盟友瓷砖之一。加固增加到+2每盟友。）

Answer 1

对于一般算法，我建议您检查由艾伯塔大学AI Games小组完成的研究：http://games.cs.ualberta.ca许多算法保证找到最佳策略。不过，我怀疑你是在寻找最佳的真正的兴趣，瞄准了“足够好”，除非你想出售在韩国的那场比赛：d

从你的描述，我已经明白游戏是两具有完全可观测性的玩家（即没有隐藏单位）以及完全确定性的玩家的行动结果不需要滚动，那么你应该看看阿尔伯塔家伙提出的实时有界搜索极小极小导数。但是，能够限制值函数备份的深度也许是向游戏添加“难度级别”的好方法。他们一直在做一些工作 - 有点腥意 - 抽样搜索空间以改进价值​​函数估计。

关于“策略”部分中，您描述：在我提到的框架，你将不得不编码知识作为评价函数。看看MichaelBüro和其他人 - 也就是U阿尔伯塔集团 - 的工作，例如这样的知识工程。

另一种可能性将是造成这一问题的强化学习问题，在对手的动作是编译为“afterstates”。你看，截至上巴托&萨顿书：http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html但是从这样的编译产生的RL问题的价值函数可能证明有点困难，以最佳解决 - 美国的数量将炸毁像氢弹。但是，如果您看到如何使用因式分解，事情会变得更容易。而你的“策略”也许可以编码为一些整形功能，这将大大加快学习过程。

编辑：该死的英语介词

Answer 2

这里游戏组的U的前成员。

那分支因素是疯了。远比Go差。

基本上，你啰嗦。

这个游戏的问题是，它不具有确定性，由于随机瓷砖的选择。这实际上增加了树中每个现有节点层之间的另一层节点。您将对我的publications on *-Minimax感兴趣，以了解随机域中搜索技术。

为了本世纪结束前完成的一层搜索，你会需要一些非常积极的向前修剪技术。尽可能的投掷最好尽早移开窗户，专注于建立良好的移动顺序。