{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T18:29:23Z","timestamp":1700418563341},"reference-count":15,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4654,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Appel and Jacobson<jats:sup>1<\/jats:sup> presented a fast algorithm for generating every possible move in a given position in the game of Scrabble using a DAWG, a finite automaton derived from the trie of a large lexicon. This paper presents a faster algorithm that uses a GADDAG, a finite automaton that avoids the non\u2010deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon. For a typical lexicon, the GADDAG is nearly five times larger than the DAWG, but generates moves more than twice as fast. This time\/space trade\u2010off is justified not only by the decreasing cost of computer memory, but also by the extensive use of move\u2010generation in the analysis of board positions used by Gordon<jats:sup>2<\/jats:sup> in the probabilistic search for the most appropriate play in a given position within realistic time constraints.<\/jats:p>","DOI":"10.1002\/spe.4380240205","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:55:23Z","timestamp":1163782523000},"page":"219-232","source":"Crossref","is-referenced-by-count":11,"title":["A faster scrabble move generation algorithm"],"prefix":"10.1002","volume":"24","author":[{"given":"Steven A.","family":"Gordon","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/42411.42420"},{"key":"e_1_2_1_3_2","unstructured":"S.Gordon \u2018A comparison between probabilistic search and weighted heuristics in a game with incomplete information\u2019 Technical Report Department of Mathematics East Carolina University August 1993. Also to appear inAAAI Fall Symposium Series Raliegh NC (October1993)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_2_1_5_2","first-page":"481","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"Knuth D.","year":"1973"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/358746.383429"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146380"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230103"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215007"},{"key":"e_1_2_1_10_2","first-page":"209","volume-title":"Computer Algorithms: Introduction to Design and Analysis","author":"Baase S.","year":"1988"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_12_2","volume-title":"The Official Scrabble Players Dictionary","author":"Milton Bradley Company","year":"1990"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","article-title":"Linear automaton transformations","volume":"9","author":"Nerode A.","year":"1958","journal-title":"Proc. AMS"},{"key":"e_1_2_1_15_2","first-page":"4","article-title":"Renaissance of Scrabble theory 2","volume":"17","author":"Ballard N.","year":"1992","journal-title":"Games Medleys"},{"key":"e_1_2_1_16_2","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"Sankoff D.","year":"1983"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380240205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380240205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T18:26:40Z","timestamp":1698172000000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380240205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,2]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,2]]}},"alternative-id":["10.1002\/spe.4380240205"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380240205","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,2]]}}}