endgame

Documentation

Overview

Package endgame solves the endgame. It uses some sort of efficient tree search.

Package endgame implements a crossword game endgame solver. The endgame solver uses the B* algorithm. See "The B* Tree Search Algorithm: A Best-First Proof Procedure" by Hans Berliner

Index

• Constants
• type AStarSolver
  • func (a *AStarSolver) Init(board *board.GameBoard, movegen *movegen.GordonGenerator, bag *alphabet.Bag, ...)
• type BStarSolver
  • func (b *BStarSolver) Init(board *board.GameBoard, movegen *movegen.GordonGenerator, bag *alphabet.Bag, ...)
  • func (b *BStarSolver) Solve(playerOnTurn, opponent *alphabet.Rack) *move.Move
• type Solver
• type TreeNode

Constants

const CostConstant = 5000

const Infinity = 1e6

I guess Infinity isn't that big.

Types

type AStarSolver

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

AStarSolver implements the A* algorithm. I don't know how to implement B* so let's see how this does first, and improve on it later. Maybe I'll learn something.

func (*AStarSolver) Init

func (a *AStarSolver) Init(board *board.GameBoard, movegen *movegen.GordonGenerator,
	bag *alphabet.Bag, gd *gaddag.SimpleGaddag)

type BStarSolver

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

BStarSolver implements the B* algorithm.

func (*BStarSolver) Init

func (b *BStarSolver) Init(board *board.GameBoard, movegen *movegen.GordonGenerator,
	bag *alphabet.Bag, gd *gaddag.SimpleGaddag)

func (*BStarSolver) Solve

func (b *BStarSolver) Solve(playerOnTurn, opponent *alphabet.Rack) *move.Move

type Solver

type Solver interface {
	Init(board *board.GameBoard, movegen *movegen.GordonGenerator,
		bag *alphabet.Bag, gd *gaddag.SimpleGaddag)
	Solve(playerOnTurn, opponent *alphabet.Rack) *move.Move
}

Solver is an interface for an endgame solver. The scores don't matter, this solver maximizes spread.

type TreeNode

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