|
Elise source code distributions and development notes IMPORTANT: The purpose of releasing Elise source code is to help spur research and improve strategy for the general good of the crossword gaming community. Therefore I ask that you share changes made to the Elise source code with the community. See the LICENSE.TXT included in the source distribution for more details. Console application: The source distribution includes an Elise console project: this is a text-based version of the application that does not require any of the various GUI libraries or Windows-specific code to build. This is portable C++ code; it should build out of the box using Visual C++, G++, or any other compiler or development environment based on the GNU tools, and should also build under other C++ compilers with no or very few changes. Documentation for this application is on this page. Move generation: There are two main move generation algorithms in Elise. The first uses a regular trie and a trie structure with edges for blanks (I called this a TRBL first from "trie" and "blank", pronounced it tribble, and finally just made .tribble the file extension). Elise does some tricky stuff to speed up searches in its tries, like specifying tiles on an edge that must be played to make a valid word; this shortcircuits a lot of trie searches and speeds move generation significantly. This algorithm is at least as fast as a GADDAG on the smaller lexicons (in particular, it kills on single-blank searches), but it is also almost certainly slower in large lexicons (Spanish, German, Unabridged English notably) because (first) the blank trie balloons in size, and (second) fewer trie searches can be shortcircuited (because there are so many valid words). Going forward I'm likely to add a third move generation algorithm for the large lexicons. There is a second, more general move generation algorithm in Elise, which does not require building any special structures beforehand and accordingly can run on any provided word list. This algorithm is fairly complicated, using a bunch of pre-calculated lookup vectors to reduce the number of necessary anagram searches. This algorithm is not as fast as the trie searches typically, but it is good for crossword games with large numbers of tiles (or blanks), for custom user-provided word lists, and may be used in simulation for racks with two blanks. Move evaluation takes about as much time (sometimes more) as move generation, so I've concentrated most of my performance efforts recently on evaluation rather than generation. One of the experimental features in version 0.1.8 (XPF_NO_DANGER_HOOKS) actually turns off a particular feature in the move evaluator, simply because it uses so much time and, although it certainly adds strength in "blitz" play using the quick move find, I am not certain that it adds appreciable strength in simulation. By testing this as an experimental feature and generating hundreds of games with the danger hooks code turned off in simulation, I hope to determine whether this feature in move evaluation should remain on during simulation. STL and performance: Elise uses STL vectors (dynamic arrays) extensively, and some implementations of the STL have better performance than others. The bulk of the performance differences I've seen in compiling Elise in different platforms come from standard library code, notably vector insert or sort. If your STL implementation has slow vectors, you may gain a lot in performance by writing your own. Clabbers move generation: Don't bother touching the existing Clabbers move generation, it's going away. I intend to replace it with my original Clabbers move generation code (1998), which was quite a lot faster than the very quick and dirty vector-search method used here. Available distributions are located in this directory. |