Ilia Denisov
a8a559993d
Add an optional "single word per turn" rule: only the main word along the
play direction is validated and scored; perpendicular cross-words are ignored
— not formed, validated, scored, or used to constrain move generation. The
zero PlayOptions stays standard Scrabble, so existing callers are unchanged.
- PlayOptions{IgnoreCrossWords} threaded through new EvaluateOpts,
Solver.{ScorePlay,ValidatePlay,GenerateMoves}Opts and the DAWG generator
(relaxed cross-sets via fullSet, main-word-only scoring).
- connected() tests perpendicular adjacency directly instead of via
Move.Cross, so an all-new main word touching the board only sideways still
connects when cross-words are suppressed (behaviour-preserving for standard
play).
- Tests: focused corner-case suite (solver_opts_test.go) and a single-word
GCG fixture; the 17 real-game GCG fixtures stay green as the standard-rules
regression guard.
91 lines
3.7 KiB
Markdown
91 lines
3.7 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`, each with an
|
||
`*Opts` variant taking `PlayOptions` for optional rule variations.
|
||
- Optional **single word per turn** rule (`PlayOptions{IgnoreCrossWords: true}`): only the
|
||
main word is validated and scored — perpendicular cross-words are ignored, including in
|
||
move generation. The zero `PlayOptions` is standard Scrabble.
|
||
- 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
|
||
```
|