海战游戏心得

攻击策略

1.简单贪心策略

最早的这个攻击策略比较暴力，主要考虑的是如果打中了某个船艇，那么就继续攻击邻近区域，直到将这整艘船艇全部击倒为止。

1.1 策略思想

• 如果成功击中敌方船艇，那么击中位置的附近位置出现船艇的概率增大；
• 如果没有成功击中敌方船艇，那么击中位置的附近位置出现船艇的概率减小；

1.2 策略实现

使用一个$10\times10$的权值数组Weight[10][10]，这里的权值就是击中位置出现船艇的概率。我们每次都遍历整个数组，每次都选择权值最大的位置作为击打位置。

初始化 Weight

Weight[10][10]初始化如下：

这样初始化的目的是，保证在打完全部的初始化位置时，至少能打中一艘长度为 5 的大船艇。

击中/未击中

如果击中，就提升击中位置附近位置的权值。由于船艇的长度最大为 5，所以就以 5 为范围由近到远递减增加权值。因为刚才的假设中是认为击中位置的附近更容易再次出现船艇，所以离击中位置越近的位置权值就越高。

如果未击中，那么就相应的减去权值。这里的减权值操作比较暴力，考虑到的条件也不是很多。

当然每次击中的位置都需要记录，这里标记的做法是直接将击中位置的权值Weight[i][j]-=10000，因为棋盘的大小就只有 $10\times10$，而每次我们都选择的是权值最大的位置，所以这样是可以有效标记已击中位置的。

1.3 策略结果

这个策略最终取得了不错的胜率，不过策略中对未击中之后的位置选取考虑的不多，我个人感觉能取得这个胜率的原因可能是大家部署的船艇之间比较接近或者船艇的上下左右几个方向刚好可以直达另一搜船。

2.贪心优化+破坏中心点策略

2.1 策略思想

上面这个策略在击中某个位置的时候，会同时改变单位长度为5的所有位置的权值。可是，如果只是想尽快击溃某一条船的全部位置，其实只需要改变单位为1的位置的权值也能做到。

如图所示，击中任意一个位置之后，其上下左右必然存在另一个可击中点（船艇长度最小也为2），那么当拥有两个相邻击中点之后，我们就已经可以判定出该船艇摆放的方向，之后只在这个方向的两个端点专门攻击即可。

因为船艇的长度最小为2，所以相邻两个击中点的情况是一定会出现的！这么做不仅可以尽快的击溃某一艘船，同时还可以起到标记效果。由于我们在判定船艇方向之后只需要对两端点发起攻击，所以只要出现连续两次未击中的情况，就说明有一艘船艇已经被完全击溃了。

但是这样又会导致另一个问题：击溃一艘船艇之后又该打哪里？ 刚才的策略中虽然半径为5的权值改变策略比较暴力，但是每次至少都有一个最大权值位置可以打（虽说可能不准）；现在这种做法击溃了一艘船艇之后对这艘船艇周围的权值影响的太少了，很多位置的权值几乎都一样，到底打哪？

这里我想到的策略是破坏中心点。在每行每列一定存在很多没有被击打的位置，这里简称之为 和平区域。对于每一行每一列的连续和平区，优先攻击中间位置。（类似二分法）

2.2 策略实现

初始化

还是使用一个$10\times10$的矩阵Weight[10][10]记录权值，这里为避免混淆，增加一个stepMemory[10][10]记录未知状态。对于成功命中的位置，stepMemory[i][j]=1；对于未成功命中的位置，stepMemory[i][j]=-1；对于和平区域，stepMemory[i][j]=0。
这里如果某位置成功命中，那么只有其距离为1的上下左右四个位置的权值+5；同样的，如果没有命中，也只有其距离为1的上下左右四个位置的权值-5。我们每次依旧选择权值最大的位置。

船艇方向判定

这里在判定方向的时候增加了一个 wrong_num，刚才说了只要出现连续两次未击中的情况，就说明有一艘船艇已经被完全击溃了，所以当有两次连续击中的时候，就将 wrong_num=2。当wrong_num=0时，就可以破坏中心点了。

// 这里如果击中点的四周也有击中点，就可以知道方向了
  // 水平方向
  if((lastj>0&&fanz_Step_Memory[lasti][lastj-1]==1)||(lastj<10&&fanz_Step_Memory[lasti][lastj+1]==1)){
   wrong_num==2;
   int cur=lastj;
   while (cur>=0)
   {
    if(fanz_Step_Memory[lasti][cur]==0)break;
    cur--;
   }
   if(cur>=0) Weight[lasti][cur]+=10;
   cur=lastj;
   while (cur<10)
   {
    if(fanz_Step_Memory[lasti][cur]==0) break;
    cur++;
   }
   if(cur<10) Weight[lasti][cur]+=10;
  }

  // 竖直方向
  else if((lasti>0&&fanz_Step_Memory[lasti-1][lastj]==1)||(lasti<10&&fanz_Step_Memory[lasti+1][lastj]==1)){
   wrong_num=2;
   int cur=lasti;
   while (cur>=0)
   {
    if(fanz_Step_Memory[cur][lastj]==0)break;
    cur--;
   }
   if(cur>=0) Weight[cur][lastj]+=10;
   cur=lasti;
   while (cur<10)
   {
    if(fanz_Step_Memory[cur][lastj]==0) break;
    cur++;
   }
   if(cur<10) Weight[cur][lastj]+=10;
  }

破坏中心点实现

这里使用窗口对每一行每一列的连续和平区域的中心点进行破坏，当wrong_num=0时就执行这段代码。

void destoryCenter(){
 // 打破每行连续安全区域的中间位置
 for(int i=0;i<10;i++){
  int start=0;
  for(;start<10;start++){
   if(fanz_Step_Memory[i][start]==0){
    int cur=start;
    while (cur<10)
    {
     if(fanz_Step_Memory[i][cur]!=0) break;
     cur++;
    }
    Weight[i][(start+cur-1)>>1]+=4;
    start=cur;
   }
  }
 }

 // 打破每列连续安全区域的中间位置
 for(int i=0;i<10;i++){
  int start=0;
  for(;start<10;start++){
   if(fanz_Step_Memory[start][i]==0){
    int cur=start;
    while (cur<10)
    {
     if(fanz_Step_Memory[cur][i]!=0) break;
     cur++;
    }

    Weight[(start+cur-1)>>1][i]+=4;
    start=cur;
   }
  }
 }
}

防守策略

关于防守策略我想的不是很多，最开始我想的摆法是这样的：

我最开始的想法是希望五艘船尽可能的处在不同的位置，并且距离尽可能选一些。但是每个人的攻击策略是不一样的，如果有人喜欢先攻击四个对角，那么我会很快损失4艘船。

所以思来想去我也想不到太好的摆法，下图就是我的摆法：