holloway@drivax.UUCP (Bruce Holloway) (03/03/86)
This is a follow up to David desJardin's comments about the game "BATTLESHIP": I wrote a battleship game for my wife last Christmas, and I tried a number of different strategies. The first was the "Monte Carlo" strategy.... pretty awful. The second was the "Every Other Position" strategy. The firing pattern looked like this: o . o . o . o . o o = shots . o . o . o . o . . = empty spaces o . o . o . o . o The specific position was generated randomly, then discarded if it didn't fit into this pattern. It's guaranteed to find every ship on the board. A variant on this strategy had the computer do a diagonal from A1 - J10, and then another from A10 - J1, then continue in the above pattern. This worked slightly better, but was too predictable. The best one I've found so far is the "Every Third Position" strategy, which is guranteed to find every ship but the PT boat. When it runs out of patterned responses, that means that only the PT boat remains to be found, and that any blank space is a possible hiding place, although the intersections of blank spaces are better choices. o . , o . , o . , o o = shots . o . . o . . o . . . = empty spaces . . o . . o . . o . , = more probable spot for PT boat o . . o . . o . . o Even better is to use a strategy randomly to confuse the human player. When placing the computer pieces, it is better to make sure none are adjacent. However, the computer player should be able to exploit the human player doing the same. In my game, the computer sees if any extra hits happened that didn't belong to the ship just sunk, and starts working from these ASAP. Enclosed is the code for my Battleship game.... ---------------------------------------------------------------------------- #include "stdio.h" #define OTHER 1-turn char numbers[] = " 0 1 2 3 4 5 6 7 8 9"; char carrier[] = "Aircraft Carrier"; char battle[] = "Battleship"; char sub[] = "Submarine"; char destroy[] = "Destroyer"; char ptboat[] = "PT Boat"; char name[] = "Bruce"; struct _ships { char *name; char symbol; char length; char start; /* Coordinates - 0,0=0; 10,10=100. */ char dir; /* Direction - 0 = right; 1 = down. */ char hits; /* How many times has this ship been hit? (-1==sunk) */ }; struct _ships plyship[] = { { carrier,'A',5,0,0,0 }, { battle,'B',4,0,0,0 }, { destroy,'D',3,0,0,0 }, { sub,'S',3,0,0,0 }, { ptboat,'P',2,0,0,0 }, }; struct _ships cpuship[] = { { carrier,'A',5,0,0,0 }, { battle,'B',4,0,0,0 }, { destroy,'D',3,0,0,0 }, { sub,'S',3,0,0,0 }, { ptboat,'P',2,0,0,0 }, }; char hits[2][100], board[2][100]; /* "Hits" board, and main board. */ int srchstep; int cpuhits; int cstart, cdir; int plywon=0, cpuwon=0; /* How many games has each won? */ int turn; /* 0=player, 1=computer */ main(){ intro(); do{ initgame(); while(awinna() == -1){ while((turn) ? cputurn() : plyturn()); turn = OTHER; } } while(playagain()); uninitgame(); } #define PR printf intro(){ clrscn(); cursor(29,4); PR("Welcome to Battleship!"); cursor(0,8); PR(" \\\n"); PR(" \\ \\ \\\n"); PR(" \\ \\ \\ \\ \\_____________\n"); PR(" \\ \\ \\_____________ \\ \\/ |\n"); PR(" \\ \\/ \\ \\/ |\n"); PR(" \\/ \\_____/ |__\n"); PR(" ________________/ |\n"); PR(" \\ S.S. Penguin |\n"); PR(" \\ /\n"); PR(" \\___________________________________________________/\n"); cursor(27,20); PR("Hit any key to continue..."); while(!__BDOS(11,0L)) rand(); __BDOS(6,0xFFL); } initgame(){ int i; clrscn(); cursor(35,0); PR("BATTLESHIP"); cursor(12,4); PR("Main Board"); cursor(0,6); PR(numbers); cursor(0,7); for(i=0; i<10; ++i){ printf("%c . . . . . . . . . . %c\n",i+'A',i+'A'); } cursor(0,17); PR(numbers); cursor(55,4); PR("Hit/Miss Board"); cursor(45,6); PR(numbers); for(i=0; i<10; ++i){ cursor(45,7+i); printf("%c . . . . . . . . . . %c",i+'A',i+'A'); } cursor(45,17); PR(numbers); for(turn=0; turn<2; ++turn) for(i=0; i<100; ++i){ hits[turn][i] = board[turn][i] = 0; } for(turn=0; turn<2; ++turn){ for(i=0; i<5; ++i) if(!turn) plyplace(&plyship[i]); else cpuplace(&cpuship[i]); } turn = rnd(2); cstart = cdir = -1; cpuhits = 0; srchstep = 3; } rnd(n) int n; { return(((rand() & 0x7FFF) % n)); } plyplace(ss) struct _ships *ss; { int c, d; do{ prompt(); PR("Place your %s (ex.%c%d) ? ",ss->name,rnd(10)+'A',rnd(10)); c = getcoord(); d = getdir(); } while(!checkplace(ss,c,d)); placeship(ss,c,d); } getdir(){ int d; prompt(); PR("What direction (0=right, 1=down) ? "); return(sgetc("01")-'0'); } placeship(ss,c,d) struct _ships *ss; int c, d; { int x, y, l, i; for(l=0; l<ss->length; ++l){ i = c + l * ((d) ? 10 : 1); board[turn][i] = ss->symbol; x = (i % 10) * 3 + 3; y = (i / 10) + 7; if(!turn){ cursor(x,y); PR("%c",ss->symbol); } } ss->start = c; ss->dir = d; ss->hits = 0; } checkplace(ss,c,d) struct _ships *ss; int c, d; { int x, y, l; x = c%10; y = c/10; if(((x+ss->length) > 10 && !d) || ((y+ss->length) > 10 && d==1)){ if(!turn) switch(rnd(3)){ case 0: error("Ship is hanging from the edge of the world"); break; case 1: error("Try fitting it on the board"); break; case 2: error("Figure I won't find it if you put it there?"); break; } return(0); } for(l=0; l<ss->length; ++l){ x = c + l * ((d) ? 10 : 1); if(board[turn][x]){ if(!turn) switch(rnd(3)){ case 0: error("There's already a ship there"); break; case 1: error("Collision alert! Aaaaaagh!"); break; case 2: error("Er, Admiral, what about the other ship?"); break; } return(0); } } return(1); } error(s) char *s; { prompt(); PR("\7%s -- hit any key to continue --",s); __BDOS(6,0xFFL); } prompt(){ int i; cursor(0,22); for(i=0; i++ < 79;) printf(" "); printf("\r"); } toupper(ch) int ch; { return((ch >= 'a' && ch <= 'z') ? ch-'a'+'A' : ch); } getcoord(){ int ch, x, y; redo: y = sgetc("ABCDEFGHIJ"); do{ ch = __BDOS(6,0xFFL); if(ch == 0x7F || ch == 8){ printf("\b \b"); goto redo; } } while(ch < '0' || ch > '9'); printf("%c",x=ch); return((y-'A')*10+x-'0'); } cursor(x,y) int x, y; { printf("\33Y%c%c",y+' ',x+' '); } clrscn(){ printf("\33H\33J"); } cpuplace(ss) struct _ships *ss; { int c, d; do{ c = rnd(100); d = rnd(2); } while(!checkplace(ss,c,d)); placeship(ss,c,d); } awinna(){ int i, j; struct _ships *ss; for(i=0; i<2; ++i){ ss = (i) ? cpuship : plyship; for(j=0; j<5; ++j, ++ss) if(ss->length != ss->hits) break; if(j == 5) return(OTHER); } return(-1); } plyturn(){ int c, res, i; char *m; prompt(); PR("Where do you want to shoot? "); c = getcoord(); if(!(res = hits[turn][c])){ hits[turn][c] = res = (board[OTHER][c]) ? 'H' : 'M'; cursor(48+3*(c%10),7+c/10); printf("%c",(res=='H') ? 'H' : 'o'); if(c = hitship(c)){ prompt(); switch(rnd(3)){ case 0: m = "\7You sank my %s!"; break; case 1: m = "I have this sinking feeling about my %s...."; break; case 2: m = "Have some mercy for my %s!"; break; } cursor(0,23); PR("\r\7"); PR(m,cpuship[c-1].name); return(awinna() == -1); } } prompt(); cursor(0,23); for(i=0; i<78; ++i) printf(" "); PR("\rYou %s.",(res=='M')?"missed":"scored a hit"); return(res == 'H'); } hitship(c) int c; { struct _ships *ss; int sym, i, j; ss = (turn) ? plyship : cpuship; if(!(sym = board[OTHER][c])) return(0); for(i=0; i<5; ++i, ++ss) if(ss->symbol == sym){ j = ss->hits; ++j; ss->hits = j; if(j == ss->length) return(i+1); return(0); } } cputurn(){ int c, res, x, y, i, d; redo: if(cstart == -1){ if(cpuhits){ for(i=0, c=rnd(100); i<100; ++i, c = (c+1) % 100) if(hits[turn][c] == 'H') break; if(i != 100){ cstart = c; cdir = -1; goto fndir; } } do{ i = 0; do{ while(hits[turn][c=rnd(100)]); x = c % 10; y = c / 10; if(++i == 1000) break; } while((x % srchstep) != (y % srchstep)); if(i == 1000) --srchstep; } while(i == 1000); } else if(cdir == -1){ fndir: for(i=0, d=rnd(4); i++ < 4; d = (d+1) % 4){ x = cstart%10; y = cstart/10; switch(d){ case 0: ++x; break; case 1: ++y; break; case 2: --x; break; case 3: --y; break; } if(x<0 || x>9 || y<0 || y>9) continue; if(hits[turn][c=y*10+x]) continue; cdir = -2; break; } if(i == 4){ cstart = -1; goto redo; } } else{ x = cstart%10; y = cstart/10; switch(cdir){ case 0: ++x; break; case 1: ++y; break; case 2: --x; break; case 3: --y; break; } if(x<0 || x>9 || y<0 || y>9 || hits[turn][y*10+x]){ cdir = (cdir+2) % 4; for(;;){ switch(cdir){ case 0: ++x; break; case 1: ++y; break; case 2: --x; break; case 3: --y; break; } if(x<0 || x>9 || y<0 || y>9){ cstart = -1; goto redo; } if(!hits[turn][y*10+x]) break; } } c = y*10 + x; } for(;;){ prompt(); PR("I shoot at %c%d. Do I (H)it or (M)iss? ",c/10+'A',c%10); res = sgetc("HM"); if((res=='H' && !board[OTHER][c]) || (res=='M' && board[OTHER][c])){ error("You lie!"); continue; } break; } printf("%c",res); hits[turn][c] = res; if(res == 'H'){ ++cpuhits; if(cstart == -1) cdir = -1; cstart = c; if(cdir == -2) cdir = d; cursor(3+3*(c%10),7+(c/10)); printf("*"); } else if(cdir == -2) cdir = -1; if(c=hitship(c)){ cstart = -1; cpuhits -= plyship[c-1].length; x = plyship[c-1].start; d = plyship[c-1].dir; y = plyship[c-1].length; for(i=0; i<y; ++i){ hits[turn][x] = '*'; x += (d) ? 10 : 1; } } if(awinna() != -1) return(0); return(res == 'H'); } playagain(){ int i, x, y, dx, dy, j; for(i=0; i<5; ++i){ x = cpuship[i].start; y = x/10+7; x = (x % 10) * 3 + 48; dx = (cpuship[i].dir) ? 0 : 3; dy = (cpuship[i].dir) ? 1 : 0; for(j=0; j < cpuship[i].length; ++j){ cursor(x,y); printf("%c",cpuship[i].symbol); x += dx; y += dy; } } if(awinna()) ++cpuwon; else ++plywon; i = 18 + (sizeof name); if(plywon >= 10) ++i; if(cpuwon >= 10) ++i; cursor((80-i)/2,2); PR("%s: %d Computer: %d",name,plywon,cpuwon); prompt(); PR((awinna()) ? "Want to be humiliated again, %s? " : "Going to give me a chance for revenge, %s? ",name); return(sgetc("YN") == 'Y'); } uninitgame(){ clrscn(); } sgetc(s) char *s; { char *s1; int ch; for(;;){ ch = toupper(__BDOS(6,0xFFL)); if(ch == 3){ uninitgame(); exit(3); } for(s1=s; *s1 && ch != *s1; ++s1); if(*s1){ __BDOS(2,(long)ch); return(ch); } } } -- +----------------------------------------------------------------------------+ |Whatever I write are not the opinions or policies of Digital Research, Inc.,| |and probably won't be in the foreseeable future. | +----------------------------------------------------------------------------+ Bruce Holloway ....!ucbvax!hplabs!amdahl!drivax!holloway (I'm not THAT Bruce Holloway, I'm the other one.)
cagordon@watnot.UUCP (Chris Gordon) (03/05/86)
So...what IS ___BDOS? It says: Undefined: ___BDOS I posted this rather than mail it as I suppose a lot of other people will get the same message.
holloway@drivax.UUCP (Bruce Holloway) (03/07/86)
In article <11574@watnot.UUCP> cagordon@watnot.UUCP (Chris Gordon) writes: > >So...what IS ___BDOS? It says: >Undefined: >___BDOS >I posted this rather than mail it as I suppose a lot of other people will >get the same message. And I suppose you're going to point out that not everyone uses CP/M-68K, eh? I posted a Unix version which should clear up this problem. Here's the Makefile, just for the fun of it: ---------------------------------------------------------------------------- battle: battle.c cc battle.c -lcurses mv a.out battle -- +----------------------------------------------------------------------------+ |Whatever I write are not the opinions or policies of Digital Research, Inc.,| |and probably won't be in the foreseeable future. | +----------------------------------------------------------------------------+ Bruce Holloway ....!ucbvax!hplabs!amdahl!drivax!holloway (I'm not THAT Bruce Holloway, I'm the other one.)