/* Building a Better Boggle Copyright 1993 by Phil Goetz
goetz@cse.buffalo.EDU
philgoetz@yahoo.com
flick@populus.net
Version 3: Genetic algorithm, sexual, dictionary, survivors.
Changes to make:
Add cba to abc; only check abc.
Make tri turn qu -> q
Note from gtoal@gtoal.com: Now modified to use an
internal boggle word finder and scoring - runs approx 10 times
faster.
Also hacked one small library incompatibility (log2/ilog2)
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define AUTO 2 /* Chance out of 64 that X mates with X */
#define BIRTHS 200
#define BS (BIRTHS+SURVIVORS)
#define DEBUG (1+8+16+32)
/*#define DEBUG (1+4+16+32+64+128+1024)*/
/* 1 Print gens & ave hiscore */
/* 2 Print each reproducing board's info about 1/16 the time */
/* 4 Print each reproducing board's info */
/* 8 Use raster chromosome */
/* 16 Print top score */
/* 32 printboard(winner) */
/* 64, 128, 256, 512, and 1024 are enabled by 2 or 4 */
/* 64 printboard */
/* 128 print score + # kids */
/* 256 print gen 0 ancestors */
/* 512 print ancestry */
/* 1024 print summary of gen 0 ancestors */
#define DICE (SIDE*SIDE)
#define GENS 30 /* generations */
#define MUTRATE 2 /* average # of mutations per descendant */
#define SIDE 4
#define STATES 6
#define SURVIVORS (BIRTHS/8)
#define TICKETS 10000. /* Total # of lottery tickets given out */
/* Global variables: */
static
char chdice[DICE][STATES] = {"aeiouy", "aeiouy", "aeiouy", "aeiouy",
"aeioue", "aeioae", "aeioae", "tdbtgp",
"tdgtdp", "tdgtdb", "tdbtpg", "rlhmnk",
"rlhmnk", "cswfhs", "cswfhs", "qxzjkv"};
/* chdice[0][5] = face 5 of dice 0 */
static
double score[BS];
static
int board[BS][DICE], /* board[][2]=3 => face 3 of dice 2 is up */
dice[DICE][STATES], /* Permuted integer version of chdice: A = 0 */
#if DEBUG & 1024
firstgen[BIRTHS], /* Track # of each 1st-gen ancestors */
#endif
new[BIRTHS][DICE];
static
struct ancestors
{ int name;
struct ancestors *mom, *dad;
}
*ancestorses[BS],
*newanc[BIRTHS];
#ifndef HAS_LOG2
/* I hope this is right. It's a quick hack because bsd doesn't
seem to have the same math funs as the author's system - Graham Toal */
static int ilog2(long l) /* rounds down */
{
int i;
if (l <= 0L) return 0; /* Shouldn't be needed */
i = 0;
for (;;) {
if (l == 0) return(i-1);
l >>= 1;
i += 1;
}
}
#endif
extern int bogglescore(char *rawboard);
static void printboard(int b, /* board # */
int nice); /* 1 = print in 2D format */
static double calcscore(int b) /* board # */
{
static int bestscore = -1;
char call[17];
int i, j, bscore;
call[16] = '\0';
for (i=0; i<SIDE; i++)
{ for (j=0; j<SIDE; j++)
call[i*SIDE+j] =
((char) dice[i*SIDE+j][board[b][i*SIDE+j]]) + 'a';
}
bscore = bogglescore(call);
if (bscore > bestscore) {
bestscore = bscore;
printboard(b, 0); fprintf(stdout, " -> %d\n", bscore);
}
return (double) (bscore-16); /* Why -16 ??? - gtoal */
}
static void init(void)
{
int b,i,j, perm[DICE], r;
/* Randomly permute the dice */
/* Make perm a random permutation of 0..DICE-1 */
for (i = 0; i < DICE; i++)
{ perm[i] = -1;
}
i = 0;
do
{ j = (rand() & 65535) / (65536/DICE); /* 0 to (DICE-1) */
if (perm[j] == -1) perm[j] = i++;
}
while (i < DICE);
for (i = 0; i < DICE; i++)
for (j=0; j<STATES; j++)
dice[i][j] = (int) (chdice[perm[i]][j] - 'a');
for (b=0; b<BIRTHS; b++)
{ for (i=0; i<DICE; i++)
{ do
r = (rand() & 65535) >> 13; /* 0 - 7 */
while (r > 5);
new[b][i] = r;
}
newanc[b] = (struct ancestors *) malloc(sizeof(struct ancestors));
newanc[b]->mom = NULL;
newanc[b]->dad = NULL;
newanc[b]->name = b;
}
for (b=BIRTHS; b<BS; b++) /* Prevent blank survivor spots */
score[b] = .0; /* from having kids in gen 0 */
}
static void printboard(int b, /* board # */
int nice) /* 1 = print in 2D format */
{
int die, i, j;
/*
if (!nice) printf("\n");
*/
for (j = 0; j < SIDE; j++) /* Row */
{ for (i=0; i<SIDE; i++)
{ die = i + SIDE*j; /* Row major */
printf("%c", (char) dice[die][board[b][die]]+'a');
}
if (nice) printf("\n"); else if (j+1<SIDE) printf(" ");
}
}
/* Create new[i] as offspring of board[mom] and board[dad] */
static void birth(int dad, int mom, int kid)
{ int
#if DEBUG & 8
chromo[] ={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},
#else
chromo[] ={4,0,1,5,6,2,3,7,11,15,14,10,9,13,12,8},
#endif
j, parent,
r, xpoint;
struct ancestors *anc;
anc = (struct ancestors *) malloc(sizeof(struct ancestors));
anc->mom = ancestorses[mom];
anc->dad = ancestorses[dad];
anc->name = kid;
newanc[kid] = anc;
parent = dad;
xpoint = (rand() & 65535) / (65536/DICE); /* 0..(DICE-1) */
for (j=0; j<DICE; j++)
{ if (j==xpoint) parent = mom;
r = (rand() & 65535) / (65536/(4*DICE)); /* 0..(4*DICE-1) */
if (r < (int) (4. * (double) MUTRATE)) /* If a mutation */
{ r = (rand() & 65535) / (65536/STATES);
new[kid][chromo[j]] = r;
}
else new[kid][chromo[j]] = board[parent][chromo[j]];
}
}
static void ancestry(struct ancestors *b)
{
if (b->dad == NULL)
#if DEBUG & 1024
firstgen[b->name]++;
#else
{printf("%d", b->name); fflush(stdout);}
#endif
else
{
#if DEBUG & 512
printf("%d (", b->name); fflush(stdout);
#endif
ancestry(b->dad);
#if (!(DEBUG & 1024))
printf(" "); fflush(stdout);
#endif
ancestry(b->mom);
#if DEBUG & 512
printf(")"); fflush(stdout);
#endif
}
}
static int survivor(int b) /* Returns 1 if board b is identical to one in survivor list */
{ int i, j;
for (i=BIRTHS; i<BS; i++)
{ j=0;
while (dice[j][board[b][j]] == dice[j][board[i][j]] && j < DICE)
{ j++; }
if (j == DICE) return 1;
}
return 0;
}
static void insert(int b) /* Insert board i into survivor list, ranked by score */
/* Assumes score[b] > score[BS-1] */
{ int i, spot;
spot = BS-1;
while (score[b] > score[spot-1] && spot > BIRTHS)
/* Move old survivors down */
{ ancestorses[spot] = ancestorses[spot-1];
for (i=0; i<DICE; i++)
board[spot][i] = board[spot-1][i];
score[spot] = score[--spot];
}
ancestorses[spot] = ancestorses[b];
for (i=0; i<DICE; i++)
board[spot][i] = board[b][i];
score[spot] = score[b];
}
#include "splib.h"
extern NODE *dict;
extern INDEX nedges;
int main(int argc, char **argv)
{
double ave, avef,
maxscore,
sum,
tscore[BS],
tssum;
int i,j,k,r,
descendants[BS],
gens, /* # of generations */
holder, /* ticket holder */
maxind,
oldholder,
tickets[BS],
tsum; /* # of tickets issued */
/* Boggle initialisation: */
if (!dawg_init("words", &dict, &nedges)) {
fprintf(stderr, "Cannot open words.dwg\n");
exit(1);
}
srand48(234987234);
srand((unsigned) time(0));
init();
for (gens=0; gens<GENS; gens++)
{
for (i=0; i<BIRTHS; i++)
{ for (j=0; j<DICE; j++)
board[i][j] = new[i][j];
ancestorses[i] = newanc[i];
}
sum = .0;
for (i=0; i<BIRTHS; i++)
{ score[i] = calcscore(i);
if (score[i] > maxscore)
{ maxscore = score[i];
maxind = i;
}
sum += score[i];
}
ave = sum/(double) BIRTHS;
tssum = .0;
avef = ave * 2./3.;
for (i=0; i<BS; i++)
{ if (score[i] > ave)
tscore[i] = (score[i]-avef)*(score[i]-avef);
else tscore[i] = 0.;
tssum += tscore[i];
descendants[i] = 0;
}
tsum = 0;
for (i=0; i<BS; i++)
{ tickets[i] = (int) (TICKETS*tscore[i]/tssum + .5);
tsum += tickets[i];
}
#if DEBUG & 1
printf("Generation %d: %d tickets issued, ave score %g\n",
gens, (int) tsum, ave); fflush(stdout);
#endif
/* Pick (2*BIRTHS) lottery winners */
/* k = smallest 2^n > tsum */
#ifdef HAS_LOG2
k = ((int) log2((double)tsum)) + 1;
#else
k = ilog2((long)tsum) + 1;
#endif
for (i=0; i<BIRTHS; i++)
{ for (j=0; j<2; j++) /* 2 parents */
{ oldholder = holder;
do
{ do
{ r = rand(); r &= (1<<k)-1;}
while (r > (tsum-1));
/* Holder of ticket r gets 1 descendant */
holder = -1;
while (r > -1)
r -= tickets[++holder];
}
while (holder == oldholder && ((rand() & 255) >> 4) > AUTO);
descendants[holder]++; /* For our info */
}
birth(holder, oldholder, i);
}
#if (DEBUG & 2) || (DEBUG & 4)
j=0;
for (i=0; i<BS; i++)
#if (DEBUG & 4)
if (descendants[i])
#else if (DEBUG & 2)
if (descendants[i] && (((rand() & 255) >> 4) == 1))
#endif
{ printf("#%2d ",i); fflush(stdout);
#if (DEBUG & 64)
printboard(i,0); fflush(stdout);
#endif
#if DEBUG & 128
printf(", sc %3g, d%3d",
score[i], descendants[i] ); fflush(stdout);
#endif
#if DEBUG & (256+512+1024)
printf(","); fflush(stdout);
#if DEBUG & 1024
for (k=0; k<BIRTHS; k++)
firstgen[k]=0;
#endif
ancestry(ancestorses[i]);
#if DEBUG & 1024
for (k=0; k<BIRTHS; k++)
if (firstgen[k])
printf(" %dx%d",firstgen[k], k);
fflush(stdout);
#endif
#endif
printf("\n"); fflush(stdout);
j+= descendants[i];
}
#endif
/* Pick survivors */
for (i=0; i<BIRTHS; i++)
/* Lowest-scoring old survivor in BS-1 */
if (score[i] > score[BS-1] && !survivor(i))
insert(i);
maxind = BIRTHS; maxscore = score[maxind];
}
#if DEBUG & 16
printf("Top score: %f #%d\n",score[maxind], maxind); fflush(stdout);
#endif
#if DEBUG & 32
printboard(maxind,0); printf("\n"); fflush(stdout);
#endif
/* Boggle termination: */
free(dict); /* no special procedure to free these. */
/* Must be done once only, at end of program */
exit(0);
}