1
§6 Decision
§6 Decision- -Making Making
decisiondecision-- making and gamesmaking and games
levels of decision-levels of decision-makingmaking
modelled knowledgemodelled knowledge
methodmethod
example methodsexample methods
finite state machinesfinite state machines
flocking algorithmsflocking algorithms
influence mapsinfluence maps
this will not be a comprehensive guide into decisionthis will not be a comprehensive guide into decision-- making!
making!
MVC (revisited) MVC (revisited)
control logic
driver
proto-view
rendering state instance core structures
input device
action configuration
instance data
synthetic view synthetic
player
script output
device human player
options perception
model
view controller
AI system AI system
World recognitionPattern Observed events Observed events
and states and states
Decision- making system Requested
Requested actions actions
Possible actions Possible actions Primitive events Primitive events
and states and states
Previous primitives
Three perspectives for decision Three perspectives for decision- -
making in computer games making in computer games
level of decision- level of decision -making making
strategic, tactical, operationalstrategic, tactical, operational
use of the modelled knowledge use of the modelled knowledge
prediction, productionprediction, production
methods methods
optimization, adaptationoptimization, adaptation
Level of decision
Level of decision- -making making
strategic strategic
what should be donewhat should be done
tactical tactical
how to actuate ithow to actuate it
operational operational
how to carry it outhow to carry it out
Strategic level Strategic level
long- long -term decisions term decisions
infrequent → can be computed offline or in the infrequent → can be computed offline or in the background
background
large amount of data, which is filtered to bring large amount of data, which is filtered to bring forth the essentials
forth the essentials
quantization problem?quantization problem?
speculative (what- speculative (what -if scenarios) if scenarios)
the cost of a wrong decision is high the cost of a wrong decision is high
2 Tactical level
Tactical level
medium medium- -term decisions term decisions
intermediary between strategic and operational intermediary between strategic and operational levels
levels
follow the plan made on the strategic levelfollow the plan made on the strategic level
convey the feedback from the operational levelconvey the feedback from the operational level
considers a group of entities considers a group of entities
a selected set of data to be scrutinized a selected set of data to be scrutinized
coco-- operation within the groupoperation within the group
Operational level Operational level
short- short -term decisions term decisions
reactive, realreactive, real-- time responsetime response
concrete and closely connected to the game concrete and closely connected to the game world
world
considers individual entities considers individual entities
the cost of a wrong decision is relatively low the cost of a wrong decision is relatively low
of course not to the entity itselfof course not to the entity itself
Use of the modelled knowledge Use of the modelled knowledge
time series data time series data
world = a generator of events and states, which world = a generator of events and states, which can be labelled with symbols
can be labelled with symbols
prediction prediction
what the generator will produce next?what the generator will produce next?
production production
simulating the output of the generatorsimulating the output of the generator
how to cope with uncertainty? how to cope with uncertainty?
Prediction Prediction
Modeller
maximum probability
Generator
Production Production
Modeller
random selection from
probability distribution
Methods: Optimization Methods: Optimization
elements: elements:
objective function to be maximized/minimizedobjective function to be maximized/minimized
variables affecting the value of the objective functionvariables affecting the value of the objective function
constraints limiting feasible variable valuesconstraints limiting feasible variable values
goal: find among the feasible solutions the one goal: find among the feasible solutions the one that gives an optimum value for the objective that gives an optimum value for the objective function
function
time consuming? time consuming?
→ heuristic rules to guide the search
→ heuristic rules to guide the search
3 Methods: Optimization (cont’d)
Methods: Optimization (cont’d)
hill hill- -climbing climbing
how to escape local optima?how to escape local optima?
tabu search tabu search
simulated annealing simulated annealing
genetic algorithms genetic algorithms
multiple search tracesmultiple search traces
swarm algorithms swarm algorithms
Methods: Adaptation Methods: Adaptation
ability to make appropriate responses to ability to make appropriate responses to changed circumstances → learning changed circumstances → learning
searches for a function behind given solutions searches for a function behind given solutions
optimization: solution for a given functionoptimization: solution for a given function
affecting factors are unknown or dynamicaffecting factors are unknown or dynamic
pattern recognition pattern recognition
Methods: Adaptation (cont’d) Methods: Adaptation (cont’d)
neural networks neural networks
training training
supervised learningsupervised learning
unsupervised learning (e.g., selfunsupervised learning (e.g., self--organizing maps)organizing maps)
executionexecution
hidden Markov model hidden Markov model
recurring structuresrecurring structures
Soft computing Soft computing
L. Zadeh: methodologies that try to solve problems L. Zadeh: methodologies that try to solve problems arising from the complexity of the natural world arising from the complexity of the natural world
approximationapproximation
partial truthpartial truth
imprecisionimprecision
uncertaintyuncertainty
computer games have used ‘hard’ computingcomputer games have used ‘hard’ computing
as the game worlds get more complex, perhaps soft as the game worlds get more complex, perhaps soft computing methods would suit better
computing methods would suit better
Soft computing methods Soft computing methods
probabilistic reasoning probabilistic reasoning
genetic algorithmsgenetic algorithms
Bayesian networksBayesian networks
artificial neural networks artificial neural networks
backback-- propagation networkspropagation networks
selfself-- organizing mapsorganizing maps
fuzzy logic fuzzy logic
fuzzy setsfuzzy sets
approximate reasoningapproximate reasoning
Finite state machine (FSM) Finite state machine (FSM)
components: components:
statesstates
transitionstransitions
eventsevents
actionsactions
state chart: fully connected directed graph state chart: fully connected directed graph
vertices = statesvertices = states
edges = transitionsedges = transitions
4 Properties of FSM
Properties of FSM
1.
1.
acceptor acceptor
does the input sequence fulfil given criteria?does the input sequence fulfil given criteria?
2.2.
transducer transducer
what is the corresponding output sequence for a what is the corresponding output sequence for a given input sequence?
given input sequence?
3.
3.
computator computator
what is the sequence of actions for a given input what is the sequence of actions for a given input sequence?
sequence?
these properties are independent! these properties are independent!
Mealy and Moore machines Mealy and Moore machines
theoretical cathegories for FSMstheoretical cathegories for FSMs
Mealy machineMealy machine
actions are in transitionsactions are in transitions
the next action is determined by the current state and the the next action is determined by the current state and the occurring event
occurring event
more compact but harder to comprehendmore compact but harder to comprehend
Moore machineMoore machine
actions are in statesactions are in states
the next action is determined by the next statethe next action is determined by the next state
helps to understand and use state machines in UMLhelps to understand and use state machines in UML
Implementation Implementation
design by contract design by contract
two parties: the supplier and the clienttwo parties: the supplier and the client
formal agreement using interfacesformal agreement using interfaces
FSM software components FSM software components
environment: view to the FSM (client)environment: view to the FSM (client)
context: handles the dynamic aspects of the FSM context: handles the dynamic aspects of the FSM (supplier)
(supplier)
structure: maintains the representation of the FSM structure: maintains the representation of the FSM (supplier)
(supplier)
Noteworthy Noteworthy
structure is staticstructure is static
hard to modifyhard to modify
reactivityreactivity
memoryless representation of all possible walks from the memoryless representation of all possible walks from the initial state
initial state
states are mutually exclusive: one state at a timestates are mutually exclusive: one state at a time
not for continuous or multivalued valuesnot for continuous or multivalued values
combinatorial explosion combinatorial explosion
if the states and events are independentif the states and events are independent
risk of total rewritingrisk of total rewriting
high cohesion of actionshigh cohesion of actions
