Transcript Using Abstract State Machines in Artificial Intelligence and Games

What´s the name of the game?
Formal Specification of
Artificial Intelligence Games
Vladimir O. Di Iorio
Eliseu C. Miguel
Alcione P. Oliveira
Universidade Federal
de Viçosa - Brasil
Roberto S. Bigonha
Mariza A. S. Bigonha
Universidade Federal
de Minas Gerais - Brasil
Introduction

Abstract State Machines (ASM):




formal method created by Yuri Gurevich (1994);
specification of algorithms at its natural level of
abstraction.
Artificial Intelligence (AI) games: interesting
tool for teaching artificial intelligence
techniques.
This work presents a framework for the
specification of AI games using ASM.
Games and Artificial Intelligence

Agents:



perceive the environment through sensors;
execute actions upon the environment.
Multi-agent games:


agents interact following predefined rules (the
rules of the game);
agents are usually called bots.
Extensible Artificial Intelligence



Games with extensible AI: it is possible for
the user to define the behaviour of bots.
Competitors are supposed to write the best
code for a bot, to fight against other bots.
Examples:



Half-life (bot kit using C++);
AI Wars (proprietary language);
Gamebots (bots defined with Java, using the
game Unreal Tournament).
Snapshot of Gamebots
A General Multi-Agent AI Game
A General Multi-Agent AI Game
A, B, C : internal bots
A General Multi-Agent AI Game
E, F : user bots
A General Multi-Agent AI Game
D : internal bot that produces visualization
Framework for AI Games using ASM

Definition of new games:



Definition of user bots:



description of the rules using ASM;
advantage: clear semantics of the rules.
using ASM itself; or
using C++.
Graphical representation with animation:
using free graphical library Clanlib.
Example - the Snake Game



Snakes grow one
cell when they "eat"
a "vitamin".
Snakes shrink when
other snakes "eat"
their tail.
Goal: grow up to N
cells.
The Snake Game using the Framework

Definition of the rules of the game:




write an ASM specification for the rules (how
snakes move, when snakes grow and shrink);
the specification must prevent user bots from
"cheating" (snakes must follow the rules for
movement).
Definition of the behaviour of user bots: write
code to move the snakes (in ASM or C++).
Define graphical representation using Clanlib.
The Snake Game using the Framework
A
C
B
D
user bots:
Y
R
B
Output Device
Abstract State Machines




States are represented by functions over a
superuniverse;
An execution is a sequence of states.
Each state is produced by the application of
transition rules over the previous state.
Main transition rules:



function update
conditional rule
block rule
Example - State represented by functions
size :: Color  Int
size (yellow) = 4
size (red) = 5
size (blue) = 3
cell :: (Color X Int)  (Int X Int)
cell (yellow,1) = (9,3)
cell (yellow,2) = (8,3)
cell (yellow,3) = (7,3)
cell (yellow,4) = (7,2)
cell (red,1) = (12,9)
...
ASM Rules

Update rule:

Sintax:
function (list_expr) := expr

Semantics:



the function is updated at the location defined by
the value of the expressions;
the change is visible only in the next step of the
exectution.
Example:
size(yellow) := size(yellow) + 1
ASM Rules

Conditional rule:

Sintax:
if condition then R1 else R2

Semantics:


if the condition is evaluated to True, rule R1 is fired;
otherwise, rule R2 is fired.
Example:
if size(yellow) < max then
size(yellow) := size(yellow) + 1
else ...
ASM Rules

Block Rule:

Sintax:
R1, R2, ..., Rk

Semantics:


The rules R1,..., Rk are fired in paralel.
Example:
a := b,
b := a
 exchange values of a and b
ASM Rules

Other Rules (rules with variables):




forall rule;
choose rule;
let rule;
etc.
Machina - an ASM-Based Language



Machina: language based in ASM, developed
in the PL Lab., DCC/UFMG.
Semantics follows main ASM definitions.
Includes primitives for definition of:



modules (separated definitions);
visibility of objetcs.
A compiler from Machina to C++ is available.
Machina - Modules


In Machina, a module is the main syntax unit.
Definitions inside a module:




ASM functions;
transition rules;
visibility of the functions.
To actually execute ASM code, it is necessary
to instantiate an agent using a module
definition.
Example: Transition Rule for Snake Game
let
p = newPosition(getHead(self), getDirection(self))
in
if insideLimits(p) then
tryMoveTo(p)
else
shrink(self)
end
end
Example: Transition Rule for Snake Game
let
p = newPosition(getHead(self), getDirection(self));
in
if insideLimits(p) then
tryMoveTo(p)
else
shrink(self)
end
self is always interpreted as
end
a reference to the current agent
Example: Transition Rule for Snake Game
let
p = newPosition(getHead(self), getDirection(self));
in
if insideLimits(p) then
tryMoveTo(p)
else
The snake tries to move to the direction
shrink(self)
specified by function getDirection.
end
This function will be updated
end
by each snake bot.
Example: Transition Rule for Snake Game
let
p = newPosition(getHead(self), getDirection(self));
in
if insideLimits(p) then
tryMoveTo(p)
else
shrink(self)
end
end
actions are abstractions
for ASM rules
Example: Action tryMoveTo
tryMoveTo (p) :=
if p = vitaminPos then
growToPosition(self,p), defNewVitaminPos
elseif isFreeOfSnakes(p) then
moveToPosition(self,p)
elseif isSnakeTail(p) then
forall s in setOfSnakes do
if getTail(s) = p then shrink(s) end
end,
growToPosition(self,p)
else
shrink(self)
end
end;
Controlling Concurrent Execution
A
C
B
D
user bots:
Y
R
B
Output Device
Controlling Concurrent Execution
A
C
B
•Y, R, B can execute at any time;
•A, B, C cannot execute in
parallel;
•A, B, C should execute "fairly";
•D should be executed after
each execution of A, B or C.
D
user bots:
Y
R
B
Output Device
Controlling Concurrent Execution
A
C
B
•Y, R, B can execute at any time;
•A, B, C cannot execute in
parallel;
•A, B, C should execute "fairly";
•D should be executed after
each execution of A, B or C.
D
user bots:
Y
R
B
Output Device
Everything can be specified
by ASM rules!
Conclusions



Simple AI games developed with our
framework have been used in AI classes for
undergraduate students.
In general, students have considered the
rules of the games very easy to understand thanks to the use of the ASM model.
The students have extra motivation to learn
AI techniques, in order to win the bot
competitions.
Future Work


Develop more sophisticated games; e.g.:
virtual versions of sport games as soccer.
Develop 3D games with animated graphic
visualization.