0

《接近》是一款类似于奥赛罗、围棋和冒险的领土统治策略游戏。两名玩家，使用 10x12 六角网格。Brian Cable于 2007 年发明的游戏。

似乎是一个值得讨论的游戏a）最佳算法然后b）如何构建人工智能。
由于随机因素和疯狂的分支因素 (20^120)，策略将基于概率或启发式。所以很难客观地比较。 每轮最多 5 秒的计算时间限制似乎是合理的 => 这排除了所有蛮力尝试。（在专家级别上玩游戏的 AI 来感受一下——基于一些简单的启发式，它做得非常好）

游戏：此处为 Flash 版本，此处为iPhone版本iProximity以及网络上其他地方的许多副本规则：此处

目的：在放置所有瓷砖后控制最多的军队。你从一个空的六角板开始。每回合你都会收到一个随机编号的瓷砖（数值在 1 到 20 支军队之间），可以放置在任何空置的棋盘空间上。如果此图块与任何 ALLY 图块相邻，它将增强每个图块的防御 +1（最大值为 20）。如果它与任何 ENEMY 瓷砖相邻，如果其数量高于敌人瓷砖上的数量，它将控制它们。

关于策略的思考：这里有一些初步的想法；将计算机 AI 设置为专家可能会学到很多东西：

  1. 最小化你的周长似乎是一个好策略，以防止翻转并最大限度地减少最坏情况下的损坏
  2. 就像围棋一样，在你的阵型中留下洞是致命的，只有六角网格更是如此，因为你可以在一次移动中失去多达 6 个方格的军队
  3. 低编号的瓷砖是一种负担，因此请将它们远离您的主要区域，靠近棋盘边缘并分散。您还可以使用低编号的瓷砖来填补阵型中的漏洞，或者在对手不会打扰进攻的外围获得小幅收益。
  4. 三块的三角形结构很牢固，因为它们相互加强，也减少了周长
  5. 每个图块最多可以翻转 6 次，即当它的相邻图块被占用时。对编队的控制可以来回流动。有时您会丢失部分阵型并堵塞任何孔以使该部分板“死”并锁定您的领土/防止进一步损失。
  6. 低编号的牌是显而易见的但价值较低的负债，但如果高编号的牌被翻转（这更难），它们可能会成为更大的负债。一个 20 军队的棋子的幸运游戏可以导致 200 的摆动（从 +100 到 -100 军队）。所以瓷砖的放置会有进攻和防守的考虑。

评论 1,2,4 似乎类似于极小极大策略，其中我们最小化最大预期可能损失（通过对对手可以从 1..20 获得的值 ß 的一些概率考虑进行修改，即只能被 ß 翻转的结构=20 瓷砖“几乎坚不可摧”。）我不清楚评论 3、5、6 对最佳策略的影响。对围棋、国际象棋或奥赛罗棋手的评论感兴趣。

（XBox Live 的续集ProximityHD 允许 4 人合作或竞争性本地多人游戏增加了分支因素，因为您现在在任何给定时间都有 5 个牌，其中您只能玩一个。加强盟友牌是每个盟友增加到 +2。）

4

2 回答 2

3

这里是 U of A GAMES 小组的前成员。

那个分支因素是疯狂的。比围棋差多了。

基本上，你被圈套了。

该游戏的问题在于，由于选择了随机图块，因此它不是确定性的。这实际上在树中每个现有节点层之间添加了另一层节点。您将对我在 *-Minimax 上的出版物感兴趣，以了解在随机域中搜索的技术。

为了在本世纪末之前完成单层搜索，您将需要一些非常激进的前向修剪技术。尽早抛出可证明的最佳移动，并专注于建立良好的移动顺序。

于 2010-05-14T18:22:22.687 回答
2

对于一般算法，我建议您查看阿尔伯塔大学 AI 游戏小组所做的研究：http ://games.cs.ualberta.ca那里的许多算法保证找到最优策略。但是，我怀疑您是否真的有兴趣找到最佳选择，除非您想在韩国销售该游戏，否则以“足够好”为目标：D

根据您的描述，我已经将游戏理解为具有完全可观察性的两人游戏，即没有隐藏单位和完全确定性，即玩家的行动结果不需要滚动，那么您应该看看实时有界-搜索由阿尔伯塔大学的家伙提出的极小极大导数。但是，能够同时限制值函数的备份深度可能是为您的游戏添加“难度级别”的好方法。他们一直在做一些工作 - 有点可疑 - 对搜索空间进行抽样以改进价值​​函数估计。

关于您描述的“策略”部分：在我提到的框架中，您必须将该知识编码为评估函数。查看 Michael Büro 和其他人的工作 - 也在 U Alberta 小组中 - 以获取此类知识工程的示例。

另一种可能性是将问题作为强化学习问题提出，其中对手的动作被编译为“后态”。在 Barto & Sutton 的书上查看：http ://webdocs.cs.ualberta.ca/~sutton/book/the-book.html然而，由这种编译产生的 RL 问题的价值函数可能有点困难以最佳方式解决 - 状态的数量会像氢弹一样爆炸。但是，如果您了解如何使用因式表示，事情会容易得多。你的“策略”也许可以编码为某种塑造功能，这将大大加快学习过程。

编辑：该死的英语介词

于 2010-05-11T10:59:36.463 回答