skrafl

package module
v0.0.0-...-3587a2c Latest Latest
Warning

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

 Go to latest Published: May 16, 2019 License: GPL-3.0 Imports: 10 Imported by: 1

README

GoSkrafl

A concurrent SCRABBLE(tm) engine and robot, written in Go

About

GoSkrafl is a fast, concurrent SCRABBLE(tm) engine and auto-playing robot. It is a package for the Go programming language, licensed under GNU GPLv3. It has been tested on Linux and Windows, and probably works fine on MacOS too.

Out of the box, GoSkrafl supports TWL06, SOWPODS and Icelandic SCRABBLE(tm) dictionaries and corresponding tile sets. But as it employs Unicode and UTF-8 throughout, GoSkrafl can easily be tweaked to accommodate most natural languages and dictionaries, and any tile bag configuration. (The only limitation is that there cannot be more different letters in an alphabet than there are bits in the native uint type.)

The GoSkrafl package encompasses the whole game lifecycle, board, rack and bag management, move validation, scoring, word and cross-word checks, as well as robot players.

The robot players make good use of Go's goroutines to discover valid moves concurrently, employing all available processor cores for parallel execution of multiple worker threads. This, coupled with Go's compilation to native machine code, and its efficient memory management, makes GoSkrafl quite fast. (As an order of magnitude, it runs at over 25 simulated TWL06 games per second on a quad-core Intel i7-4400 processor @ 3.4 GHz, or less than 40 milliseconds per game.)

The design and code of GoSkrafl borrow heavily from a battle-hardened SCRABBLE(tm) engine in Python by the same author.

Status

GoSkrafl is currently in Beta. Issues and pull requests are welcome.

Adding new dictionaries

To add support for a new dictionary, assemble the word list in a UTF-8 text file, with all words in lower case, one word per line. Use the DAWG builder from Netskrafl to build a .bin.dawg file. Copy it to the /GoSkrafl/dicts/ directory, then add a snippet of code at the bottom of dawg.go to wrap it in an instance of the Dawg class. Remember to add an alphabet string as well, cf. the IcelandicAlphabet and EnglishAlphabet variables. The same alphabet string must be used for the encoding in dawgbuilder.py. Post an issue if you need help.

Example

To enjoy seeing two robots slug it out at the SCRABBLE(tm) board:

package main

import (
    "fmt"
    skrafl "github.com/vthorsteinsson/GoSkrafl"
)

func main() {
    // Set up a game of SOWPODS SCRABBLE(tm)
    game := skrafl.NewSowpodsGame()
    game.SetPlayerNames("Robot A", "Robot B")
    // Create a robot that always selects
    // the highest-scoring valid move
    robot := skrafl.NewHighScoreRobot()
    // Print the initial game board and racks
    fmt.Printf("%v\n", game)
    // Generate moves until the game ends
    for {
        // Extract the game state
        state := game.State()
        // Find the highest-scoring move available
        move := robot.GenerateMove(state)
        // Apply the (implicitly validated) move to the game
        game.ApplyValid(move)
        // Print the new game state after the move
        fmt.Printf("%v\n", game)
        if game.IsOver() {
            fmt.Printf("Game over!\n")
            break
        }
    }
}

A fancier main program for exercising the GoSkrafl engine can be found here.

Original Author

Vilhjálmur Þorsteinsson, Reykjavík, Iceland.

Contact me via GitHub for queries or information regarding GoSkrafl, for instance if you would like to use GoSkrafl as a basis for your own game program, server or website but prefer not to do so under the conditions of the GNU GPL v3 license (see below).

License

GoSkrafl - a concurrent SCRABBLE(tm) engine and robot, written in Go

Copyright (C) 2019 Vilhjálmur Þorsteinsson

This set of programs is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This set of programs is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

The full text of the GNU General Public License is available here: http://www.gnu.org/licenses/gpl.html.

Trademarks

SCRABBLE is a registered trademark. This software or its author are in no way affiliated with or endorsed by the owners or licensees of the SCRABBLE trademark.

Documentation

Index

Constants

View Source 
const (
	ABOVE = 0
	LEFT  = 1
	RIGHT = 2
	BELOW = 3
)

Indices into AdjSquares

View Source 
const BingoBonus = 50

BingoBonus is the number of extra points awarded for laying down all the 7 tiles in the rack in one move

View Source 
const BoardSize = 15

BoardSize is the size of the Board

View Source 
const EnglishAlphabet = "abcdefghijklmnopqrstuvwxyz"

EnglishAlphabet contains the English SCRABBLE(tm) alphabet.

View Source 
const IcelandicAlphabet = "aábdðeéfghiíjklmnoóprstuúvxyýþæö"

IcelandicAlphabet contains the Icelandic letters as they are indexed in the compressed binary DAWG. Note that the Icelandic alphabet does not contain 'c', 'q', w' or 'z'. TODO: move this to the DAWG file.

View Source 
const IllegalMoveWord = "[???]"

IllegalMoveWord is the move.Word of an illegal move

View Source 
const RackSize = 7

RackSize contains the number of slots in the Rack

Variables

View Source 
var EnglishTileSet = initEnglishTileSet()

EnglishTileSet is the standard English SCRABBLE(tm) tile set

View Source 
var IcelandicDictionary = makeDawg("ordalisti.bin.dawg", IcelandicAlphabet)

IcelandicDictionary is a Dawg instance containing the Icelandic Scrabble(tm) dictionary, as derived from the BÍN database (Beygingarlýsing íslensks nútímamáls)

View Source 
var NewIcelandicTileSet = initNewIcelandicTileSet()

NewIcelandicTileSet is the new standard Icelandic tile set

View Source 
var SowpodsDictionary = makeDawg("sowpods.bin.dawg", EnglishAlphabet)

SowpodsDictionary is a Dawg instance containing the SOWPODS word list, used in European and U.S. SCRABBLE(tm).

View Source 
var Twl06Dictionary = makeDawg("TWL06.bin.dawg", EnglishAlphabet)

Twl06Dictionary is a Dawg instance containing the Tournament Word List 06, used in U.S. SCRABBLE(tm).

Functions

func FindLeftParts 

func FindLeftParts(dawg *Dawg, rack string) [][]*LeftPart

FindLeftParts returns all left part permutations that can be generated from the given rack, grouped by length

Types

type AdjSquares 

type AdjSquares [4]*Square

AdjSquares is a list of four Square pointers, with a nil if the corresponding adjacent Square does not exist

type Alphabet 

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

Alphabet stores the set of runes found within the DAWG, and supports bit map (set) operations

func (*Alphabet) Init 

func (a *Alphabet) Init(alphabet string)

Init initializes an Alphabet, including a precalculated bit map for its runes

func (*Alphabet) Length 

func (a *Alphabet) Length() int

Length returns the number of runes in the Alphabet

func (*Alphabet) MakeSet 

func (a *Alphabet) MakeSet(runes []rune) uint

MakeSet converts a list of runes to a bit map, with the extra twist that if any of the runes is '?', a bit map with all bits set is returned

func (*Alphabet) Member 

func (a *Alphabet) Member(r rune, set uint) bool

Member checks whether a rune is represented in a bit map

type Axis 

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

Axis stores information about a row or column on the board where the robot player is looking for valid moves

func (*Axis) Allows 

func (axis *Axis) Allows(index int, letter rune) bool

Allows returns true if the given letter can be placed in the indexed square within the Axis, in compliance with the cross checks

func (*Axis) GenerateMoves 

func (axis *Axis) GenerateMoves(lenRack int, leftParts [][]*LeftPart) []Move

GenerateMoves returns a list of all legal moves along this Axis

func (*Axis) Init 

func (axis *Axis) Init(state *GameState, rackSet uint, index int, horizontal bool)

Init initializes a fresh Axis object, associating it with a board row or column

func (*Axis) IsAnchor 

func (axis *Axis) IsAnchor(index int) bool

IsAnchor returns true if the given square within the Axis is an anchor square

func (*Axis) IsOpen 

func (axis *Axis) IsOpen(index int) bool

IsOpen returns true if the given square within the Axis is open for a new Tile from the Rack

type Bag 

type Bag struct {
	// Tiles is a fixed array of all tiles in a game,
	// copied at the start of the game from a TileSet
	Tiles []Tile
	// Contents is a list of pointers into the Tiles array,
	// corresponding to the current contents of the bag
	Contents []*Tile
}

Bag is a randomized list of tiles, initialized from a tile set, that is yet to be drawn and used in a game

func (*Bag) DrawTile 

func (bag *Bag) DrawTile() *Tile

DrawTile pops one tile from the (randomized) bag and returns it

func (*Bag) DrawTileByLetter 

func (bag *Bag) DrawTileByLetter(letter rune) *Tile

DrawTileByLetter draws the specified tile from the bag and returns it

func (*Bag) ExchangeAllowed 

func (bag *Bag) ExchangeAllowed() bool

ExchangeAllowed returns true if there are at least RackSize tiles left in the bag, thus allowing exchange of tiles

func (*Bag) ReturnTile 

func (bag *Bag) ReturnTile(tile *Tile)

ReturnTile returns a previously drawn Tile to the Bag

func (*Bag) String 

func (bag *Bag) String() string

String returns a string representation of a Bag

func (*Bag) TileCount 

func (bag *Bag) TileCount() int

TileCount returns the number of tiles in a Bag

type BitMap 

type BitMap map[rune]uint

BitMap maps runes to corresponding bit positions within an uint. It follows that the Alphabet cannot have more runes in it than uint has bits. Fortunately, few alphabets have more than 32/64 runes in them.

type Board 

type Board struct {
	Squares   [BoardSize][BoardSize]Square
	Adjacents [BoardSize][BoardSize]AdjSquares
	// The number of tiles on the board
	NumTiles int
}

Board represents the board as a matrix of Squares, and caches an adjacency matrix for each Square, consisting of pointers to adjacent Squares

func (*Board) CrossScore 

func (board *Board) CrossScore(row, col int, horizontal bool) (hasCrossing bool, score int)

CrossScore returns the sum of the scores of the tiles crossing the given tile, either horizontally or vertically. If there are no crossings, returns false, 0. (Note that true, 0 is a valid return value, if a crossing has only blank tiles.)

func (*Board) CrossWords 

func (board *Board) CrossWords(row, col int, horizontal bool) (left, right string)

CrossWords returns the word fragments above and below, or to the left and right of, the given co-ordinate on the board.

func (*Board) Fragment 

func (board *Board) Fragment(row, col int, direction int) []*Tile

Fragment returns a list of the tiles that extend from the square at row, col in the direction specified (ABOVE/BELOW/LEFT/RIGHT).

func (*Board) Init 

func (board *Board) Init()

Init initializes an empty board

func (*Board) NumAdjacentTiles 

func (board *Board) NumAdjacentTiles(row, col int) int

NumAdjacentTiles returns the number of tiles on the Board that are adjacent to the given coordinate

func (*Board) Sq 

func (board *Board) Sq(row, col int) *Square

Sq returns a pointer to a Board square

func (*Board) String 

func (board *Board) String() string

String represents a Board as a string

func (*Board) TileAt 

func (board *Board) TileAt(row, col int) *Tile

TileAt returns a pointer to the Tile in a given Square

func (*Board) WordFragment 

func (board *Board) WordFragment(row, col int, direction int) (result string)

WordFragment returns the word formed by the tile sequence emanating from the given square in the indicated direction, not including the square itself.

type Coding 

type Coding map[byte]Prefix

Coding maps an encoded byte to a legal letter, eventually suffixed with '|' to denote a final node in the Dawg

type Coordinate 

type Coordinate struct {
	Row, Col int
}

Coordinate stores a Board co-ordinate as as row, col tuple

type Cover 

type Cover struct {
	Letter  rune
	Meaning rune
}

Cover is a part of a TileMove, describing the covering of a single Square by a Letter. The Letter may be '?' indicating a blank tile, in which case the Meaning gives its meaning.

type Covers 

type Covers map[Coordinate]Cover

Covers is a map of board coordinates to a tile covering

type Dawg 

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

Dawg encapsulates the externally generated, compressed Directed Acyclic Word Graph as a byte buffer. Within the DAWG, letters from the alphabet are represented as indices into the alphabet string (below). The Coding map translates these indices to the actual letters. The iterNodeCache map is built on the fly, when each Dawg node is traversed for the first time. In practice, many nodes will never be traversed.

func (*Dawg) CrossSet 

func (dawg *Dawg) CrossSet(left, right string) uint

CrossSet calculates a bit-mapped set of allowed letters in a cross-check set, given a left/top and right/bottom string that intersects the square being checked.

func (*Dawg) Find 

func (dawg *Dawg) Find(word string) bool

Find attempts to find a word in a DAWG, returning true if found or false if not.

func (*Dawg) Init 

func (dawg *Dawg) Init(filePath string, alphabet string) error

Init reads the Dawg into memory (TODO: or memory-maps it)

func (*Dawg) Match 

func (dawg *Dawg) Match(pattern string) []string

Match returns all words in the Dawg that match a given pattern string, which can include '?' wildcards/blanks.

func (*Dawg) MatchRunes 

func (dawg *Dawg) MatchRunes(pattern []rune) []string

MatchRunes returns all words in the Dawg that match a given pattern, which can include '?' wildcards/blanks.

func (*Dawg) Navigate 

func (dawg *Dawg) Navigate(navigator Navigator)

Navigate performs a navigation through the DAWG under the control of a Navigator

func (*Dawg) NavigateResumable 

func (dawg *Dawg) NavigateResumable(navigator Navigator)

NavigateResumable performs a resumable navigation through the DAWG under the control of a Navigator

func (*Dawg) Permute 

func (dawg *Dawg) Permute(rack string, minLen int) []string

Permute finds all permutations of the given rack, returning them as a list (slice) of strings. The rack may contain '?' wildcards/blanks.

func (*Dawg) Resume 

func (dawg *Dawg) Resume(navigator Navigator, state *navState, matched string)

Resume resumes a navigation through the DAWG under the control of a Navigator, from a previously saved state

type ExchangeMove 

type ExchangeMove struct {
	Letters string
}

ExchangeMove is a move that exchanges 1-7 tiles from the player's Rack with the Bag. It is only valid when at least 7 tiles are left in the Bag.

func NewExchangeMove 

func NewExchangeMove(letters string) *ExchangeMove

NewExchangeMove returns a reference to a fresh ExchangeMove

func (*ExchangeMove) Apply 

func (move *ExchangeMove) Apply(game *Game) bool

Apply replenishes the exchanged tiles in the Rack from the Bag

func (*ExchangeMove) IsValid 

func (move *ExchangeMove) IsValid(game *Game) bool

IsValid returns true if an exchange is allowed and all exchanged tiles are actually in the player's rack

func (*ExchangeMove) Score 

func (move *ExchangeMove) Score(state *GameState) int

Score is always 0 for an ExchangeMove

func (*ExchangeMove) String 

func (move *ExchangeMove) String() string

String return a string description of the ExchangeMove

type ExtendRightNavigator 

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

ExtendRightNavigator implements the core of the Appel-Jacobson algorithm. It proceeds along an Axis, covering empty Squares with Tiles from the Rack while obeying constraints from the Dawg and the cross-check sets. As final nodes in the Dawg are encountered, valid tile moves are generated and saved.

func (*ExtendRightNavigator) Accept 

func (ern *ExtendRightNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*ExtendRightNavigator) Accepts 

func (ern *ExtendRightNavigator) Accepts(letter rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*ExtendRightNavigator) Done 

func (ern *ExtendRightNavigator) Done()

Done is called when the navigation is complete

func (*ExtendRightNavigator) Init 

func (ern *ExtendRightNavigator) Init(axis *Axis, anchor int, rack string)

Init initializes a fresh ExtendRightNavigator for an axis, starting from the given anchor, using the indicated rack

func (*ExtendRightNavigator) IsAccepting 

func (ern *ExtendRightNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*ExtendRightNavigator) PopEdge 

func (ern *ExtendRightNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*ExtendRightNavigator) PushEdge 

func (ern *ExtendRightNavigator) PushEdge(letter rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type FinalMove 

type FinalMove struct {
	OpponentRack   string
	MultiplyFactor int
}

FinalMove represents the final adjustments that are made to player scores at the end of a Game

func NewFinalMove 

func NewFinalMove(rackOpp string, multiplyFactor int) *FinalMove

NewFinalMove returns a reference to a fresh FinalMove

func (*FinalMove) Apply 

func (move *FinalMove) Apply(game *Game) bool

Apply always succeeds and returns true for a FinalMove

func (*FinalMove) IsValid 

func (move *FinalMove) IsValid(game *Game) bool

IsValid always returns true for a FinalMove

func (*FinalMove) Score 

func (move *FinalMove) Score(state *GameState) int

Score returns the opponent's rack leave, multiplied by a multiplication factor that can be 1 or 2

func (*FinalMove) String 

func (move *FinalMove) String() string

String return a string description of the FinalMove

type FindNavigator 

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

FindNavigator stores the state for a plain word search in the Dawg, and implements the Navigator interface

func (*FindNavigator) Accept 

func (fn *FindNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*FindNavigator) Accepts 

func (fn *FindNavigator) Accepts(chr rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*FindNavigator) Done 

func (fn *FindNavigator) Done()

Done is called when the navigation is complete

func (*FindNavigator) Init 

func (fn *FindNavigator) Init(word string)

Init initializes a FindNavigator with the word to search for

func (*FindNavigator) IsAccepting 

func (fn *FindNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*FindNavigator) PopEdge 

func (fn *FindNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*FindNavigator) PushEdge 

func (fn *FindNavigator) PushEdge(chr rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type Game 

type Game struct {
	PlayerNames [2]string
	Scores      [2]int
	Board       Board
	Racks       [2]Rack
	Bag         *Bag
	MoveList    []*MoveItem
	// The DAWG dictionary to use in the game
	Dawg *Dawg
	// The tile set to use in the game
	TileSet *TileSet
	// The number of consecutive non-tile, zero-point moves
	// (when 6 consecutive such moves have been made,
	// the game is over)
	NumPassMoves int
	// Whether to validate words formed by tile moves in
	// the game
	ValidateWords bool
}

Game is a container for an in-progress game between two players, having a Board and two Racks, as well as a Bag and a list of Moves made so far. We also keep track of the number of Tiles that have been placed on the Board.

func NewIcelandicGame 

func NewIcelandicGame() *Game

NewIcelandicGame instantiates a new Game with the Icelandic TileSet and returns a reference to it

func NewSowpodsGame 

func NewSowpodsGame() *Game

NewSowpodsGame instantiates a new Game with the English TileSet and returns a reference to it

func NewTwl06Game 

func NewTwl06Game() *Game

NewTwl06Game instantiates a new Game with the English TileSet and returns a reference to it

func (*Game) Apply 

func (game *Game) Apply(move Move) bool

Apply applies a move to the game, after validating it

func (*Game) ApplyValid 

func (game *Game) ApplyValid(move Move) bool

ApplyValid applies an already validated Move to a Game, appends it to the move list, replenishes the player's Rack if needed, and updates scores.

func (*Game) ForceRack 

func (game *Game) ForceRack(player int, letters string) bool

ForceRack forces the rack of the given player (or -1 = player whose move it is) to contain the given tiles. The tiles that were previously in the rack are first returned to the bag, and then the specified new tiles are drawn. If any of them is not found in the bag, the operation is aborted and false is returned.

func (*Game) Init 

func (game *Game) Init(tileSet *TileSet, dawg *Dawg)

Init initializes a new game with a fresh bag copied from the given tile set, and draws the player racks from the bag

func (*Game) IsOver 

func (game *Game) IsOver() bool

IsOver returns true if the Game is over after the last move played

func (*Game) MakePassMove 

func (game *Game) MakePassMove() bool

MakePassMove appends a pass move to the Game's move list

func (*Game) MakeTileMove 

func (game *Game) MakeTileMove(row, col int, horizontal bool, tiles []*Tile) bool

MakeTileMove creates a tile move and appends it to the Game's move list

func (*Game) PlayTile 

func (game *Game) PlayTile(tile *Tile, row, col int) bool

PlayTile moves a tile from the player's rack to the board

func (*Game) PlayerToMove 

func (game *Game) PlayerToMove() int

PlayerToMove returns 0 or 1 depending on which player's move it is

func (*Game) SetPlayerNames 

func (game *Game) SetPlayerNames(player0, player1 string)

SetPlayerNames sets the names of the two players

func (*Game) State 

func (game *Game) State() *GameState

State returns a new GameState instance describing the state of the game in a minimal manner so that a robot player can decide on a move

func (*Game) String 

func (game *Game) String() string

String returns a string representation of a Game

func (*Game) TileAt 

func (game *Game) TileAt(row, col int) *Tile

TileAt is a convenience function for returning the Tile at a given coordinate on the Game Board

func (*Game) TilesOnBoard 

func (game *Game) TilesOnBoard() int

TilesOnBoard returns the number of tiles already laid down on the board

type GameState 

type GameState struct {
	Dawg    *Dawg
	TileSet *TileSet
	Board   *Board
	// The rack of the player whose move it is
	Rack *Rack
	// contains filtered or unexported fields
}

GameState contains the bare minimum of information that is needed for a robot player to decide on a move in a Game.

func (*GameState) GenerateMoves 

func (state *GameState) GenerateMoves() []Move

GenerateMoves returns a list of all legal moves in the GameState, considering the Board and the player's Rack. The generation works by dividing the task into 30 sub-tasks of finding legal moves within each Axis, i.e. all columns and rows of the board. These sub-tasks are performed concurrently (and hopefully in parallel to some extent) by 30 goroutines.

type HighScoreRobot 

type HighScoreRobot struct {
}

HighScoreRobot implements a simple strategy: it always picks the highest-scoring move available, or exchanges all tiles if there is no valid tile move, or passes if exchange is not allowed.

func (*HighScoreRobot) PickMove 

func (robot *HighScoreRobot) PickMove(state *GameState, moves []Move) Move

PickMove for a HighScoreRobot picks the highest scoring move available, or an exchange move, or a pass move as a last resort

type LeftFindNavigator 

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

LeftFindNavigator is similar to FindNavigator, but instead of returning only a bool result, it returns the full navigation state as it is when the requested word prefix is found. This makes it possible to continue the navigation later with further constraints.

func (*LeftFindNavigator) Accept 

func (lfn *LeftFindNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*LeftFindNavigator) Accepts 

func (lfn *LeftFindNavigator) Accepts(chr rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*LeftFindNavigator) Done 

func (lfn *LeftFindNavigator) Done()

Done is called when the navigation is complete

func (*LeftFindNavigator) Init 

func (lfn *LeftFindNavigator) Init(prefix Prefix)

Init initializes a LeftFindNavigator with the word to search for

func (*LeftFindNavigator) IsAccepting 

func (lfn *LeftFindNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*LeftFindNavigator) PopEdge 

func (lfn *LeftFindNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*LeftFindNavigator) PushEdge 

func (lfn *LeftFindNavigator) PushEdge(chr rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type LeftPart 

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

LeftPart stores the navigation state after matching a particular left part within the DAWG, so we can resume navigation from that point to complete an anchor square followed by a right part

func (*LeftPart) String 

func (lp *LeftPart) String() string

String returns a string representation of a LeftPart, for debugging purposes

type LeftPermutationNavigator 

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

LeftPermutationNavigator finds all left parts of words that are possible with a particular rack, and accumulates them by length. This is done once at the start of move generation.

func (*LeftPermutationNavigator) Accept 

func (lpn *LeftPermutationNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*LeftPermutationNavigator) Accepts 

func (lpn *LeftPermutationNavigator) Accepts(chr rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*LeftPermutationNavigator) Done 

func (lpn *LeftPermutationNavigator) Done()

Done is called when the navigation is complete

func (*LeftPermutationNavigator) Init 

func (lpn *LeftPermutationNavigator) Init(rack string)

Init initializes a fresh LeftPermutationNavigator using the given rack

func (*LeftPermutationNavigator) IsAccepting 

func (lpn *LeftPermutationNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*LeftPermutationNavigator) LeftParts 

func (lpn *LeftPermutationNavigator) LeftParts(length int) []*LeftPart

LeftParts returns a list of strings containing the left parts of words that could be found in the given Rack

func (*LeftPermutationNavigator) PopEdge 

func (lpn *LeftPermutationNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*LeftPermutationNavigator) PushEdge 

func (lpn *LeftPermutationNavigator) PushEdge(chr rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type MatchNavigator 

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

MatchNavigator stores the state for a pattern matching navigation of a Dawg, and implements the Navigator interface

func (*MatchNavigator) Accept 

func (mn *MatchNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*MatchNavigator) Accepts 

func (mn *MatchNavigator) Accepts(chr rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*MatchNavigator) Done 

func (mn *MatchNavigator) Done()

Done is called when the navigation is complete

func (*MatchNavigator) Init 

func (mn *MatchNavigator) Init(pattern []rune)

Init initializes a MatchNavigator with the word to search for

func (*MatchNavigator) IsAccepting 

func (mn *MatchNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*MatchNavigator) PopEdge 

func (mn *MatchNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*MatchNavigator) PushEdge 

func (mn *MatchNavigator) PushEdge(chr rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type Move 

type Move interface {
	IsValid(*Game) bool
	Apply(*Game) bool
	Score(*GameState) int
}

Move is an interface to various types of moves

type MoveItem 

type MoveItem struct {
	RackBefore string
	Move       Move
}

MoveItem is an entry in the MoveList of a Game. It contains the player's Rack as it was before the move, as well as the move itself. 

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

Navigation contains the state of a single navigation that is underway within a Dawg 

func (nav *Navigation) FromEdge(state *navState, matched string)

FromEdge navigates along an edge in the Dawg. An edge consists of a prefix string, which may be longer than one letter. 

func (nav *Navigation) FromNode(offset uint32, matched string)

FromNode continues a navigation from a node in the Dawg, enumerating through outgoing edges until the navigator is satisfied 

func (nav *Navigation) Go(dawg *Dawg, navigator Navigator)

Go starts a navigation on the underlying Dawg using the given Navigator 

func (nav *Navigation) Resume(dawg *Dawg, navigator Navigator, state *navState, matched string)

Resume continues a navigation on the underlying Dawg using the given Navigator, from a previously saved navigation state 

type Navigator interface {
	IsAccepting() bool
	Accepts(rune) bool
	Accept(matched string, final bool, state *navState)
	PushEdge(rune) bool
	PopEdge() bool
	Done()
}

Navigator is an interface that describes behaviors that control the navigation of a Dawg

type OneOfNBestRobot 

type OneOfNBestRobot struct {
	N int
}

OneOfNBestRobot picks one of the N highest-scoring moves at random.

func (*OneOfNBestRobot) PickMove 

func (robot *OneOfNBestRobot) PickMove(state *GameState, moves []Move) Move

PickMove for OneOfNBestRobot selects one of the N highest-scoring moves at random, or an exchange move, or a pass move as a last resort

type PassMove 

type PassMove struct {
}

PassMove is a move that is always valid, has no effect when applied, and has a score of 0

func NewPassMove 

func NewPassMove() *PassMove

NewPassMove returns a reference to a fresh PassMove

func (*PassMove) Apply 

func (move *PassMove) Apply(game *Game) bool

Apply always succeeds and returns true for a PassMove

func (*PassMove) IsValid 

func (move *PassMove) IsValid(game *Game) bool

IsValid always returns true for a PassMove

func (*PassMove) Score 

func (move *PassMove) Score(state *GameState) int

Score is always 0 for a PassMove

func (*PassMove) String 

func (move *PassMove) String() string

String return a string description of the PassMove

type PermutationNavigator 

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

PermutationNavigator stores the state for a plain word search in the Dawg, and implements the Navigator interface

func (*PermutationNavigator) Accept 

func (pn *PermutationNavigator) Accept(matched string, final bool, state *navState)

Accept is called to inform the navigator of a match and whether it is a final word

func (*PermutationNavigator) Accepts 

func (pn *PermutationNavigator) Accepts(chr rune) bool

Accepts returns true if the navigator should accept and 'eat' the given character

func (*PermutationNavigator) Done 

func (pn *PermutationNavigator) Done()

Done is called when the navigation is complete

func (*PermutationNavigator) Init 

func (pn *PermutationNavigator) Init(rack string, minLen int)

Init initializes a PermutationNavigator with the word to search for

func (*PermutationNavigator) IsAccepting 

func (pn *PermutationNavigator) IsAccepting() bool

IsAccepting returns false if the navigator should not expect more characters

func (*PermutationNavigator) PopEdge 

func (pn *PermutationNavigator) PopEdge() bool

PopEdge returns false if there is no need to visit other edges after this one has been traversed

func (*PermutationNavigator) PushEdge 

func (pn *PermutationNavigator) PushEdge(chr rune) bool

PushEdge determines whether the navigation should proceed into an edge having chr as its first letter

type Prefix 

type Prefix []rune

A Prefix is an array of runes that prefixes an outgoing edge in the Dawg

type Rack 

type Rack struct {
	Slots [RackSize]Square
	// Letters is a map of letters in the rack with their count,
	// with blank tiles being represented by '?'
	Letters map[rune]int
}

Rack represents a player's rack of Tiles

func (*Rack) AsRunes 

func (rack *Rack) AsRunes() []rune

AsRunes returns the tiles in the Rack as a list of runes

func (*Rack) AsSet 

func (rack *Rack) AsSet(alphabet *Alphabet) uint

AsSet returns the rack as a bit-mapped set of runes. If the rack contains a blank tile ('?'), the bitmap will have all bits set.

func (*Rack) AsString 

func (rack *Rack) AsString() string

AsString returns the tiles in the Rack as a contiguous string

func (*Rack) Extract 

func (rack *Rack) Extract(numTiles int, meaning rune) []*Tile

Extract obtains the given number of tiles from the rack, returning them as a list. If a tile is blank, assign the given meaning to it. This function is useful for debugging and testing purposes.

func (*Rack) Fill 

func (rack *Rack) Fill(bag *Bag) bool

Fill draws tiles from the bag to fill a rack. Returns false if unable to fill all empty slots.

func (*Rack) FillByLetters 

func (rack *Rack) FillByLetters(bag *Bag, letters []rune) bool

FillByLetters draws tiles identified by the given array of letters from the Bag to fill the Rack, at least as far as possible. Returns false if a tile corresponding to a letter from the array is not found in the bag.

func (*Rack) FindTile 

func (rack *Rack) FindTile(letter rune) *Tile

FindTile finds a tile with the given letter (or '?') in the rack and returns a pointer to it, or nil if not found

func (*Rack) FindTiles 

func (rack *Rack) FindTiles(letters []rune) []*Tile

FindTiles finds tiles corresponding to the given letters (or '?') in the rack and returns a list. If tiles are not found in the rack, they are not included in the result. Note that the same tile is not returned twice, even if a particular letter is requested twice.

func (*Rack) HasTile 

func (rack *Rack) HasTile(tile *Tile) bool

HasTile returns true if the given Tile is in the Rack

func (*Rack) Init 

func (rack *Rack) Init()

Init initializes an empty rack

func (*Rack) IsEmpty 

func (rack *Rack) IsEmpty() bool

IsEmpty returns true if the Rack is empty

func (*Rack) RemoveTile 

func (rack *Rack) RemoveTile(tile *Tile) bool

RemoveTile removes a tile from a Rack

func (*Rack) ReturnToBag 

func (rack *Rack) ReturnToBag(bag *Bag)

ReturnToBag returns the tiles in the Rack to a Bag

func (*Rack) String 

func (rack *Rack) String() string

String returns a printable string representation of a Rack

type Robot 

type Robot interface {
	PickMove(state *GameState, moves []Move) Move
}

Robot is an interface for automatic players that implement a playing strategy to pick a move given a list of legal tile moves.

type RobotWrapper 

type RobotWrapper struct {
	Robot
}

RobotWrapper wraps a Robot implementation

func NewHighScoreRobot 

func NewHighScoreRobot() *RobotWrapper

NewHighScoreRobot returns a fresh instance of a HighestScoreRobot

func NewOneOfNBestRobot 

func NewOneOfNBestRobot(n int) *RobotWrapper

NewOneOfNBestRobot returns a fresh instance of a OneOfNBestRobot

func (*RobotWrapper) GenerateMove 

func (rw *RobotWrapper) GenerateMove(state *GameState) Move

GenerateMove generates a list of legal tile moves, then asks the wrapped robot to pick one of them to play

type Square 

type Square struct {
	Tile             *Tile
	LetterMultiplier int
	WordMultiplier   int
	Row              int // Board row 0..14, or -1 if rack square
	Col              int // Board column 0..14, or rack square 0..6
}

Square is a Board square or Rack slot that can hold a Tile

func (*Square) String 

func (square *Square) String() string

String represents a Square as a string. An empty Square is indicated by a dot ('.').

type Tile 

type Tile struct {
	Letter   rune
	Meaning  rune // Meaning of blank tile (if Letter=='?')
	Score    int  // The nominal score of the tile
	PlayedBy int  // Which player played the tile
}

Tile is a tile from the Bag

func (*Tile) String 

func (tile *Tile) String() string

String represents a Tile as a string

type TileMove 

type TileMove struct {
	TopLeft     Coordinate
	BottomRight Coordinate
	Covers      Covers
	Horizontal  bool
	Word        string
	CachedScore *int
	// If ValidateWords is true, IsValid() should check all words
	// formed by this move against the game dictionary
	ValidateWords bool
}

TileMove represents a normal tile move by a player, where one or more Squares are covered by a Tile from the player's Rack

func NewTileMove 

func NewTileMove(board *Board, covers Covers) *TileMove

NewTileMove creates a new TileMove object with the given Covers, i.e. Tile coverings

func NewUncheckedTileMove 

func NewUncheckedTileMove(board *Board, covers Covers) *TileMove

NewUncheckedTileMove creates a new TileMove object with the given Covers, i.e. Tile coverings. In contrast to NewTileMove(), this function does not check that the words formed by the tile move are valid. It is intended for testing purposes.

func (*TileMove) Apply 

func (move *TileMove) Apply(game *Game) bool

Apply moves the tiles in the Covers from the player's Rack to the board Squares

func (*TileMove) Init 

func (move *TileMove) Init(board *Board, covers Covers, validateWords bool)

Init initializes a TileMove instance for a particular Board using a map of Coordinate to Cover

func (*TileMove) IsValid 

func (move *TileMove) IsValid(game *Game) bool

IsValid returns true if the TileMove is valid in the current Game

func (*TileMove) Score 

func (move *TileMove) Score(state *GameState) int

Score returns the score of the TileMove, if played in the given Game

func (*TileMove) String 

func (move *TileMove) String() string

String return a string description of a TileMove

type TileSet 

type TileSet struct {
	Tiles  []Tile
	Scores map[rune]int
}

TileSet is a static list of tiles, used as a prototype to copy new Bags from

Source Files

View all Source files

Directories

Path Synopsis

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.