海战棋的最佳策略

SAY

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

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

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

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



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

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

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

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

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

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

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

http://zh.battleship-game.org

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

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

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

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

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

uzmetub

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

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

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

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

akomosuse

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

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

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

edzugxoggixo

我计算出来的状态数目是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的船。

aecupeemow

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

1. #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   7std::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)#endifvoid 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)

agihaku

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

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

1. #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   7std::map<long,long> s2c[N*N];#ifdef DALLstd::map<long, long> prev[N*N];#endifstatic 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)#endifvoid 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)#endifint 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);}

复制代码