Files

T

Ilia Denisov a8a559993d scrabble: add single-word-per-turn rule via PlayOptions

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.

2026-06-12 01:37:39 +02:00

3.7 KiB

Raw Permalink Blame History

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.

See ALGORITHM.md for the algorithm (the single source of truth) and 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 repository, which publishes the DAWG set as a release artifact.

Usage

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

go run ./cmd/stress -games 100   # greedy AI-vs-AI self-play; reports speed and memory

Tests

go test ./...           # unit tests + a brute-force move-generation oracle
go test ./... -short    # skips the full-dictionary game test

3.7 KiB Raw Permalink Blame History Unescape Escape