/*
(The definitive word list for this game can be found here:
http://www.thewordlist.com/main/wordlineDict.htm
)
Maybe this will turn in to a program to play 'wordox' (like 'reversi'
but with words)
Currently 'work in progress' and does NOT yet work. Well, actually
sort of it does, but I've only put 15 minutes of work into it so far
and don't really want to mislead anyone that it might be useful.
See: http://players.won.net/quickgames/web/ for the rules.
The file format is more like that of the upwords code, except the digit
before each letter denotes which color the letter is, and there
is an extra parameter after the rack etc which says what your
colour is for this play.
E L L S . . . . . . . . .
2N .2A . . . . . . . . . .
2G .2K .2P . . . . . . . .
2I .2E .2S . . . . . . . .
R E S T A R T . . . . . .
2T . . .2L . . . . . . . .
. . . .2M . . . . . . . .
f l a g s . . . . . . . . <--- this is the suggested move (see below)
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
XAGSFLX 0 0 1
This version of the program is modified to print out two pieces
of useful information along with the simple score - the first
is the single-letter hooks at the left or right of the word,
which are an indication of how easily the word can be stolen
by placing another word perpendicular to it. The second is
a count of how many words exist which contain this word inside
them. This is an indication of how easily a word can be stolen
by expanding on it in the same direction.
The former test is very cheap and can be done on the fly, but the
latter test is currently rather expensive, taking about 2.5 hours
for a single board evaluiation. *However*... both tests are
effectively static and can be worked out in advance and the
results coded into a table (eg a hash table, or a keyed database,
or a keyed trie) thus allowing instant lookup during a game.
See the files wtest.dat and wtest.out for a sample game with output.
In the game above, the 4 best moves are:
play: flags at A8 across for 9 ([]flags[]; *flags* -> 12 words)
play: fags at B8 across for 8 ([]fags[]; *fags* -> 1 words)
play: gals at B8 across for 8 ([]gals[]; *gals* -> 35 words)
play: lags at B8 across for 8 ([cfs]lags[]; *lags* -> 35 words)
Of the 8 point moves, fags is clearly a better choice because it has
no adjacent hooks for vertical words and cannot be extended horizontally
either (the 1 match for the *fags* wildcard is the word fags itself)
Whether it is better to just take the points with the 9-point word
flags, versus playing the very safe 8 point word fags, is something
that will have to be determined by experience. I think it should
be possible to codify choices like that with a parameter, have a
computer play against a computer in several thousand games, and
adjust its threshholds according to play, to make the right decision.
One factor this code does not take into account is whose colour you
are stealing. In a two-player game, it doesn't matter, but in a
4-player game, you probably want to attack the highest-scoring
rival rather than just score high yourself. I.e. the evaluation
function should be your win + highest rival's loss, not just your win.
Strategy: the French seem to be much more interested in Wordox than
the Americans. Here are some strategic tips from a French web site...
Si vous ouvrez la grille :
Essayez avant tout de faire un mot de 7 lettres reliant la case centrale ` une case rose. Ainsi, vous gagnez 7 points imprenables.
Si c'est impossible, jouez le mot le plus tordu possible, n'admettant aucune rallonge en une lettre et ne permettant pas des collages faciles. Les abriviations sont intiressantes pour cela.
Si vous complitez une grille :
Ne jouez pas sur vos lettres, sauf si cela permet de protiger difinitivement un mot assez long.
Attaquez un mot de l'adversaire le mieux placi au score, de prifirence par une rallonge, ` difaut un collage ou un raccord perpendiculaire.
Jouez pluttt les lettres simples, les S, les E, pour laisser un reliquat pourri.
Si vous menez au score :
N'hisitez pas ` vider la grille, surtout si vous avez des points orange.
Incitez l'adversaire ` vider la grille si vous ne pouvez le faire vous-mjme.
Passez votre tour si vous n'avez pas de bonnes lettres et que vos mots sont volables.
Si vous jtes meni au score :
Ne vous approchez pas du bord de la grille, mais magonnez le plus possible.
Avec de belles lettres, prenez le risque de poser un mot long. Avec un peu de chance, vous le garderez, sinon dites-vous que ce n'itait pas votre partie !
Et si vous jtes un vrai truand, commencez par faire un raccord faux et faites semblant de voir mieux ailleurs. Votre adversaire se laissera peut-jtre intoxiquer ...
Here is the list of acceptable 2/3 letter words in Wordox:
http://perso.infonie.fr/chr.amet/wordox23.htm
plus some others typed in by players:
http://donaldz.free.fr/wordox/
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include "splib.h"
#ifndef FALSE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
int spell_verbose = FALSE;
static int debug = FALSE;
#define WIDTH 13
#define HEIGHT 13
#define RACKSIZE 7
#define MAX_TILES 100
/* 1..WIDTH for board, 0 and (WIDTH+1) for tombstones */
/* these two are swapped x/y with orientation */
static char board[(HEIGHT+2)][(WIDTH+2)]; /* row, col format */
static char colour[(HEIGHT+2)][(WIDTH+2)];
/* these two are recalculated on each orientation so don't need to be swapped */
static char *crosschecks[(HEIGHT+2)][(WIDTH+2)];
static int vertical_score[(HEIGHT+2)][(WIDTH+2)];
static char remaining_tiles[MAX_TILES+1];
static int score, tiles_left_in_bag, my_colour = 1;
static int tiles_held = 0;
static char tiles[RACKSIZE+1];
/* To do: when calculating crosschecks, work out how much putting a tile
on the crosscheck square will get you, from the vertical component.
Pre-compute all but the last part (i.e. the value of the placed tile) */
#define HORIZONTAL 1
#define VERTICAL 2
static NODE *dawg;
static INDEX nedges;
#define swap(a,b,temp) {temp = a; a = b; b = temp;}
/*--------------------- tactical play support code -------------------------*/
int do_wild(
NODE *dawg, INDEX i, char *word, char *res, int len, int *found) {
int endsword, last, ch, target;
NODE node;
INDEX link;
INDEX origi;
origi = i;
target = ((int)*word)&255; /* care taken for signed ISO alphabets */
if (*word == '*') {
res[len] = '\0';
(void) do_wild(dawg, origi, word+1 /* skip '*', match nothing */,
res, len, found);
}
for (;;) {
node = dawg[i++];
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;
res[len] = ch; res[len+1] = '\0';
if (ch != 0) {
if (ch == target || target == '?') {
/* single wildcard 1 letter match */
if (endsword && *(word+1) == '\0') {
/*fprintf(stdout, "word: %s\n", res);*/ (*found)++;
} else if ((endsword && *(word+1) == '*') && (*(word+2) == '\0')) {
/* special-case hack for trailing * */
/*fprintf(stdout, "word: %s\n", res);*/ (*found)++;
}
if (*(word+1) != '\0' && link != 0)
(void) do_wild(dawg, link, word+1, res, len+1, found);
} else if (target == '*') {
/* multiple wildcard - 0-N letters match */
if (endsword && *(word+1) == '\0') {
/* trailing* */
/*fprintf(stdout, "word: %s\n", res);*/ (*found)++;
}
if (link != 0) { /* link == 0 means this letter terminates here */
/* skip the * and see what we get if it has matched to here: */
(void) do_wild(dawg, link, word+1 /* skip '*' */, res, len+1, found);
/* let this letter match the * and see
if the rest of the pattern matches: */
(void) do_wild(dawg, link, word /* keep '*' */, res, len+1, found);
}
}
}
if (last) break;
}
return(0==0);
}
/* Simply return a count of the number of words which this wildcard
can expand to. Since the wildcard we use is "*word*", this returns
the number of words which can be built around this one. (+1, because
it returns "word" itself too)
*/
int wildcard(NODE *dawg, char *word) {
char result[MAX_WORD_LEN];
int i = 0;
(void)do_wild(dawg, (INDEX)ROOT_NODE, word, result, 0, &i);
return(i);
}
/*--------------------- crosscheck code -------------------------*/
static int crosscheck_internal(
NODE *dawg, INDEX i,
char *word, char *res, char *set,
int len, int *found
)
{
int endsword, last, ch, target;
NODE node;
INDEX link;
static int wildch = '\0';
for (;;) {
node = dawg[i++];
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;
res[len] = ch; res[len+1] = '\0';
target = ((int)*word)&255;
if (ch != 0) {
if (ch == target || target == '?') {
if (target == '?') {
wildch = ch;
}
if (endsword && *(word+1) == '\0') {
int i;
(*found)++;
/* Add ch to crosscheck set if not already there */
/* We just assume only 1 '?' per word, and last wildch was it */
if (strchr(set, wildch) == NULL) {
i = strlen(set);
set[i] = wildch; set[i+1] = '\0';
}
}
if (*(word+1) != '\0' && link != 0)
(void) crosscheck_internal(dawg, link, word+1, res, set, len+1, found);
}
}
if (last) break;
}
return(0==0);
}
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(stdout, "wildcard: %s\n", word);
(void)crosscheck_internal(dawg, (INDEX)ROOT_NODE, word, result, set, 0, &i);
if (i == 0) return(NULL);
if (debug) fprintf(stdout, " -> %s\n", set);
return(set);
}
/*--------------------- placement code -------------------------*/
static void fix_wordox(
NODE *dawg, INDEX i,
char *word, char *res, char *tilesleft,
int len, int *found, int L, int n,
int hscore, int vscore, int orientation)
{
int endsword, last, ch, target;
NODE node;
INDEX link;
for (;;) {
node = dawg[i++];
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;
res[len] = ch; res[len+1] = '\0';
target = *word; target &= 255;
if (ch != 0) {
if (ch == target) { /* matches a tile on the board already */
if (endsword && *(word+1) == '\0') {
char lh[256], rh[256];
char s[WIDTH+2];
char *set;
char comments[1024];
sprintf(s, "?%s", res);
set = convert_wildcard_to_permitted_set(dawg, s);
strcpy(lh, (set == NULL ? "" : set));
sprintf(s, "%s?", res);
set = convert_wildcard_to_permitted_set(dawg, s);
strcpy(rh, (set == NULL ? "" : set));
sprintf(s, "*%s*", res);
sprintf(comments, " ([%s]%s[%s]; *%s* -> %0d words)", lh, res, rh,
res, wildcard(dawg,s));
fprintf(stdout, "play: %s at %c%d %s for %d%s\n", res, L, n,
(orientation == HORIZONTAL ? "across" : "down"),
hscore+vscore, comments
);
(*found)++;
}
if (*(word+1) != '\0' && link != 0) {
fix_wordox(dawg, link, word+1, res, tilesleft,
len+1, found, L, n, hscore, vscore, orientation);
}
} else if (target == '[') { /* Is this letter in our set of valid letters? */
char choices[(WIDTH * (256+2)) + 1];
char *s, *saved = word;
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;
{
char lh[256], rh[256];
char s[WIDTH+2];
char *set;
char comments[1024];
sprintf(s, "?%s", res);
set = convert_wildcard_to_permitted_set(dawg, s);
strcpy(lh, (set == NULL ? "" : set));
sprintf(s, "%s?", res);
set = convert_wildcard_to_permitted_set(dawg, s);
strcpy(rh, (set == NULL ? "" : set));
sprintf(s, "*%s*", res);
sprintf(comments, " ([%s]%s[%s]; *%s* -> %0d words)", lh, res, rh,
res, wildcard(dawg,s));
fprintf(stdout, "play: %s at %c%d %s for %d%s\n", res, L, n,
(orientation == HORIZONTAL ? "across" : "down"),
hscore+vscore, comments
);
}
(*found)++;
}
}
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;
fix_wordox(dawg, link, word+1, res, tilesleft+1,
len+1, found, L, n, hscore, vscore, orientation);
}
}
}
word = saved;
}
}
if (last) break;
}
}
void wordox_match(
NODE *dawg, char *word, char *tiles, int L, int n, int orientation,
int hscore, int vscore)
{
int i = 0;
char result[MAX_WORD_LEN];
result[0] = '\0';
if (debug) fprintf(stdout, "match: '%s' using '%s' at %c%0d %s\n", word, tiles, L, n,
(orientation == HORIZONTAL ? "across" : "down"));
fix_wordox(dawg, (INDEX)ROOT_NODE, word, result, tiles, 0, &i, L, n,
hscore, vscore,
orientation);
}
/*--------------------------------------------------------------*/
/*
Board layout is different from Scrabble.
*/
void read_board(char *fname)
{
int row, col;
int c;
FILE *sample;
sample = fopen(fname, "r");
if (sample == NULL) {
fprintf(stderr, "Cannot open board file '%s'\n", fname);
exit(0);
}
for (row = 1; row <= WIDTH; row++) {
if (debug) fprintf(stderr, "Row %02d: ", row);
for (col = 1; col <= WIDTH; col++) {
colour[row][col] = 0;
c = fgetc(sample);
if (c == ' ') {
colour[row][col] = 1;
c = fgetc(sample);
} else if (isdigit(c)) {
colour[row][col] = c-'0';
c = fgetc(sample);
}
if (isalpha(c)) { /* Take care with locale for other language versions */
board[row][col] = tolower(c);
if (debug) fprintf(stderr, "%c", tolower(c));
} else if (debug) fprintf(stderr, " ");
}
c = fgetc(sample); /* newline */
if (c != '\n') {
fprintf(stderr, "Data format in .dat file\n");
exit(0);
}
if (debug) fprintf(stderr, "\n");
}
tiles_held = 0;
for (col = 0; col < RACKSIZE; col++) {
c = fgetc(sample);
if (c == '?') continue;
if (c == '*') c = '?';
if (isalpha(c)) c = tolower(c);
tiles[tiles_held++] = c;
}
tiles[tiles_held] = '\0';
fscanf(sample, " %d %d %d\n", &score, &tiles_left_in_bag, &my_colour);
if (debug) {
fprintf(stderr, "%0d Tiles: %s\n", tiles_held, tiles);
}
remaining_tiles[0] = '\0';
fgets(remaining_tiles, MAX_TILES+1, sample); /* Don't care if error */
fclose(sample);
}
/*--------------------------------------------------------------*/
char *create_crosscheck_wildcard(int r, int c)
{
char crosscheck[(WIDTH+2)];
char *s;
int rp;
int vscore = 0;
int flat = TRUE;
/* Already tiles 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);
rp = r-1;
while (board[rp][c] != 0) {
if (colour[rp][c] != my_colour) vscore += 1;
// do I need to backport the scrabble bugfix for treating
// blanks as a fixed letter?
//if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
rp -= 1; /* what's above? */
}
rp += 1; /* row of 1st letter in crosscheck word */
s = crosscheck; while (rp != r) *s++ = board[rp++][c];
*s++ = '?'; /* r */
rp = r+1;
while ((*s++ = board[rp][c]) != '\0') {
if (colour[rp][c] != my_colour) vscore += 1;
// do I need to backport the scrabble bugfix for treating
// blanks as a fixed letter?
//if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
rp += 1;
/* what's below? */;
}
vertical_score[r][c] = vscore; /* NOT including this tile */
return(strdup(crosscheck));
}
/*--------------------------------------------------------------*/
void slot_internal(int orig_r, int orig_c,
int r, int c,
int still_to_place, int placed,
char *pattern, /* wild-card pattern, built on fly */
int touches_center, int touches_horiz,
int touches_vert, int touches_below,
int tile_showing,
int orientation, int hscore, int vscore)
{
int valid;
int pp = strlen(pattern);
char *s;
/* 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;
if (board[r][c] != 0) {
int i;
/* There is already a tile on the board here. */
pattern[pp++] = board[r][c]; pattern[pp] = '\0';
slot_internal(orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
TRUE, orientation,
hscore+(colour[r][c] != my_colour ? 1 : 0), vscore);
/* add the horizontal component of the score */
pattern[--pp] = '\0'; /* undo recursion */
return;
} else {
/* single tile being placed on board */
hscore += 1;
if (vertical_score[r][c] != 0) vscore += vertical_score[r][c];
}
/* If center square is empty this must be the first move */
if (board[(WIDTH/2)+1][(HEIGHT/2)+1] == 0) {
touches_center = (touches_center || TRUE);
}
if (board[r][c-1] != 0 || board[r][c+1] != 0) touches_horiz = (touches_horiz || TRUE);
if (board[r-1][c] != 0 || board[r+1][c] != 0) touches_vert = (touches_vert || TRUE);
if (crosschecks[r][c] == NULL) {
crosschecks[r][c] = strdup(tiles);
}
/* If no valid crosscheck at all, then reject this slot */
if (*crosschecks[r][c] == '!') return;
assert(strcmp(crosschecks[r][c], "?") != 0);
sprintf(pattern+pp, "[%s]", crosschecks[r][c]);
pp = strlen(pattern);
placed += 1; still_to_place -= 1;
if (still_to_place != 0) {
slot_internal(orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
tile_showing,
orientation, hscore, vscore);
pattern[pp] = '\0';
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 (board[r][p] != 0) {
if (colour[r][p] != my_colour) hscore += 1;
touches_horiz = TRUE; tile_showing = TRUE;
pattern[pp++] = board[r][p++];
}}
pattern[pp] = '\0';
valid = (touches_horiz ||
(touches_vert && (placed > 1)) ||
(touches_center && (placed > 1))); /* Eliminate any plays totally on top of another word */
if (valid) wordox_match(dawg, pattern, tiles,
(orientation == HORIZONTAL ? orig_c : orig_r)-1+'A',
(orientation == HORIZONTAL ? orig_r : orig_c), orientation,
hscore, vscore);
}
void slot(int r, int c, int still_to_place, int orientation) /* wrapper */
{
int touches_center = FALSE;
int touches_horiz = FALSE;
int touches_vert = FALSE;
int touches_below = FALSE;
int tile_showing = FALSE;
char pattern[(WIDTH * (256+2)) + 1];
int placed=0;
pattern[0] = '\0';
/* Covered with an earlier hook */
if (board[r][c-1] != 0) return;
return(slot_internal(r, c,
r, c, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
tile_showing,
orientation, 0, 0));
}
int main(int argc, char **argv)
{
int orientation = 0;
int row = 0, col = 0;
int length = 0;
char *dict = NULL, *boardfile = NULL;
if (argc != 3) {
if (argc == 2) {
dict = "twl98";
} else {
fprintf(stderr, "syntax: %s board.dat dict?\n", argv[0]);
exit(1);
}
} else dict = argv[2]; /* Default word list is TWL98 */
boardfile = argv[1];
if (!dawg_init(dict, &dawg, &nedges)) {
fprintf(stderr, "%s: cannot open wordlist '%s'\n", argv[0], dict);
exit(2);
}
for (row = 0; row < (WIDTH+2); row++) { /* Clear the arrays */
for (col = 0; col < (WIDTH+2); col++) {
board[row][col] = 0;
crosschecks[row][col] = NULL;
}
}
read_board(boardfile);
for (orientation = HORIZONTAL; orientation <= VERTICAL; orientation++) {
for (row = 1; row < (HEIGHT+1); row++) {
for (col = 0; col < (WIDTH+2); col++) {
vertical_score[row][col] = 0;
if (crosschecks[row][col] != NULL) free(crosschecks[row][col]);
crosschecks[row][col] = NULL;
}
for (col = 1; col < (WIDTH+1); col++) {
if (crosschecks[row][col] != NULL) free(crosschecks[row][col]);
crosschecks[row][col] = create_crosscheck_wildcard(row, col);
if (crosschecks[row][col] == NULL) {
crosschecks[row][col] = strdup(tiles); /* was strdump("?") */
} else {
char *s = convert_wildcard_to_permitted_set(dawg, crosschecks[row][col]);
free(crosschecks[row][col]);
crosschecks[row][col] = strdup((s == NULL) ? "!" : s);
}
}
for (col = 1; col < (WIDTH+1); col++) {
for (length = 2; length <= tiles_held; length++) {
if (debug) fprintf(stdout, "Testing %c%d %s: %d\n",
(orientation == HORIZONTAL ? col : row)-1+'A',
(orientation == HORIZONTAL ? row : col),
(orientation == HORIZONTAL ? "across" : "down"),
length);
slot(row, col, length, orientation);
}
}
} /* Try every row on the board */
/* flip the board around the x=y diagonal */
assert(WIDTH == HEIGHT);
for (row = 1; row < (WIDTH+1); row++) {
for (col = 1; col < (WIDTH+1); col++) {
int i;
if (row > col) { /* avoid doing twice (which would be a no-op) */
swap(board[row][col], board[col][row], i);
swap(colour[row][col], colour[col][row], i);
}
}
}
} /* end of horiz/vert placement loop */
{int i; FILE *sample;
sample = fopen(boardfile, "w"); if (sample == NULL) exit(1);
/* If want to make best play on board and save it, do it here */
for (row = 1; row < HEIGHT+1; row++) {
for (col = 1; col < WIDTH+1; col++) {
if (colour[row][col] <= 1) fputc(' ', sample); else fputc('0'+colour[row][col], sample);
if (board[row][col] != 0) fputc(toupper(board[row][col]), sample); else fputc('.', sample);
}
fputc('\n', sample);
}
for (i = 0; i < strlen(tiles); i++) fputc(toupper(tiles[i]), sample);
for (i = strlen(tiles); i < 7; i++) fputc('?', sample);
fprintf(sample, " %d %d %d\n", score, tiles_left_in_bag, my_colour);
if (*remaining_tiles != '\0') fprintf(sample, "tiles: %s\n", remaining_tiles);
fclose(sample);
}
exit(0);
}