Scrabble® [1]Back to Contents Prev: [2]Summary Next: [3]Recommendations _________________________________________________________________ Conclusions Conclusions relating to the research and development process through the duration of the project are discussed under Process Post-mortem while conclusions relating to the actual results of the project are discussed under Project Results. Process Post-mortem I underestimated the time required to design and implement much of the infrastructure; in particular, the client UI and the overall communications model required substantially more work than anticipated. Overall scheduling for actual game play related work ended up being mostly accurate, however much more time was spent building the lexicon data structure than expected, due to gross underestimation of the work required to minimize the graph. Time was also spent investigating the possible need for implementing the lexicon code in C for performance reasons (this turned out to be unnecessary). On the positive side, implementation of the move generation algorithm proceeded more rapidly than expected, although several subtle bugs took some time to track down. Project Results The client-server infrastructure is sufficiently well-designed to allow for easy extension of research into this domain. The combination of a DAWG lexicon representation and the Appel and Jacobson exhaustive move search algorithm are efficient enough to permit a focus on move selection heuristics. While the number of playable moves per turn can vary from the 10's to the 100's, on a Sparc-1 all moves can typically be generated in 3-4 seconds. However, this is not to say that further work on improving the speed of move generation is useless; quite the contrary, since faster move generation will increase the practicalness of opponent search techniques, which is especially helpful in the end-game. The currently implemented simple greedy heuristic (picking the highest scoring move every turn) is more than strong enough to beat most casual human players. 30 games were simulated with the heuristic playing itself; the results are summarized in the following table: CAPTION: Greedy Computer Player Statistics Player 1 Score Player 2 Score Total Score 338 371 709 328 385 713 305 358 663 457 331 788 278 418 696 436 383 819 359 491 850 487 373 860 363 407 770 351 380 731 395 346 741 418 370 788 346 404 750 421 405 826 408 296 704 366 481 847 429 378 807 425 354 779 401 373 774 313 436 749 372 408 780 461 359 820 411 493 904 334 346 680 322 307 629 413 411 824 350 382 732 448 373 821 414 397 811 338 431 769 Average: 382.90 388.23 771.13 As expected, both players averaged very similar total game scores. Victories were split evenly down the middle, with 15 apiece. Most casual human players score between 100 and 250 points per game. However, stronger players usually manage to exploit the greedy algorithm's inattention to strategy and often manage 350-450 points per game. Given a strong vocabulary, it seems fair to conclude that even slightly stronger heuristics will enable to the computer player to challenge even strong human players. _________________________________________________________________ [4]Back to Contents Prev: [5]Summary Next: [6]Recommendations References 1. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html 2. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/summary.html 3. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/recs.html 4. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html 5. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/summary.html 6. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/recs.html