// exhaustive search othello game history with iterative deeping method // version 0.6: // The usage of the program and the summery of this algorithm // are written in the last of this file. #include #include // for malloc() #include // for time() #include // for memcpy() // (number of histories at the depth t) = histories[t][1] * RADIX + histories[t][0] #define RADIX 1000000000 // constant value // charactors for board debugging static const char *EMPTYCELL = "--"; static const char *BLACKSTONE = "##"; static const char *WHITESTONE = "[]"; static const char *MARK = "++"; // static variables static char maxmobility[61]; // max of mobility at the turn t static unsigned long int histories[61][2]; // number of histories at the turn t static unsigned long int passends[61]; // number of pass-end at the turn t static unsigned long int passes[61]; // number of passes at the turn t // print board into STDOUT void printboard(char *b){ int x,y; for(y=1;y<9;y++){ for(x=1;x<9;x++){ switch(b[x*9+y]){ case 1:printf("%s",BLACKSTONE);break; case 2:printf("%s",WHITESTONE);break; default: printf("%s",EMPTYCELL);break; } } printf("\n"); } printf("\n"); } // print board and mark (x,y) into STDOUT void printboard2(char *b,int xx,int yy){ int x,y; for(y=1;y<9;y++){ for(x=1;x<9;x++){ if(x==xx && y==yy){ printf("%s",MARK); }else{ switch(b[x*9+y]){ case 1:printf("%s",BLACKSTONE);break; case 2:printf("%s",WHITESTONE);break; default: printf("%s",EMPTYCELL);break; } } } printf("\n"); } printf("\n"); } // recursive deeping function // param: // b = input board table // turn = color of the stone put at the turn // t = input depth of the search // ispass = whether pass is occurred at b // (sx,sy)--(ex,ey) = rectangle window needed in search void seekput(char *b, char turn, char t, char tmax, char ispass){ // (x,y) = tried cell // (kx,ky) = direction of the reversing register int x,y,kx,ky,k,x2; char *b2; // next board in deeping char mobility; // number of puttable empty cells. char isreversible; // flag stone is puttable in b[x][y] or not. char aturn; // next turn // judge of end of deeping if(t>tmax){return;} // make next turn if(turn==1){aturn=2;}else{aturn=1;} // seeking reversible empty cells mobility=0; for(x=1;x<=8;x++){ for(y=1;y<=8;y++){ // try (x,y)-------------------------------- isreversible=0; if(b[x*9+y]==0){ // case that (x,y) is empty for(kx=-1;kx<2;kx++){ for(ky=-1;ky<2;ky++){ // for each direction for(k=1;b[(x+kx*k)*9+y+ky*k]==aturn;k++); if(k>=2 && b[(x+kx*k)*9+y+ky*k]==turn){ // case that puttable empty cells is found if(!isreversible){ // case that (x,y) is the first reversible case for board b // copy b into b2 b2=(char *)malloc(sizeof(char *)*90); memcpy(b2,b,90); } isreversible=1; // put stone into (x,y) b2[x*9+y]=turn; while(k>0){ // reverse stones b2[(x+kx*k)*9+y+ky*k]=turn; k--; } } } } } // end of try (x,y)-------------------------------- // check (x,y) is reversible or not ---------------------- if(isreversible){ // can reverse (b2 has pattern of the next board) // renew static infomation histories[t][0]+=4; if(histories[t][0]==RADIX){ histories[t][0]=0; histories[t][1]++; } mobility++; if(mobility>maxmobility[t]){ maxmobility[t] = mobility; } // deeping seekput(b2,aturn,t+1,tmax,0); // free memoryfield for the pattern of the next board free(b2); } // backtruck } } // seeking is over in the all board. if(mobility==0){ // stone cannot be put on the any empty cells if(!ispass){ // no pass occurred in previous turn passes[t-1]+=4; seekput(b,aturn,t,tmax ,1); // deeping }else{ //cannot put both turn passends[t-1]+=4; } } } int main(int argc,char **argv){ int x,y,t,tmax; char *b; unsigned long int time0,time1; // start time and end time of the search in [ms] if(argc<1){ exit(-1); } tmax=atoi(argv[1]); // initializing board and static variables // into the board in which black is put E3 for(t=0;t<=tmax;t++){ histories[t][0]=0; histories[t][1]=0; passends[t]=0; passes[t]=0; maxmobility[t]=0; } b=(char *)malloc(sizeof(char *)*90); for(x=0;x<9;x++){ for(y=0;y<9;y++){ b[x*9+y]=0; } } b[32]=1; b[40]=1;b[41]=1; b[49]=2;b[50]=1; histories[1][0]=4; maxmobility[1]=4; passends[1]=0; passes[1]=0; time0=clock(); // start deeping from t=2, turn=2 seekput(b,2,2,tmax,0); time1=clock()-time0; // output results into STDOUT for(t=1;t<=tmax;t++){ printf("t=%2d,",t); printf("m=%2d,",maxmobility[t]); if(histories[t][1]>0){ printf("h=%9d%09d ",histories[t][1],histories[t][0]); }else{ printf("h= %9d ",histories[t][0]); } printf("p=%9d ",passes[t]); printf("e=%9d\n",passends[t]); } printf("(time = %2.2f [s] , %2.2f [min] , %2.2f [h] ) \n",((double)time1)/1000.0,((double)time1)/1000.0/60.0,((double)time1)/1000.0/60.0/60.0); printf("(speed = %4.2f [ns/paths]) \n",((double)time1)/(((double)histories[tmax][1])*RADIX+((double)histories[tmax][0]))*1000000.0); return 0; } // Summery of this algorithm: // // (1) charactoristics of the algorithm: // * board is implemented with 1 dimension array [v0.6] // * 1/4 synmetric pruning on first turn [v0.5] // // (2) semantics: // * board b[x*9+y] = {0=empty, 1=black, 2=white} // * x=0--9 (0=out of the board, 1--8 = 'A'--'F') // * y=0--9 (0=out of the board, 1--8 = '1'--'8') // * t = (depth of the tree) = 60 - (number of all stones on the board, even if any passes are occurred in histories) // // (3) flow: // deeping(board){ // if(depth is over max value){return} // for all empty cells{ // if(puttable){ // count up number of histories and mobility; // put and deeping(next board); // } // } // if not puttable in any empty cells and pass is not occured -> count up number of passes and deeping(pass) // if not puttable in any empty cells and pass is not occured -> count up number of pass-ends // } // // (4) Usage of the program: // idothello [N] // param: // N = max depth of search