/*
TO DO: assign a sequential index to each generated 'play' request,
and pass it as a parameter to the 'play' command.
Modify the 'play' command to print that number before printing its result.
This will let us decouple the requests.
Perhaps should also generate requests breadthwise, with 1 request for each
board position (plus drill-down on highest-scoring and bingoes)
Don't yet have rules to suggest that swaps are better. Shouldn't be too
hard to do a single GA pass to work out expected value of swaps???
Still to consider trick of playing wild cards as a way to evaluate board
position. Easy to do, and helped by knowing our held tiles which we ensure
opponent cannot play. In fact - best solution - play wild cards which
consist only of our 7 tiles on each square, not a 27-letter wildcard
(unless *we* hold a blank)
(also pass the dictionary name to 'play' - last outstanding piece of
hidden state)
*/
#define GLOBALTEST
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <time.h>
#include <assert.h>
FILE *logfile;
FILE *errfile;
time_t start_time, end_time, elapsed_time;
int spell_verbose = (0!=0);
#include <time.h> /* for randomising the shuffle */
int irand(int max) /* assert: max > 0 */ /* used in shuffle */
{
long l = random();
if (l < 0) l = -l;
l = l % max; /* assert: 0 <= l < max */
return((int)l);
}
#ifndef FALSE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
#ifdef MEMDEBUG
#include "mnemosyne.h" /* Use this to track heap leaks */
#endif
#include "probfn.c" /* Probability function */
#include "latin1.c" /* because setlocale() appears to be broken on my system */
#include "bitsigs.c" /* fast data structure based on Ars Magna anagram program */
#include "rackgen.c" /* fast internal unique rack generator */
/* This is the format that we use to store potential plays */
typedef struct playfm {
char place[8];
char pos[4];
char dirn;
int score;
int freq;
int cumfreq;
bitsig sig;
} playfm;
/* Unfortunately handling every possible play in every position on the
board, where we can also use one or two blanks, appears to be too
large for the 'play' array. So we need to make some arbitrary
cut-off. This isn't so bad since there is some point in the mid-game
where the complexity becomes tractible. Not quite sure exactly
where yet. */
// 177315 is the count of words in SOWPODS. Temp and arbitrary hack. Bitsig phase already too slow
#define MAX_PLAYS (176915 * 4)
playfm play[MAX_PLAYS];
static int nextfree = 0;
static int excess_plays = 0; // during debugging we can find out what the largest number of plays was,
// without actually recording them.
// NOT YET IMPLEMENTED
/* in cases where we can't do every move, we'll at least do one of every 'shape',
which is a much smaller number. This ought to give us an idea of dangerous
openings of premium squares. If a prticular shape scores higher than average,
we can drill down on the other plays for that shape. */
#define MAX_SHAPES ((7+6+5+4+3+2+1) * 8 * 15)
playfm shape[MAX_SHAPES]; /* Do minimax on at least 1 example of each play shape. Use highest scoring... */
static int nextfreeshape = 0;
#include "sortfn.c" /* auxilliary function for sorting playfm array */
#define MAX_PLAYSCORE 2000 /* surely enough - has to be > highest score you can make on one play */
static double playscore[MAX_PLAYSCORE]; /* eg playscore[87] would contain the probability (count
of the # of ways) of making a play worth 87. */
#include "movegen.c"
int main(int argc, char **argv)
{
int desired_confidence = 85; // This should be a parameter passed in from the call to 'play'
int FINAL_SCORE = 0; // This is the score we return to the caller!
/*-------------------------------------------------------------*/
int c;
int i, len, compatible;
char inittarget[64];
char *target;
char *textbuffer;
char **wordlist;
int wfreqs[27];
int shapes_seen = 0;
char forms[1024];
char bag[128];
int cumfreq = 0;
int each, rc;
logfile = fopen("/tmp/gtoal-scrabble-experiment.log", "w");
if (logfile == NULL) {
fprintf(errfile, "global: cannot create log file /tmp/gtoal-scrabble-experiment.log\n");
exit(1);
}
errfile = fopen("/tmp/gtoal-scrabble-experiment.err", "w");
if (errfile == NULL) {
fprintf(errfile, "global: cannot create errfile file /tmp/gtoal-scrabble-experiment.err\n");
exit(1);
}
#include "init.c"
strcpy(bag, fullrack);
//fprintf(errfile, "Generating sigs for \"%s\"\n", fullrack);
// wordsigs = (bitmask *)malloc(sizeof(bitmask) * maxwords);
makefreqs(FULLRACK, freqs); // *** THIS WAS THE BUG :-) Had "bag" before...
choosefields(freqs);
makeonesig(bag, bagsig);
bagsigcopy[0] = bagsig[0];
bagsigcopy[1] = bagsig[1];
bagsigcopy[2] = bagsig[2];
makeuf(freqs, letmask, letbit, letwidth);
start_time = time(NULL);
/* Generate all possible plays */
for (orientation = HORIZONTAL; orientation <= VERTICAL; orientation++) {
/* We assume throughout that we are examining only horizontal plays,
and just flip the board to handle vertical plays. We flip it back
at the end, in case we want to update it with a play and write it
back to file. (but we don't do that yet) */
for (row = 1; row <= HEIGHT; row++) {
/* calculate crosschecks for this row before we look at
placements for this row. We could actually do this for
the whole board first, but it isn't necessary */
for (col = 1; col <= WIDTH; col++) {
char *s;
/* Clean up from previous tries */
/* This is about our only use of the heap and I bet if we were
to make these fixed size statics it would speed up the code... */
if (crosschecks[row][col] != NULL) {
free(crosschecks[row][col]); crosschecks[row][col] = NULL;
}
if (vertical_word[row][col] != NULL) {
free(vertical_word[row][col]); crosschecks[row][col] = NULL;
}
vertical_word[row][col] = NULL;
/* first of all get wildcard pattern, eg "w?rd" : */
crosschecks[row][col] = create_crosscheck_wildcard(row, col);
/* Then convert it to a set of valid letters */
if (crosschecks[row][col] == NULL) {
/* crosschecks don't make sense here */
crosschecks[row][col]= strdup("?"); /* BUGFIX: forgot strdup! */
} else {
/* BUG!!! crosschecks[row][col] for an already-played blank is
returning '?' rather than the letter that the blank
represents. Looks like the error is in create_crosscheck_wildcard */
s = convert_wildcard_to_permitted_set(dawg, crosschecks[row][col]);
free(crosschecks[row][col]);
if (s == NULL) {
/* No letter can currently be placed in this square legally */
crosschecks[row][col] = strdup("!");
/* "!" is easier to debug than empty string */
} else {
crosschecks[row][col] = strdup(s);
}
}
}
/* Now do placements: try every square on this row as position for
first tile to be placed down. Rest follow automatically */
//fprintf(errfile, "horizontal placements\n");
for (col = 1; col <= WIDTH; col++) {
if (debug) fprintf(errfile, "Testing row %d col %d\n", row, col);
for (length = 1; length <= MIN(tiles_held, 7); length++) {
int words_played = 0, total_score = 0;
/* Can I legally place this many tiles onto the board here? */
if (slot(row, col, length, orientation, &words_played, &total_score)) {
/* would be nice to pass the wildcard string back to here
and then expand it/search for plays, and make the plays
separately. The hack above was for convenience only. */
/* record row,col,length and wildcard for move generator (maybe) */
}
if (words_played) {
fprintf(logfile, "SHAPE: %d plays at %d %d/%d with %d tiles averaging %0.1f\n",
words_played, row, col, orientation, length, (float)total_score/(float)words_played);
shapes_seen += 1;
// TO DO: add this to the shape[] array of playfm's.
}
}
}
} /* Try every row on the board */
/* flip the board around the x=y diagonal */
//fprintf(errfile, "flip the board in X=Y...\n");
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i;
if (row > col) { /* avoid doing twice (no-op) */
/* swap board and apparent_letter at row,col */
i = board[row][col];
board[row][col] = board[col][row];
board[col][row] = i;
i = apparent_letter[row][col];
apparent_letter[row][col] = apparent_letter[col][row];
apparent_letter[col][row] = i;
}
}
}
} /* end of horiz/vert placement loop */
end_time = time(NULL); elapsed_time = end_time-start_time;
fprintf(logfile, "%d plays (consisting of %d different shapes) generated in %ld seconds elapsed time\n",
nextfree, shapes_seen, elapsed_time);
// NOW... for every possible rack, find the highest score with that rack...
/* We can do this more efficiently if we sort by score, and exit on
the first (ie highest) matching score .. */
start_time = time(NULL);
qsort(play, (size_t)nextfree, sizeof(play[0]), compare_score);
end_time = time(NULL); elapsed_time = end_time-start_time;
fprintf(logfile, "Plays sorted using system qsort in %ld seconds elapsed time\n", elapsed_time);
{ // THIS IS A VERY EXPENSIVE SECTION
FILE *allracks;
char *s, line[128];
int nextuniquerack = 0, rack;
double count, realracks = 0.0;
bitsig racksig;
static int countdown;
start_time = time(NULL);
countdown = 3199724/79; // one line's worth of dots. 3199724 is the largest number of unique racks possible.
for (;;) {
int tmp;
double compatible;
countdown -= 1;
if (countdown == 0) {countdown = 3199724/79;fflush(logfile);fflush(errfile);fprintf(errfile, ".");fflush(errfile);}
s = nextdraw(7, tiles);
if (s == NULL) break;
strcpy(line, s);
makeonesig(line, racksig);
{
/* error if any wanted tile in "Tiles" does not exist in "Bag" */
// count the racks in order to generate probabilities
realracks += (compatible = RackCount(line, tiles, 7)); // TO DO (presumably refers to the '7')
if (compatible == 0.0) {
// We're sure that the rack is compatible with this bag, yet
// RackCount seems to be saying that there are 0 ways of making this rack from
// the tiles in the bag. Must be a bug :-(
fprintf(errfile, "Exiting...\n");
Debug_Probs = TRUE;
(void)RackCount(line, tiles, 7); // re-do with debug turned on.
fprintf(errfile, "rack: %s\nbag: %s\n", line, tiles);
exit(1);
} else {
int bestscore = 0;
/* for every rack, find the highest score with that rack. */
// this is an expensive N^2 loop - need algorithmic improvement
for (each = 0; each < nextfree; each++) {
/* check every play, if it can be made with this rack and the score is higher, record it */
if (COMPATIBLE(play[each].sig, racksig) != 0) { /* First match is now highest score */
//printf("Rack %d found at %d\n", nextuniquerack, each);
bestscore = play[each].score; // racksfound += 1;
break;
}
}
if (bestscore == 0) printf("Rack %d: %s has no plays available.\n", nextuniquerack, line);
playscore[bestscore] += compatible; /* It's OK to set playscore[0] */
nextuniquerack += 1;
}
}
}
fputc('\n', errfile);
end_time = time(NULL); elapsed_time = end_time-start_time;
fprintf(logfile, "Signatures calculated and compatible racks extracted in %ld seconds elapsed time\n", elapsed_time);
fprintf(logfile, "There are %d possible racks from this bag\n", nextuniquerack);
fprintf(logfile, "Total no of draws to make these racks = %10.0f\n", realracks);
{
double totalplays = 0.0;
double cumcount = 0.0;
int score;
for (score = MAX_PLAYSCORE; score >= 0; score--) {
cumcount += playscore[score];
if (playscore[score] != 0.0) {
if ((100.0-(cumcount/realracks*100.0)) >= (float)desired_confidence) FINAL_SCORE = score;
fprintf(logfile, "%04d: %10.0f (%10.0f) %3.2f%% confidence\n",
score, playscore[score], cumcount, cumcount/realracks*100.0);
}
}
}
}
//#ifdef NEVER
fprintf(logfile, "Let us test this hypothesis by taking some random racks and finding the best scores:\n\n");
{ /* Consistency check: do a small Monte-Carlo and see how well it
matches the maths ... */
int i, j, k, c;
srandom((int)time(NULL));
for (k = 0; k < 20; k++) { /* No of results to be printed */
// shuffle
char rack[8];
for (i = strlen(fullrack)-1; i > 0; --i) { /* E.g. array could be rack[0] to rack[99] inclusive */
j = irand(i); /* random int between 0 and i-1 inclusive */
c = fullrack[i]; fullrack[i] = fullrack[j]; fullrack[j] = c;
}
strncpy(rack, fullrack, 7); rack[7] = '\0';
fprintf(logfile, "Let's try: %0.7s\n\n", rack);
{
double compatible;
int bestscore = 0, each;
bitsig racksig;
makeonesig(rack, racksig);
for (each = 0; each < nextfree; each++) {
/* First match is now highest score due to earlier qsorting */
//fprintf(errfile, "playsig: "); printmask('A',play[each].sig);
//fprintf(errfile, "racksig: "); printmask('B',racksig);
//fprintf(errfile, "\n");
if (COMPATIBLE(play[each].sig, racksig) != 0) {
bestscore = play[each].score;
break;
}
}
if (bestscore == 0) {
fprintf(logfile, "No plays known\n");
} else {
fprintf(logfile, "Place tiles %s at %s (%d) for %d\n", play[each].place, play[each].pos, play[each].dirn, play[each].score);
}
}
fputc('\n', errfile);
}
}
//#endif
// NOW WE PRINT THE FINAL VALUE, THE EXPECTED SCORE AT THIS CONFIDENCE LEVEL!
fprintf(stdout, "%d\n", FINAL_SCORE); fflush(errfile);
//fprintf(logfile, "#define MAX_PLAYS (%d+%d)\n", MAX_PLAYS, excess_plays);
exit(0);
}