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

This file implements the "dynamic programming" solver, the somewhat inaccurate V1 of the endgame solver.

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 DynamicProgSolver
  • func (s *DynamicProgSolver) Init(board *board.GameBoard, movegen *movegen.GordonGenerator, bag *alphabet.Bag, ...)
  • func (s *DynamicProgSolver) Solve(playerOnTurn, opponent *alphabet.Rack) *move.Move
• type TreeNode

Constants

const (
	OurPlayTable = iota
	TheirPlayTable
)

const CostConstant = 5000

const Infinity = 1e6

I guess Infinity isn't that big.

const VeryLowEvaluation = -100000

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 DynamicProgSolver

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

DynamicProgSolver implements an endgame solver that uses dynamic programming to build up tables of endgame move valuations, similar to approach #1 in the Sheppard paper.

func (*DynamicProgSolver) Init

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

func (*DynamicProgSolver) Solve

func (s *DynamicProgSolver) Solve(playerOnTurn, opponent *alphabet.Rack) *move.Move

Solve generates the tables and returns the best calculated move for playerOnTurn.

type TreeNode

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