movegen

package
v0.13.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 11, 2026 License: GPL-3.0 Imports: 16 Imported by: 2

Documentation

Overview

Package movegen contains all the move-generating functions. It makes heavy use of the GADDAG. Implementation notes: - Is the specification in the paper a bit buggy? Basically, if I assume an anchor is the leftmost tile of a word, the way the algorithm works, it will create words blindly. For example, if I have a word FIRE on the board, and I have the letter E on my rack, and I specify F as the anchor, it will create the word EF! (Ignoring the fact that IRE is on the board) You can see this by just stepping through the algorithm. It seems that anchors can only be on the rightmost tile of a word

Package movegen - shadow.go implements the shadow play algorithm for best-first move finding. The algorithm was originally developed in wolges (https://github.com/andy-k/wolges/blob/main/details.txt) and ported to macondo from magpie's implementation.

Shadow computes an upper bound on the score achievable from each anchor square, then uses a max-heap to process anchors in descending order. This allows early termination once we can prove no remaining anchor can beat the best move found so far.

wordmap_gen.go: WMP-based word retrieval for shadow-best-first move generation. Mirrors MAGPIE's wordmap_gen + record_wmp_plays_for_word + record_wmp_play.

Given a WMP-recorded anchor (one with TilesToPlay, PlaythroughBlocks, WordLength, LeftmostStartCol, RightmostStartCol populated), wordmapGen asks the WMP for every blankless word that fits the anchor's (rack subset, word length) tuple, then for each word and start column it:

  1. Checks the play against the board (cross-sets and playthrough match), filling gen.strip with playthrough markers and unblanked-letter placements.
  2. Recursively decides which non-playthrough positions are designated blanks vs real tiles, given how many blanks the subrack has.
  3. Scores each fully-specified play and emits it via gen.playRecorder.

This replaces recursive_gen for WMP anchors. The advantage over recursive_gen is that the WMP gives us the entire word list directly — no GADDAG traversal — and the per-(blocks, tiles) anchor structure avoids the redundant work that the previous integration suffered from.

Index

Constants

View Source 
const DefaultSmallPlayCapacity = 250_000

DefaultSmallPlayCapacity is the pre-allocated capacity for the smallPlays slice on each GordonGenerator. It matches magpie's DEFAULT_SMALL_MOVE_LIST_CAPACITY (config_defs.h:10). Two-blank racks can produce very large move counts, so we allocate generously to avoid any reallocation during move generation.

Variables

This section is empty.

Functions

func AllPlaysRecorder added in v0.4.9 

func AllPlaysRecorder(gen MoveGenerator, rack *tilemapping.Rack, leftstrip, rightstrip int, t move.MoveType, score int)

func AllPlaysSmallRecorder added in v0.8.7 

func AllPlaysSmallRecorder(gen MoveGenerator, rack *tilemapping.Rack, leftstrip, rightstrip int, t move.MoveType, score int)

AllPlaysSmallRecorder is a recorder that records all plays, but as "SmallMove"s, which allocate much less and are smaller overall than a regular move.Move

func NullPlayRecorder added in v0.4.9 

func NullPlayRecorder(gen MoveGenerator, a *tilemapping.Rack, leftstrip, rightstrip int, t move.MoveType, score int)

func TopNPlayRecorder added in v0.10.2 

func TopNPlayRecorder(gen MoveGenerator, rack *tilemapping.Rack, leftstrip, rightstrip int, t move.MoveType, score int)

func TopPlayOnlyRecorder added in v0.4.9 

func TopPlayOnlyRecorder(gen MoveGenerator, rack *tilemapping.Rack, leftstrip, rightstrip int, t move.MoveType, score int)

TopPlayOnlyRecorder is a heavily optimized, ugly function to avoid allocating a lot of moves just to throw them out. It only records the very top move.

Types

type Anchor added in v0.12.4 

type Anchor struct {
	HighestPossibleEquity float64
	HighestPossibleScore  int32
	Row                   uint8
	Col                   uint8
	LastAnchorCol         uint8
	Dir                   board.BoardDirection

	// WMP-only fields. Zero when not produced by the WMP path.
	TilesToPlay       uint8
	PlaythroughBlocks uint8
	WordLength        uint8
	LeftmostStartCol  uint8
	RightmostStartCol uint8
}

Anchor represents a board anchor with its shadow-computed upper bound.

The WMP-specific fields (TilesToPlay, PlaythroughBlocks, WordLength, LeftmostStartCol, RightmostStartCol) are populated only when WMP is active and the anchor came out of the per-(blocks, tiles) WMP anchor table. They mirror MAGPIE's Anchor extension fields used by wmp_move_gen_add_anchors / wordmap_gen.

Layout-packed: 8 (equity) + 4 (score) + 9 × 1 (uint8 fields) = 21 bytes, padded to 24 with 8-byte alignment. Down from 80 bytes when every field was a Go `int`. Smaller anchors mean cheaper heap operations: heapifyDown swaps cost ~3× less and the heap fits more entries per cache line. The sentinel value for LastAnchorCol is math.MaxUint8 (255) instead of the 100 used previously.

All "small int" fields use uint8 directly (not a typed alias) so callers don't need ad-hoc conversions every time they read one. Score uses int32 because a 7-tile bingo on triple-triples can exceed 255 but is bounded well below int16's max.

type AnchorHeap added in v0.12.4 

type AnchorHeap struct {
	// contains filtered or unexported fields
}

AnchorHeap is a max-heap of anchors ordered by highestPossibleEquity.

type GordonGenerator added in v0.2.0 

type GordonGenerator struct {
	// contains filtered or unexported fields
}

GordonGenerator is the main move generation struct. It implements Steven A. Gordon's algorithm from his paper "A faster Scrabble Move Generation Algorithm"

func NewGordonGenerator added in v0.2.0 

func NewGordonGenerator(gd gaddag.WordGraph, board *board.GameBoard,
	ld *tilemapping.LetterDistribution) *GordonGenerator

NewGordonGenerator returns a Gordon move generator.

func (*GordonGenerator) AtLeastOneTileMove added in v0.7.0 

func (gen *GordonGenerator) AtLeastOneTileMove(rack *tilemapping.Rack) bool

AtLeastOneTileMove generates moves. We don't care what they are; return true if there is at least one move that plays tiles, false otherwise.

func (*GordonGenerator) GADDAG added in v0.7.0 

func (gen *GordonGenerator) GADDAG() *kwg.KWG

func (*GordonGenerator) GenAll added in v0.2.0 

func (gen *GordonGenerator) GenAll(rack *tilemapping.Rack, addExchange bool) []*move.Move

GenAll generates all moves on the board. It assumes anchors have already been updated, as well as cross-sets / cross-scores. When shadow is enabled (via SetPlayRecorderTopPlay or SetRecordNTopPlays), GenAll uses the shadow algorithm for best-first move finding, which allows early termination when looking for only the top move(s). Shadow can be disabled for endgame where all moves must be found without the overhead of computing upper bounds.

func (*GordonGenerator) GenAllWithShadow added in v0.12.4 

func (gen *GordonGenerator) GenAllWithShadow(rack *tilemapping.Rack, addExchange bool) []*move.Move

GenAllWithShadow generates all moves using shadow for best-first ordering. Only useful when we need the best move (not all moves).

func (*GordonGenerator) Plays added in v0.2.0 

func (gen *GordonGenerator) Plays() []*move.Move

Plays returns the generator's generated plays.

func (*GordonGenerator) RunShadowOnly added in v0.12.4 

func (gen *GordonGenerator) RunShadowOnly(rack *tilemapping.Rack) []Anchor

RunShadowOnly runs the shadow pass and returns anchors sorted by descending highest possible score. For testing.

func (*GordonGenerator) RunShadowOnlyWMP added in v0.13.0 

func (gen *GordonGenerator) RunShadowOnlyWMP(rack *tilemapping.Rack, tilesInBag, oppRackScore int) []Anchor

RunShadowOnlyWMP runs the shadow pass with full WMP (and leave map) initialization, mirroring the slice of GenAllWithShadow that comes before recursiveGen. Returns the anchors in descending equity order (the same order MAGPIE's extract_sorted_anchors_for_test produces).

tilesInBag and oppRackScore are stamped onto the generator so shadow_record's equity branch matches the MAGPIE shadow tests. For score-only assertions (sortingParameter == SortByScore) the exact tilesInBag value doesn't matter as long as it is > 0, since shadow.bestLeaves remains zero with no equity calculator set.

Intended for tests that want to inspect anchor output without running the full recursive_gen pipeline.

func (*GordonGenerator) SetEquityCalculators added in v0.5.0 

func (gen *GordonGenerator) SetEquityCalculators(calcs []equity.EquityCalculator)

func (*GordonGenerator) SetGADDAG added in v0.13.0 

func (gen *GordonGenerator) SetGADDAG(g *kwg.KWG)

SetGADDAG replaces the underlying word graph used for move generation. Used by the endgame solver to swap in a pruned KWG for the duration of a solve and restore the original afterwards.

func (*GordonGenerator) SetGame added in v0.4.9 

func (gen *GordonGenerator) SetGame(g *game.Game)

func (*GordonGenerator) SetGenPass added in v0.7.0 

func (gen *GordonGenerator) SetGenPass(p bool)

func (*GordonGenerator) SetMaxCanExchange added in v0.9.9 

func (gen *GordonGenerator) SetMaxCanExchange(m int)

func (*GordonGenerator) SetMaxTileUsage added in v0.8.0 

func (gen *GordonGenerator) SetMaxTileUsage(t int)

func (*GordonGenerator) SetPlayRecorder added in v0.4.9 

func (gen *GordonGenerator) SetPlayRecorder(pr PlayRecorderFunc)

func (*GordonGenerator) SetPlayRecorderTopPlay added in v0.12.4 

func (gen *GordonGenerator) SetPlayRecorderTopPlay()

SetPlayRecorderTopPlay sets the play recorder to TopPlayOnlyRecorder with shadow enabled for best-first move finding.

func (*GordonGenerator) SetRecordNTopPlays added in v0.10.2 

func (gen *GordonGenerator) SetRecordNTopPlays(n int)

func (*GordonGenerator) SetSortingParameter added in v0.2.0 

func (gen *GordonGenerator) SetSortingParameter(s SortBy)

SetSortingParameter tells the play sorter to sort by score, equity, or perhaps other things. This is useful for the endgame solver, which does not care about equity.

func (*GordonGenerator) SetWMP added in v0.13.0 

func (gen *GordonGenerator) SetWMP(w *wmp.WMP)

SetWMP enables WMP-aware move generation. Pass nil to disable. When set, shadow play uses the WMP existence checks to tighten the highestShadowEquity bound for each anchor square AND records per-(playthrough_blocks, tiles_to_play) sub-anchors that are processed by wordmapGen (instead of recursive_gen) during the best-first scoring pass. Mirrors MAGPIE's player_set_wmp + the wmp_move_gen_init call inside gen_load_position.

func (*GordonGenerator) SetWMPRecordSubAnchors added in v0.13.0 

func (gen *GordonGenerator) SetWMPRecordSubAnchors(b bool)

SetWMPRecordSubAnchors lets callers override the default sub-anchor recording behavior. SetWMP turns this on automatically; the override is mostly for benchmarks that want to compare the shadow-only-gating variant against the full WMP integration.

func (*GordonGenerator) SmallPlays added in v0.8.7 

func (gen *GordonGenerator) SmallPlays() []tinymove.SmallMove

SmallPlays returns the generator's generated SmallPlays

func (*GordonGenerator) WMP added in v0.13.0 

func (gen *GordonGenerator) WMP() *wmp.WMP

WMP returns the WMP currently in use, or nil if WMP is disabled.

type MoveGenerator added in v0.2.11 

type MoveGenerator interface {
	GenAll(rack *tilemapping.Rack, addExchange bool) []*move.Move
	SetMaxCanExchange(int)
	SetSortingParameter(s SortBy)
	Plays() []*move.Move
	SmallPlays() []tinymove.SmallMove
	SetPlayRecorder(pf PlayRecorderFunc)
	SetEquityCalculators([]equity.EquityCalculator)
	AtLeastOneTileMove(rack *tilemapping.Rack) bool
	SetMaxTileUsage(int)
	SetGenPass(bool)
}

MoveGenerator is a generic interface for generating moves.

type PlayRecorderFunc added in v0.4.9 

type PlayRecorderFunc func(MoveGenerator, *tilemapping.Rack, int, int, move.MoveType, int)

type SortBy added in v0.2.0 

type SortBy int
const (
	SortByScore SortBy = iota
	SortByNone
)

Source Files

View all Source files

Directories

Path Synopsis
Package wordprune implements a pruned KWG (word graph) for endgame solving.
 Package wordprune implements a pruned KWG (word graph) for endgame solving.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.