Difference between revisions of "Offline BeepBeep 3 Benchmark1"

From CRV
Jump to: navigation, search
Line 37: Line 37:
 
IDs are unique within each individual <code>message</code> element, but obviously, they repeat from one event to the next. Some Pingus, however, may disappear at some point in the trace if they die, so the number of <code>character</code> elements is not fixed for the entire trace. Within each <code>message</code>, IDs do not appear in any particular order: this depends on the iterator on game elements provided by the game itself. We cannot assume either that IDs start at 0 or that they form a continuous sequence.
 
IDs are unique within each individual <code>message</code> element, but obviously, they repeat from one event to the next. Some Pingus, however, may disappear at some point in the trace if they die, so the number of <code>character</code> elements is not fixed for the entire trace. Within each <code>message</code>, IDs do not appear in any particular order: this depends on the iterator on game elements provided by the game itself. We cannot assume either that IDs start at 0 or that they form a continuous sequence.
  
Since Pingus' game loop runs at about 160 Hz, <code>message</code> elements correspond to snapshots of the game's state roughly 0.08 seconds apart. Therefore, processing the trace in real time requires handling at least that many events per second.
+
Since Pingus' game loop runs at about 160 Hz, <code>message</code> elements correspond to snapshots of the game's state roughly 0.006 seconds apart. Therefore, processing the trace in real time requires handling at least that many events per second.
  
 
=== The Property Part ===
 
=== The Property Part ===
  
See the rules for the necessary descriptions of what should be included in the following sections
+
The paper on Pingus (see link at top of the page) describes many properties one can verify on the execution of the game. For the purpose of this benchmark, we picked three of them.
  
==== Informal Description ====
+
==== Property 1 ====
  
==== Demonstration Traces ====
+
===== Informal Description =====
  
==== Formal Specification ====
+
This property reads as follows: "From one event to the next, Pingus can only disappear from the game field; no Pingu can be created mid-game."
  
==== A FO-LTL Specification ====
+
===== Demonstration Traces =====
 +
 
 +
Here are two counter-examples of this property (for the sake of clarity, we only list IDs occurring in each event):
 +
 
 +
<nowiki>
 +
  {0,1,2}, {0,1,2,4}
 +
  {0,1,2}, {0,1,3}
 +
</nowiki>
 +
 
 +
Here are two examples of this property (for the sake of clarity, we only list IDs occurring in each event):
 +
 
 +
<nowiki>
 +
  {0,1,2}, {0,1,2}, {0,1,2}
 +
  {0,1,2}, {0,2}, {0,2}, {0}
 +
</nowiki>
 +
 
 +
===== Formal Specification =====
 +
 
 +
This property can be checked in multiple ways. For example, in past-time first-order LTL:
 +
 
 +
<nowiki><b>G</b> (&forall; x ∊ id : <b>Y</b> (&exists; y ∊ id : x = y))</nowiki>
 +
 
 +
===== A FO-LTL Specification =====
  
 
== Clarification Requests ==
 
== Clarification Requests ==
  
 
This is a space where other teams can ask for clarifications and the submitting team can answer. When a team requests a clarification, the team should be mentioned in the request and the request timestamped. The team submitting the benchmark should ensure they watch this page so that they get notifications of questions.
 
This is a space where other teams can ask for clarifications and the submitting team can answer. When a team requests a clarification, the team should be mentioned in the request and the request timestamped. The team submitting the benchmark should ensure they watch this page so that they get notifications of questions.

Revision as of 08:49, 28 May 2016

Name of benchmark Synthetic execution traces of the video game Pingus, used for runtime verification. All details regarding these traces can be found in the paper Automated Bug Finding in Video Games: A Case Study for Runtime Monitoring. We highly recommend you scan that paper first.

List of categories

Benchmark Data

Pingus is a clone of Psygnosis’ Lemmings game series made by Ingo Ruhnke. It regularly counts among the highest quality open source games available and was once ranked in the Top 10 Linux games by CNN. The game is divided into more than 70 levels, each of which being populated with various kinds of obstacles, walls, and gaps. Between 10 and 100 autonomous, penguin-like characters (the Pingus) progressively enter the level from a trapdoor and start walking across the area. A Pingu keeps walking in the same direction until it either reaches a wall (in which case it turns around) or falls into a gap (and dies, if it falls from too high).

The goal of the game is to have a minimum percentage of the incoming Pingus safely reach the exit door. To this end, the player can give special abilities to certain Pingus, allowing them to modify the landscape in order to create a walkable path to the goal. For example, some Pingus can become Bashers and dig into the ground; others can become Builders and construct a staircase to reach over a gap. Other abilities modify the behaviour of other Pingus: hence the Blocker stands in the way and makes any Pingu that reaches it turn around as if it encountered a wall.

The Trace Part

The dataset is made of 20 traces consisting of a simulated execution of the game; each of these traces contains from 5 to 95 Pingus walking in the game field at the same time. You can download the trace files from DataHub (click on the button "Go to resource").

All traces are in XML format. Each event of the trace has the following structure:

<message>
 <characters>
  <character>
   <id>0</id>
   <status>WALKER</status>
   <position>
    <x>62</x>
    <y>0</y>
   </position>
   <velocity>
    <x>1</x>
    <y>0</y>
   </velocity>
  </character>
  ...
 </characters>
</message>

The event is contained in a message element, which contains a single characters element. Within this element, there are multiple character elements, corresponding to the properties of a single Pingu on the game field. Each Pingu has a unique ID, a position (x-y) and a velocity vector (x-y). In addition, each Pingu has a status, which can be "walker" (normal state), or any of these special abilities: "blocker", "floater", "basher", "blower", "faller".

IDs are unique within each individual message element, but obviously, they repeat from one event to the next. Some Pingus, however, may disappear at some point in the trace if they die, so the number of character elements is not fixed for the entire trace. Within each message, IDs do not appear in any particular order: this depends on the iterator on game elements provided by the game itself. We cannot assume either that IDs start at 0 or that they form a continuous sequence.

Since Pingus' game loop runs at about 160 Hz, message elements correspond to snapshots of the game's state roughly 0.006 seconds apart. Therefore, processing the trace in real time requires handling at least that many events per second.

The Property Part

The paper on Pingus (see link at top of the page) describes many properties one can verify on the execution of the game. For the purpose of this benchmark, we picked three of them.

Property 1

Informal Description

This property reads as follows: "From one event to the next, Pingus can only disappear from the game field; no Pingu can be created mid-game."

Demonstration Traces

Here are two counter-examples of this property (for the sake of clarity, we only list IDs occurring in each event):

  {0,1,2}, {0,1,2,4}
  {0,1,2}, {0,1,3}

Here are two examples of this property (for the sake of clarity, we only list IDs occurring in each event):

  {0,1,2}, {0,1,2}, {0,1,2}
  {0,1,2}, {0,2}, {0,2}, {0}

Formal Specification

This property can be checked in multiple ways. For example, in past-time first-order LTL:

<b>G</b> (∀ x ∊ id : <b>Y</b> (&exists; y ∊ id : x = y))

A FO-LTL Specification

Clarification Requests

This is a space where other teams can ask for clarifications and the submitting team can answer. When a team requests a clarification, the team should be mentioned in the request and the request timestamped. The team submitting the benchmark should ensure they watch this page so that they get notifications of questions.