optimization

Documentation

Index

• func Beam[T GameState[T, U], U any](start T, beamSize int, limit time.Duration) []U
• func Chokudai[T GameState[T, U], U any](start T, width, maxTurns int, limit time.Duration) (path []U)
• func GeneticAlgorithm(first *State, populationSize int, eliteSize int, mutationRate float64, ...) []*maze.Node
• func MCTS[T GameState[T, U], U any](first T, simulations int, c float64, limit time.Duration) []U
• func Mutate(individual *Chromosome, mutationRate float64)
• type Chromosome
  • func Breed(parent1, parent2 Chromosome) Chromosome
  • func NewChromosome(w maze.World) Chromosome
  • func (c *Chromosome) CalcFitness() float64
• type GameState
• type Gene
• type MCTSNode
• type Population
  • func BreedPopulation(matingPool []Chromosome, eliteSize int) (children Population)
  • func NewPopulation(size int, w maze.World) Population
  • func (p *Population) MutatePopulation(mutationRate float64)
  • func (p *Population) NextGeneration(eliteSize int, mutationRate float64) Population
  • func (p *Population) Rank()
  • func (p *Population) Selection(eliteSize int) []Chromosome
• type State
  • func (s *State) Apply(move *maze.Node) *State
  • func (s *State) CameFrom() *State
  • func (s *State) Clone() *State
  • func (s *State) CreatedBy() *maze.Node
  • func (s *State) Evaluation() int
  • func (s *State) NextStates() []*State
  • func (s *State) PossibleNextMoves() []*maze.Node

Functions

func Beam

func Beam[T GameState[T, U], U any](start T, beamSize int, limit time.Duration) []U

Beam is like BFS but restricts the search space to save time by only looking at the best nodes.

func Chokudai

func Chokudai[T GameState[T, U], U any](start T, width, maxTurns int, limit time.Duration) (path []U)

Chokudai is DFS but considers the highest priority nodes first and restricts the search space.

func GeneticAlgorithm

func GeneticAlgorithm(first *State, populationSize int, eliteSize int, mutationRate float64, limit time.Duration) []*maze.Node

func MCTS

func MCTS[T GameState[T, U], U any](first T, simulations int, c float64, limit time.Duration) []U

MCTS performs a Monte Carlo Tree Search with Upper Confidence Bound.

func Mutate

func Mutate(individual *Chromosome, mutationRate float64)

Mutate may modify an individual route with a swap mutation

Types

type Chromosome

type Chromosome struct {
	Route   []Gene
	Fitness float64
}

Chromosome is a route through all Goals

func Breed

func Breed(parent1, parent2 Chromosome) Chromosome

Breed implements ordered crossover since the travelling salesman problem we are solving involves going through each goal 1 time.

func NewChromosome

func NewChromosome(w maze.World) Chromosome

NewChromosome creates a random sampling of goal nodes

func (*Chromosome) CalcFitness

func (c *Chromosome) CalcFitness() float64

CalcFitness returns 0 for a bad route up to 1 for a good route

type GameState

type GameState[T, U any] interface {
	comparable
	// PossibleNextMoves returns an index of possible moves.
	PossibleNextMoves() []U
	// Evaluation returns a high value for a good state, low value for a bad state.
	Evaluation() int
	// Apply returns a new state with the move applied.
	Apply(U) T
	// CameFrom returns the state that this one was generated from.
	CameFrom() T
	// CreatedBy returns the move that created this state.
	CreatedBy() U
}

GameState represents the state of the game at a given point in time.

type Gene

type Gene = *maze.Node

Gene is a Goal node

type MCTSNode

type MCTSNode[T GameState[T, U], U any] struct {
	// contains filtered or unexported fields
}

type Population

type Population struct {
	Routes []Chromosome
}

Population is all routes this generation

func BreedPopulation

func BreedPopulation(matingPool []Chromosome, eliteSize int) (children Population)

func NewPopulation

func NewPopulation(size int, w maze.World) Population

NewPopulation creates the first generation

func (*Population) MutatePopulation

func (p *Population) MutatePopulation(mutationRate float64)

func (*Population) NextGeneration

func (p *Population) NextGeneration(eliteSize int, mutationRate float64) Population

func (*Population) Rank

func (p *Population) Rank()

Rank sorts the routes by their fitness, best being first

func (*Population) Selection

func (p *Population) Selection(eliteSize int) []Chromosome

Selection implements Fitness Proportionate Selection, a.k.a Roulette Wheel Selection

type State

type State struct {
	World maze.World
	At    *maze.Node
	Score int
	Steps int
	// contains filtered or unexported fields
}

State represents the game state at each moment

func (*State) Apply

func (s *State) Apply(move *maze.Node) *State

Apply creates a new state that is the result of performing the move on the current state.

func (*State) CameFrom

func (s *State) CameFrom() *State

func (*State) Clone

func (s *State) Clone() *State

func (*State) CreatedBy

func (s *State) CreatedBy() *maze.Node

func (*State) Evaluation

func (s *State) Evaluation() int

Evaluation returns an int that represents how good the state is, higher is better.

func (*State) NextStates

func (s *State) NextStates() []*State

func (*State) PossibleNextMoves

func (s *State) PossibleNextMoves() []*maze.Node

PossibleNextMoves returns a list of moves you can make at a state