#define MINIMAL 1
#define TARGET_TILES 15
#define USE_GAMESTATE
//#define GLOBALTEST
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#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
int spell_verbose = TRUE;
FILE *errfile = NULL;
#include "global_analysis/latin1.c"
/* Only externals used here are my 'dawg' library, and even that is
only for loading the dict file. However in a later iteration I
may move the two dawg-based procedures here to the library */
#include "splib.h" /* load dictionary */
static int debug = FALSE;
static int megaanalysis = FALSE; /* If doing global_analysis */
static int opt_html = FALSE; /* Generate html or text? */
#define MIN(a, b) (a < b ? a : b)
#define BLANKCH '?' /* We're making the assumption that
the ascii code for '?' is not going to
be used for a letter. See the explanation
in gameconfig about charset portability */
#include "gameconfig.c" /* Board shape, scores, alphabet etc */
static int bestscore = 0;
#define HORIZONTAL 1
#define VERTICAL 2
static int report = TRUE;
typedef struct GAMESTATE { // THIS IS THE ALTERNATIVE TO THE ABOVE
int ply;
int player;
int tilesplaced;
char board[HEIGHT+2][WIDTH+2]; // **UNDER DEVELOPMENT**
char apparent_letter[HEIGHT+2][WIDTH+2];
int tiles_held /* = 0*/;
char tiles[/*RACKSIZE*/MAX_TILES+1]; /* Empty, for static analysis */
char remaining_tiles[MAX_TILES+1]; /* Full, for static analysis */
int myscore /*= 0*/;
int oppscore /*= 0*/;
int vertical_score[HEIGHT+2][WIDTH+2];
char fullrack[MAX_TILES+1];
char *crosschecks[HEIGHT+2][WIDTH+2];
char *vertical_word[HEIGHT+2][WIDTH+2];
int vindex[HEIGHT+2][WIDTH+2];
char *boardfile /* = NULL*/; /* This should be in "main()" but
for hacky reasons (HTML in playword()) it is global *for now* */
int bestscore;
char playtiles[/*RACKSIZE*/MAX_TILES+1]; /* Empty, for static analysis */
char playword[/*RACKSIZE*/MAX_TILES+1]; /* Empty, for static analysis */
char playtilesleft[/*RACKSIZE*/MAX_TILES+1]; /* Empty, for static analysis */
char playtemplate[/*RACKSIZE*/MAX_TILES+1]; /* Empty, for static analysis */
int playplaced;
int playLetter;
int playnumber;
int playorientation;
int movesconsidered;
} GAMESTATE;
void enumerate_all_plays(GAMESTATE *game);
void recursive_playword(GAMESTATE *game, char *tiles, char *word, char *tilesleft, char *template,
int placed, int Letter, int number, int orientation)
{
GAMESTATE copy;
int hscore = 0, vscore = 0;
int row, col;
int tmp, tmpch, i, nexttile = 0;
int wmult = 1;
char *s = word;
char outbuff[1024]; char *outbuffp = outbuff;
int ga_score, confidence;
tiles[placed] = '\0';
// place the candidate word on the board, and recurse on the move generator.
#ifdef PRINT_MOVES // untested - may duplicate some of what follows
/* we treat the board as horizontal even if it's not */
row = (orientation == HORIZONTAL ? number : Letter-'A'+1);
col = (orientation == HORIZONTAL ? Letter-'A'+1 : number);
if (report) outbuffp += sprintf(outbuffp,
(orientation == VERTICAL ? "place %s at %c%d %s (%s) => "
: "place %s at %d%c %s (%s) => "),
tiles,
(orientation == VERTICAL ? Letter : number),
(orientation == VERTICAL ? number : Letter),
(orientation == VERTICAL ? "down" : "across"),
template);
assert((word != NULL) && (game->boardfile != NULL) && (game->fullrack != NULL) && (tiles != NULL));
if (report) {
if (opt_html) {
outbuffp += sprintf(outbuffp, "<A HREF=\"play?word=%s&board=%s&bagwas=%s&rackwas=%s%s&letter=%c&number=%d&orientation=%d&game->myscore=%d&game->oppscore=%d\">%s</A>",
word, game->boardfile, game->fullrack, tiles,tilesleft, Letter, number, orientation, game->myscore, game->oppscore,
word);
} else {
outbuffp += sprintf(outbuffp, "%s", word);
}
}
i = col;
for (;;) {
if (*s == '\0') break;
if (game->board[row][i] == 0) {
/* Place first letter from "tiles" here */
hscore += ((tmp = score[tmpch = tiles[nexttile++]]) * lettermult[row][i]);
if (debug) outbuffp += sprintf(outbuffp, "row %d col %d: add %d%s to hscore for %c\n",
row, i,
tmp,
(lettermult[row][i] == 2 ? "*2L" : (
lettermult[row][i] == 3 ? "*3L" : "")
),
tmpch);
wmult *= wordmult[row][i];
// BUG: when we call playword again just to print the best scoring move,
// it is failing to add in the vscore component. Don't yet know why...
// it MAY be because the orientation has changed (best score was across,
// we've since also done the downs, and perhaps the move evaluator is
// looking at some global state that is not stored in the playlist.
// perhaps I need to keep 2 copies of the cross-check info and index
// into them by orientation.
if (game->vertical_word[row][i] != NULL) {
tmp = (game->vertical_score[row][i] + (score[tmpch] * lettermult[row][i]))
* wordmult[row][i];
vscore += tmp;
game->vertical_word[row][i][game->vindex[row][i]] = *s; /* Plug in the letter to the vword */
if (report) outbuffp += sprintf(outbuffp, "/%s(%d", game->vertical_word[row][i], tmp);
if (wordmult[row][i] != 1) if (report) outbuffp += sprintf(outbuffp, ":%dWS", wordmult[row][i]);
if (report) outbuffp += sprintf(outbuffp, ")");
game->vertical_word[row][i][game->vindex[row][i]] = '?'; /* restore */
}
if (debug) if (game->vertical_word[row][i] != NULL) {
outbuffp += sprintf(outbuffp, "Intersects with %s ", game->vertical_word[row][i]);
game->vertical_word[row][i][game->vindex[row][i]] = *s; /* Plug in the letter to the vword */
outbuffp += sprintf(outbuffp, "forming %s, worth %d", game->vertical_word[row][i], tmp);
if (wordmult[row][i] != 1) outbuffp += sprintf(outbuffp, " (%dWS)", wordmult[row][i]);
game->vertical_word[row][i][game->vindex[row][i]] = '?'; /* restore */
outbuffp += sprintf(outbuffp, "\n");
}
} else {
/* The tile is already placed - game->apparent_letter takes care of blanks */
/* no bonuses, AND DO NOT ADD IN VSCORE!!! */
tmp = score[tmpch = game->apparent_letter[row][i]];
hscore += tmp;
if (debug) outbuffp += sprintf(outbuffp, "add %d to hscore for %c\n", tmp, tmpch);
}
s += 1;
i += 1;
} /* simple hscore, and vscores now all added */
if (debug) if (wmult != 1) outbuffp += sprintf(outbuffp, "Multiply score by %d\n", wmult);
hscore *= wmult;
assert(nexttile == placed);
if (placed == RACKSIZE) {
hscore += BINGO;
if (debug) outbuffp += sprintf(outbuffp, "Add 50 for a bingo!\n");
}
if (megaanalysis) {
if (report) outbuffp += sprintf(outbuffp, ". SCORE %d\n", hscore+vscore);
} else {
if (report) {
char do_global_analysis[1024];
FILE *ga;
int rc;
outbuffp += sprintf(outbuffp, ", leaving %s. SCORE %d. ", tilesleft, hscore+vscore);
// --word \"%s\"
// --board "%s\"
// --bagwas \"%s\"
// --rackwas \"%s%s\"
// --letter \"%c\"
// --number \"%d\"
// --orientation \"%d\"
// --myscore \"%d\"
// --oppscore \"%d\"
sprintf(do_global_analysis, "~/gtoal.com/wordgames/scrabble_solver/global_analysis/play"
" --word \"%s\""
// " --board \"/home/gtoal/gtoal.com/wordgames/boardgen/temp/wsc_%s.dat\""
" --board \"%s\""
" --bagwas \"%s\"" /* THIS IS PASSING THE WRONG VALUE FOR USED BLANKS (tiles) */
" --rackwas \"%s%s\""
" --letter \"%c\""
" --number \"%d\""
" --orientation \"%d\""
" --myscore \"%d\""
" --oppscore \"%d\"",
word, game->boardfile, game->fullrack,
tiles, tilesleft, Letter, number, orientation,
game->myscore+hscore+vscore, game->oppscore
);
ga = popen(do_global_analysis, "r");
rc = fscanf(ga, "%d", &ga_score);
if (rc != 1) ga_score = 0;
outbuffp += sprintf(outbuffp, "(- <= %d with %d%% confidence => %d)\n", ga_score, confidence, hscore+vscore-ga_score);
pclose(ga);
}
}
if (megaanalysis && report) {
static int printed = 0, local_best_score = 0, moves = 0;
moves += 1;
if (moves == 1000000) {
outbuffp = outbuff; // throw current output away
outbuffp += sprintf(outbuffp, "\nOK, I\'m quitting after 1,000,000 moves so as not to be antisocial to my ISP!\n\n");
outbuffp += sprintf(outbuffp, "\nIt might be better if you don't get into 'mega analysis' mode until after the\n");
outbuffp += sprintf(outbuffp, "board has been closed up a bit and there aren't so many choices of move available...\n");
outbuffp += sprintf(outbuffp, "(I.e. go back to the previous page and enter your tiles, rather than leaving them\n");
outbuffp += sprintf(outbuffp, " all set to \'No Tile\')\n\n");
superquit = TRUE;
*outbuffp = '\0';
fprintf(stdout, "%s", outbuff);
outbuffp = outbuff;
}
if ((printed < 21) || (hscore+vscore > local_best_score)) {
static int announced = 0;
if ((announced == 0) && (printed >= 21)) {
announced = 1;
outbuffp += sprintf(outbuffp, "\nToo many results are being returned. From now on we'll only list ones with better scores...\n\n");
}
local_best_score = hscore+vscore;
*outbuffp = '\0';
fprintf(stdout,
"%sThe probability of playing this move is P(\"%s\", \"%s\") = %1.7f\n", outbuff,
tiles, game->fullrack, RackProb(tiles, game->fullrack, 7 /*BUG*/));
printed += 1;
}
fflush(stdout);
if ((strlen(word) +
strlen(game->boardfile) +
strlen(game->fullrack) +
strlen(tiles) +
strlen(tilesleft)) > 7000) exit(1); // hacking attempt on web interface?
sprintf(lookahead, "~gtoal/gtoal.com/wordgames/scrabble_solver/global_analysis/play"
" --word \"%s\""
" --board \"%s\""
" --bagwas \"%s\""
" --rackwas \"%s%s\""
" --letter \"%c\""
" --number \"%d\""
" --orientation \"%d\""
" --myscore \"%d\""
" --oppscore \"%d\"",
word, game->boardfile, game->fullrack,
tiles, tilesleft, Letter, number, orientation,
game->myscore, game->oppscore,
word);
//system(lookahead); // and we want a single numeric value returned as a result!
//fflush(stdout);
} else {
*outbuffp = '\0';
fprintf(stdout, "%s", outbuff);
}
outbuffp = outbuff;
game->movesconsidered += 1;
if (hscore+vscore > game->bestscore) {
// save the highest scoring play in the game state so that
game->bestscore = hscore+vscore;
strcpy(game->playtiles, tiles);
strcpy(game->playword, word);
strcpy(game->playtilesleft, tilesleft);
strcpy(game->playtemplate, template);
game->playplaced = placed;
game->playLetter = Letter;
game->playnumber = number;
game->playorientation = orientation;
}
#endif
if (game->tilesplaced+placed > TARGET_TILES) return; // should I increment the count of moves placed?
if (placed > 4) return; // should I increment the count of moves placed?
memmove(©, game, sizeof(GAMESTATE));
strcpy(game->remaining_tiles, tilesleft);
/* we treat the board as horizontal even if it's not */
fprintf(stderr, "ply %d, player %d - %c%d %s - tiles: %s word: %s template: %s - placed: %d+%d remaining: %d (%s)\n",
game->ply, game->player, Letter, number, (orientation == VERTICAL ? "down" : "across"), tiles, word, template, game->tilesplaced, placed, strlen(tilesleft), tilesleft);
#ifdef never
fprintf(stderr, "\nApparent+Board on entry:\n");
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i = game->apparent_letter[row][col];
if (i == 0) i = '.';
fputc(i, stderr);
}
fputc('\n', stderr);
}
fputc('\n', stderr);
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i = game->board[row][col];
if (i == 0) i = '.';
fputc(i, stderr);
}
fputc('\n', stderr);
}
fflush(stderr);
#endif
/* we treat the board as horizontal even if it's not */
row = (orientation == HORIZONTAL ? number : Letter-'A'+1);
col = (orientation == HORIZONTAL ? Letter-'A'+1 : number);
assert((word != NULL) && (game->boardfile != NULL) && (game->fullrack != NULL) && (tiles != NULL));
i = col;
for (;;) {
if (*s == '\0') break;
if (game->board[row][i] == 0) {
/* Place first letter from "tiles" here */
hscore += ((tmp = score[tmpch = tiles[nexttile]]) * lettermult[row][i]);
game->board[row][i] = tmpch; // PLACE THE TILE ON THE BOARD. Not sure where to get apparent_letter
game->apparent_letter[row][i] = word[i-col];
wmult *= wordmult[row][i];
nexttile += 1;
if (game->vertical_word[row][i] != NULL) {
tmp = (game->vertical_score[row][i] + (score[tmpch] * lettermult[row][i]))
* wordmult[row][i];
vscore += tmp;
game->vertical_word[row][i][game->vindex[row][i]] = *s; /* Plug in the letter to the vword */
game->vertical_word[row][i][game->vindex[row][i]] = '?'; /* restore */
}
} else { // letter on the board already
tmp = score[tmpch = game->apparent_letter[row][i]];
hscore += tmp;
}
s += 1;
i += 1;
} /* simple hscore, and vscores now all added */
hscore *= wmult;
if (nexttile != placed) {
fprintf(stderr, "nexttile: %d placed: %d\n", nexttile, placed);
assert(nexttile == placed); // will only be false if some tile was on the board where we expected the square to be empty
}
if (placed == RACKSIZE) {
hscore += BINGO;
}
game->movesconsidered += 1;
if (hscore+vscore > game->bestscore) {
// save the highest scoring play in the game state so that
game->bestscore = hscore+vscore;
strcpy(game->playtiles, tiles);
strcpy(game->playword, word);
strcpy(game->playtilesleft, tilesleft);
strcpy(game->playtemplate, template);
game->playplaced = placed;
game->playLetter = Letter;
game->playnumber = number;
game->playorientation = orientation;
}
#ifdef never
fprintf(stderr, "\n\nBoard at end:\n");
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i = game->apparent_letter[row][col];
if (i == 0) i = '.';
fputc(i, stderr);
}
fputc('\n', stderr);
}
fputc('\n', stderr);
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i = game->board[row][col];
if (i == 0) i = '.';
fputc(i, stderr);
}
fputc('\n', stderr);
}
fflush(stderr);
#endif
// recurse here
if (game->player == 0) {
game->player = 1;
} else {
game->player = 0; game->ply++;
}
game->tilesplaced += placed;
strcpy(game->tiles, game->remaining_tiles); // may not need 'remaning_tiles'. That's basically wht 'tiles' is in this program.
{
int before = game->movesconsidered;
enumerate_all_plays(game);
if (game->movesconsidered == before) { // broken test due to game being restored on exit
// no moves found
fprintf(stderr, "-------------\nSOLUTION!\n\n");
for (row = 1; row <= HEIGHT; row++) {
for (col = 1; col <= WIDTH; col++) {
int i = game->board[row][col];
if (i == 0) i = '.';
fputc(i, stderr);
}
fputc('\n', stderr);
}
fflush(stderr);
}
}
memmove(game, ©, sizeof(GAMESTATE));
/* I guess the recursive call to 'minimax()' should go here??? */
}
static int myscore = 0;
static int oppscore = 0;
static char *dict = NULL;
static int vertical_score[HEIGHT+2][WIDTH+2];
static int tiles_held = 0;
static char tiles[/*RACKSIZE*/MAX_TILES+1];
static char fullrack[MAX_TILES+1];
static char *crosschecks[HEIGHT+2][WIDTH+2];
static char *vertical_word[HEIGHT+2][WIDTH+2];
static int vindex[HEIGHT+2][WIDTH+2];
static char remaining_tiles[MAX_TILES+1];
static char *boardfile = NULL; /* This should be in "main()" but
for hacky reasons (HTML in playword()) it is global *for now* */
//static int orientation = 0;
static NODE *dawg;
static INDEX nedges;
/*--------------------- crosscheck code -------------------------*/
/*
When placing a word horizontally, if it abuts to any tiles either
above or below, we will have generated a wildcard string consisting
of the tiles above, a "?", and the tiles below, from which we then
find all the valid words allowed which match that wildcard string.
From that we find which letters were valid at that position, and
we return the set of valid letters to the scrabble code, so that
the search for legal plays can be trimmed for speed.
*/
/* External interface procedure follows this internal procedure, which needs
a lot of extra parameters that the interface isn't really interested in */
#include "crosscheck.c"
/* This is a 'black box' procedure which can be replaced by anything which
behaves the same even though implemented differently. In fact the
internal code of this function is a 'quick hack' and probably should
be replaced by something neater.
INTERFACE: inputs: word list, wild-card string containing one "?"
output: string of letters which the "? could represent
or NULL if none found. (i.e this square is blocked)
example: twl98, "c?t" -> "auo"
(cat, cut and cot all matching the pattern)
*/
char *convert_wildcard_to_permitted_set(NODE *dawg, char *word)
{
char result[MAX_WORD_LEN];
static char set[MAX_WORD_LEN];
int i = 0;
*set = '\0';
if (debug) fprintf(stderr, "wildcard: %s\n", word);
(void)crosscheck_internal(dawg, (INDEX)ROOT_NODE, word, result, set, 0, &i);
if (i == 0) return(NULL);
if (debug) fprintf(stderr, " -> %s\n", set);
return(set);
}
//#include "fix_scrabble.c"
static void fix_scrabble(
#ifdef USE_GAMESTATE
GAMESTATE *game,
#define GAME game,
#define STATE game->
#define playword recursive_playword
#else
#define GAME
#define STATE
#endif
NODE *dawg, INDEX i,
char *word, char *template, char *res, char *tilesleft,
char *placedtiles, int placed,
int len, int *found, int L, int n,
int orientation
)
{
int endsword, last, ch, target;
NODE node;
INDEX link;
//fprintf(stderr, "fix 1\n");
for (;;) {
//fprintf(stderr, "fix 2: node = %p, dawg = %p, i = %d (max %d)\n", node, dawg, i, nedges); // 165374
node = dawg[i++];
//fprintf(stderr, "fix 2a\n");
ch = (int)((node >> V_LETTER) & M_LETTER);
last = ((node & (INDEX)M_END_OF_NODE) != 0);
endsword = ((node & M_END_OF_WORD) != 0);
link = node & M_NODE_POINTER;
//fprintf(stderr, "fix 2b\n");
res[len] = ch; res[len+1] = '\0';
//fprintf(stderr, "fix 2c\n");
target = *word; target &= 255;
//fprintf(stderr, "fix 3\n");
if (ch != 0) {
if (ch == target) { /* matches a tile on the board already */
//fprintf(stderr, "fix 4\n");
if (endsword && *(word+1) == '\0') {
playword(GAME placedtiles, res, tilesleft, template,
placed, L, n, orientation);
(*found)++;
}
if (*(word+1) != '\0' && link != 0) {
(void) fix_scrabble(GAME dawg, link, word+1, template, res, tilesleft,
placedtiles, placed, len+1, found, L, n, orientation);
}
//fprintf(stderr, "fix 5\n");
} else if (target == BLANKCH) { /* We matched a wildcard. If we have
the correct letter, play it; otherwise play the blank */
if (endsword && *(word+1) == '\0') {
//fprintf(stderr, "fix 6\n");
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
placedtiles[placed] = ch;
playword(GAME placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation);
(*found)++;
}
//fprintf(stderr, "fix 7\n");
s = strchr(tilesleft, BLANKCH);
if (s != NULL) { /* If not, do we have a blank left to play? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
//fprintf(stderr, "fix 8\n");
res[len] = latin1_toupper(ch); /* Signal blank to display routine */
/* This trick is not ideal. Would be better to have a
parallel array to 'res' which is given the equivalent
of 'apparent_letter' instead of uppercase. (i.e. the actual
blank character. Note in almost every case I can think of,
it is better to play the actual letter if you have it
rather than the blank. The only exception is when you're
playing the same letter twice in a word, once as the letter
and once as the blank. In that case, you don't know which
of the two positions may be a double or triple letter square.
But if the blank is not needed in a word at all because
you already have all the letters, why would you ever play it?
*/
placedtiles[placed] = BLANKCH; /* blank */
playword(GAME placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation);
(*found)++;
}
//fprintf(stderr, "fix 9\n");
}
if (*(word+1) != '\0' && link != 0) {
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
placedtiles[placed] = ch;
(void) fix_scrabble(GAME dawg, link, word+1, template, res, tilesleft+1,
placedtiles, placed+1, len+1, found, L, n, orientation);
}
//fprintf(stderr, "fix 10\n");
s = strchr(tilesleft, BLANKCH);
if (s != NULL) { /* If not, do we have a blank left? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
res[len] = latin1_toupper(ch); /* Signal blank to display routine */
placedtiles[placed] = BLANKCH; /* Blank */
(void) fix_scrabble(GAME dawg, link, word+1, template, res, tilesleft+1,
placedtiles, placed+1, len+1, found, L, n, orientation);
}
}
} else if (target == '[') { /* Is this letter in our set of valid letters? */
char choices[(WIDTH * (256+2)) + 1];
char *s, *saved = word;
//fprintf(stderr, "fix 11\n");
strcpy(choices, word+1);
s = strchr(choices, ']'); /* We assume well-formed expressions */
*s = '\0';
word = strchr(word, ']');
if (strchr(choices, ch) != NULL) {
if (endsword && *(word+1) == '\0') {
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
placedtiles[placed] = ch;
playword(GAME placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation);
(*found)++;
}
s = strchr(tilesleft, BLANKCH);
if (s != NULL) { /* If not, do we have a blank left? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
res[len] = latin1_toupper(ch); /* Signal blank to display routine */
placedtiles[placed] = BLANKCH; /* Blank */
playword(GAME placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation);
(*found)++;
}
}
//fprintf(stderr, "fix 12\n");
if (*(word+1) != '\0' && link != 0) {
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
placedtiles[placed] = ch;
(void) fix_scrabble(GAME dawg, link, word+1, template, res, tilesleft+1,
placedtiles, placed+1, len+1, found, L, n, orientation);
}
s = strchr(tilesleft, BLANKCH);
if (s != NULL) { /* If not, do we have a blank left? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
res[len] = latin1_toupper(ch); /* Signal blank to display routine */
placedtiles[placed] = BLANKCH; /* Blank */
(void) fix_scrabble(GAME dawg, link, word+1, template, res, tilesleft+1,
placedtiles, placed+1, len+1, found, L, n, orientation);
}
}
}
//fprintf(stderr, "fix 13\n");
word = saved;
}
}
//fprintf(stderr, "fix 14\n");
if (last) break;
}
//fprintf(stderr, "fix 15\n");
}
#undef STATE
#undef GAME
#ifdef playword
#undef playword
#endif
int scrabble_match(
#ifdef USE_GAMESTATE
GAMESTATE *game,
#endif
NODE *dawg, char *word, char *tiles,
int L, int n, int orientation)
{
char result[MAX_WORD_LEN];
char placedtiles[MAX_WORD_LEN];
int i = 0;
//fprintf(stderr, "match 1\n");
result[0] = '\0'; placedtiles[0] = '\0';
fix_scrabble(
#ifdef USE_GAMESTATE
game,
#endif
dawg, (INDEX)ROOT_NODE, word, word, result, tiles,
placedtiles, 0, 0, &i, L, n,
orientation);
//fprintf(stderr, "match 2\n");
return(i);
}
/*--------------------------------------------------------------*/
/*
This reads a board in the simple file format which Kevin Cowtan
uses in his board-graphic image generator software. I just happened
to have some cgi web page software which generates this format so I
plan to reuse it to create a graphical front-end to solving scrabble
problems.
*/
#include "readboard.c"
/*--------------------------------------------------------------*/
/*
This looks at the place where a tile is likely to be played, and
whether there are tiles abutting above or below it, which would
permit or deny a word to be placed there. This generates a
wild-card string which is then expanded in the code above to
generate the set of letters which are valid here. It is that
set which is stored, not the wild card string or the words themselves.
*/
#ifdef USE_GAMESTATE
char *create_crosscheck_wildcard(GAMESTATE *game, int r, int c)
{
char crosscheck[WIDTH+2];
char *s;
int rp;
game->vertical_score[r][c] = 0;
/* Already a tile here so crosscheck is meaningless */
if (game->board[r][c] != 0) return(NULL);
/* none above and none below? */
if ((game->board[r-1][c] == 0) && (game->board[r+1][c] == 0)) return(NULL);
/* what's above? */
rp = r-1;
while (game->board[rp][c] != 0) rp -= 1;
rp += 1; /* row of 1st letter in crosscheck word */
s = crosscheck;
while (rp != r) {
*s = game->apparent_letter[rp][c];
game->vertical_score[r][c] += score[*s]; /* 0 if blank */
if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
s += 1; rp += 1;
}
*s++ = '?'; /* r */
game->vindex[r][c] = s-crosscheck-1;
/* what's below? */
rp = r+1;
while (game->board[rp][c] != 0) {
*s = game->apparent_letter[rp][c];
game->vertical_score[r][c] += score[*s]; /* 0 if blank */
if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
s += 1; rp += 1;
}
*s = '\0';
game->vertical_word[r][c] = strdup(crosscheck);
if (crosscheck == NULL) return NULL; // this is a temp patch and may not fix the bug...
return(strdup(crosscheck));
}
#else
char *create_crosscheck_wildcard(int r, int c)
{
char crosscheck[WIDTH+2];
char *s;
int rp;
vertical_score[r][c] = 0;
/* Already a tile here so crosscheck is meaningless */
if (board[r][c] != 0) return(NULL);
/* none above and none below? */
if ((board[r-1][c] == 0) && (board[r+1][c] == 0)) return(NULL);
/* what's above? */
rp = r-1;
while (board[rp][c] != 0) rp -= 1;
rp += 1; /* row of 1st letter in crosscheck word */
s = crosscheck;
while (rp != r) {
*s = apparent_letter[rp][c];
vertical_score[r][c] += score[*s]; /* 0 if blank */
if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
s += 1; rp += 1;
}
*s++ = BLANKCH; /* r */
vindex[r][c] = s-crosscheck-1;
/* what's below? */
rp = r+1;
while (board[rp][c] != 0) {
*s = apparent_letter[rp][c];
vertical_score[r][c] += score[*s]; /* 0 if blank */
if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
s += 1; rp += 1;
}
*s = '\0';
vertical_word[r][c] = strdup(crosscheck);
return(strdup(crosscheck));
}
#endif
/*--------------------------------------------------------------*/
/*
Can we slot a word into the board at this row,col and length(*)?
If so, then the very last thing we do before returning is to actually
generate the words. This is not really good design - we should
pass the wildcard which this generates up a level and have that
level do the search. This procedure generates a wild-card string
using fixed letters, "[...]" letter sets, and wildcards ("?")
which when expanded returns valid words which can be played here.
*: Note 'length' here doesn't mean word length. It means number of
tiles to be placed. The word may be longer because of tiles
already on the board that we are placing around.
*/
void slot_internal(
GAMESTATE *game,
#define GAME game,
#define STATE game->
int orig_r, int orig_c,
int r, int c,
int still_to_place, int placed,
char *pattern,
int touches_center, int touches_horiz, int touches_vert,
int orientation)
{
int valid;
int pp = strlen(pattern);
int opp = strlen(pattern);
char *s;
//fprintf(stderr, "slot 1\n");
/* No more loop. Just place one, and recurse. If I had done this
with the scrabble program to begin with, I wouldn't have had the
stupid bug to do with playing blanks as the same letter as another
letter you hold in the rack... */
/* Ran off end of board with tiles still to place? */
if ((c > WIDTH) && (still_to_place > 0)) return;
/* Covered with an earlier hook? */
if ((placed == 0) && (STATE board[r][c-1] != 0) && (c != 1)) return;
/* (special case for first col ... */
//fprintf(stderr, "slot 2\n");
while (STATE board[r][c] != 0) {
/* There is already a tile on the board here. Careful with blanks */
pattern[pp++] = STATE apparent_letter[r][c++]; pattern[pp] = '\0';
}
if ((c) > WIDTH) return; /* Oops, we went over the edge */
/* If center square was empty this must be the first move */
if ((STATE board[WIDTH/2+1][HEIGHT/2+1] == 0)
&& (((WIDTH/2)+1 == r) && (c == (WIDTH/2)+1))
) {
touches_center = (touches_center || TRUE);
}
if (STATE board[r][c-1] != 0 || STATE board[r][c+1] != 0) touches_horiz = (touches_horiz || TRUE);
if (STATE board[r-1][c] != 0 || STATE board[r+1][c] != 0) touches_vert = (touches_vert || TRUE);
//fprintf(stderr, "slot 3\n");
if (STATE crosschecks[r][c] == NULL) { /* no tiles above or below in this col */
if (strchr(STATE tiles, '?') != NULL) {
/* We hold a blank so it could be anything */
sprintf(pattern+pp, "?");
} else {
/* restrict search space when possible, ie only those letters
for which we hold tiles */
sprintf(pattern+pp, "[%s]", STATE tiles);
}
} else if (*STATE crosschecks[r][c] == '!') {
/* If no valid crosscheck at all, then reject this slot - square is blocked */
pattern[opp] = '\0'; /* undo recursion */
return;
} else if ((strcmp(STATE crosschecks[r][c], "?") == 0)
&& (strchr(STATE tiles, '?') == NULL)) {
/* we don't hold a blank, so do a reduction-in-strength of a
wild-card "?" to [abcdefg] (i.e. only the tiles we hold) */
sprintf(pattern+pp, "[%s]", STATE tiles);
} else if (strcmp(STATE crosschecks[r][c], "?") == 0) {
/* we do hold a blank, so allow anything */
sprintf(pattern+pp, "%s", STATE crosschecks[r][c]);
} else {
/* This letter is constrained by specific cross-checks */
sprintf(pattern+pp, "[%s]", STATE crosschecks[r][c]);
}
//fprintf(stderr, "slot 4\n");
pp = strlen(pattern); pattern[pp] = '\0';
placed += 1; still_to_place -= 1;
if (still_to_place != 0) {
/* Should this test be moved up before some of the code above? */
//fprintf(stderr, "slot 5\n");
slot_internal(GAME orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz, touches_vert,
orientation);
//fprintf(stderr, "slot 5a\n");
pattern[opp] = '\0'; /* undo recursion */
//fprintf(stderr, "slot 5b\n");
return;
}
/* after placing all tiles, are there still some letters abutting
to the right? If so, add them to the string to be matched */
{int p = c+1; while (STATE board[r][p] != 0) {
/*hscore += ...[r][p];*/
touches_horiz = TRUE;
pattern[pp++] = STATE apparent_letter[r][p++]; /* Careful with blanks */
}}
pattern[pp] = '\0';
//fprintf(stderr, "slot 6\n");
valid = (touches_horiz ||
(touches_vert && (placed > 1)) ||
(touches_center && (placed > 1)));
//fprintf(stderr, "slot 7\n");
if (valid) scrabble_match(GAME dawg, pattern, STATE tiles,
(orientation == HORIZONTAL ? orig_c : orig_r)-1+'A',
(orientation == HORIZONTAL ? orig_r : orig_c), orientation);
/* the x/y param could be done more intelligently */
//fprintf(stderr, "slot 8\n");
}
#undef STATE
#undef GAME
int slot(
GAMESTATE *game,
int r, int c, int l, int orientation)
{
char pattern[(WIDTH*(256+2))+1];
pattern[0] = '\0';
slot_internal(
#ifdef USE_GAMESTATE
game,
#endif
r, c, r, c, l, 0, pattern, FALSE, FALSE, FALSE,
orientation);
//fprintf(stderr, "slot returned\n");
return(0); /* Needs to be true if any were placed */
}
void enumerate_all_plays(GAMESTATE *game)
{
int row = 0, col = 0;
int length = 0;
int orientation = 0;
if ((game->ply == 0) && (game->player == 0)) {
// Initial move. The code above would work but we want to restrict the first plays
// as an optimisation
row = 8; col = 7;
for (length = 2; length <= 4; length++) {
/* Can I legally place this many tiles onto the board here? */
if (slot(game, row, col, length, orientation)) {
}
}
} else {
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 game->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 (game->vertical_word[row][col] != NULL) free(game->vertical_word[row][col]); game->vertical_word[row][col] = NULL;
if (game->crosschecks[row][col] != NULL) free(game->crosschecks[row][col]);
/* first of all get wildcard pattern, eg "w?rd" : */
game->crosschecks[row][col] = create_crosscheck_wildcard(game, row, col);
/* Then convert it to a set of valid letters */
if (game->crosschecks[row][col] == NULL) {
char *tmp;
/* game->crosschecks don't make sense here */
fprintf(stderr, "calling strdup\n");
tmp = strdup("?");
fprintf(stderr, "-> Assign to game[][]\n");
game->crosschecks[row][col] = tmp;
fprintf(stderr, "<- Assign to game[][]\n");
} else {
s = convert_wildcard_to_permitted_set(dawg, game->crosschecks[row][col]);
free(game->crosschecks[row][col]); game->crosschecks[row][col] = NULL;
if (s == NULL) {
/* No letter can currently be placed in this square legally */
game->crosschecks[row][col] = strdup("!");
/* "!" is easier to debug than empty string */
} else {
game->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 */
for (col = 1; col <= WIDTH; col++) {
/* if (debug) fprintf(stderr, "Testing row %d col %d\n", row, col); */
for (length = 1; length <= 4/*MIN(game->tiles_held, 7)*/; length++) {
/* Can I legally place this many tiles onto the board here? */
if (slot(game, row, col, length, orientation)) {
/* 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) */
}
}
}
} /* Try every row on the board */
/* flip the board around the x=y diagonal */
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 game->apparent_letter at row,col */
i = game->board[row][col];
game->board[row][col] = game->board[col][row];
game->board[col][row] = i;
i = game->apparent_letter[row][col];
game->apparent_letter[row][col] = game->apparent_letter[col][row];
game->apparent_letter[col][row] = i;
}
}
}
} /* end of horiz/vert placement loop */
}
return;
/* If want to make best play on board and save it, do it here */
report = TRUE;
// OUTSTANDING BUG: when playword displays this move again, it forgets to add in the vscore component!??!
if (game->bestscore != 0) {
/* if orientation == VERTICAL it expects the board
to have already been swapped... quick hack... */
if (game->playorientation == VERTICAL) {
/* flip the board around the x=y diagonal */
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 game->apparent_letter at row,col */
i = game->board[row][col];
game->board[row][col] = game->board[col][row];
game->board[col][row] = i;
i = game->apparent_letter[row][col];
game->apparent_letter[row][col] = game->apparent_letter[col][row];
game->apparent_letter[col][row] = i;
}
}
}
}
// redo crosschecks: THIS DUPLICATED CODE SHOULD BE MADE INTO A PROCEDURE
for (row = 1; row <= HEIGHT; row++) {
/* calculate game->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 (game->crosschecks[row][col] != NULL) free(game->crosschecks[row][col]);
if (game->vertical_word[row][col] != NULL) free(game->vertical_word[row][col]);
game->vertical_word[row][col] = NULL;
/* first of all get wildcard pattern, eg "w?rd" : */
game->crosschecks[row][col] = create_crosscheck_wildcard(game, row, col);
/* Then convert it to a set of valid letters */
if (game->crosschecks[row][col] == NULL) {
/* game->crosschecks don't make sense here */
game->crosschecks[row][col]= strdup("?");
} else {
s = convert_wildcard_to_permitted_set(dawg, game->crosschecks[row][col]);
free(game->crosschecks[row][col]);
if (s == NULL) {
/* No letter can currently be placed in this square legally */
game->crosschecks[row][col] = strdup("!");
/* "!" is easier to debug than empty string */
} else {
game->crosschecks[row][col] = strdup(s);
}
}
}
}
fprintf(stdout, "\n");
recursive_playword(game, game->playtiles, game->playword, game->playtilesleft,
game->playtemplate, game->playplaced, game->playLetter,
game->playnumber, game->playorientation);
}
fprintf(stdout, "%d moves were considered for this play\n", game->movesconsidered);
}
int main(int argc, char **argv)
{
int i;
int row = 0, col = 0;
int length = 0;
int orientation = 0;
char *dict = NULL;
GAMESTATE *game;
if (debug) report = TRUE;
if (opt_html) report = TRUE;
game = calloc(1, sizeof(struct GAMESTATE));
if (argc != 3) {
if (argc <= 2) {
dict = "owl2";
} else {
fprintf(stderr, "syntax: %s board.dat dict?\n", argv[0]);
exit(1);
}
} else dict = argv[2]; /* Default word list is TWL98 */
/* default param when debugging makes running gbd easier */
if (argv[1] == NULL) game->boardfile = "empty.txt"; else game->boardfile = argv[1];
if (!dawg_init(dict, &dawg, &nedges)) {
fprintf(stderr, "%s: cannot open wordlist '%s'\n", argv[0], dict);
exit(2);
}
/* Clear the arrays */
assert(WIDTH == HEIGHT);
for (row = 0; row < (HEIGHT+2); row++) {
for (col = 0; col < (WIDTH+2); col++) {
game->board[row][col] = 0; game->apparent_letter[row][col] = 0;
game->crosschecks[row][col] = NULL;
game->vertical_word[row][col] = NULL;
game->vindex[row][col] = 0;
}
}
for (i = 0; i < 256; i++) {
tot[i] = 2; /* Blank ;-) */
score[i] = 0;
totprob[i] = 0.0;
watkins_rackvalue[i] = 25.0;
}
for (i = 0; i < 26; i++) {
tot['a'+i] = itot[i];
score['a'+i] = iscore[i];
watkins_rackvalue['a'+i] = iwatkins_rackvalue[i];
}
/* hand-coded random board. This could be replaced by a more complex
format which includes tile distributions, values, language etc */
strcpy(game->fullrack, FULLRACK); /* If no tiles given in file, do megamove analysis */
game->fullrack[strlen(game->fullrack)-2] = '\0';
read_board(game, game->boardfile);
if (game->tiles[0] == '\0') {
megaanalysis = TRUE;
game->tiles_held = strlen(game->fullrack);
strcpy(game->tiles, game->fullrack);
}
game->ply = 0; game->player = 0; game->tilesplaced = 0;
enumerate_all_plays(game);
exit(0);
}