Ilia Denisov
256999b42c
- Rename module to gitea.iliadenisov.ru/developer/scrabble-solver so it can be consumed as a versioned dependency (no go.work replace / CI clone). - De-internalize wordlist and dictdawg as public packages. - Remove cmd/builddict, dictprep/, the dictionaries submodule and the dawg Makefile: the word-list parsing and DAWG build now live in the separate scrabble-dictionary repository, which publishes the DAWG set as a release artifact. - internal/dict loads the committed dawg/en_sowpods.dawg fixture for cmd/stress. - Update README/CLAUDE docs accordingly.
87 lines
3.4 KiB
Markdown
87 lines
3.4 KiB
Markdown
# scrabble-solver
|
||
|
||
A Go library that, given a dictionary, a board position and a rack, returns **every
|
||
legal play ranked by score**, and also **scores** or **validates** arbitrary plays. The
|
||
move generator is the DAWG algorithm of Appel & Jacobson, *The World's Fastest Scrabble
|
||
Program*. It operates on compact byte-indexed inputs/outputs and is dictionary-driven via
|
||
[`github.com/iliadenisov/dafsa`](https://github.com/iliadenisov/dafsa).
|
||
|
||
See [`ALGORITHM.md`](ALGORITHM.md) for the algorithm (the single source of truth) and
|
||
[`RESULTS.md`](RESULTS.md) for the DAWG-vs-GADDAG benchmark that settled the design.
|
||
|
||
## Status
|
||
|
||
- DAWG move generation (across / down / both orientations), with full tournament scoring
|
||
(cross-words, premiums, all-tiles bonus) and a per-tile breakdown.
|
||
- Public `Solver`: `GenerateMoves` (ranked), `ScorePlay`, `ValidatePlay`.
|
||
- Rulesets: **English** Scrabble, **Russian** Scrabble, **Эрудит**; `rules.Ruleset` is
|
||
fully parameterizable (board, premiums, tile values/counts, blanks, rack, bonus).
|
||
- A GADDAG (Gordon) was implemented, benchmarked and then **removed** — for a scoring
|
||
solver it was ~7× larger and no faster.
|
||
|
||
## Layout
|
||
|
||
```
|
||
scrabble/ public API: Solver, Move/Play types, DAWG generator, scoring, validation
|
||
board/ rack/ rules/ board grid (+transpose), rack, rulesets (English/Russian/Эрудит)
|
||
wordlist/ dictdawg/ public word-list parsing and DAWG build/load helpers
|
||
internal/ encoding (byte conventions), dict (committed-DAWG loader), graph
|
||
cmd/stress/ greedy self-play benchmark of the generator
|
||
selfplay/ bag + greedy player + game loop
|
||
```
|
||
|
||
## Setup
|
||
|
||
The committed dictionary DAWGs under `dawg/` (`en_sowpods`, `ru_scrabble`, `ru_erudit`)
|
||
are used directly — no build step. The word-list parsing and DAWG build pipeline lives in
|
||
the separate [`scrabble-dictionary`](https://gitea.iliadenisov.ru/developer/scrabble-dictionary)
|
||
repository, which publishes the DAWG set as a release artifact.
|
||
|
||
## Usage
|
||
|
||
```go
|
||
rs := rules.English()
|
||
finder, _ := dict.EnglishDAWG() // loads dawg/en_sowpods.dawg
|
||
s := scrabble.NewSolver(rs, finder)
|
||
|
||
b := board.New(rs.Rows, rs.Cols) // empty board (first move)
|
||
|
||
r := rack.New(rs.Size()) // rack "friends"
|
||
tiles, _ := rs.Alphabet.Encode("friends")
|
||
for _, t := range tiles {
|
||
r.Add(t)
|
||
}
|
||
|
||
moves := s.GenerateMoves(b, r, scrabble.Both) // ranked, highest score first
|
||
best := moves[0]
|
||
// best.Main / best.Cross hold the words (alphabet indexes; decode via rs.Alphabet),
|
||
// best.Tiles the placed tiles (with blank flags), best.Score the total.
|
||
|
||
// Score or validate an arbitrary play (placed tiles + direction):
|
||
m, err := s.ValidatePlay(b, scrabble.Horizontal, best.Tiles)
|
||
_ = m
|
||
_ = err
|
||
```
|
||
|
||
Words and tiles are alphabet **indexes** throughout (no string wrapper); convert with the
|
||
ruleset's `alphabet.Indexer` (`Encode`/`Decode`) when you need text.
|
||
|
||
## Rulesets
|
||
|
||
`rules.English()`, `rules.RussianScrabble()`, `rules.Erudit()`, or build your own with
|
||
`rules.FromTemplate(...)`. For Эрудит, fold Ё→Е while preparing the dictionary with
|
||
`wordlist.FoldYo` (the engine treats them as one letter; it is a dictionary-prep step).
|
||
|
||
## Benchmark
|
||
|
||
```sh
|
||
go run ./cmd/stress -games 100 # greedy AI-vs-AI self-play; reports speed and memory
|
||
```
|
||
|
||
## Tests
|
||
|
||
```sh
|
||
go test ./... # unit tests + a brute-force move-generation oracle
|
||
go test ./... -short # skips the full-dictionary game test
|
||
```
|