C "Battleship"程序在 10k+ 次迭代后的非统计输出

Question

我正在尝试在 http://thevirtuosi.blogspot.com/2011/10/linear-theory-of-battleship.html 复制发现结果.他的发现是，随后较小尺寸的船只的观察/经验概率图迫使它们离开中心，而尺寸增加的船只往往会聚集在那里。尽管他的结果在垂直轴和水平轴之间是对称的，但我编写的代码产生的结果是水平轴在船上的位置明显更多——尽管我正在尽我所能来彻底随机化垂直或水平之间的过程第一的。这种不对称性在任何大小的 map 上都存在。传达问题的最少代码是 171 行。这个论坛适合这个吗？这与家庭作业、工作或类无关。我只是对战舰算法感兴趣。输出是将某艘船放置在某个地点的实际迭代次数、这样的百分比以及这样的 ASCII 字符映射 - 以便更容易地观察不对称性。任何方向表示赞赏。

#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#include <string.h>

int main(void)
{
clock_t start, end;
double cpu_time_used;
srand(time(NULL));
int obstruction;
int done;
int waysVert=0;
int waysHorz=0;
int counter=0;
int vertCounter=0;
int horzCounter=0;
int iGuess=0;
int jGuess=0;
int shipType=0;
int shotCounter=0;
int hitCounter=0;
int shipCellCounter=0;
int guessCounter=0;
int lenShip=0;
int highestProb=0;
int highestOccur=0;
int iteration=0;
int i=0;//x dimension
int j=0;//y dimension
int k=0;//z dimension and information dimension
int n=0;//number dimension
char shipChar;
char shipName[20]="";
char shipList[]="ABCDS";//question for later: How does placement order affect heat map?
int numberShips=strlen(shipList);
int jShipStart=0;
int iShipStart=0;
int polShipDir=0;
int biasShipDir=0;
int jShipDir=0;
int iShipDir=0;
int NUM_COLS=10;//x dimension
int NUM_ROWS=10;//y dimension
int NUM_LEVS=21;//[0,7] Theoretical Prob. [10,16] Empirical Prob. 20 Presentation Level
char                grid[NUM_LEVS][NUM_ROWS][NUM_COLS];
long int empiricalGrid[NUM_LEVS][NUM_ROWS][NUM_COLS];


for(k=0;k<NUM_LEVS;k++){for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){           grid[k][j][i]=0;}}}//initialize 1-byte levels
for(k=0;k<NUM_LEVS;k++){for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){empiricalGrid[k][j][i]=0;}}}//initialize 4-byte levels
k=20;//k=20 is the presentation level
//for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){grid[k][j][i]='~';}}//initialize water character (first time, single run)

start = clock();
for(iteration=0;iteration<50000;iteration++){//has run at 50000000 iteration//could put scaling onto the printout using digit length of iterations
    for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){grid[k][j][i]='~';}}//initialize water character (every time, in loop)

    //PLACEMENT ROUTINE FOR-LOOP AND DO-WHILE LOOP
    for (shipType = 0; shipType < strlen(shipList); shipType++){
        shipChar=shipList[shipType];

        switch(shipChar){
        case 'A':lenShip=5;break;
        case 'B':lenShip=4;break;
        case 'C':lenShip=3;break;
        case 'D':lenShip=2;break;
        case 'S':lenShip=3;break;//since ran out of 3, think low number as in low elevation, beneath any other ships 
        }
        shipCellCounter+=lenShip;
        k=20;

        do{
            jShipStart=0;
            iShipStart=0;
            polShipDir=0;
            biasShipDir=0;
            jShipDir=0;
            iShipDir=0;
            obstruction=0;//printf("\nSet to no obstruction to %d\n",obstruction);
            if(rand()%2==0){
                jShipStart=rand()%NUM_ROWS;//printf("jShipStart %d starting row (0-%d)\n",jShipStart,NUM_ROWS-1);//
                iShipStart=rand()%NUM_COLS;//printf("iShipStart %d starting col (0-%d)\n",iShipStart,NUM_COLS-1);//
            }
            else{
                iShipStart=rand()%NUM_COLS;//printf("iShipStart %d starting col (0-%d)\n",iShipStart,NUM_COLS-1);//
                jShipStart=rand()%NUM_ROWS;//printf("jShipStart %d starting row (0-%d)\n",jShipStart,NUM_ROWS-1);//
            }
            polShipDir  = (rand()%2) * 90;//printf("polShipDir %d degrees\n",polShipDir);//polarity 00 deg => prop horz, 90 = prop vert
            biasShipDir = (rand()%2) * (-2) + 1;//printf("biasShipDir %d\n",biasShipDir);

            if(rand()%2==0){
                if( polShipDir==90 && jShipStart  > lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir==90 && jShipStart <= lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir== 0 && iShipStart  > lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir== 0 && iShipStart <= lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
            }
            else{
                if( polShipDir== 0 && iShipStart <= lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir== 0 && iShipStart  > lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir==90 && jShipStart <= lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
                if( polShipDir==90 && jShipStart  > lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
            }

            for(n=0;n<lenShip;n++){//Check to see if ANY part of the ship runs off map.
                if(rand()%2==0){
                    if( polShipDir== 90 && jShipStart + n * jShipDir >= NUM_ROWS || polShipDir==  0 && iShipStart + n * iShipDir >= NUM_COLS ){
                        obstruction=1;
                    }
                }
                else{
                    if( polShipDir==  0 && iShipStart + n * iShipDir >= NUM_COLS || polShipDir== 90 && jShipStart + n * jShipDir >= NUM_ROWS){
                        obstruction=1;
                    }
                }
            }

            for(n=0;n<lenShip;n++){//Check to see if ANY part of the ship DID NOT hit water.
                if( grid [ k ] [ jShipStart + n * jShipDir ] [ iShipStart + n * iShipDir ] != '~' ){
                obstruction=1;
                }//ANY single obstruction means start over for this ship.
            }

            if(obstruction==0){//If prior loop HAS NOT resulted in ANY obstruction: THEN assign this ship
                for(n=0;n<lenShip;n++){
                    grid [ k ] [ jShipStart + n * jShipDir ] [ iShipStart + n * iShipDir ] = shipChar;
                }
            }
        }
        while(obstruction==1);
    }

    for(i=0;i<NUM_COLS;i++){for(j=0;j<NUM_ROWS;j++){
             if(grid[20][j][i]=='A'){empiricalGrid[15][j][i]++;}
        else if(grid[20][j][i]=='B'){empiricalGrid[14][j][i]++;}
        else if(grid[20][j][i]=='C'){empiricalGrid[13][j][i]++;}
        else if(grid[20][j][i]=='S'){empiricalGrid[10][j][i]++;}//DONT CHANGE THIS RECORD OF SEQUENCE ANYWHERE ELSE. KEEP IT HERE.
        else if(grid[20][j][i]=='D'){empiricalGrid[12][j][i]++;}
        }
    }
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

for(k=16;k>=10;k--){for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){if(highestOccur<=empiricalGrid[k][j][i]){highestOccur=empiricalGrid[k][j][i];}}}}
printf("Level %d Highest occurance = %d\n",k,highestOccur);

for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%10lu", empiricalGrid[15][j][i]);}printf("\n");}printf("A\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%10lu", empiricalGrid[14][j][i]);}printf("\n");}printf("B\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%10lu", empiricalGrid[13][j][i]);}printf("\n");}printf("C\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%10lu", empiricalGrid[12][j][i]);}printf("\n");}printf("D\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%10lu", empiricalGrid[10][j][i]);}printf("\n");}printf("S\n");
printf("Iterations: %d. CPU time used: %lf seconds. CLOCKS_PER_SEC = %d\n",iteration,cpu_time_used,CLOCKS_PER_SEC);

for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2.2lf ", (double) empiricalGrid[15][j][i]/highestOccur);}printf("\n");}printf("A^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2.2lf ", (double) empiricalGrid[14][j][i]/highestOccur);}printf("\n");}printf("B^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2.2lf ", (double) empiricalGrid[13][j][i]/highestOccur);}printf("\n");}printf("C^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2.2lf ", (double) empiricalGrid[12][j][i]/highestOccur);}printf("\n");}printf("D^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2.2lf ", (double) empiricalGrid[10][j][i]/highestOccur);}printf("\n");}printf("S^\n");
printf("Iterations: %d. CPU time used: %lf seconds. CLOCKS_PER_SEC = %d\n",iteration,cpu_time_used,CLOCKS_PER_SEC);

for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2c", 33+(int)(10*((double) empiricalGrid[15][j][i]/highestOccur)));}printf("\n");}printf("A^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2c", 33+(int)(10*((double) empiricalGrid[14][j][i]/highestOccur)));}printf("\n");}printf("B^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2c", 33+(int)(10*((double) empiricalGrid[13][j][i]/highestOccur)));}printf("\n");}printf("C^\n");
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2c", 33+(int)(10*((double) empiricalGrid[10][j][i]/highestOccur)));}printf("\n");}printf("S^\n");//SWITCH BACK
for(j=0;j<NUM_ROWS;j++){for(i=0;i<NUM_COLS;i++){printf("%2c", 33+(int)(10*((double) empiricalGrid[12][j][i]/highestOccur)));}printf("\n");}printf("D^\n");

printf("Iterations: %d. CPU time used: %lf seconds. CLOCKS_PER_SEC = %d\n",iteration,cpu_time_used,CLOCKS_PER_SEC);
printf("!=00s, \"=10s, #=20s, $=30s, %%=40s, &=50s, \'=60s, (=70s, )=80s, *=90s\n");
return 0;
}

Answer 1

我没有看到任何会产生您所说的偏见的错误，但我确实看到了一些不必要的并发症，我可以提供一些建议:

• 正如 wildplasser 在评论中所建议的那样，使用 % 从 C 运行时库 rand() 中提取小的随机数通常会产生非常糟糕的性能。尝试使用 /dev/urandom 之类的更强的 RNG，甚至更好的实际随机性。至少，尝试使用它来播种另一个 RNG。

• 作为快速但非决定性的测试，尝试将 polShipDir = (rand()%2) * 90; 更改为 polShipDir = (1 - rand()%2) * 90;。现在对垂直船有偏见吗？如果是这样，那么问题肯定是 RNG，因为有了好的 RNG，前面两个语句平均应该是等价的。

• 在两个不同的地方，您不必要地随机化执行两个无关紧要的测试的顺序!首先:

(显然需要这一行来格式化......)

if(rand()%2==0){
            if( polShipDir==90 && jShipStart  > lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir==90 && jShipStart <= lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir== 0 && iShipStart  > lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir== 0 && iShipStart <= lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
        }
        else{
            if( polShipDir== 0 && iShipStart <= lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir== 0 && iShipStart  > lenShip-1){ iShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir==90 && jShipStart <= lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
            if( polShipDir==90 && jShipStart  > lenShip-1){ jShipDir=(rand()%2) * (-2) + 1; }
        }

可以简化为

if( polShipDir==90){ jShipDir=(rand()%2) * (-2) + 1; }
if( polShipDir== 0){ iShipDir=(rand()%2) * (-2) + 1; }

其次，在以注释 //Check to see if ANY part of the ship runs out map. 注释开始的循环中也发生了很多相同的事情。 (顺便说一句，你根本不需要这个测试的循环:检查船的起点和终点是否在有效位置就足够了。)