logo标签列表

策略游戏的算法

algorithmlanguage-agnosticartificial-intelligence
6

这是一个我已经思考了一个星期左右的问题，由同事提出：

想象一个在36x36的网格上玩的游戏。游戏的目标是创建任何大小（例如2x2、3x3、4x4等）的正方形的四个角。第一个玩家可以在除中心四个网格空间以外的任何地方放置游戏棋子。第一步后，玩家可以在网格的任何地方放置游戏棋子。放置的棋子不能移动。就是这样，游戏简单有趣。

我一直在努力想出一种算法来赢得这个游戏，或者至少做得不错。有什么建议吗？

你只需要在正方形的角落放置棋子才能赢，而且你不能移动到对手已经移动过的空格上吗？这个正方形必须与坐标轴对齐，还是倾斜45度的正方形也可以赢得比赛？ - Jason Orendorff
1
1x1也是一个正方形，但如果你先手的话，那将使游戏变得非常容易赢得胜利 :-) - paxdiablo
1
继续Jason的问题，什么构成了“任意大小的正方形”？四个角落，正方形的轮廓，实心瓷砖？ - John
2
类似这样的游戏已经存在于iPhone上，您可以根据正方形的大小获得积分，首先达到一定分数的玩家获胜。旋转的正方形也是允许的。它被称为MetaSquares。您可以在此处在线玩：http://www.metatools.com/iphonemsq/ - FogleBird
这是一个双人游戏吗？游戏棋子的大小是单位正方形吗？而且，这个正方形是否填充？ - Alok Singhal
显示剩余2条评论
4个回答
7
这是一个完全信息的游戏，玩家轮流进行，就像国际象棋一样，因此可以使用国际象棋引擎中使用的相同方法。使用minimax（可能带有alpha-beta pruning）算法来搜索有效移动的树。您可以使用某些评估函数来指导搜索，偏爱具有最多几乎完成的正方形的位置。
3
像FogleBird所写的极小化极大算法可能是最好的选择。问题在于如何评估当前棋盘的得分。这个游戏非常复杂，一开始就有一千多个领域。在像井字棋这样的小游戏中，您可以计算到极小极大搜索树的末尾的所有可能的移动，然后给获胜者1分，输家-1分，并回溯树以找到最佳移动。在这个游戏中，您需要某种启发式方法来计算下降三个10步后板的得分。
我没有关于游戏的很多信息，所以我只能猜测好的启发式方法：
  • 因为完成的正方形而得分（如果您可以获得更多的正方形），这将是最简单的方法，因为您的启发式方法直接与游戏得分相关
  • 因敌人完成的正方形而扣分
  • 可能的正方形数量
  • 拥有的边界领域中的领地数量
  • 小邻域中拥有的领地数

有很多启发式方法可供选择，大多数情况下您需要混合使用其中一些。

2

您需要填充正方形还是只需将其放置在角落里？

例如，以下情况是否为胜利？

.......................
.X..X..................
.......................
.......................
.X..X..................
.......................

以下内容是什么？
或者是以下内容？
.......................
.XXXX..................
.X..X..................
.X..X..................
.XXXX..................
.......................

以下是什么？
.......................
.XXXX..................
.XXXX..................
.XXXX..................
.XXXX..................
.......................
我希望如此，因为在第一局中强制获胜很容易。 - BlueRaja - Danny Pflughoeft
任何一种都将构成胜利。 - Gideon
0

好的，我正在将垃圾读入游戏中...因为它是模棱两可的...我假设这个游戏类似于“点和线”，其中移动空间是连接两个相邻点的线。所以2x2网格将有9个顶点，4个1x1获胜位置和1个2x2获胜位置。当一个人完成一个正方形时，游戏以胜利结束，一旦两个玩家都用完了可赢的解决方案，就会打成平局。

由于你正在处理正方形，一些逻辑很好。你可以计算任何线段对所有可能的框的成员资格。所以在2x2的例子中，半径将在2个1x1框中具有成员资格，而侧面将在一个1x1和一个2x2中具有成员资格。这种成员资格变得很重要。

在游戏开始时，您需要为所有线段生成所有成员资格。制作2份副本...(就像玩战舰一样)敌人的副本将被初始化为他完成每个框所剩余的回合数...所以在36x36上，将有144次行动来完成大框架，4组140次行动来完成4个35x35的框架。

在你的移动过程中，你会减少所有受影响的敌方方块。在你的移动中，任何一个你所做的移动都会使包含该移动的所有方块无效。你可以将这些方块设置为负1、无限或20亿……只要知道这些方块是不可能的即可。

现在，你需要创建一个反向的敌方方块副本，即“反敌方副本”。其中包含完成给定方块所需的步数。

对于给定的移动，首先检查是否存在获胜的情况。如果你能够移动并获胜（反敌方副本中有一个方块为1），则进行移动。然后检查是否需要阻止对手（敌方棋盘上有任何一个方块为1）。

现在，如果你愿意，可以添加一个极小化-极大化函数。

或者使用搜索来找到摧毁尽可能多的低分方块的位置，或者创建一条线路，在反敌方棋盘上减少多个低分方块。这应该是合理的，因为它不是试图完成任何特定的方块，而是一个极小化-极大化，你们两个都在争取低分数的情况下，这将是一个更好的情况。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接