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.)