utilsys

package
v0.2.21 Latest Latest
Warning

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

 Go to latest Published: Jun 11, 2021 License: MIT Imports: 5 Imported by: 0

README

utilsys

This package provides a completely self-contained utility system structure, which is a very well-known method of generating complex, emergent AI behavior without an excessive amount of computational resources. There is no requirement that clients use this technique for generating behavior.

An introduction to utility systems can be found on wikipedia.

The naming conventions of this package are inspired by the rust crate https://docs.rs/big-brain however it is not a port.

Overview

  • An Action is capable of manipulating the state.
  • A Scorer assesses the environment and produces a measure of the utility of an Action.
  • A Thinker is a type of Action which delegates to other Actions based on their utility.
  • A Qualifier is a type of Scorer which delegates to other Scorers to combine or rescale them.
  • A BayesScorer is a special type of Scorer where the action has a utility of 1, but success is probabilistic and can be estimated using Bayes' rule. BayesScorer rely on a the standard odds (e.g. in general 1 succeed for every 5 failures) and a set of BayesFactors (e.g, 3x as likely to succeed when Y is researched) to produce the final odds (e.g. 3 successes for every 5 failures) which are then converted to the final probability (e.g. 3 / (3+5) = 0.375).
  • A ScoredAction is a Scorer and Action pair. Note that Scorer and Actions are often but not always independent. For an example of a dependendent pair, see CooldownQualifiedScoredAction. It is usually simpler to build as much as possible about the combination independently and then merge them with a ScoredAction specifically focused on how they are tied together, as dependent Scorer and Action logic can be harder to follow.
Scoring Convention

Although not required, it's recommended that Scorers follow a scoring convention where all scores are between 0 and 1 (inclusive), where the values are interpreted as:

  • <0.1: Useless, valueless, or impossible. For example, the score for healing a full health entity.
  • 0.1: Possible, but doesn't do anything to achieve your goals.
  • 0.1 - 1: There is some value in doing this, and that value increases linearly with the score.
  • 1: It is not possible to get more worth or value from the action. For example, a failure to perform this action right now will immediately result in the game being lost.

Example

Creating an Action

Actions generally consist of two components - the exposed action, which acts just as a stateless builder for actions, and the private action, which actually does the thing and is stateful.

type meanderAction struct{
    // the default value is utilsys.ActionStateInit, which means that
    // the next thing to happen to this action is Attached()
    state utilsys.ActionState
}

func (a *meanderAction) State() utilsys.ActionState {
    return a.state
}

func (a *meanderAction) Attached(world interface{}, actor interface{}) {
    // Typically you would do some kind of type assertion here
    // on world and actor then save them to the meanderAction
    // so they can be used on Execute()

    // When this is called state is ActionStateInit and usually this should
    // change the state to ActionStateRequested

    // This SHOULD NOT manipulate the world or actor. That should be done
    // in Execute.

    a.state = utilsys.ActionStateRequested
}

func (a *meanderAction) Execute(delta time.Duration) {
    // This is called if state is ActionStateRequested or ActionStateExecuting,
    // one per tick, and should eventually set the state to ActionStateSuccess
    // or ActionStateFailure. For the utilsys ActionStateRequested and
    // ActionStateExecuting are basically the same, but you can use them to
    // distinguish the first call to Execute with future calls to Execute

    if a.state == utilsys.ActionStateRequested {
        // For the purposes of demo lets pretend we need another tick
        a.state = utilsys.ActionStateExecuting
        return
    }

    a.state = utilsys.ActionStateSuccess
}

func (a *meanderAction) Cancel() {
    // This is called when the state is ActionStateRequested or ActionStateExecuting,
    // but for some reason we want the action to end as soon as possible. Invoking
    // this function should eventually result in ActionStateSuccess or ActionStateFailure.
    a.state = utilsys.ActionStateCanceled
}

func (a *meanderAction) FinishCanceling(delta time.Duration) {
    // FinishCanceling is called if state is ActionStateCanceled once per tick
    // and should eventually set the state to ActionStateSuccess or ActionStateFailure.
    a.state = utilsys.ActionStateFailed
}

func (a *menaderAction) Reset() {
  // This is called when the state is ActionStateSuccess or ActionStateFailure and
  // should result in ActionStateRequested, ActionStateExecuting, ActionStateSuccess,
  // or ActionStateFailure. This should NOT manipulate the world or actor.
  a.state = utilsys.ActionStateRequested
}

type MeanderAction struct{}
func (a MeanderAction) Build() utilsys.Action {
    return &meanderAction{}
}
Creating a Scorer

Scorers follow essentially the same pattern as Action, but simpler.

type foodScorer struct{
    // normally you'd use a stricter type for these here, since you
    // would have casted them in Attached()

    world interface{}
    actor interface{}
}

func (s *foodScorer) Attach(world interface{}, actor interface{}) {
    s.world = world
    s.actor = actor
}

func (s *foodScorer) Score() float64 {
    // some calculation here to get a number between 0 and 1. A good
    // default choice is that your Score() functions always use the
    // full range and then you use Qualifier's as necessary to rescale
    // or clip scores.
    return 0.5
}

type FoodScorer struct{}
func (s FoodScorer) Build() utilsys.Scorer {
    return &foodScorer{}
}
Building the AI

Notice how there are few pointers as everything constructed at this step, with the exception of world, is intended to be essentially stateless. This is not a hard requirement but if it does not come naturally you may be interpreting the interfaces incorrectly. Remember, MeanderAction is really an ActionBuilder at this step.

This example uses HighestScore technique which is the simplest type of thinker, which just runs whatever has the highest score at a given point, breaking ties uniformly at random. This is what is classically meant by a utility system.

Other types you should definitely consider, especially when nesting:

  • A FirstToScore system is less theoretically pure but is more stable. It runs the first action in the list whose score meets or exceeds a threshold, falling back to HighestScore.
  • A LinearProbabilistic system adds a lot of randomness to the AI. It selects an action from the given list of choices at random, where the odds of selecting an action is proportional to its score. Note this will often result in very low-score selections. One can specify a threshold for the minimum score to be included (so long as at least something reaches the minimum score) to avoid particularly ridiculous behavior.
  • A SoftMaxProbabilistic system adds a bit of randomness to the AI. It selects an action from the given list of choices at random, where the odds of selecting an action is proportional to e^(factor*score). This is much more predictable than the LinearProbabilistic system for a reasonable factor value (usually between 5 and 30). Higher factors mean less random.
var world interface{} // typically your pkg.Game
utilsys.NewAI(
    world,
    utilsys.NewHighestScoreThinker([]utilsys.ScoredActionBuilder{
        ScorerBuilderAndActionBuilder{
            Action: MeanderAction{},
            Scorer: utilsys.FixedScorer{Score: 0.1}
        },
        ScorerBuilderAndActionBuilder{
            Action: AcquireResourceAction{Resource: "gold"},
            Scorer: AcquireResourceScorer{}
        },
    })
)
Using the AI

Using the AI just requires that you add all the actors to the AI via

// actor is typically a Player or SmartObject, some actions could be either.
// Typically you would get this from (*client.State).OnSelfLoaded or
// (*client.State).OnControllableSmartObjectLoaded
var actor interface{}

ai.AddActor(actor)

Make sure you remember to detach any actors you no longer want to control:

// Typically this would happen from (*client.State).OnSelfLost or
// (*client.State).OnControllableSmartObjectLost
var actor interface{}

ai.RemoveActor(actor)

And then you regularly tick the AI:

// Typically this would happen from your (pkg.Game).Tick
var delta time.Duration

ai.Tick(delta)

And that's all there is to it!

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type AI 

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

AI runs Actions on all the actors within the world.

func NewAI 

func NewAI(world interface{}, coreAction ActionBuilder) *AI

NewAI constructs a new AI within the given world, which uses the given coreAction for all actors. Typically coreAction is a Thinker, though this is not enforced.

func (*AI) AddActor 

func (ai *AI) AddActor(actor interface{})

AddActor adds the given actor to be handled by this AI.

performance: O(1) amortized

func (*AI) RemoveActor 

func (ai *AI) RemoveActor(actor interface{})

RemoveActor removes the given actor from being handled by this AI.

performance: O(n) where n is the number of actors

func (*AI) Tick 

func (ai *AI) Tick(delta time.Duration)

Tick all of the actions for actors handled by this AI, informing them the given amount of time has passed.

type Action 

type Action interface {
	// State returns the state of this action. Actions are responsible for
	// ensuring their state goes through the correct phases.
	State() ActionState

	// Attached is called when the action is in the state Init to let them know
	// which world and actor they are acting upon. The Action should typically
	// verify these are of the appropriate type and store them in a stricter
	// type, then move to Requested, Success, or Failure as appropriate. A
	// single Action is not reused across actors.
	Attached(world, actor interface{})

	// Execute this action within the world on the actor, after the given
	// amount of elapsed time since the last call (or an arbitrary value
	// if never called before). Should eventually result in the action
	// transitioning to Success or Failure.
	Execute(delta time.Duration)

	// Cancel this action, which tells the Action to do whatever is necessary
	// to get to the Success or Failure state as quickly as possible. Typically
	// this will either imemdiately update the state of the Action to Success
	// or Failure, or move the action into the Canceled state. This is NOT called
	// if the actor is removed from the AI - the Action simply will no longer
	// receive callbacks in that event, to avoid tedious nil handling within
	// each Action.
	Cancel()

	// FinishCanceling is called when the Action is in the Cancel state, and
	// should eventually move the action to the Success or Failure state. It
	// is passed the elapsed time since the last call or an arbitrary value
	// if never called before.
	FinishCanceling(delta time.Duration)

	// Reset is called only in the Success or Failure state, and acts as the
	// equivalent of Attached except for an instance that's already been used
	// before.
	Reset()
}

Action is a stateful object that acts upon a given actor in a given world. These are produced by action builders, which are what go into the AI.

type ActionBuilder 

type ActionBuilder interface {
	// Build the action
	Build() Action
}

ActionBuilder is something capable of building unattached actions and is generally stateless

func NewFirstToScoreThinker 

func NewFirstToScoreThinker(threshold float64, children []ScoredActionBuilder) ActionBuilder

NewFirstToScoreThinker produces a Thinker which performs the first child whose score meets or exceeds the threshold, falling back to a HighestScoreThinker if no children meet or exceed the threshold.

func NewHighestScoreThinker 

func NewHighestScoreThinker(actions []ScoredActionBuilder) ActionBuilder

NewHighestScoreThinker produces a Thinker which performs whichever action from the given list of scored actions has the highest score. In the event of ties, it chooses uniformly at random from the ties.

func NewLinearProbabilisticThinker 

func NewLinearProbabilisticThinker(threshold float64, children []ScoredActionBuilder) ActionBuilder

NewLinearProbabilisticThinker produces a new Thinker which selects which child randomly, where the probability of a child being selected is proportional to its score. If any of the children scores meet or exceed the threshold, then all children below the threshold score are ignored.

func NewSoftMaxProbabilisticThinker 

func NewSoftMaxProbabilisticThinker(threshold float64, factor float64, children []ScoredActionBuilder) ActionBuilder

NewSoftMaxProbabilisticThinker produces a Thinker which selects a child randomly from the children with a probability proportional to e^(score*factor). If there are any children whose score meets or exceeds the given threshold, then all children whose score is below the threshold are ignored.

A factor of 1 makes this a pure soft-max function. A factor of 0 makes this a completely random choice. A higher factor reduces the amount of randomness. The factor is typically between 5 and 30

func NewThinkerBuilder 

func NewThinkerBuilder(thinker Thinker, actions []ScoredActionBuilder) ActionBuilder

NewThinkerBuilder produces an ActionBuilder out of something implementing the Thinker interface and the non-empty slice of children.

type ActionState 

type ActionState int
const (
	// The initial state of an Action; implies it needs to be Attach'd.
	ActionStateInit ActionState = 0

	// The action has never been Execute'd before and should have Execute
	// called
	ActionStateRequested ActionState = 1

	// The action has had Execute called before but still needs Execute
	// to be called
	ActionStateExecuting ActionState = 2

	// Something has requested the action be canceled, but it is not done
	// canceling so FinishCanceling should be called
	ActionStateCanceled ActionState = 3

	// The action succeeded
	ActionStateSuccess ActionState = 4

	// The action failed
	ActionStateFailure ActionState = 5
)

type BayesFactor 

type BayesFactor interface {
	// Attached is called once to tell the factor the world and actor
	// it is operating within. Typically the factor will store more
	// strictly typed representations.
	Attached(world, actor interface{})

	// Factor returns how much information was gained by this factor.
	// If this factor is not informative, this will return
	// `big.NewRat(1, 1)`. If this increases the probability of success
	// by a factor of 2, this returns `big.NewRat(2, 1)`. If it decreases
	// the odds of success by a factor of 2, this returns `big.NewRat(1, 2)`.
	Factor() *big.Rat
}

BayesFactor describes something which can alter our prediction about something by a given factor. It is stateful and only used for a single actor in a single world.

type BayesFactorBuilder 

type BayesFactorBuilder interface {
	// Build a new BayesFactor not attached yet.
	Build() BayesFactor
}

BayesFactorBuilder acts as a constructor for BayesFactors, since we need one BayesFactor per actor. Typically stateless.

type BayesScorer 

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

BayesScorer is a type of ScorerBuilder that assumes that the utility of the action is 1, but it only succeeds probabilistically. It has some general chance at success, such as 1 success per 4 failures. It also has a set of things which alter its odds of success based on the world, such as "succeeds twice as often when Y is researched" in order to produce the final probability of succeeds.

func (BayesScorer) Build 

func (s BayesScorer) Build() Scorer

type CooldownQualifiedScoredAction added in v0.2.0 

type CooldownQualifiedScoredAction struct {
	ScoredAction ScoredActionBuilder

	MinCooldown time.Duration
	MaxCooldown time.Duration

	CooldownSuppressedOnSuccess bool
	CooldownSuppressedOnFailure bool
}

CooldownQualifiedScoredAction creates a dependency between the scorer and action provided. Specifically, the Score is set to 0 if it's been less than the MinCooldown since the Action completed, it is scaled linearly between 0 and 1 between the MinCooldown and MaxCooldown, and it is unmodified past the MaxCooldown.

func (CooldownQualifiedScoredAction) Build added in v0.2.0 

func (b CooldownQualifiedScoredAction) Build() ScoredAction

type FixedScorer 

type FixedScorer struct {
	// Score is the score that the fixed scorer returns for all actors
	// at all times in all worlds
	Score float64
}

FixedScorer is the simplest type of scorer which always returns the same value

func (FixedScorer) Build 

func (s FixedScorer) Build() Scorer

Build implements ScorerBuilder

type IdleAction added in v0.1.2 

type IdleAction struct {
	// MinDuration is the minimum duration to idle for.
	MinDuration time.Duration

	// MaxDuration is the maximum duration to idle for.
	MaxDuration time.Duration
}

IdleAction idles for a random amount of time selected uniformly between the min and max duration.

func (IdleAction) Build added in v0.1.2 

func (b IdleAction) Build() Action

type InverterQualifier added in v0.2.7 

type InverterQualifier struct {
	// Scorer is the scorer to invert
	Scorer ScorerBuilder
}

InverterQualifier inverts the score of the child, i.e., returns 1 - Scorer.Score()

func (InverterQualifier) Build added in v0.2.7 

func (b InverterQualifier) Build() Scorer

type MultCombineQualifier added in v0.2.7 

type MultCombineQualifier struct {
	// Children are the children the score is built from
	Children []ScorerBuilder
}

MultCombineQualifier produces a score from the children by multiplying their scores together.

func (MultCombineQualifier) Build added in v0.2.7 

func (b MultCombineQualifier) Build() Scorer

type ScoredAction 

type ScoredAction struct {
	Action Action
	Scorer Scorer
}

ScoredAction is a convenience struct for describing an Action and a Score. This is typically only used within actual Actions, - for nesting ActionBuilder's use ScoredActionBuilder

type ScoredActionBuilder 

type ScoredActionBuilder interface {
	Build() ScoredAction
}

ScoredActionBuilder builds pairs of actions and scores. If the action and scorer are independent then the obvious implementation is done via ScorerBuilderAndActionBuilder. For example, when the Scorer is a fixed scorer, then the action and scorer are independent, i.e., you can build the action without building the scorer. If the Scorer is a cooldown scorer, where the cooldown starts when the action finishes, then the Scorer is not independent of the Action and hence they must be built in tandem.

type Scorer 

type Scorer interface {
	// Attached is called once when the Scorer is first attached to the AI to
	// let it know which world it is operating in and the actor which the scorer
	// is determining the utility of the action for. It should store these with
	// a stricter type.
	Attached(world, actor interface{})

	// Score returns the current measure, typically a 0-1 value where 0 is the
	// least valuable and 1 is the most valuable.
	Score() float64
}

A Scorer is something which is capable of producing a measure of utility for something. There is one instance per actor in the world and it is assumed to be stateful.

type ScorerBuilder 

type ScorerBuilder interface {
	// Build a new scorer and return it so it may be attached
	Build() Scorer
}

ScorerBuilder builds Scorer's

func NewBayesScorer 

func NewBayesScorer(prior *big.Rat, factors []BayesFactorBuilder) ScorerBuilder

NewBayesScorer produces a ScorerBuilder that has a score of 1 on the action, but the action only succeeds probabilistically. The estimate of the odds of success is prior. Note that prior should NOT be interpreted as a fraction, e.g., 3/5. Instead, it's interpreted such that the numerator is the number of successes and the denominator is the number of failures. so "3/9" should be interpreted as 3 successes to 9 failures. A "1/1" prior means 1 success to 1 failure, aka a 50% chance of success.

func NewFactorQualifier 

func NewFactorQualifier(factor float64, scorer ScorerBuilder) ScorerBuilder

NewFactorQualifier creates a new Qualifier that qualifies the score of the child by multiplying it by the given factor.

type ScorerBuilderAndActionBuilder added in v0.2.0 

type ScorerBuilderAndActionBuilder struct {
	// Action builds actions
	Action ActionBuilder

	// Scorer builds scorers
	Scorer ScorerBuilder
}

ScorerBuilderAndActionBuilder merges a scorer and an action. The scorer and action might not be independent.

func (ScorerBuilderAndActionBuilder) Build added in v0.2.0 

func (b ScorerBuilderAndActionBuilder) Build() ScoredAction

Build implements ScoredActionBuilder but only works if the action and scorer are independent. Hence when receiving a ScorerBuilderAndActionBuilder as that type this function should not be called, but this allows receiving a ScorerBuilderAndActionBuilder type asserted as a ScoredActionBuilder, which is convenenient if you want to make a ScoredActionBuilder with an independent Scorer and Action.

type Thinker 

type Thinker interface {
	// Select the index of the child which should be exected from the given
	// slice of scored actions.
	Select(children []ScoredAction) int
}

Thinker describes the standard Thinker interface which can be wrapped with NewThinkerBuilder to produce an ActionBuilder.

Note that when we use the word "Thinker" in this package we are almost never referring to this interface. We are simply referring to any ActionBuilder which selects which ActionBuilder to delegate to based on its score. The most common way to implement that concept of Thinker is by implementing this interface and using NewThinkerBuilder as the constructor for the ActionBuilder.

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.