海战棋的最佳策略
海战棋是一个双人的非完全信息博弈，简单来说就是猜对方的船只在哪儿。开战前双方在10乘10的格子阵中，摆放1搜长度为4的船只、2搜长度为3的船只、3搜长度为2的船只、4搜长度为1的船只，共计10艘船占20个格子。
摆放的船只不能紧邻（占领的格子不能有公共边），也不能对角相邻（占领的格子不能有公共点）。
这是一种可行的摆法（蓝色矩形表示船只）：
双方都摆好后，就轮流轰炸对方阵地。
对于每轮轰炸，都是选择对方阵地中的1个格子进行轰炸，
如果轰炸的格子有船只，则可以继续另选格子进行轰炸，
直到轰炸的格子没有船只为止，本轮轰炸结束。
如果某艘船所占的格子都被轰炸过，则必须立即把这艘船亮出来，然后这艘船周围一圈的格子都无需再轰炸。
先把对方10艘船所占的20个格子都轰炸完的一方获胜。
在这个网站上，无需注册账号就可以玩这个游戏：
http://zh.battleship-game.org
本贴希望编程解决以下问题：
问题1：我方有多少种摆法？
问题2：分别以多大的概率选择每种摆法，可以使得对方轰炸的轮数的期望值达到最大（假设对方使用最佳策略轰炸）？
问题3：我方应如何轰炸对方阵地，可以使得轰炸所需轮数的期望值达到最小（假设对方使用最佳策略摆船）？
问题4：当双方都使用纳什均衡策略进行摆船和轰炸时，先手的胜率是多少？ 我从$2^6*10^20$种摆法中，随机抽取了$2240000000$种摆法进行判断，结果仅有$187391$种摆法是合规摆法，
因此可以估算出我方有$2^6*10^20*187391/2240000000\approx 5.354*10^17$种摆法。
这是按$10$艘船都不一样来计算的摆法数。
实际上有些船是一样的，所以摆法数没那么多。
這是一個紙筆遊戲，參見這個網站。
這個遊戲的船隻數量有很多版本，樓主的那個版本比較少見，因為一個格子的船太多了。一個格子的比較難打中。
從遊戲設計的角度考慮，最需要測試的是，到底船隻數量及大小如何安排比較合理。大船容易被打中的同時，它也排除了週邊水域。 我计算出来的状态数目是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的船。
修正了一个bug,每个格子前面考虑了上面，左边，左上的格子，但是忘了考虑右上格子也必须空时才能非空。
修正后计算出来数目为2140733320018399，折算成Fans的估算数目约$6.165\times10^{17}$
#include <stdio.h>
#include <time.h>
#include <map>
#define N 10
#define EMPT0
#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;
static char bsbits={7,3,3,1};
static char bsstart={0,3,5,7};
struct DS{
char uc;
char bs;
};
int getuc(long v, int bs)
{
int r=(v>>55)&255;
return (r>>bsstart)&bsbits;
}
long setuc(long v,int bs, int s)
{
int off=55+bsstart;
v&=~(((1L<<bsbits)-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=getuc(v,i);
for(i=0;i<N+1;i++)ds.bs=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);
for(i=0;i<N+1;i++)v=setposstat(v,i,ds.bs);
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);}
printf(" } ");
for(i=0;i<N+1;i++){
if(ds.bs==CS(EMPT,0))printf("E");
else printf("%c%d%d",getstattype(ds.bs)&1?'|':'-',getstattype(ds.bs)/2+1,getstatoff(ds.bs));
}
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=ds.uc=ds.uc=ds.uc=0;
for(j=0;j<N+1;j++)ds.bs=0;
int s = CS(i,0); //The first block in stat s
x = 0;
ds.bs=s;
if(i!=EMPT){
int uc=i>>1;
ds.uc=1;
}
s2c.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.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;
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;
int st = getstattype(os);
int sp = getstatoff(os);
if(getstattype(ds1.bs)!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(i%N<N-1&&getstattype(ds1.bs)!=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=nexttype;
if(i%N==N-1){
ds2.bs=CS(EMPT,0);
}else{
ds2.bs=ds1.bs;
}
long v = encode(ds2);
s2c+=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=s;
if(i%N==N-1){
ds2.bs=CS(EMPT,0);
}else{
ds2.bs=ds1.bs;
}
if(j>0){
int cc=j/2;
if(ds2.uc+cc>=4)continue;
ds2.uc++;
}
long v=encode(ds2);
s2c+=mit->second;
DUMP(i,ds1,ds2);
}
}
}
long time_diff = time(NULL)-t;
printf("Total %ld stats for level %d (%ld s)\n",s2c.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!=4)break;
}
if(i<4)continue;
for(i=0;i<N;i++){
if(getstattype(ds1.bs)&1){//lie
if(getstattype(ds1.bs)/2!=getstatoff(ds1.bs))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)
更新一个代码，可以将7x7的所有解输出来，比如：
代码编译时通过编译选项-DDALL可以将所有解输出
#include <stdio.h>
#include <time.h>
#include <map>
#include <vector>
#define N 7
#define EMPT0
#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;
#ifdef DALL
std::map<long, long> prev;
#endif
static char bsbits={7,3,3,1};
static char bsstart={0,3,5,7};
struct DS{
char uc;
char bs;
};
int getuc(long v, int bs)
{
int r=(v>>55)&255;
return (r>>bsstart)&bsbits;
}
long setuc(long v,int bs, int s)
{
int off=55+bsstart;
v&=~(((1L<<bsbits)-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=getuc(v,i);
for(i=0;i<N+1;i++)ds.bs=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);
for(i=0;i<N+1;i++)v=setposstat(v,i,ds.bs);
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);}
printf(" } ");
}
for(i=0;i<N+1;i++){
if(ne&&i==N)break;
if(ds.bs==CS(EMPT,0))printf("E");
else printf("%c%d%d",getstattype(ds.bs)&1?'|':'-',getstattype(ds.bs)/2+1,getstatoff(ds.bs));
}
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=ds.uc=ds.uc=ds.uc=0;
for(j=0;j<N+1;j++)ds.bs=0;
int s = CS(i,0); //The first block in stat s
x = 0;
ds.bs=s;
if(i!=EMPT){
int uc=i>>1;
ds.uc=1;
}
s2c.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,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.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=CS(vi,0);
}else if(vi&1){//lie
if(getstattype(ds1.bs)==vi){
ds2.bs=CS(vi, getstatoff(ds1.bs)-1);
}else{
ds2.bs=CS(vi, vi/2);
}
}else{//hang
if(level%N==N-1||getstattype(ds1.bs[(level+1)%N])!=vi){
ds2.bs=CS(vi, vi/2);
}else{
ds2.bs=CS(vi, getstatoff(ds1.bs[(level+1)%N])-1);
}
}
if(level%N==0){
ds2.bs=0;
}else if(vN<=1){
ds2.bs=CS(vN,0);
}else if(vN&1){//lie
if(getstattype(ds1.bs[(level-1)%N])==vN){
ds2.bs=CS(vN, getstatoff(ds1.bs[(level-1)%N])-1);
}else{
ds2.bs=CS(vN, vN/2);
}
}else{//hang
if(getstattype(ds2.bs)==vN){
ds2.bs=CS(vN, getstatoff(ds2.bs)-1);
}else{
ds2.bs=CS(vN, vN/2);
}
}
if(getstattype(ds1.bs)>0 && getstatoff(ds1.bs)==0){
ds2.uc)/2]--;
}
long v=encode(ds2);
std::map<long, long>::iterator mit2;
mit2 = s2c.find(v);
if(mit2 != s2c.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.clear();
#endif
for(mit=s2c.begin();mit!=s2c.end();++mit){
decode(mit->first,ds1);
// printf("from ");outds(ds1);
int nexttype=-1;
if(i>=N){
int os=ds1.bs;
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;
int st = getstattype(os);
int sp = getstatoff(os);
if(getstattype(ds1.bs)!=EMPT){
if(nexttype!=-1&&nexttype!=CS(EMPT,0))continue;
nexttype=CS(EMPT,0);
}
if(i%N<N-1&&getstattype(ds1.bs)!=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=nexttype;
int pvs = 0;
pvs=getstattype(ds1.bs)*8+getstattype(ds1.bs);
if(i%N==N-1){
ds2.bs=CS(EMPT,0);
}else{
ds2.bs=ds1.bs;
}
long v = encode(ds2);
s2c+=mit->second;
#ifdef DALL
prev|=1L<<pvs;
#endif
DUMP(i,ds1,ds2);
}else{
int j;
int pvs = getstattype(ds1.bs)*8+getstattype(ds1.bs);
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=s;
if(i%N==N-1){
ds2.bs=CS(EMPT,0);
}else{
ds2.bs=ds1.bs;
}
if(j>0){
int cc=j/2;
if(ds2.uc+cc>=4)continue;
ds2.uc++;
}
long v=encode(ds2);
s2c+=mit->second;
#ifdef DALL
prev|=1L<<pvs;
#endif
DUMP(i,ds1,ds2);
}
}
}
long time_diff = time(NULL)-t;
printf("Total %ld stats for level %d (%ld s)\n",s2c.size(),i,time_diff);
fflush(stdout);
}
long total=0;
for(mit=s2c.begin();mit!=s2c.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!=4)break;
}
if(i<4)continue;
for(i=0;i<N;i++){
if(getstattype(ds1.bs)&1){//lie
if(getstattype(ds1.bs)/2!=getstatoff(ds1.bs))break;
}
}
if(i<N)continue;
#ifdef DALL
trace(mit->first, NM1);
#endif
total+=mit->second;
}
printf("Total %ld\n",total);
}
页:
[1]