# 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
```