海战棋的最佳策略

KeyTo9_Fans · 发表于 2021-11-24 09:49:44

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

海战棋是一个双人的非完全信息博弈，简单来说就是猜对方的船只在哪儿。

开战前双方在10乘10的格子阵中，摆放1搜长度为4的船只、2搜长度为3的船只、3搜长度为2的船只、4搜长度为1的船只，共计10艘船占20个格子。

摆放的船只不能紧邻（占领的格子不能有公共边），也不能对角相邻（占领的格子不能有公共点）。

这是一种可行的摆法（蓝色矩形表示船只）：

双方都摆好后，就轮流轰炸对方阵地。

对于每轮轰炸，都是选择对方阵地中的1个格子进行轰炸，

如果轰炸的格子有船只，则可以继续另选格子进行轰炸，

直到轰炸的格子没有船只为止，本轮轰炸结束。

如果某艘船所占的格子都被轰炸过，则必须立即把这艘船亮出来，然后这艘船周围一圈的格子都无需再轰炸。

先把对方10艘船所占的20个格子都轰炸完的一方获胜。

在这个网站上，无需注册账号就可以玩这个游戏：

http://zh.battleship-game.org

本贴希望编程解决以下问题：

问题1：我方有多少种摆法？

问题2：分别以多大的概率选择每种摆法，可以使得对方轰炸的轮数的期望值达到最大（假设对方使用最佳策略轰炸）？

问题3：我方应如何轰炸对方阵地，可以使得轰炸所需轮数的期望值达到最小（假设对方使用最佳策略摆船）？

问题4：当双方都使用纳什均衡策略进行摆船和轰炸时，先手的胜率是多少？

KeyTo9_Fans · 发表于 2021-12-3 23:33:33

我从$2^6*10^20$种摆法中，随机抽取了$2240000000$种摆法进行判断，结果仅有$187391$种摆法是合规摆法，

因此可以估算出我方有$2^6*10^20*187391/2240000000\approx 5.354*10^17$种摆法。

这是按$10$艘船都不一样来计算的摆法数。

实际上有些船是一样的，所以摆法数没那么多。

ejsoon · 发表于 2021-12-17 11:01:21

這是一個紙筆遊戲，參見這個網站。

這個遊戲的船隻數量有很多版本，樓主的那個版本比較少見，因為一個格子的船太多了。一個格子的比較難打中。

從遊戲設計的角度考慮，最需要測試的是，到底船隻數量及大小如何安排比較合理。大船容易被打中的同時，它也排除了週邊水域。

mathe · 发表于 2022-8-26 15:53:35

我计算出来的状态数目是5429981475002236 （没有考虑旋转翻转等对称性),动态规划计算时间在10分钟左右，就是比较难验证代码的正确性。但是数目和Fans的估算还是偏差比较大，大概3倍关系。
程序可以顺便统计出最后一行状态的分布，比如
UC{ 4 3 2 1 } -20-21E  |21E  |32E  |32E  |43是22364483种
UC{ 4 3 2 1 } E  |21E  |21E  |32E  |32E  |43是18181372种，
其中UC {4 3 2 1}代表四种长度的船分别使用了4,3,2,1只。最后一行中E  代表这个格子是空的|21代表这个格子是一个竖排的船，长度为2，这个格子在船上编号从上到下为1（第一格编号为0）。-20-21代表一个横排的长度为2的船。

mathe · 发表于 2022-8-26 16:44:16

修正了一个bug,每个格子前面考虑了上面，左边，左上的格子，但是忘了考虑右上格子也必须空时才能非空。
修正后计算出来数目为2140733320018399，折算成Fans的估算数目约$6.165\times10^{17}$

#include <stdio.h>
#include <time.h>
#include <map>
#define N 10
#define EMPT 0
#define B1 1
#define B2H 2
#define B2L 3
#define B3H 4
#define B3L 5
#define B4H 6
#define B4L 7
std::map<long,long> s2c[2];
static char bsbits[4]={7,3,3,1};
static char bsstart[4]={0,3,5,7};
struct DS{
char uc[4];
char bs[N+1];
};
int getuc(long v, int bs)
{
int r=(v>>55)&255;
return (r>>bsstart[bs])&bsbits[bs];
}
long setuc(long v,int bs, int s)
{
int off=55+bsstart[bs];
v&=~(((1L<<bsbits[bs])-1)<<off);
v|=((long)s)<<off;
return v;
}
int getposstat(long v, int k)
{
return (v>>(k*5))&31;
}
long setposstat(long v, int k, int s)
{
int off=k*5;
v&=~(31L<<off);
v|=(long)s<<off;
return v;
}
int getstattype(int s)
{
return (s>>2)&7;
}
int getstatoff(int s)
{
return s&3;
}
int createstat(int type, int off)
{
return (type<<2)|off;
}
void decode(long v, DS& ds)
{
int i;
for(i=0;i<4;i++)ds.uc[i]=getuc(v,i);
for(i=0;i<N+1;i++)ds.bs[i]=getposstat(v,i);
}
long encode(const DS& ds)
{
long v=0L;
int i;
for(i=0;i<4;i++)v=setuc(v,i,ds.uc[i]);
for(i=0;i<N+1;i++)v=setposstat(v,i,ds.bs[i]);
return v;
}
#define CS(t,o) createstat(t,o)
void outds(const DS& ds)
{
int i;
printf("UC{");
for(i=0;i<4;i++){printf(" %d", ds.uc[i]);}
printf(" } ");
for(i=0;i<N+1;i++){
if(ds.bs[i]==CS(EMPT,0))printf("E ");
else printf("%c%d%d",getstattype(ds.bs[i])&1?'|':'-',getstattype(ds.bs[i])/2+1,getstatoff(ds.bs[i]));
}
printf("\n");
}
void init0()
{
long x=0;//all empty
int i,j;
DS ds;
for(i=0;i<8;i++){//all 8 stattype
ds.uc[0]=ds.uc[1]=ds.uc[2]=ds.uc[3]=0;
for(j=0;j<N+1;j++)ds.bs[j]=0;
int s = CS(i,0); //The first block in stat s
x = 0;
ds.bs[0]=s;
if(i!=EMPT){
int uc=i>>1;
ds.uc[i>>1]=1;
}
s2c[0].insert(std::make_pair(encode(ds),1));
}
}
#ifdef DEBUG
#define DUMP(a,b,c) dump(a,b,c)
#else
#define DUMP(a,b,c)
#endif
void dump(int id, const DS& dsf, const DS& dst)
{
printf("(%d,%d)\n",id/N,id%N);
printf("FROM ");outds(dsf);
printf("TO ");outds(dst);
printf("\n");
}
int main()
{
int i;
DS ds1,ds2;
time_t t=time(NULL);
init0();
std::map<long,long>::iterator mit;
for(i=1;i<=N*N-1;i++){
s2c[i%2].clear();
for(mit=s2c[(i-1)%2].begin();mit!=s2c[(i-1)%2].end();++mit){
decode(mit->first,ds1);
// printf("from ");outds(ds1);
int nexttype=-1;
if(i>=N){
int os=ds1.bs[i%N];
int st =getstattype(os);
int sp = getstatoff(os);
if(st>=B1)nexttype=CS(EMPT,0);
if(st>=B2H&&(st&1)){//lie
if(sp<(st/2)){
nexttype=CS(st,sp+1);
}
}
}
if(i%N>0){
int os=ds1.bs[i%N-1];
int st = getstattype(os);
int sp = getstatoff(os);
if(getstattype(ds1.bs[N])!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(i%N<N-1&&getstattype(ds1.bs[i%N+1])!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(st>=B1){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
if(st>=B2H&&!(st&1)){//hang
if(sp<(st/2)){
if(nexttype>=0)continue;
nexttype=CS(st,sp+1);
}
}
if(nexttype<0)nexttype=CS(EMPT,0);
}
}
if(nexttype>=0){
ds2=ds1;
ds2.bs[i%N]=nexttype;
if(i%N==N-1){
ds2.bs[N]=CS(EMPT,0);
}else{
ds2.bs[N]=ds1.bs[i%N];
}
long v = encode(ds2);
s2c[i%2][v]+=mit->second;
DUMP(i,ds1,ds2);
}else{
int j;
for(j=0;j<8;j++){//try put stattype j
int s = CS(j,0); //The block i in stat s
ds2=ds1;
if(j>=B2H){
if(j&1){
if(i/N+(j/2)+1>N)continue;
}else{
if(i%N+(j/2)+1>N)continue;
}
}
ds2.bs[i%N]=s;
if(i%N==N-1){
ds2.bs[N]=CS(EMPT,0);
}else{
ds2.bs[N]=ds1.bs[i%N];
}
if(j>0){
int cc=j/2;
if(ds2.uc[cc]+cc>=4)continue;
ds2.uc[cc]++;
}
long v=encode(ds2);
s2c[i%2][v]+=mit->second;
DUMP(i,ds1,ds2);
}
}
}
long time_diff = time(NULL)-t;
printf("Total %ld stats for level %d (%ld s)\n",s2c[i%2].size(),i,time_diff);
fflush(stdout);
}
long total=0;
for(mit=s2c[(N-1)&1].begin();mit!=s2c[(N-1)&1].end();++mit){
printf("status %lx count %ld\n",mit->first, mit->second);
decode(mit->first,ds1);
outds(ds1);
for(i=0;i<4;i++){
if(ds1.uc[i]+i!=4)break;
}
if(i<4)continue;
for(i=0;i<N;i++){
if(getstattype(ds1.bs[i])&1){//lie
if(getstattype(ds1.bs[i])/2!=getstatoff(ds1.bs[i]))break;
}
}
if(i<N)continue;
total+=mit->second;
}
printf("Total %ld\n",total);
}

复制代码

而7*7的格子放置同样多的海船将只有694381种，可以全部输出用于验证代码的正确性

6x6:  0    (0s)
7x7:  694381    (4s)
8x8:  29346468159       (32s)
9x9:  19523498027639    (158s)
10x10:2140733320018399    (663s)

mathe · 发表于 2022-8-27 11:10:24

更新一个代码，可以将7x7的所有解输出来，比如：

代码编译时通过编译选项-DDALL可以将所有解输出

#include <stdio.h>
#include <time.h>
#include <map>
#include <vector>
#define N 7
#define EMPT 0
#define B1 1
#define B2H 2
#define B2L 3
#define B3H 4
#define B3L 5
#define B4H 6
#define B4L 7
std::map<long,long> s2c[N*N];
#ifdef DALL
std::map<long, long> prev[N*N];
#endif
static char bsbits[4]={7,3,3,1};
static char bsstart[4]={0,3,5,7};
struct DS{
char uc[4];
char bs[N+1];
};
int getuc(long v, int bs)
{
int r=(v>>55)&255;
return (r>>bsstart[bs])&bsbits[bs];
}
long setuc(long v,int bs, int s)
{
int off=55+bsstart[bs];
v&=~(((1L<<bsbits[bs])-1)<<off);
v|=((long)s)<<off;
return v;
}
int getposstat(long v, int k)
{
return (v>>(k*5))&31;
}
long setposstat(long v, int k, int s)
{
int off=k*5;
v&=~(31L<<off);
v|=(long)s<<off;
return v;
}
int getstattype(int s)
{
return (s>>2)&7;
}
int getstatoff(int s)
{
return s&3;
}
int createstat(int type, int off)
{
return (type<<2)|off;
}
void decode(long v, DS& ds)
{
int i;
for(i=0;i<4;i++)ds.uc[i]=getuc(v,i);
for(i=0;i<N+1;i++)ds.bs[i]=getposstat(v,i);
}
long encode(const DS& ds)
{
long v=0L;
int i;
for(i=0;i<4;i++)v=setuc(v,i,ds.uc[i]);
for(i=0;i<N+1;i++)v=setposstat(v,i,ds.bs[i]);
return v;
}
#define CS(t,o) createstat(t,o)
void outds(const DS& ds, int ne=0)
{
int i;
if(ne==0){
printf("UC{");
for(i=0;i<4;i++){printf(" %d", ds.uc[i]);}
printf(" } ");
}
for(i=0;i<N+1;i++){
if(ne&&i==N)break;
if(ds.bs[i]==CS(EMPT,0))printf("E ");
else printf("%c%d%d",getstattype(ds.bs[i])&1?'|':'-',getstattype(ds.bs[i])/2+1,getstatoff(ds.bs[i]));
}
printf("\n");
}
void init0()
{
long x=0;//all empty
int i,j;
DS ds;
for(i=0;i<8;i++){//all 8 stattype
ds.uc[0]=ds.uc[1]=ds.uc[2]=ds.uc[3]=0;
for(j=0;j<N+1;j++)ds.bs[j]=0;
int s = CS(i,0); //The first block in stat s
x = 0;
ds.bs[0]=s;
if(i!=EMPT){
int uc=i>>1;
ds.uc[i>>1]=1;
}
s2c[0].insert(std::make_pair(encode(ds),1));
}
}
#ifdef DEBUG
#define DUMP(a,b,c) dump(a,b,c)
#else
#define DUMP(a,b,c)
#endif
void dump(int id, const DS& dsf, const DS& dst)
{
printf("(%d,%d)\n",id/N,id%N);
printf("FROM ");outds(dsf);
printf("TO ");outds(dst);
printf("\n");
}
#ifdef DALL
#define IM1 (i-1)
#define NM1 (N*N-1)
#define I (i)
std::vector<long> status_stack;
void outputresult()
{
int i;
for(i=status_stack.size()-1;i>=0;i--){
DS ds1;
decode(status_stack[i],ds1);
outds(ds1,1);
}
printf("\n");
}
void trace(long status, int level)
{
int i,j;
if(level%N==N-1){
status_stack.push_back(status);
if(level==N-1){
outputresult();
status_stack.pop_back();
return;
}
}
if(level==0)return;
std::map<long, long>::iterator mit;
DS ds1, ds2;
{
decode(status, ds1);
mit = prev[level].find(status);
for(i=0;i<64;i++){
if(mit->second&(1L<<i)){
int vN=i/8;
int vi=i%8;
ds2=ds1;
if(vi<=1){
ds2.bs[level%N]=CS(vi,0);
}else if(vi&1){//lie
if(getstattype(ds1.bs[level%N])==vi){
ds2.bs[level%N]=CS(vi, getstatoff(ds1.bs[level%N])-1);
}else{
ds2.bs[level%N]=CS(vi, vi/2);
}
}else{//hang
if(level%N==N-1||getstattype(ds1.bs[(level+1)%N])!=vi){
ds2.bs[level%N]=CS(vi, vi/2);
}else{
ds2.bs[level%N]=CS(vi, getstatoff(ds1.bs[(level+1)%N])-1);
}
}
if(level%N==0){
ds2.bs[N]=0;
}else if(vN<=1){
ds2.bs[N]=CS(vN,0);
}else if(vN&1){//lie
if(getstattype(ds1.bs[(level-1)%N])==vN){
ds2.bs[N]=CS(vN, getstatoff(ds1.bs[(level-1)%N])-1);
}else{
ds2.bs[N]=CS(vN, vN/2);
}
}else{//hang
if(getstattype(ds2.bs[level%N])==vN){
ds2.bs[N]=CS(vN, getstatoff(ds2.bs[level%N])-1);
}else{
ds2.bs[N]=CS(vN, vN/2);
}
}
if(getstattype(ds1.bs[level%N])>0 && getstatoff(ds1.bs[level%N])==0){
ds2.uc[getstattype(ds1.bs[level%N])/2]--;
}
long v=encode(ds2);
std::map<long, long>::iterator mit2;
mit2 = s2c[level-1].find(v);
if(mit2 != s2c[level-1].end()){
trace(mit2->first, level-1);
}else{
printf("Invalid reverse finding:\n");
DUMP(level-1,ds2,ds1);
}
}
}
}
if(level%N==N-1){
status_stack.pop_back();
}
}
#else
#define IM1 ((i-1)%2)
#define NM1 ((N-1)%2)
#define I ((i)%2)
#endif
int main()
{
int i;
DS ds1,ds2;
time_t t=time(NULL);
init0();
std::map<long,long>::iterator mit;
for(i=1;i<=N*N-1;i++){
#ifndef DALL
s2c[i%2].clear();
#endif
for(mit=s2c[IM1].begin();mit!=s2c[IM1].end();++mit){
decode(mit->first,ds1);
// printf("from ");outds(ds1);
int nexttype=-1;
if(i>=N){
int os=ds1.bs[i%N];
int st =getstattype(os);
int sp = getstatoff(os);
if(st>=B1)nexttype=CS(EMPT,0);
if(st>=B2H&&(st&1)){//lie
if(sp<(st/2)){
nexttype=CS(st,sp+1);
}
}
}
if(i%N>0){
int os=ds1.bs[i%N-1];
int st = getstattype(os);
int sp = getstatoff(os);
if(getstattype(ds1.bs[N])!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(i%N<N-1&&getstattype(ds1.bs[i%N+1])!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(st>=B1){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
if(st>=B2H&&!(st&1)){//hang
if(sp<(st/2)){
if(nexttype>=0)continue;
nexttype=CS(st,sp+1);
}
}
if(nexttype<0)nexttype=CS(EMPT,0);
}
}
if(nexttype>=0){
ds2=ds1;
ds2.bs[i%N]=nexttype;
int pvs = 0;
pvs=getstattype(ds1.bs[N])*8+getstattype(ds1.bs[i%N]);
if(i%N==N-1){
ds2.bs[N]=CS(EMPT,0);
}else{
ds2.bs[N]=ds1.bs[i%N];
}
long v = encode(ds2);
s2c[I][v]+=mit->second;
#ifdef DALL
prev[I][v]|=1L<<pvs;
#endif
DUMP(i,ds1,ds2);
}else{
int j;
int pvs = getstattype(ds1.bs[N])*8+getstattype(ds1.bs[i%N]);
for(j=0;j<8;j++){//try put stattype j
int s = CS(j,0); //The block i in stat s
ds2=ds1;
if(j>=B2H){
if(j&1){
if(i/N+(j/2)+1>N)continue;
}else{
if(i%N+(j/2)+1>N)continue;
}
}
ds2.bs[i%N]=s;
if(i%N==N-1){
ds2.bs[N]=CS(EMPT,0);
}else{
ds2.bs[N]=ds1.bs[i%N];
}
if(j>0){
int cc=j/2;
if(ds2.uc[cc]+cc>=4)continue;
ds2.uc[cc]++;
}
long v=encode(ds2);
s2c[I][v]+=mit->second;
#ifdef DALL
prev[I][v]|=1L<<pvs;
#endif
DUMP(i,ds1,ds2);
}
}
}
long time_diff = time(NULL)-t;
printf("Total %ld stats for level %d (%ld s)\n",s2c[I].size(),i,time_diff);
fflush(stdout);
}
long total=0;
for(mit=s2c[NM1].begin();mit!=s2c[NM1].end();++mit){
#ifndef DALL
printf("status %lx count %ld\n",mit->first, mit->second);
#endif
decode(mit->first,ds1);
#ifndef DALL
outds(ds1);
#endif
for(i=0;i<4;i++){
if(ds1.uc[i]+i!=4)break;
}
if(i<4)continue;
for(i=0;i<N;i++){
if(getstattype(ds1.bs[i])&1){//lie
if(getstattype(ds1.bs[i])/2!=getstatoff(ds1.bs[i]))break;
}
}
if(i<N)continue;
#ifdef DALL
trace(mit->first, NM1);
#endif
total+=mit->second;
}
printf("Total %ld\n",total);
}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 海战棋的最佳策略

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。