18

I made the original battleship and now I'm looking to upgrade my AI from random guessing to guessing statistically probably locations. I'm having trouble finding algorithms online, so my question is what kinds of algorithms already exist for this application? And how would I implement one?

Ships: 5, 4, 3, 3, 2

Field: 10X10

Board:

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

If you'd like to see the rest of the code, I posted it here: (https://github.com/Dbz/Battleship/blob/master/BattleShip.py); I didn't want to clutter the question with a lot of irrelevant code.

4

4 回答 4

5

最终的天真的解决方案是检查所有可能的船只放置（在已知信息的情况下是合法的）并计算每个方格被填满的次数。

显然，在一个相对空的棋盘中，由于排列太多，这是行不通的，但一个好的开始可能是：

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

如果其余船只可以合法放置，同时涵盖所有已知的“命中”（已知包含船只的地方），则改进可能是还检查每个可能的船只放置。

为了提高性能，如果只能将一艘船放置在给定地点，则不再需要在其他地点进行测试。此外，当有许多“命中”时，首先覆盖所有已知的“命中”可能会更快，然后为每个可能的覆盖遍历其余部分。

编辑：您可能想查看 DFS。

编辑：在评论中详细说明 OP (@Dbz) 的建议：持有一组已取消的船舶放置 ('dismissed')（可以表示为字符串，例如"4V5x3"在 5x3、5x4、5x5、5x6 中放置长度为 4 的船舶)，在猜测之后，您添加所有猜测取消的展示位置，然后对于每个正方形保存一组与其相交的展示位置 ('placements[x,y]')，那么概率将是： 34-|intersection(placements[x,y], dissmissed)|/(3400-|dismissed|)

要添加到已解雇列表：

  1. 如果在 (X,Y) 处的猜测是未命中添加placements[x,y]
  2. 如果对 (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>...
    • if |intersection(placements[x,y], dissmissed)|==33，即只有一个位置可能添加船（见下文）
  3. 检查任何预览命中是否只剩下一个可能的位置，如果是，添加船
  4. 检查是否有任何船只只有可能的位置，如果有，添加船只

添加船：

  • 将该船的所有其他位置添加到已解雇
  • 对于船舶放置的每个 (x,y)，添加placements[x,y]没有实际放置
  • 对于每个 (x,y) 的船舶放置标记作为命中猜测（如果还不知道）运行阶段 2
  • 对于与船舶放置标记相邻的每个 (x,y) 作为未猜测（如果还不知道）运行阶段 1
  • 运行阶段 3 和 4。

我可能对此过于复杂，可能会有一些多余的动作，但你明白了。

于 2013-07-29T04:46:41.520 回答
2

好问题，我喜欢你对统计方法的想法。
我想我会尝试一种机器学习方法来解决这个问题，如下所示：

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

接下来，您需要开发一些“功能”。您可以将(x,y)[as you may have part knowledge on it] 的周围环境作为您的特征。

比如下面这个小板中间的特征（+表示要判断是否有船的方格）：

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。起初，射击会有点随机——但随着你射击的次数越多，你将在棋盘上获得更多信息，人工智能将利用它来做出更好的预测。

请注意，我给出了基于大小为 1 的正方形的特征。您当然可以选择任何一个k并在这个更大的正方形上查找特征 - 它会为您提供更多特征，但每个特征可能信息量较少。没有经验法则会更好——应该对其进行测试。

于 2013-07-29T09:59:05.457 回答
1
  • 找出哪些船还活着：alive = [2,2,3,4] # 活着的船的长度
  • 找出你没有拍摄的地方，例如使用 numpy.where()
  • 环游可以拍摄的地点。
  • 检查给定位置的侧面。左右走，多少格？上上下下，多少格？如果你能在这么多空间里装一艘船，你就可以装下任何更小的船，所以这个循环我会从最大的船向下做，我会在这个位置添加与更小的船一样多的 +1比适合的那个。
  • 一旦你完成了所有这些，得分更多的位置应该是最有可能攻击和击中东西的位置。

当然，它可以变得任意复杂。您也可以问自己，而不是我的下一个命中，哪些命中组合将使我在更少的命中或问题的任何其他组合/参数化中获得胜利。祝你好运！

于 2013-08-02T12:17:40.220 回答
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，你就有了要命中的坐标。

这可以通过预先计算每行的累积权重来优化，玩得开心:)

于 2013-07-29T01:34:08.110 回答