‘Proximity‘ 是一款领土争夺的策略游戏，类似于黑白棋、围棋和风险游戏。两位玩家在一个 10×12 的六边形网格上进行游戏。该游戏由 Brian Cable 于 2007 年发明。
这个游戏似乎值得讨论 a) 最佳算法 以及 b) 如何构建 AI。
由于随机性因素和疯狂的分支因子 (20^120)，策略将是基于概率或启发式的。因此，客观地比较将会非常困难。每个回合最多 5 秒的计算时间限制似乎是合理的 => 这排除了所有蛮力尝试。（在专家级别上玩游戏的 AI 以获得感觉 – 它基于一些简单的启发式方法做得非常好）
游戏： Flash 版本在这里，iPhone 版本 iProximity 在这里，以及网络上的许多副本。规则：在这里
目标：在所有方块都被放置后，控制最多的军队。你从一个空的六边形棋盘开始。每个回合你都会收到一个随机编号的方块（值在 1 到 20 之间），可以放置在任何空闲的棋盘位置上。如果此方块与任何盟友方块相邻，它将加强每个盟友方块的防御力 +1（最高值为 20）。如果它与任何敌对方块相邻，并且它的数字高于敌对方块上的数字，它将控制敌对方块。
关于策略的思考： 这里有一些初步的想法；将计算机 AI 设置为专家级别可能会学到很多：
- 最小化你的周长似乎是一个好策略，以防止翻转并最小化最坏情况的损失
- 像围棋一样，在你的阵型中留下漏洞是致命的，对于六边形网格来说更是如此，因为你可能会在一个动作中失去多达 6 个方格上的军队
- 低编号的方块是一种负担，因此将它们放置在远离你主要领土的地方，靠近棋盘边缘并分散放置。你也可以使用低编号的方块来填补你阵型中的漏洞，或者在对手不愿攻击的周长上取得小小的收益。
- 三个棋子的三角形阵型很强大，因为它们相互加强，并且还减少了周长
- 每个方块最多可以被翻转 6 次，即当其相邻方块被占据时。一个阵型的控制权可以来回流动。有时你会失去阵型的一部分，并填补任何漏洞以使棋盘的该部分“死亡”并锁定你的领土/防止进一步的损失。
- 低编号的方块是显而易见但价值较低的负担，但高编号的方块如果被翻转（这更难），可能会成为更大的负担。用一个 20 军的方块幸运地一击，可能会导致 200 的波动（从 +100 到 -100 军）。因此，方块的放置将具有进攻和防御方面的考虑。
评论 1、2、4 似乎类似于极小极大策略，我们在其中最小化最大预期可能损失（通过对手可以从 1..20 获得的值 ß 的一些概率考虑来修改，即只能通过 ß=20 的方块翻转的结构是“几乎坚不可摧的”。）我不清楚评论 3、5、6 对最佳策略的影响是什么。对围棋、象棋或黑白棋玩家的评论感兴趣。
（续集 ProximityHD for XBox Live，允许 4 人 – 合作或 – 竞争的本地多人游戏 增加了分支因子，因为你现在手头有 5 个方块，但在任何给定的时间你只能玩一个。盟友方块的加强增加到每个盟友 +2。）
回答：
对于通用算法，我建议你查看阿尔伯塔大学 AI 游戏小组所做的研究：http://games.cs.ualberta.ca 那里的许多算法保证找到最佳策略。但是，我怀疑你是否真的对找到最佳策略感兴趣，除非你想在韩国销售这款游戏，否则就瞄准“足够好”就可以了：D
从你的描述中，我了解到该游戏是一个具有完全可观察性的双人游戏，即没有隐藏单位等，并且是完全确定性的，即玩家的行动结果不需要掷骰子，那么你应该看看阿尔伯塔大学的人提出的实时有界搜索极小极大值推导。但是，能够绑定价值函数备份的深度也可能是为你的游戏添加“难度级别”的好方法。他们一直在做一些工作 – 我认为有点可疑 – 关于采样搜索空间以改进价值函数估计。
关于你描述的“策略”部分：在我提到的框架中，你将必须将该知识编码为评估函数。查看 Michael Büro 和其他人的工作 – 也在阿尔伯塔大学小组中 – 以获取此类知识工程的示例。
另一种可能性是将问题视为强化学习问题，其中对手的行动被编译为“后状态”。在 Barto & Sutton 的书中查找：http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html 但是，由此编译产生的强化学习问题的价值函数可能很难得到最佳解决 – 状态的数量会像氢弹一样爆炸。但是，如果你看到如何使用分解表示，事情可能会容易得多。并且你的“策略”或许可以被编码为一些塑造函数，这将大大加快学习过程。
编辑：该死的英语介词
