C, średnio 500+ 1500 1750 punktów
Jest to stosunkowo niewielka poprawa w stosunku do wersji 2 (patrz uwagi na temat poprzednich wersji poniżej). Istnieją dwie części. Po pierwsze: Zamiast losowego wybierania plansz z puli, program wykonuje teraz iterację po każdej planszy w puli, używając każdej z nich przed powrotem na szczyt puli i powtarzania. (Ponieważ pula jest modyfikowana podczas tej iteracji, nadal będą deski wybierane dwa razy z rzędu lub gorzej, ale nie jest to poważny problem.) Druga zmiana polega na tym, że program śledzi teraz zmiany puli , a jeśli program działa zbyt długo bez poprawiania zawartości puli, określa, że wyszukiwanie „utknęło w martwym punkcie”, opróżnia pulę i zaczyna od nowa. Nadal robi to, dopóki nie miną dwie minuty.
Początkowo myślałem, że zastosuję jakieś wyszukiwanie heurystyczne, aby wyjść poza zakres 1500 punktów. Komentarz @ mellamokb na temat 4527-punktowej tablicy doprowadził mnie do wniosku, że jest dużo miejsca do poprawy. Używamy jednak stosunkowo małej listy słów. Tablica z 4527 punktami zdobywała punkty za pomocą YAWL, która jest najbardziej inkluzywną listą słów dostępną na rynku - jest nawet większa niż oficjalna lista słów Scrabble w USA. Mając to na uwadze, ponownie zbadałem tablice znalezione przez mój program i zauważyłem, że wydaje się, że istnieje ograniczony zestaw tablic powyżej około 1700. Na przykład miałem wiele przebiegów, które odkryły tablicę z wynikiem 1726, ale zawsze była to dokładnie ta sama tablica, która została znaleziona (ignorując obroty i odbicia).
Jako kolejny test uruchomiłem mój program, używając YAWL jako słownika, i po kilkunastu uruchomieniach znalazłem tablicę 4527-punktową. Biorąc to pod uwagę, wysuwam hipotezę, że mój program znajduje się już w górnej granicy przestrzeni wyszukiwania, a zatem planowane przeze mnie przepisywanie wprowadziłoby dodatkową złożoność przy bardzo niewielkim zysku.
Oto moja lista pięciu najlepszych tablic, które mój program znalazł za pomocą listy english.0słów:
1735 : D C L P E I A E R N T R S E G S
1738 : B E L S R A D G T I N E S E R S
1747 : D C L P E I A E N T R D G S E R
1766 : M P L S S A I E N T R N D E S G
1772: G R E P T N A L E S I T D R E S
Wierzę, że „grep board” z 1772 r. (Jak to nazywałem), z 531 słowami, jest tablicą z największą liczbą możliwych punktów przy tej liście słów. Ponad 50% dwuminutowych uruchomień mojego programu kończy się na tej płycie. Zostawiłem też program uruchomiony na noc, nie znajdując nic lepszego. Więc jeśli istnieje tablica o wyższej punktacji, prawdopodobnie musiałaby mieć jakiś aspekt, który pokona technikę wyszukiwania programu. Na przykład plansza, w której każda możliwa mała zmiana układu powoduje ogromny spadek wyniku, może nigdy nie zostać wykryta przez mój program. Mam przeczucie, że taka tablica prawdopodobnie nie istnieje.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define WORDLISTFILE "./english.0"
#define XSIZE 4
#define YSIZE 4
#define BOARDSIZE (XSIZE * YSIZE)
#define DIEFACES 6
#define WORDBUFSIZE 256
#define MAXPOOLSIZE 32
#define STALLPOINT 64
#define RUNTIME 120
/* Generate a random int from 0 to N-1.
*/
#define random(N) ((int)(((double)(N) * rand()) / (RAND_MAX + 1.0)))
static char const dice[BOARDSIZE][DIEFACES] = {
"aaeegn", "elrtty", "aoottw", "abbjoo",
"ehrtvw", "cimotu", "distty", "eiosst",
"delrvy", "achops", "himnqu", "eeinsu",
"eeghnw", "affkps", "hlnnrz", "deilrx"
};
/* The dictionary is represented in memory as a tree. The tree is
* represented by its arcs; the nodes are implicit. All of the arcs
* emanating from a single node are stored as a linked list in
* alphabetical order.
*/
typedef struct {
int letter:8; /* the letter this arc is labelled with */
int arc:24; /* the node this arc points to (i.e. its first arc) */
int next:24; /* the next sibling arc emanating from this node */
int final:1; /* true if this arc is the end of a valid word */
} treearc;
/* Each of the slots that make up the playing board is represented
* by the die it contains.
*/
typedef struct {
unsigned char die; /* which die is in this slot */
unsigned char face; /* which face of the die is showing */
} slot;
/* The following information defines a game.
*/
typedef struct {
slot board[BOARDSIZE]; /* the contents of the board */
int score; /* how many points the board is worth */
} game;
/* The wordlist is stored as a binary search tree.
*/
typedef struct {
int item: 24; /* the identifier of a word in the list */
int left: 16; /* the branch with smaller identifiers */
int right: 16; /* the branch with larger identifiers */
} listnode;
/* The dictionary.
*/
static treearc *dictionary;
static int heapalloc;
static int heapsize;
/* Every slot's immediate neighbors.
*/
static int neighbors[BOARDSIZE][9];
/* The wordlist, used while scoring a board.
*/
static listnode *wordlist;
static int listalloc;
static int listsize;
static int xcursor;
/* The game that is currently being examined.
*/
static game G;
/* The highest-scoring game seen so far.
*/
static game bestgame;
/* Variables to time the program and display stats.
*/
static time_t start;
static int boardcount;
static int allscores;
/* The pool contains the N highest-scoring games seen so far.
*/
static game pool[MAXPOOLSIZE];
static int poolsize;
static int cutoffscore;
static int stallcounter;
/* Some buffers shared by recursive functions.
*/
static char wordbuf[WORDBUFSIZE];
static char gridbuf[BOARDSIZE];
/*
* The dictionary is stored as a tree. It is created during
* initialization and remains unmodified afterwards. When moving
* through the tree, the program tracks the arc that points to the
* current node. (The first arc in the heap is a dummy that points to
* the root node, which otherwise would have no arc.)
*/
static void initdictionary(void)
{
heapalloc = 256;
dictionary = malloc(256 * sizeof *dictionary);
heapsize = 1;
dictionary->arc = 0;
dictionary->letter = 0;
dictionary->next = 0;
dictionary->final = 0;
}
static int addarc(int arc, char ch)
{
int prev, a;
prev = arc;
a = dictionary[arc].arc;
for (;;) {
if (dictionary[a].letter == ch)
return a;
if (!dictionary[a].letter || dictionary[a].letter > ch)
break;
prev = a;
a = dictionary[a].next;
}
if (heapsize >= heapalloc) {
heapalloc *= 2;
dictionary = realloc(dictionary, heapalloc * sizeof *dictionary);
}
a = heapsize++;
dictionary[a].letter = ch;
dictionary[a].final = 0;
dictionary[a].arc = 0;
if (prev == arc) {
dictionary[a].next = dictionary[prev].arc;
dictionary[prev].arc = a;
} else {
dictionary[a].next = dictionary[prev].next;
dictionary[prev].next = a;
}
return a;
}
static int validateword(char *word)
{
int i;
for (i = 0 ; word[i] != '\0' && word[i] != '\n' ; ++i)
if (word[i] < 'a' || word[i] > 'z')
return 0;
if (word[i] == '\n')
word[i] = '\0';
if (i < 3)
return 0;
for ( ; *word ; ++word, --i) {
if (*word == 'q') {
if (word[1] != 'u')
return 0;
memmove(word + 1, word + 2, --i);
}
}
return 1;
}
static void createdictionary(char const *filename)
{
FILE *fp;
int arc, i;
initdictionary();
fp = fopen(filename, "r");
while (fgets(wordbuf, sizeof wordbuf, fp)) {
if (!validateword(wordbuf))
continue;
arc = 0;
for (i = 0 ; wordbuf[i] ; ++i)
arc = addarc(arc, wordbuf[i]);
dictionary[arc].final = 1;
}
fclose(fp);
}
/*
* The wordlist is stored as a binary search tree. It is only added
* to, searched, and erased. Instead of storing the actual word, it
* only retains the word's final arc in the dictionary. Thus, the
* dictionary needs to be walked in order to print out the wordlist.
*/
static void initwordlist(void)
{
listalloc = 16;
wordlist = malloc(listalloc * sizeof *wordlist);
listsize = 0;
}
static int iswordinlist(int word)
{
int node, n;
n = 0;
for (;;) {
node = n;
if (wordlist[node].item == word)
return 1;
if (wordlist[node].item > word)
n = wordlist[node].left;
else
n = wordlist[node].right;
if (!n)
return 0;
}
}
static int insertword(int word)
{
int node, n;
if (!listsize) {
wordlist->item = word;
wordlist->left = 0;
wordlist->right = 0;
++listsize;
return 1;
}
n = 0;
for (;;) {
node = n;
if (wordlist[node].item == word)
return 0;
if (wordlist[node].item > word)
n = wordlist[node].left;
else
n = wordlist[node].right;
if (!n)
break;
}
if (listsize >= listalloc) {
listalloc *= 2;
wordlist = realloc(wordlist, listalloc * sizeof *wordlist);
}
n = listsize++;
wordlist[n].item = word;
wordlist[n].left = 0;
wordlist[n].right = 0;
if (wordlist[node].item > word)
wordlist[node].left = n;
else
wordlist[node].right = n;
return 1;
}
static void clearwordlist(void)
{
listsize = 0;
G.score = 0;
}
static void scoreword(char const *word)
{
int const scoring[] = { 0, 0, 0, 1, 1, 2, 3, 5 };
int n, u;
for (n = u = 0 ; word[n] ; ++n)
if (word[n] == 'q')
++u;
n += u;
G.score += n > 7 ? 11 : scoring[n];
}
static void addwordtolist(char const *word, int id)
{
if (insertword(id))
scoreword(word);
}
static void _printwords(int arc, int len)
{
int a;
while (arc) {
a = len + 1;
wordbuf[len] = dictionary[arc].letter;
if (wordbuf[len] == 'q')
wordbuf[a++] = 'u';
if (dictionary[arc].final) {
if (iswordinlist(arc)) {
wordbuf[a] = '\0';
if (xcursor == 4) {
printf("%s\n", wordbuf);
xcursor = 0;
} else {
printf("%-16s", wordbuf);
++xcursor;
}
}
}
_printwords(dictionary[arc].arc, a);
arc = dictionary[arc].next;
}
}
static void printwordlist(void)
{
xcursor = 0;
_printwords(1, 0);
if (xcursor)
putchar('\n');
}
/*
* The board is stored as an array of oriented dice. To score a game,
* the program looks at each slot on the board in turn, and tries to
* find a path along the dictionary tree that matches the letters on
* adjacent dice.
*/
static void initneighbors(void)
{
int i, j, n;
for (i = 0 ; i < BOARDSIZE ; ++i) {
n = 0;
for (j = 0 ; j < BOARDSIZE ; ++j)
if (i != j && abs(i / XSIZE - j / XSIZE) <= 1
&& abs(i % XSIZE - j % XSIZE) <= 1)
neighbors[i][n++] = j;
neighbors[i][n] = -1;
}
}
static void printboard(void)
{
int i;
for (i = 0 ; i < BOARDSIZE ; ++i) {
printf(" %c", toupper(dice[G.board[i].die][G.board[i].face]));
if (i % XSIZE == XSIZE - 1)
putchar('\n');
}
}
static void _findwords(int pos, int arc, int len)
{
int ch, i, p;
for (;;) {
ch = dictionary[arc].letter;
if (ch == gridbuf[pos])
break;
if (ch > gridbuf[pos] || !dictionary[arc].next)
return;
arc = dictionary[arc].next;
}
wordbuf[len++] = ch;
if (dictionary[arc].final) {
wordbuf[len] = '\0';
addwordtolist(wordbuf, arc);
}
gridbuf[pos] = '.';
for (i = 0 ; (p = neighbors[pos][i]) >= 0 ; ++i)
if (gridbuf[p] != '.')
_findwords(p, dictionary[arc].arc, len);
gridbuf[pos] = ch;
}
static void findwordsingrid(void)
{
int i;
clearwordlist();
for (i = 0 ; i < BOARDSIZE ; ++i)
gridbuf[i] = dice[G.board[i].die][G.board[i].face];
for (i = 0 ; i < BOARDSIZE ; ++i)
_findwords(i, 1, 0);
}
static void shuffleboard(void)
{
int die[BOARDSIZE];
int i, n;
for (i = 0 ; i < BOARDSIZE ; ++i)
die[i] = i;
for (i = BOARDSIZE ; i-- ; ) {
n = random(i);
G.board[i].die = die[n];
G.board[i].face = random(DIEFACES);
die[n] = die[i];
}
}
/*
* The pool contains the N highest-scoring games found so far. (This
* would typically be done using a priority queue, but it represents
* far too little of the runtime. Brute force is just as good and
* simpler.) Note that the pool will only ever contain one board with
* a particular score: This is a cheap way to discourage the pool from
* filling up with almost-identical high-scoring boards.
*/
static void addgametopool(void)
{
int i;
if (G.score < cutoffscore)
return;
for (i = 0 ; i < poolsize ; ++i) {
if (G.score == pool[i].score) {
pool[i] = G;
return;
}
if (G.score > pool[i].score)
break;
}
if (poolsize < MAXPOOLSIZE)
++poolsize;
if (i < poolsize) {
memmove(pool + i + 1, pool + i, (poolsize - i - 1) * sizeof *pool);
pool[i] = G;
}
cutoffscore = pool[poolsize - 1].score;
stallcounter = 0;
}
static void selectpoolmember(int n)
{
G = pool[n];
}
static void emptypool(void)
{
poolsize = 0;
cutoffscore = 0;
stallcounter = 0;
}
/*
* The program examines as many boards as it can in the given time,
* and retains the one with the highest score. If the program is out
* of time, then it reports the best-seen game and immediately exits.
*/
static void report(void)
{
findwordsingrid();
printboard();
printwordlist();
printf("score = %d\n", G.score);
fprintf(stderr, "// score: %d points (%d words)\n", G.score, listsize);
fprintf(stderr, "// %d boards examined\n", boardcount);
fprintf(stderr, "// avg score: %.1f\n", (double)allscores / boardcount);
fprintf(stderr, "// runtime: %ld s\n", time(0) - start);
}
static void scoreboard(void)
{
findwordsingrid();
++boardcount;
allscores += G.score;
addgametopool();
if (bestgame.score < G.score) {
bestgame = G;
fprintf(stderr, "// %ld s: board %d scoring %d\n",
time(0) - start, boardcount, G.score);
}
if (time(0) - start >= RUNTIME) {
G = bestgame;
report();
exit(0);
}
}
static void restartpool(void)
{
emptypool();
while (poolsize < MAXPOOLSIZE) {
shuffleboard();
scoreboard();
}
}
/*
* Making small modifications to a board.
*/
static void turndie(void)
{
int i, j;
i = random(BOARDSIZE);
j = random(DIEFACES - 1) + 1;
G.board[i].face = (G.board[i].face + j) % DIEFACES;
}
static void swapdice(void)
{
slot t;
int p, q;
p = random(BOARDSIZE);
q = random(BOARDSIZE - 1);
if (q >= p)
++q;
t = G.board[p];
G.board[p] = G.board[q];
G.board[q] = t;
}
/*
*
*/
int main(void)
{
int i;
start = time(0);
srand((unsigned int)start);
createdictionary(WORDLISTFILE);
initwordlist();
initneighbors();
restartpool();
for (;;) {
for (i = 0 ; i < poolsize ; ++i) {
selectpoolmember(i);
turndie();
scoreboard();
selectpoolmember(i);
swapdice();
scoreboard();
}
++stallcounter;
if (stallcounter >= STALLPOINT) {
fprintf(stderr, "// stalled; restarting search\n");
restartpool();
}
}
return 0;
}
Uwagi do wersji 2 (9 czerwca)
Oto jeden ze sposobów wykorzystania początkowej wersji mojego kodu jako punktu wyjścia. Zmiany w tej wersji składają się z mniej niż 100 linii, ale potroiły średni wynik gry.
W tej wersji program utrzymuje „pulę” kandydatów, składającą się z N najwyżej ocenianych tablic wygenerowanych do tej pory przez program. Za każdym razem, gdy generowana jest nowa plansza, jest ona dodawana do puli i usuwana jest tablica o najniższych wynikach w puli (która może równie dobrze być właśnie dodaną tablicą, jeśli jej wynik jest niższy niż obecny). Pula jest początkowo zapełniana losowo generowanymi płytkami, po czym utrzymuje stały rozmiar przez cały czas działania programu.
Główna pętla programu polega na wybraniu losowej planszy z puli i zmianie jej, określeniu wyniku nowej planszy, a następnie umieszczeniu jej w puli (jeśli osiąga wystarczającą liczbę punktów). W ten sposób program nieustannie udoskonala tablice z najlepszymi wynikami. Główną czynnością jest wprowadzanie stopniowych, przyrostowych ulepszeń, ale wielkość puli pozwala również programowi znajdować wieloetapowe ulepszenia, które tymczasowo pogarszają wynik tablicy, zanim będzie ona w stanie poprawić.
Zazwyczaj ten program dość szybko znajduje dobre maksimum lokalne, po którym przypuszczalnie jakiekolwiek lepsze maksimum jest zbyt odległe, aby je znaleźć. I tak po raz kolejny nie ma sensu uruchamiać programu dłużej niż 10 sekund. Można to poprawić, np. Wykrywając tę sytuację przez program i rozpoczynając nowe wyszukiwanie od nowej puli kandydatów. Przyniosłoby to jednak jedynie niewielki wzrost. Właściwa heurystyczna technika poszukiwania byłaby prawdopodobnie lepszą drogą eksploracji.
(Uwaga dodatkowa: Widziałem, że ta wersja generuje około 5 tys. Tablic / s. Ponieważ pierwsza wersja zazwyczaj generowała 20 tys. Tablic / s, początkowo byłem zaniepokojony. Po profilowaniu odkryłem jednak, że spędziłem dodatkowy czas na zarządzaniu listą słów. Innymi słowy, było to całkowicie spowodowane tym, że program znalazł o wiele więcej słów na tablicę. W związku z tym rozważałem zmianę kodu w celu zarządzania listą słów, ale biorąc pod uwagę, że ten program używa tylko 10 z przydzielonych 120 sekund, takich optymalizacja byłaby bardzo przedwczesna).
Uwagi do wersji 1 (2 czerwca)
To bardzo, bardzo proste rozwiązanie. Wszystko, co robi, generuje losowe plansze, a następnie po 10 sekundach generuje tę z najwyższym wynikiem. (Domyślnie ustawiłem 10 sekund, ponieważ dodatkowe 110 sekund dozwolone przez specyfikację problemu zazwyczaj nie poprawia ostatecznego rozwiązania, na które warto było czekać.) Jest to więc bardzo głupie. Ma jednak całą infrastrukturę, aby stanowić dobry punkt wyjścia do bardziej inteligentnego wyszukiwania, a jeśli ktoś chce skorzystać z niej przed upływem terminu, zachęcam go do tego.
Program rozpoczyna się od odczytania słownika w strukturze drzewa. (Forma nie jest tak zoptymalizowana, jak mogłaby być, ale jest wystarczająca do tych celów.) Po innej podstawowej inicjalizacji zaczyna generować tablice i oceniać je. Program sprawdza około 20 000 płyt na sekundę na mojej maszynie, a po około 200 000 płyt losowe podejście zaczyna działać na sucho.
Ponieważ w danym momencie oceniana jest tylko jedna tablica, dane punktacji są przechowywane w zmiennych globalnych. To pozwala mi zminimalizować ilość stałych danych, które muszą być przekazywane jako argumenty do funkcji rekurencyjnych. (Jestem pewien, że da to niektórym ludziom pokrzywkę i przepraszam.) Lista słów jest przechowywana jako drzewo wyszukiwania binarnego. Każde znalezione słowo należy wyszukać na liście słów, aby duplikaty słów nie były liczone dwukrotnie. Lista słów jest jednak potrzebna tylko podczas procesu oceny, więc jest odrzucana po znalezieniu wyniku. Dlatego pod koniec programu wybrana tablica musi zostać ponownie oceniona, aby można było wydrukować listę słów.
Ciekawostka: średni wynik losowo wygenerowanej planszy Boggle, według oceny english.0, wynosi 61,7 punktu.
4527(1414suma słów), znaleziony tutaj: ai.stanford.edu/~chuongdo/boggle/index.html