Scrabble® [1]Back to Contents Prev: [2]Conclusions Next: [3]Introduction _________________________________________________________________ Recommendations With the basic infrastructure available, further work in this domain should focus on improving move generation speed and game strategy. Improving Move Generation Speed [4]Gordon analyzes a variant of the DAWG that takes substantially more space, but improves move generation speed by a factor of 2. [5]Appel and Jacobson suggest investigation into the possibility of increasing the amount of pruning that their generation algorithm can perform via an additional data structure that maintains a list of possible word prefixes. Game Strategy The move selection heuristics and end-game engine utilizing opponent search mentioned in the [6]Move Selection section are good candidates for analysis and implementation. An interesting approach to consider for developing a rack leave heuristic weighting function is to analyze the lexicon for letter patterns that occur with high frequency and/or contribute to high-scoring words, and the assign such patterns higher weight. Such an analysis would probably best be implemented using some efficient hashing structures and would benefit from fast string comparison routines. A larger lexicon would obviously improve game performance. Building such a lexicon is currently work in progress. More extensive logging support (beyond the current rudimentary logging) from the game server would facilitate analysis of computer player behaviour. From the standpoint of improving the "realism" of the program, investigating ways to set the strength level of the program in a "natural" manner might prove illuminating. While opponent search appears infeasible on a single machine, it may be more realistic in a distributed environment. It might be worth implementing a distributed network of slave processes that simply accept a game state and compute branches of the game tree, then doing a local evaluation and sending the results back to the main controller game server. _________________________________________________________________ [7]Back to Contents Prev: [8]Conclusions Next: [9]Introduction References 1. 2. 3. 4. 5. 6. 7. 8. 9.