swisslib

package
v0.1.2 Latest Latest
Warning

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

 Go to latest Published: Apr 13, 2026 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package swisslib provides shared data structures and algorithms for Swiss pairing engines. Both the Dutch (C.04.3) and Burstein (C.04.4.2) engines build on this foundation.

This mirrors the FIDE regulation structure: C.04.1 and C.04.2 define common rules both systems share.

Index

Constants

View Source 
const (
	IdxC8  = 0  // look-ahead (0=OK, 1=fails)
	IdxC10 = 1  // topscorer |color diff| > 2 (count)
	IdxC11 = 2  // topscorer 3+ same streak (count)
	IdxC12 = 3  // color pref not granted (count)
	IdxC13 = 4  // strong color pref not granted (count)
	IdxC14 = 5  // downfloat prev round (count)
	IdxC15 = 6  // upfloat prev round (count)
	IdxC16 = 7  // downfloat 2 rounds ago (count)
	IdxC17 = 8  // upfloat 2 rounds ago (count)
	IdxC18 = 9  // max diff downfloat prev (int, score×2)
	IdxC19 = 10 // max diff upfloat prev (int, score×2)
	IdxC20 = 11 // max diff downfloat prev-2 (int, score×2)
	IdxC21 = 12 // max diff upfloat prev-2 (int, score×2)
)

Violation array indices — maps to FIDE C.04.3 criteria.

View Source 
const NumViolations = 13

NumViolations is the number of optimization criteria tracked (C8, C10-C21).

Variables

This section is empty.

Functions

func AllocateColor 

func AllocateColor(a, b *PlayerState, topScorerRules bool, boardNumber int, topSeedColor *Color) (string, string)

AllocateColor decides which player gets White and which gets Black for a specific pairing, implementing bbpPairings' choosePlayerNeutralColor and choosePlayerColor (dutch.cpp lines 488-516, common.cpp lines 250-315).

topSeedColor controls round 1 board alternation when no player has color history. nil = default (higher-ranked gets White on odd boards). Non-nil overrides the color assigned to the higher-ranked player on board 1; subsequent boards alternate from there.

Priority (from choosePlayerNeutralColor):

  1. Compatible preferences → grant first player's preference
  2. One absolute, stronger imbalance or opponent not absolute → grant
  3. One strong, other not → grant strong player's preference
  4. findFirstColorDifference → swap from most recent differing round

Fallback (from choosePlayerColor, when neutral returns COLOR_NONE):

  1. If both have preferences but same color → higher-ranked gets preferred
  2. If neither has preference → alternate by board (FIDE C.04.3 A.6.e)

Returns (whiteID, blackID).

func ApplyBakuAcceleration 

func ApplyBakuAcceleration(players []PlayerState, currentRound, totalRounds, gaSize int)

ApplyBakuAcceleration modifies PairingScore for each player by adding virtual points based on the Baku acceleration system.

Players in Group A (InitialRank <= gaSize) receive virtual points. Players outside Group A are not modified.

func AssertPairingInvariants 

func AssertPairingInvariants(t *testing.T, state *chesspairing.TournamentState, result *chesspairing.PairingResult)

AssertPairingInvariants checks universal structural properties of a pairing result. Call this from every integration test to catch bugs even when exact expected output is unknown.

Properties checked:

  • Every active player appears in exactly one pairing or one bye (completeness)
  • No player appears more than once (uniqueness)
  • No pairing is a rematch of a previous round (no-rematch, C1 equivalent)
  • Board numbers are sequential starting from 1
  • Bye type is ByePAB
  • No inactive player appears in pairings or byes

func BakuAccelerationRounds 

func BakuAccelerationRounds(totalRounds int) (accelerated, fullVP, halfVP int)

BakuAccelerationRounds returns the number of accelerated rounds, full virtual point rounds, and half virtual point rounds for the Baku acceleration system (FIDE C.04.7).

  • accelerated = ceil(totalRounds / 2)
  • fullVP = ceil(accelerated / 2)
  • halfVP = accelerated - fullVP

func BakuGASize 

func BakuGASize(totalPlayers int) int

BakuGASize returns the size of Group A (top-ranked players) for Baku acceleration: 2 * ceil(totalPlayers / 4).

func BakuVirtualPoints 

func BakuVirtualPoints(totalRounds, currentRound int, isGA bool) float64

BakuVirtualPoints returns the virtual points for a player in a given round under Baku acceleration.

  • GA player in a full VP round: 1.0
  • GA player in a half VP round: 0.5
  • All other cases: 0.0

func C1NoRematches 

func C1NoRematches(pair *ProposedPairing, ctx *CriteriaContext) bool

C1NoRematches returns true if the two players have NOT already played each other (forfeits excluded from opponent history).

func C2NoSecondPAB 

func C2NoSecondPAB(player *PlayerState, ctx *CriteriaContext) bool

C2NoSecondPAB returns true if the player has not already received a bye. Used to validate bye candidates, not pair evaluation.

func C3AbsoluteColorConflict 

func C3AbsoluteColorConflict(pair *ProposedPairing, ctx *CriteriaContext) bool

C3AbsoluteColorConflict returns true if the pairing does NOT create an absolute color conflict.

FIDE C.04.3 (Feb 2026) Article 2.1.3 [C3]: "Non-topscorers with the same absolute colour preference shall not meet."

This means C3 only applies when BOTH players are non-topscorers. If EITHER player is a topscorer (Article 1.8: score > 50% of max possible in the final round), C3 does not apply.

func C4CompleteBracket 

func C4CompleteBracket(bp *BracketPairing, playerCount int) bool

C4CompleteBracket checks that all players in a bracket are accounted for as either paired or floaters. Structural validation.

func CanonicalPairKey 

func CanonicalPairKey(a, b string) [2]string

CanonicalPairKey returns a canonicalized key for a pair of player IDs. The IDs are sorted lexicographically so that (a,b) and (b,a) produce the same key.

func ComputeBaseEdgeWeight 

func ComputeBaseEdgeWeight(
	higherPlayer, lowerPlayer *PlayerState,
	inCurrentBracket, inNextBracket bool,
	params *EdgeWeightParams,
) *big.Int

ComputeBaseEdgeWeight computes the Blossom edge weight for a pair of players using math/big.Int multi-precision integers. This mirrors bbpPairings' computeEdgeWeight EXACTLY, using the same bit widths: - Boolean fields: scoreGroupSizeBits wide - Score-indexed fields: scoreGroupsShift wide, positioned at scoreGroupShifts[score]

higherPlayer = player with higher score (smaller index in sorted array). lowerPlayer = player with lower score (larger index). inCurrentBracket = lowerPlayer is in the current score group. inNextBracket = lowerPlayer is in the next score group.

Returns a zero big.Int if the pair is incompatible (already played or absolute color conflict). The caller handles C1/C3 checks before calling this.

func ConsecutiveSameFloat 

func ConsecutiveSameFloat(history []Float, dir Float) int

ConsecutiveSameFloat counts how many times the player has floated in the given direction in consecutive recent rounds (from the end of history backwards). Stops at the first round that doesn't match.

func FloatedToSameScoreGroup 

func FloatedToSameScoreGroup(history []Float, targetScore float64, scores []float64) bool

FloatedToSameScoreGroup returns true if the player floated (down) to the same score group in the previous round. Used by Dutch C14 to prevent consecutive downfloats to the same score group.

history: player's float history (one entry per round) targetScore: the score group the player would float to now scores: the score the player had after each round (parallel to history)

func GamesPlayed 

func GamesPlayed(p *PlayerState) int

GamesPlayed returns the number of games a player has played (rounds with a color, excluding byes/absences).

func HasPlayed 

func HasPlayed(a, b *PlayerState) bool

HasPlayed returns true if player a has played against player b (based on opponent history, which excludes forfeits).

func IsForbiddenPair 

func IsForbiddenPair(pair *ProposedPairing, ctx *CriteriaContext) bool

IsForbiddenPair returns true if the two players are in the forbidden pairs list. This is an absolute criterion: forbidden pairs must never be matched.

func IsPairForbiddenByID 

func IsPairForbiddenByID(aID, bID string, ctx *CriteriaContext) bool

IsPairForbiddenByID checks if two player IDs are in the forbidden pairs list. Convenience function for edge-generation code that works with player IDs directly.

func NeedsBye 

func NeedsBye(playerCount int) bool

NeedsBye returns true if the player count is odd.

func PairBracketsGlobal 

func PairBracketsGlobal(
	scoreGroups []ScoreGroup,
	ctx *CriteriaContext,
	playerMap map[string]*PlayerState,
) ([]ProposedPairing, *PlayerState, []string)

PairBracketsGlobal performs global Blossom matching across all score groups. This mirrors bbpPairings' computeMatching architecture: a single global matching graph is built with all players, and brackets are processed top-down using a 7-phase loop that incrementally updates edge weights.

For odd player counts, a completability pre-matching (Stage 0.5) runs first to determine which player will receive the bye. The unmatched player's score becomes ByeAssigneeScore in EdgeWeightParams, which influences the real edge weights via isByeCandidate logic.

Used by Dutch (C.04.3) and Burstein (C.04.4.2) Swiss pairing systems. The behavior is controlled through the CriteriaContext (TopScorers, LookAhead, ForbiddenPairs) and the edge weight parameters which encode system-specific optimization criteria.

Returns the committed pairings, the unmatched player (bye recipient for odd player counts, nil for even), and diagnostic notes.

func SatisfiesAbsolute 

func SatisfiesAbsolute(cand *Candidate, ctx *CriteriaContext) bool

SatisfiesAbsolute checks if ALL pairs in a candidate satisfy the absolute criteria: forbidden pairs, C1 (no rematches) and C3 (no absolute color conflicts). Returns false if any pair violates an absolute criterion.

func ValidatePairing 

func ValidatePairing(players []PlayerState, result *chesspairing.PairingResult) error

ValidatePairing checks that a PairingResult is structurally valid: - Every active player is either paired exactly once or has a bye. - No player appears in more than one pairing. - No unknown player IDs in pairings or byes. - Board numbers are sequential starting from 1.

Types

type Bracket 

type Bracket struct {
	Players       []*PlayerState
	Homogeneous   bool
	OriginalScore float64        // native score of this bracket
	Downfloaters  []*PlayerState // players floated down from higher brackets (heterogeneous)
}

Bracket is the processing unit for the pairing algorithm. A homogeneous bracket contains players with the same native score. A heterogeneous bracket contains downfloaters merged with a native group.

func BuildBrackets 

func BuildBrackets(groups []ScoreGroup) []Bracket

BuildBrackets creates initial homogeneous brackets from score groups. Each score group becomes one homogeneous bracket. Returns brackets in descending score order.

func CollapseBrackets 

func CollapseBrackets(upper, lower Bracket) Bracket

CollapseBrackets merges two consecutive brackets into one. Used when a bracket fails to pair and must be combined with the next. Players are deduplicated by ID to prevent self-pairings from repeated collapse operations.

func MergeIntoHeterogeneous 

func MergeIntoHeterogeneous(native Bracket, floaters []*PlayerState) Bracket

MergeIntoHeterogeneous creates a heterogeneous bracket by merging downfloaters into a native bracket.

type BracketPairing 

type BracketPairing struct {
	Pairs    []ProposedPairing
	Floaters []*PlayerState // players that couldn't be paired in this bracket
}

BracketPairing is the complete pairing result for a bracket.

type BursteinByeSelector 

type BursteinByeSelector struct{}

BursteinByeSelector selects the bye player per Burstein system rules: 1. Lowest score 2. Among ties: most games played 3. Among ties: lowest ranking (highest TPN)

func (BursteinByeSelector) SelectBye 

func (s BursteinByeSelector) SelectBye(players []*PlayerState) *PlayerState

SelectBye returns the player to receive the bye per Burstein rules.

type ByeSelector 

type ByeSelector interface {
	SelectBye(players []*PlayerState) *PlayerState
}

ByeSelector selects a player to receive the pairing-allocated bye (PAB).

type Candidate 

type Candidate struct {
	Pairs          []ProposedPairing // paired players
	Floaters       []*PlayerState    // S1 players floating down
	Residuals      []*PlayerState    // unmatched S2 players for sub-bracket pairing
	DownfloaterIDs map[string]bool   // S1 player IDs (for C14-C21 float criteria)
	BracketScore   float64           // native bracket score (for C18-C21 score diff)
}

Candidate represents a complete bracket pairing attempt to be scored.

type CandidateScore 

type CandidateScore struct {
	FloaterScores      []float64          // C7: scores of downfloaters, sorted descending
	FloaterTPNs        []int              // C7 tiebreaker: TPNs of floaters, sorted ascending (lower TPN preferred)
	Violations         [NumViolations]int // C8-C21: violation counts per criterion
	TranspositionOrder int                // FIDE B.3: lower = closer to identity transposition = preferred
}

CandidateScore holds the quality metrics for a Candidate. Compared lexicographically: FloaterScores first (C7), then Violations (C8-C21), then FloaterTPNs (C7 tiebreaker: higher-ranked floater preferred), then TranspositionOrder (FIDE C.04.3 B.3: prefer identity over later transpositions when all quality metrics are equal).

func (*CandidateScore) Compare 

func (s *CandidateScore) Compare(other *CandidateScore) int

Compare returns -1 if s is better than other, +1 if worse, 0 if equal. Comparison order:

  1. FloaterScores (C7): fewer floaters and lower scores are better
  2. Violations (C8-C21): lower violation counts are better
  3. FloaterTPNs (C7 tiebreaker): lower TPN (higher-ranked) preferred
  4. TranspositionOrder (FIDE B.3): earlier transposition is preferred

FloaterScores are compared lexicographically after sorting descending. Fewer floaters is always better. For equal-length lists, lower values win.

Violations are compared lexicographically by index (C8 first, C21 last). Lower values are better at each position.

FloaterTPNs break ties after violations. Lower TPN (higher-ranked player) is preferred. This ensures that when two transpositions produce identical violation scores, the one that floats the higher-ranked player is chosen, matching FIDE convention that quality criteria determine preference over transposition order.

TranspositionOrder (FIDE C.04.3 B.3) is the final tiebreaker: when two candidates have identical quality (floater scores, violations, and floater TPNs), the one closer to the identity transposition is preferred.

func (*CandidateScore) IsPerfect 

func (s *CandidateScore) IsPerfect() bool

IsPerfect returns true if this score has no floaters and no violations.

type Color 

type Color int

Color represents a player's color assignment in a round. 

const (
	ColorNone Color = iota // bye, absent, or no game
	ColorWhite
	ColorBlack
)

func (Color) Opposite 

func (c Color) Opposite() Color

Opposite returns the opposite color (White↔Black). None returns None.

func (Color) String 

func (c Color) String() string

String returns the color name for debugging.

type ColorPreference 

type ColorPreference struct {
	Color              *Color  // preferred color (nil = no preference)
	ColorImbalance     int     // abs(whites - blacks), always >= 0
	AbsolutePreference bool    // must play this color (imbalance > 1 OR 2+ consecutive)
	StrongPreference   bool    // should play this color (imbalance > 0, NOT absolute)
	PlayedColors       []Color // played color history (no byes), for findFirstColorDifference
}

ColorPreference holds the computed color preference for a player.

This matches bbpPairings' three-tier system (tournament.cpp computePlayerData):

  • AbsolutePreference: colorImbalance > 1 OR 2+ consecutive same color
  • StrongPreference: colorImbalance > 0 AND NOT absolute
  • Otherwise: mild preference (alternation) or no preference

The Color field holds the preferred color direction regardless of strength. ColorImbalance and HasConsecutive are used by AllocateColor for tiebreaking.

func ComputeColorPreference 

func ComputeColorPreference(history []Color) ColorPreference

ComputeColorPreference derives a player's color preference from their color history, matching bbpPairings' computePlayerData exactly.

bbpPairings logic (tournament.cpp lines 43-93): 

colorPreference =
  colorImbalance > 1 ? lowerColor                    // absolute (imbalance)
  : consecutiveCount > 1 ? invert(repeatedColor)     // absolute (consecutive)
  : colorImbalance > 0 ? lowerColor                  // strong
  : consecutiveCount > 0 ? invert(repeatedColor)     // mild
  : COLOR_NONE

absoluteColorPreference = colorImbalance > 1 || repeatedColor != NONE
  (repeatedColor is cleared to NONE when consecutiveCount <= 1)
  So effectively: colorImbalance > 1 || consecutiveCount > 1

strongColorPreference = !absoluteColorPreference && colorImbalance > 0

ColorNone (byes/absences) is skipped for all calculations.

func (ColorPreference) PreferredColor 

func (cp ColorPreference) PreferredColor() *Color

PreferredColor returns the color this player prefers, or nil if none.

type CriteriaContext 

type CriteriaContext struct {
	Players      map[string]*PlayerState
	TotalRounds  int
	CurrentRound int
	IsLastRound  bool
	TopScorers   map[string]bool // player IDs with >50% max score (final round only)

	// ForbiddenPairs contains canonicalized player ID pairs that must not be
	// paired together (e.g., players from the same club or family members).
	// Keys are [2]string with IDs in lexicographic order.
	// Enforced as an absolute criterion alongside C1 and C3.
	ForbiddenPairs map[[2]string]bool

	// RemainingBrackets holds the brackets after the current one being paired.
	// Set by the orchestrator (dutch.go) before calling MatchBracketMulti.
	// Used by C8 to simulate whether floaters allow the next bracket to pair.
	RemainingBrackets []Bracket

	// LookAhead attempts to pair a bracket without C8 (to avoid infinite recursion).
	// Set by the orchestrator (dutch.go) as a closure wrapping MatchBracketMulti
	// with a criteria slice that has C8 set to nil.
	LookAhead LookAheadFunc

	// Deadline is the time by which the pairing algorithm must complete.
	// When set, the matching algorithm returns the best result found so far
	// when the deadline is exceeded. Zero value means no deadline.
	Deadline time.Time
}

CriteriaContext holds tournament-wide state needed to evaluate criteria.

func (*CriteriaContext) DeadlineExceeded 

func (ctx *CriteriaContext) DeadlineExceeded() bool

DeadlineExceeded returns true if a deadline is set and has been exceeded.

type DutchByeSelector 

type DutchByeSelector struct{}

DutchByeSelector selects the bye player per Dutch system rules: lowest-ranked player (highest TPN) in the lowest score group who has not already received a PAB.

func (DutchByeSelector) SelectBye 

func (s DutchByeSelector) SelectBye(players []*PlayerState) *PlayerState

SelectBye returns the player to receive the bye, or nil if all have already received one (shouldn't happen in valid tournaments).

type EdgeWeightParams 

type EdgeWeightParams struct {
	// ScoreGroupSizeBits = bitsToRepresent(maxScoreGroupSize).
	// Used for boolean field widths AND reserve bits at the bottom.
	ScoreGroupSizeBits int

	// ScoreGroupsShift is the total width (in bits) of a score-indexed
	// field. Computed as the sum of bitsToRepresent(sgSize) for each
	// score group, iterated LOW→HIGH (matching bbpPairings lines 685-712).
	ScoreGroupsShift int

	// ScoreGroupShifts maps score → per-SG bit offset within a
	// scoreGroupsShift-wide field. Each SG's offset is the cumulative
	// width of all lower-scoring SGs. Matches bbpPairings' scoreGroupShifts.
	ScoreGroupShifts map[float64]int

	// PlayedRounds is the number of rounds already played.
	PlayedRounds int

	// ByeAssigneeScore is the score of the player determined to receive the
	// bye by the completability pre-matching. Used by isByeCandidate: a
	// player is a bye candidate if eligibleForBye AND score <= ByeAssigneeScore.
	// Set to -1 when even player count (no bye needed), which makes
	// isByeCandidate always false.
	ByeAssigneeScore float64

	// IsSingleDownfloaterTheByeAssignee is true when the bye assignee is
	// the single downfloater in the top bracket. When true, C9 (minimize
	// unplayed games of bye assignee) takes effect.
	IsSingleDownfloaterTheByeAssignee bool

	// UnplayedGameRanks maps playedGames count → rank (0-based, sorted by
	// most played games first). Used for C9 when IsSingleDownfloaterTheByeAssignee.
	UnplayedGameRanks map[int]int

	// ReserveBits = 3*ScoreGroupSizeBits + 1 (matches bbpPairings' reserve
	// for edgeWeightComputer addend).
	ReserveBits int

	// TotalBits is the total width of the edge weight.
	TotalBits int
}

EdgeWeightParams holds precomputed parameters for edge weight computation. Computed once before the main loop in pairBracketsGlobal.

func ComputeEdgeWeightParams 

func ComputeEdgeWeightParams(scoreGroups []ScoreGroup, playedRounds int) EdgeWeightParams

ComputeEdgeWeightParams builds EdgeWeightParams from sorted score groups (highest score first). This mirrors bbpPairings' computeMatching setup (lines ~685-715) where it iterates from LOWEST to HIGHEST score to compute scoreGroupShifts, using each SG's actual size to determine its bit width within score-indexed fields.

type Float 

type Float int

Float represents a player's float direction in a round. 

const (
	FloatNone Float = iota
	FloatUp
	FloatDown
)

func LastFloat 

func LastFloat(history []Float) Float

LastFloat returns the most recent non-None float direction, or FloatNone if there is none.

type LookAheadFunc 

type LookAheadFunc func(bracket Bracket, ctx *CriteriaContext) bool

LookAheadFunc attempts to pair a bracket using only C1-C7 criteria. Returns true if a valid pairing exists (at least one pair), false otherwise. Used by C8 to check whether floaters allow the next bracket to be paired. The function must NOT call C8 recursively (no infinite recursion).

type PlayerState 

type PlayerState struct {
	ID           string
	DisplayName  string
	InitialRank  int      // starting rank (by rating desc, then name asc), 1-based
	TPN          int      // Tournament Pairing Number (re-ranked each round), 1-based
	Score        float64  // actual score (standard 1-½-0, not tournament scoring)
	PairingScore float64  // pairing score = Score + virtual points (0 if no acceleration)
	ColorHistory []Color  // color per round (index 0 = round 1)
	FloatHistory []Float  // float per round (index 0 = round 1, Dutch only)
	Opponents    []string // IDs of opponents faced (forfeits excluded)
	ByeReceived  bool     // already received a PAB
	Active       bool
	Rating       int
}

PlayerState holds the computed state of a single player for the pairing algorithm. Built once per Pair() call from the engine's TournamentState.

func BuildPlayerStates 

func BuildPlayerStates(state *chesspairing.TournamentState) []PlayerState

BuildPlayerStates converts a TournamentState into a sorted slice of PlayerState values ready for the pairing algorithm.

Active players only. Sorted by score (desc), then initial rank (asc). TPN assigned sequentially after sorting.

Pairing scores use standard 1-½-0 regardless of tournament scoring system. Forfeit games are excluded from opponent history (players can be paired again).

type ProposedPairing 

type ProposedPairing struct {
	White        *PlayerState
	Black        *PlayerState
	BracketScore float64 // native bracket score (for board ordering: higher bracket pairs first)
}

ProposedPairing is a candidate pairing being evaluated. BracketScore records the originating bracket's score for board ordering.

type ScoreGroup 

type ScoreGroup struct {
	Score   float64
	Players []*PlayerState // ordered by TPN ascending
}

ScoreGroup holds all players with the same pairing score. Players are ordered by TPN ascending within the group.

func BuildScoreGroups 

func BuildScoreGroups(players []PlayerState) []ScoreGroup

BuildScoreGroups creates score groups from player states. Players are grouped by PairingScore and each group is sorted by TPN ascending. Returns groups in descending score order. Input need not be pre-sorted.

Source Files

View all Source files

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.