如何为战舰游戏生成统计上可能的船只位置

Question

如何为战舰游戏生成统计上可能的船只位置

pythonalgorithmmathstatistics

18

我制作了最初的战舰游戏，现在我想将我的人工智能从随机猜测升级为根据统计学概率猜测位置。我在网上找不到算法，所以我的问题是，这个应用程序已经存在哪些算法？我该如何实现其中之一？

船只：5、4、3、3、2

场地：10X10

棋盘：

OCEAN = "O"
FIRE = "X"
HIT = "*"
SIZE = 10
SEA = [] # Blank Board
for x in range(SIZE):
    SEA.append([OCEAN] * SIZE)

如果您想查看剩余的代码，我在这里发布了它：（https://github.com/Dbz/Battleship/blob/master/BattleShip.py）; 我不想用很多无关的代码来混淆问题。

- Dbz

6

谷歌搜索结果看起来很有前途... - Bernhard Barker

1

可能性大的模型是什么？所有可能的船位都是均等概率的吗（即均匀分布）？还是您有另一种分布来模拟船只位置？ - mitchus

2

有一个关于这个问题的 Stackoverflow 竞赛：https://dev59.com/JHI-5IYBdhLWcg3w3cvS。第三个答案使用了最有可能的战舰位置上的热图。 - Thomas Ahle

还请查看这篇文章：http://thevirtuosi.blogspot.dk/2011/10/linear-theory-of-battleship.html - Thomas Ahle

你看过这段代码了吗？（https://github.com/GrahamBlanshard/AI-Battleship/blob/master/prograham/battleship/ProbabilityMap.java） - scohe001

4个回答

2

不错的问题，我喜欢你用统计方法的想法。我认为我会尝试以下机器学习方法来解决这个问题：

首先将你的问题建模为分类问题。分类问题是：给定一个正方形(x,y)，你想知道在这个正方形中有船的可能性。让这种可能性为p。

接下来，你需要开发一些“特征”。你可以把(x,y)的周围[因为你可能只有部分知识]作为你的特征。

例如，以下迷你棋盘的中间部分的特征（+表示你要确定是否在该方格中有船）：

OO*
O+*
?O?

可以是类似于这样的东西：

f1 = (0,0) = false
f2 = (0,1) = false
f3 = (0,2) = true
f4 = (1,0) = false
**note skipping (1,1)
f5 = (1,2) = true
f6 = (2,0) = unknown
f7 = (2,1) = false
f8 = (2,2) = unknown

我会实现与原点相关的功能（在这种情况下-（1,1）），而不是在棋盘上绝对位置上（因此，到（3,3）的正方形也将是f2）。

现在，创建一个训练集。训练集是一个“标记”的特征集-基于一些真实的棋盘。您可以手动创建它（创建大量棋盘），通过放置的随机生成器自动创建，或通过其他您可以收集的数据创建。

将训练集提供给学习算法。该算法应能够处理“未知”并能够提供“真实”概率，而不仅仅是布尔答案。我认为朴素贝叶斯的变体可以很好地适用于这里。

在获得分类器之后-使用您的AI进行利用。当轮到您时，选择射击具有最大值的正方形

p

。起初，射击可能会有些随机-但是随着您发射更多的射击，您将获得有关棋盘的更多信息，并且AI将利用它进行更好的预测。

请注意，我基于大小为1的正方形给出了特征。当然，您可以选择任何k并在这个更大的正方形上找到特征 - 这将给您更多的特征，但每个特征可能会更少信息。没有什么经验法则可以确定哪个更好 - 这应该进行测试。

- amit

1

找出还存活的船只：alive = [2,2,3,4] # 存活船只的长度
找出你尚未射击的位置，例如使用numpy.where()
循环遍历可以射击的位置。
检查给定位置的侧面。向左和向右移动多少空间？向上和向下移动多少空间？如果可以放入一艘船，那么可以放入任何比它小的船只，因此我会从最大的船只开始循环，并在该位置上添加与适合的船只长度相等的数量。
完成所有这些操作后，得分最高的位置应该是攻击和命中某物最有可能的位置。

当然，它可以变得更加复杂。您也可以问自己，而不是我的下一个攻击点是哪里，哪些攻击组合将在较少的攻击次数内带来胜利或任何其他问题的组合/参数化。祝好运！

- Jblasco

1

主要问题是，您将如何找到统计上可能的位置。它们已知还是您想弄清楚？无论哪种情况，我只会使网格加权。在您的情况下，每个插槽的初始权重将为1.0 /（SIZE ^ 2）。权重总和必须等于1。然后，您可以根据从N个最近玩过的游戏中收集的统计数据调整权重。现在，当您的AI做出选择时，它基于加权概率选择要击中的坐标。快速简单的方法是：

1. 在范围[0..1]内生成随机数R 2. 从插槽(0, 0)开始添加权重，即S = W(0, 0) + W(0, 1) + ...其中W(n, m)是相应插槽的权重。一旦S> = R，则已经得到要击中的坐标。

这可以通过为每行预先计算累积权重来进行优化，祝好运 :)

- Karadur

我认为加权网格是一个好主意。但是，我不想收集统计数据，因为我是随机生成船只位置的。 - Dbz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pseudoDust · Accepted Answer

最朴素的解决方法是遍历所有可能的船只位置（在已知信息下合法），并计算每个方格被填满的次数。

显然，在相对空旷的棋盘上，这种方法行不通，因为排列组合太多。但一个好的开始可能是：

对于棋盘上的每个方格：遍历所有船只，并计算其在该方格中适合的不同方式。即对于船只长度的每个方格，检查其是否水平和垂直地适合。

改进之处可能是，还要检查每个可能的船只位置，以确保其余的船只可以合法放置，同时覆盖所有已知的“命中”（已知包含船只的位置）。

为了提高性能，如果在给定的位置只能放置一艘船只，则无需在其他位置进行测试。此外，当有许多“命中”时，可能更快地首先覆盖所有已知的“命中”，然后针对每个可能的覆盖进行处理。

编辑：您可能需要研究深度优先搜索（DFS）。

编辑：关于评论中@Dbz的建议的详细说明：保留一个被拒绝的船只放置集合（可以表示为字符串，例如"4V5x3"表示在5x3、5x4、5x5和5x6中放置长度为4的船只），在猜测后，将猜测所拒绝的所有放置添加到集合中。然后，对于每个方格，保留与其相交的放置集合（'placements[x,y]'）。则概率为： 34-|intersection(placements[x,y], dissmissed)|/(3400-|dismissed|) 要添加到被拒绝列表中：

如果在（X，Y）处的猜测是未命中的，则添加placements[x,y]
如果在（X，Y）处的猜测是命中的：
- 添加相邻的放置（假设船只不能相邻放置），即添加：
  - <(2,3a,3b,4,5)>H<X+1>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y+1>
  - <(2,3a,3b,4,5)>H<X-(2,3,3,4,5)>x<Y>, <(2,3a,3b,4,5)>V<X>x<Y-(2,3,3,4,5)>
  - 2H<X+-1>x<Y+(-2 to 1)>, 3aH<X+-1>x<Y+(-3 to 1)> ...
  - 2V<X+(-2 to 1)>x<Y+-1>, 3aV<X+(-3 to 1)>x<Y+-1> ...
- 如果|intersection(placements[x,y], dissmissed)|==33，即只有一种可能的放置方式，则添加船只（参见后面）
检查任何先前的命中是否只剩下一种可能的放置方式，如果是，则添加船只
检查是否有任何船只只有一种可能的放置方式，如果是，则添加船只

添加一艘船：

将该船的所有其他放置方式添加到dissmissed中
对于该船的每个（x，y），将placements[x,y]添加到不包含实际放置方式的位置
对于该船的每个（x，y）在其放置方式上标记为命中猜测（如果尚未知晓），并运行第二阶段
对于该船的每个相邻的（x，y），将其标记为未命中猜测（如果尚未知晓），并运行第一阶段
运行第三和第四阶段。

我可能过于复杂了，可能存在一些冗余的操作，但您明白我的意思。