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

Question

我制造了原始战舰,现在我正在寻求将我的AI从随机猜测升级到统计上猜测位置.我无法在线查找算法,所以我的问题是这个应用程序已经存在哪种算法？我将如何实现一个？

船舶: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); 我不想用很多不相关的代码来混淆这个问题.

Answer 1

最终的天真解决方案是通过每个可能的船只放置(合法的,知道什么信息)和计算每个方格已满的次数.

很明显,在一个相对空白的板上,这不会起作用,因为有太多的排列,但一个好的开始可能是:

对于船上的每个方格:通过所有船只并计算它在该方格中适合的方式,即对于每个方格的船长检查它是否适合水平和垂直.

如果其他船舶可以合法放置,同时覆盖所有已知的"撞击"(已知包含船舶的地方),则可以对每个可能的船舶放置进行检查.

为了提高性能,如果只有一艘船可以放置在给定的位置,则不再需要在其他位置进行测试.此外,当有很多"命中"时,首先覆盖所有已知的"命中"可能会更快,并且每个可能的封面都可以通过其余部分.

编辑:您可能想要查看DFS.

编辑:在评论中详细说明OP的(@Dbz)建议:持有一组被驳回的放置('被驳回')船舶(可以表示为字符串,比如说"4V5x3"5x3,5x4,5x5,5x6中长度为4的船的位置),在猜测后你添加了猜测所解释的所有展示位置,然后对于每个正方形保持一组与它相交的展示位置('展示位置[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>...
   • 如果|intersection(placements[x,y], dissmissed)|==33,即只有一个可能的位置添加船(见后)
3. 检查是否有任何预览点击只剩下一个可能的位置,如果是,请添加该船
4. 检查是否有任何船舶只有可能的位置,如果是,请添加船舶

添加船:

• 添加该船的所有其他展示位置以予以解雇
• 对于船舶展示位置的每个(x,y),添加placements[x,y]实际展示位置
• 对于每个(x,y)船舶放置标记作为命中猜测(如果尚未知道)运行阶段2
• 对于每个(x,y)相邻的船舶放置标记作为未命中猜测(如果尚未知道)运行阶段1
• 跑第3和第4阶段.

我可能已经过度复杂了,可能会有一些冗余的动作,但你明白了.