[Toss-devel-svn] SF.net SVN: toss:[1354] trunk/Toss
Status: Beta
Brought to you by:
lukaszkaiser
Menu
▾
▴
[Toss-devel-svn] SF.net SVN: toss:[1354] trunk/Toss
|
From: <luk...@us...> - 2011-03-12 17:52:00
|
Revision: 1354
http://toss.svn.sourceforge.net/toss/?rev=1354&view=rev
Author: lukaszkaiser
Date: 2011-03-12 17:51:51 +0000 (Sat, 12 Mar 2011)
Log Message:
-----------
Website corrections, debug ocamldoc.
Modified Paths:
--------------
trunk/Toss/Arena/Term.mli
trunk/Toss/Formula/Formula.mli
trunk/Toss/Makefile
trunk/Toss/Play/GameTree.mli
trunk/Toss/Play/Play.mli
trunk/Toss/Toss.odocl
trunk/Toss/www/.cvsignore
trunk/Toss/www/Makefile
trunk/Toss/www/contact.xml
trunk/Toss/www/create.xml
trunk/Toss/www/docs.xml
trunk/Toss/www/gui_interface.xml
trunk/Toss/www/ideas.xml
trunk/Toss/www/index.xml
trunk/Toss/www/navigation.xml
trunk/Toss/www/play.xml
trunk/Toss/www/xsl/include/common.xsl
Added Paths:
-----------
trunk/Toss/www/reference/
trunk/Toss/www/reference/.cvsignore
trunk/Toss/www/reference/Makefile
trunk/Toss/www/reference/reference.bib
trunk/Toss/www/reference/reference.tex
Removed Paths:
-------------
trunk/Toss/www/reference.bib
trunk/Toss/www/reference.tex
Property Changed:
----------------
trunk/Toss/www/
Modified: trunk/Toss/Arena/Term.mli
===================================================================
--- trunk/Toss/Arena/Term.mli 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Arena/Term.mli 2011-03-12 17:51:51 UTC (rev 1354)
@@ -76,7 +76,7 @@
eq_sys -> eq_sys
-(** {2 Runge-Kutta Method for Term Equations *)
+(** {2 Runge-Kutta Method for Term Equations} *)
(** Perform a Runge-Kutta (RK4) step for [vars] with [vals_init] and right-hand
Modified: trunk/Toss/Formula/Formula.mli
===================================================================
--- trunk/Toss/Formula/Formula.mli 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Formula/Formula.mli 2011-03-12 17:51:51 UTC (rev 1354)
@@ -52,6 +52,8 @@
| Or of formula list
| Ex of var list * formula
| All of var list * formula
+
+(** Real-valued terms allow counting, characteristic functions and arithmetic. *)
and real_expr =
RVar of string
| Const of float
@@ -61,6 +63,7 @@
| Char of formula
| Sum of fo_var list * formula * real_expr
+
val pow : real_expr -> int -> real_expr
val size : ?acc : int -> formula -> int
Modified: trunk/Toss/Makefile
===================================================================
--- trunk/Toss/Makefile 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Makefile 2011-03-12 17:51:51 UTC (rev 1354)
@@ -46,10 +46,12 @@
OCB_CFLAG=-cflags -I,+oUnit,-g
OCB_LIB=-libs str,nums,unix,oUnit
OCB_PP=-pp "camlp4o ../caml_extensions/pa_let_try.cmo ../caml_extensions/pa_backtrace.cmo"
-OCAMLBUILD=ocamlbuild -j 8 -menhir ../menhir_conf $(OCB_PP) \
+OCAMLBUILD=ocamlbuild -log build.log -j 8 -menhir ../menhir_conf $(OCB_PP) \
$(OCB_LIB) $(OCB_CFLAG) $(OCB_LFLAG)
-OCAMLBUILDBT=ocamlbuild -j 8 menhir ../menhir_conf $(OCB_PP) \
+OCAMLBUILDBT=ocamlbuild -log build.log -j 8 menhir ../menhir_conf $(OCB_PP) \
$(OCB_LIB) $(OCB_CFLAG) $(OCB_LFLAGBT)
+OCAMLBUILDNOPP=ocamlbuild -log build.log -j 8 -menhir ../menhir_conf \
+ $(OCB_LIB) $(OCB_CFLAG) $(OCB_LFLAG)
FormulaINC=Formula/Sat
SolverINC=Formula,Formula/Sat,Solver/RealQuantElim
@@ -76,7 +78,8 @@
doc: Formula/Sat/minisat/SatSolver.o Formula/Sat/minisat/MiniSATWrap.o \
caml_extensions/pa_let_try.cmo caml_extensions/pa_backtrace.cmo
- $(OCAMLBUILD) -Is $(.INC) Toss.docdir/index.html
+ $(OCAMLBUILDNOPP) -Is +oUnit,$(.INC) Toss.docdir/index.html
+ make -C www code_doc_link
# ---------- TESTS --------
Modified: trunk/Toss/Play/GameTree.mli
===================================================================
--- trunk/Toss/Play/GameTree.mli 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Play/GameTree.mli 2011-03-12 17:51:51 UTC (rev 1354)
@@ -2,6 +2,8 @@
val set_debug_level : int -> unit
+(** {2 Abstract Game Trees} *)
+
(** Abstract game tree, just stores state and move information. *)
type ('a, 'b) abstract_game_tree =
| Terminal of Arena.game_state * int * 'b (** terminal state with player *)
@@ -42,7 +44,7 @@
-(** -------------- TREES WITH PAYOFF AND HEURISTIC DATA --------------- *)
+(** {2 Trees with Payoff and Heuristic Data} *)
(** How to exchange payoffs for heuristics. *)
val cPAYOFF_AS_HEUR : float ref
Modified: trunk/Toss/Play/Play.mli
===================================================================
--- trunk/Toss/Play/Play.mli 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Play/Play.mli 2011-03-12 17:51:51 UTC (rev 1354)
@@ -6,7 +6,7 @@
val cancel_timeout : unit -> unit
-(** ------------ MAXIMAX BY DEPTH ------------- *)
+(** {2 Maximax by depth} *)
(** Maximax by depth unfolding function. Throws Not_found if ready. *)
val unfold_maximax : ?ab:bool -> Arena.game -> Formula.real_expr array array ->
Modified: trunk/Toss/Toss.odocl
===================================================================
--- trunk/Toss/Toss.odocl 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/Toss.odocl 2011-03-12 17:51:51 UTC (rev 1354)
@@ -1,16 +1,27 @@
Formula/Formula
+Formula/FormulaParser
Formula/BoolFormula
Formula/FFTNF
Formula/FormulaOps
Solver/Structure
+Solver/StructureParser
Solver/AssignmentSet
Solver/Assignments
-Solver/FFSolver
Solver/Solver
Solver/Class
+Solver/ClassParser
Arena/Term
+Arena/TermParser
Arena/DiscreteRule
+Arena/DiscreteRuleParser
Arena/ContinuousRule
+Arena/ContinuousRuleParser
Arena/Arena
+Arena/ArenaParser
Play/Heuristic
+Play/Move
+Play/GameTree
+Play/Play
Play/Game
+GGP/GDL
+GGP/GDLParser
\ No newline at end of file
Property changes on: trunk/Toss/www
___________________________________________________________________
Modified: svn:ignore
- # We are still using .cvsignore files as we find them easier to manage
# than svn properties. Therefore if you change .cvsignore do the following.
# svn propset svn:ignore -F .cvsignore .
*.html
*.html.de
*.html.en
*.texml
*.xml.de
*.xml.en
reference.xml
reference.pdf
*.ps
*.dvi
*.aux
*.out
*.log
*.bbl
*.blg
*.idx
*.thm
*.snm
*.nav
*.toc
*.flc
*~
+ # We are still using .cvsignore files as we find them easier to manage
# than svn properties. Therefore if you change .cvsignore do the following.
# svn propset svn:ignore -F .cvsignore .
*.html
*.html.de
*.html.en
*.texml
*.xml.de
*.xml.en
reference.xml
code_doc
*.ps
*.dvi
*.aux
*.out
*.log
*.bbl
*.blg
*.idx
*.thm
*.snm
*.nav
*.toc
*.flc
*~
Modified: trunk/Toss/www/.cvsignore
===================================================================
--- trunk/Toss/www/.cvsignore 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/.cvsignore 2011-03-12 17:51:51 UTC (rev 1354)
@@ -9,7 +9,7 @@
*.xml.de
*.xml.en
reference.xml
-reference.pdf
+code_doc
*.ps
*.dvi
*.aux
Modified: trunk/Toss/www/Makefile
===================================================================
--- trunk/Toss/www/Makefile 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/Makefile 2011-03-12 17:51:51 UTC (rev 1354)
@@ -1,3 +1,8 @@
TOPDIR = .
include $(TOPDIR)/default.mak
+
+code_doc_link:
+ ln -fs ../Toss.docdir code_doc
+ cp code_doc/index.html code_doc/index.html.en
+ cp code_doc/index.html code_doc/index.html.de
Modified: trunk/Toss/www/contact.xml
===================================================================
--- trunk/Toss/www/contact.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/contact.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -15,7 +15,7 @@
<section title="Email">
<par>Toss is an open source project hosted by
<a href="http://sourceforge.net">SourceForge</a>
- and distributed under the BSD licence.</par>
+ and distributed under the BSD licence.<br/></par>
<par>Contact us by writing to:
<mailto address="tos...@li..."/>
</par>
Modified: trunk/Toss/www/create.xml
===================================================================
--- trunk/Toss/www/create.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/create.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -10,22 +10,53 @@
<link id="create" href="/create.html">Create</link>
</history>
- <section title="Create New Games" lang="en">
- <par>The <a href="http://vimeo.com/10110495">Toss Tutorial</a> below
+ <section title="Two Ways to Create a New Game">
+ <par>When you are done playing the games already defined in Toss, it's
+ time to start the real fun – create your own game!
+ There are two ways to create a game in Toss.</par>
+ <itemize>
+ <item>You can use the GUI to edit and create games</item>
+ <item>You can edit the .toss files directly</item>
+ </itemize>
+ If you plan to make small changes or an easy experiment, the GUI might
+ be the better option. For larger or completely new games, it is more
+ convenient to edit the files in your favourite text editor.
+ </section>
+
+ <section title="Creating Games in Toss GUI">
+ <par>To start the Toss GUI do the following.</par>
+ <itemize>
+ <item><em>Download</em> Toss from the
+ <a href="http://sourceforge.net/project/showfiles.php?group_id=115606">
+ Sourceforge Download Page</a>.</item>
+ <item><em>Run Toss</em> by clicking <em>Toss.py</em>.
+ You can start by opening a file from the <em>examples</em>
+ directory.</item>
+ </itemize>
+ <par>When you have the GUI running, we recommend that you watch the
+ <a href="http://vimeo.com/10110495">Toss Tutorial</a> below, which
shows all the steps needed to define a simple game in Toss and explains
- several other features. Alternatively, you can just take a look at our
- <a href="interface.php">Interface</a> page and play with the examples.
- </par>
- <toss-video/>
+ several other features. Alternatively, you can take a look at our
+ <a href="gui_interface.html">GUI interface</a> description page
+ and play with the examples.<br/></par>
+ <par><br/><toss-video/></par>
</section>
- <section title="Neue Spiele Erzeugen" lang="de">
- <par>The <a href="http://vimeo.com/10110495">Toss Tutorial</a> below
- shows all the steps needed to define a simple game in Toss and explains
- several other features. Alternatively, you can just take a look at our
- <a href="interface.php">Interface</a> page and play with the examples.
+ <section title="Creating Games in Text Editor" lang="en">
+ <par>For larger games, we find it easier to edit them in text
+ form than from the GUI. To understand the meaning of the fields
+ in the text file, you should probably first be acquainted with
+ Toss (e.g. go through the tutorial above) and at least skim through
+ the <a href="reference/reference.pdf">referece.pdf</a> file, look
+ at our <a href="docs.html">documentation</a>. After this, you can
+ simply edit the .toss file, maybe starting with one of these.
</par>
- <toss-video/>
+ <itemize>
+ <item><a href="http://toss.svn.sourceforge.net/viewvc/toss/trunk/Toss/examples/Breakthrough.toss?revision=1349">Breakthrough</a></item>
+ <item><a href="http://toss.svn.sourceforge.net/viewvc/toss/trunk/Toss/examples/Chess.toss?revision=1349">Chess</a></item>
+ <item><a href="http://toss.svn.sourceforge.net/viewvc/toss/trunk/Toss/examples/Tic-Tac-Toe.toss?revision=1349">Tic-Tac-Toe</a></item>
+ </itemize>
</section>
+
</personal>
Modified: trunk/Toss/www/docs.xml
===================================================================
--- trunk/Toss/www/docs.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/docs.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -10,24 +10,48 @@
<link id="docs" href="/docs.html">Documentation</link>
</history>
- <section title="Background">
+ <section title="Using Toss">
+ <par>If you want to learn how to use Toss to create games,
+ go to the <a href="create.html">Create Games</a> page
+ or just watch the video tutorial below to get started.<br/></par>
+ <par><br/><toss-video/></par>
+ </section>
+
+ <section title="Reference">
+ <par>The Toss Design and Specification reference is an evolving document
+ in which we try to describe the high-level mathematical model of Toss
+ and the main ideas used in the implementation. The document is best
+ viewed as <a href="reference/reference.pdf">reference.pdf</a> but
+ a <a href="reference/">html version</a> is available as well
+ for fast fact-checking.</par>
+ </section>
+
+ <section title="Code Documentation">
+ We generate <a href="code_doc/">documentation from code comments</a> using
+ <a href="http://caml.inria.fr/pub/docs/manual-ocaml/manual029.html">
+ ocamldoc</a>. It gives the most up-to date information on our code,
+ modules and their interfaces.
+ </section>
+
+ <section title="Scientific Background">
<par>To learn more about the mathematical background and
- the design of Toss, use the following links.</par>
+ the design of Toss, go to the <a href="Publications/">Papers
+ and Talks</a> page or use the following links.</par>
<itemize>
-<item><em>Compact description</em> of the mathematical model behind Toss and
-our game playing algorithm can be found in the paper
-<a href="http://logic.rwth-aachen.de/~kaiser/playing_structure_rewriting_games.pdf">Playing Structure Rewriting Games</a>.</item>
-
-<item><em>Design and specification</em> of Toss are described in
- the <a href="reference.pdf">reference.pdf</a> document.</item>
-
-<item> <em>Complexity</em> of a syntactic fragment of Toss was analyzed in
- the paper <a href="http://logic.rwth-aachen.de/~kaiser/graph_games_short.pdf">
- Synthesis for Structure Rewriting Systems</a>.</item>
-<item><em>Presentation</em> on the mathematics behind Toss was given at
- <em>IIT Kanpur</em> and can be
- <a href="http://www2.cse.iitk.ac.in/~fsttcs/2009/videos/star/LukaszKaiser.avi">
- watched</a> online.</item>
+ <item><em>Compact description</em> of the mathematical model behind
+ Toss and our game playing algorithm can be found in the paper
+ <a href="pub/playing_structure_rewriting_games.pdf">Playing
+ Structure Rewriting Games</a>.
+ </item>
+ <item> <em>Complexity</em> of a syntactic fragment of Toss was
+ analyzed in the paper <a href="pub/graph_games_short.pdf">
+ Synthesis for Structure Rewriting Systems</a>.
+ </item>
+ <item><em>Presentation</em> on the mathematics behind Toss was given at
+ <em>IIT Kanpur</em> and can be
+ <a href="http://www2.cse.iitk.ac.in/~fsttcs/2009/videos/star/LukaszKaiser.avi">
+ watched</a> online.
+ </item>
</itemize>
</section>
Modified: trunk/Toss/www/gui_interface.xml
===================================================================
--- trunk/Toss/www/gui_interface.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/gui_interface.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -11,19 +11,8 @@
<link id="examples" href="/examples.html">Examples</link>
</history>
- <section title="Running the Toss GUI">
- <itemize>
- <item><em>Download</em> Toss from the
- <a href="http://sourceforge.net/project/showfiles.php?group_id=115606">
- Sourceforge Download Page</a>.</item>
- <item><em>Run Toss</em> by clicking <em>Toss.py</em>.
- You can start by opening a file from the <em>examples</em>
- directory.</item>
- <item><em>Screenshots</em> of a few example games are
- given on the <a href="/examples.html">Examples</a> page.</item>
- </itemize>
- </section>
+
<section title="Changing Elements">
<itemize>
<item>
Modified: trunk/Toss/www/ideas.xml
===================================================================
--- trunk/Toss/www/ideas.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/ideas.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -71,14 +71,14 @@
<item>Go definition in Toss without Ko (medium)</item>
<item>Toss extension to handle repeated positions (medium)</item>
<item>Go definition with Ko (easy after 3)</item>
- <item>Adapting Heuristics, Minimax, UCT to play somehow (medium)</item>
+ <item>Adapting Minimax and UCT to play somehow (medium)</item>
<item>Optimizing the algorithms to play well (unknown)</item>
</enumerate>
<br/></par>
<par><em>Needed Skills and Difficulty.</em>
Good OCaml programming skills are required, and some general knowledge
- of game playing algorithms will be necessary. Between easy and medium,
- but can become very interesting and challenging in the last phase!
+ of game playing algorithms will be necessary. This is a medium difficulty
+ project, but it can become very interesting in the last phase!
<br/><br/></par>
<par><em>Possible Mentors (in order of preference):</em>
Łukasz Stafiniak, Łukasz Kaiser,
@@ -155,7 +155,7 @@
interface design is necessary, and a lot of testing to make it right.
<br/><br/></par>
<par><em>Possible Mentors (in order of preference):</em>
- Dietmar Berwanger, Michał Wójcik, Tobias Ganzow
+ Dietmar Berwanger, Michał Wójcik, Diana Fischer
</par>
</section>
@@ -189,8 +189,8 @@
<par><em>Needed Skills and Difficulty.</em>
This project is technical and requires very good understanding
of OCaml, the interface between OCaml and C, and the various factors
- which can influence performance. Some knowledge of databases and
- their optimization techniques can be helpful.
+ which can influence performance. Some knowledge of either databases and
+ their optimization techniques or constraint solving will be helpful.
<br/><br/></par>
<par><em>Possible Mentors (in order of preference):</em>
Tobias Ganzow, Łukasz Kaiser, Łukasz Stafiniak
@@ -226,10 +226,11 @@
</enumerate>
<br/></par>
<par><em>Needed Skills and Difficulty.</em>
- The GDL translation is not that hard in principle, but turns out to be
- quite tricky in practice. Good knowlede of OCaml is necessary, and some
- previous knowledge of GGP/GDL or Prolog would be good. But passsion
- for GGP is the best recommendation for this project!
+ Due to different design choices behind the GDL and Toss formalisms,
+ the translation is a complex task and it requires acquaintance with
+ concepts from logic programming. Good knowledge of OCaml is necessary of
+ course, but some previous knowledge of GGP/GDL or Prolog would be helpful.
+ Still, passion for GGP is the best recommendation for this project!
<br/><br/></par>
<par><em>Possible Mentors (in order of preference):</em>
Łukasz Stafiniak, Łukasz Kaiser, maybe someone from GGP Galaxy
Modified: trunk/Toss/www/index.xml
===================================================================
--- trunk/Toss/www/index.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/index.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -43,8 +43,8 @@
shows all the steps needed to define a simple game in Toss and explains
several other features. Alternatively, you can just take a look at our
<a href="interface.php">Interface</a> page and play with the examples.
- </par>
- <toss-video/>
+ <br/></par>
+ <par><br/><toss-video/></par>
</section>
<section title="Neue Spiele Erzeugen" lang="de">
@@ -52,8 +52,8 @@
shows all the steps needed to define a simple game in Toss and explains
several other features. Alternatively, you can just take a look at our
<a href="interface.php">Interface</a> page and play with the examples.
- </par>
- <toss-video/>
+ <br/></par>
+ <par><br/><toss-video/></par>
</section>
<section title="Features">
@@ -74,7 +74,7 @@
<item><em>Solver</em> in Toss is optimized: it does quantifier elimination and
formula decomposition (with <a href="http://minisat.se/">MiniSat</a>).</item>
<item><em>Move hints</em> are given in all games using our general
- game playing algorithm based on UCT.</item>
+ game playing algorithm based on UCT or Maximax.</item>
</itemize>
</section>
Modified: trunk/Toss/www/navigation.xml
===================================================================
--- trunk/Toss/www/navigation.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/navigation.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -15,7 +15,9 @@
</menu>
<item href="/play.html" id="play">Watch Toss Play</item>
<menu title="Documentation" href="/docs.html" id="docs">
- <item href="/background.html" id="background">Background</item>
+ <item href="/reference/reference.pdf" id="refpdf">Reference (pdf)</item>
+ <item href="/reference/" id="refhtml">Reference (html)</item>
+ <item href="/code_doc/" id="code">Code Documentation</item>
</menu>
<item href="/Publications/" id="Publications">Papers and Talks</item>
<item href="/contact.html" id="contact">Contact and Links</item>
Modified: trunk/Toss/www/play.xml
===================================================================
--- trunk/Toss/www/play.xml 2011-03-12 04:23:27 UTC (rev 1353)
+++ trunk/Toss/www/play.xml 2011-03-12 17:51:51 UTC (rev 1354)
@@ -10,8 +10,157 @@
<link id="play" href="/play.html">Toss Play</link>
</history>
- <section title="Watch Toss Play">
- <par>Here you can watch Toss play. Beware of Heuristics!</par>
+ <section title="General Game Playing">
+ <a href="http://en.wikipedia.org/wiki/General_Game_Playing">General
+ Game Playing</a>, GGP in short, is a name for the task of playing
+ a previously unknown game. GGP is currently a popular field of AI,
+ with people at <a href="http://games.stanford.edu/">Stanford</a>
+ and in <a href="http://www.general-game-playing.de/">Germany</a>
+ doing great work. Players which accept games in the GDL format can
+ play on the <a href="http://euklid.inf.tu-dresden.de:8180/ggpserver/">
+ Dresden GGP Server</a> and Toss recently started competing there as well.
+ Games in GDL format are not directly suited for online presentation, but
+ the <a href="http://code.google.com/p/ggp-galaxy/">GGP Galaxy Project</a>
+ has recently started to work on bringing them online – something
+ we already have for games in the Toss format. Below we show a few of
+ the games played by Toss against Fluxplayer on the Dresden Server.
</section>
+
+ <section title="Breakthrough Games">
+ <itemize>
+ <item><ggp-game match_id="breakthrough.1297045579170"
+ name="Breakthrough 1"/></item>
+ <item><ggp-game match_id="breakthrough.1297045589259"
+ name="Breakthrough 2"/></item>
+ <item><ggp-game match_id="breakthrough.1297173861071"
+ name="Breakthrough 3"/></item>
+ <item><ggp-game match_id="breakthrough.1297173869694"
+ name="Breakthrough 4"/></item>
+ <item><ggp-game match_id="breakthrough.1297173874334"
+ name="Breakthrough 5"/></item>
+ <item><ggp-game match_id="breakthrough.1297173876674"
+ name="Breakthrough 6"/></item>
+ <item><ggp-game match_id="breakthrough.1297173880713"
+ name="Breakthrough 7"/></item>
+ <item><ggp-game match_id="breakthrough.1297173884736"
+ name="Breakthrough 8"/></item>
+ <item><ggp-game match_id="breakthrough.1297173889956"
+ name="Breakthrough 9"/></item>
+ <item><ggp-game match_id="breakthrough.1297173895209"
+ name="Breakthrough 10"/></item>
+ <item><ggp-game match_id="breakthrough.1297190115986"
+ name="Breakthrough 11"/></item>
+ <item><ggp-game match_id="breakthrough.1297190121191"
+ name="Breakthrough 12"/></item>
+ <item><ggp-game match_id="breakthrough.1297190129741"
+ name="Breakthrough 13"/></item>
+ <item><ggp-game match_id="breakthrough.1297190137203"
+ name="Breakthrough 14"/></item>
+ <item><ggp-game match_id="breakthrough.1297190149280"
+ name="Breakthrough 15"/></item>
+ <item><ggp-game match_id="breakthrough.1297190159057"
+ name="Breakthrough 16"/></item>
+ <item><ggp-game match_id="breakthrough.1297190171807"
+ name="Breakthrough 17"/></item>
+ <item><ggp-game match_id="breakthrough.1297190182797"
+ name="Breakthrough 18"/></item>
+ <item><ggp-game match_id="breakthrough.1297204058168"
+ name="Breakthrough 19"/></item>
+ <item><ggp-game match_id="breakthrough.1297204063753"
+ name="Breakthrough 20"/></item>
+ </itemize>
+ </section>
+
+ <section title="Gomoku Games">
+ <itemize>
+ <item><ggp-game match_id="connect5.1297281103161"
+ name="Gomoku 1"/></item>
+ <item><ggp-game match_id="connect5.1297281122315"
+ name="Gomoku 2"/></item>
+ <item><ggp-game match_id="connect5.1297281150565"
+ name="Gomoku 3"/></item>
+ <item><ggp-game match_id="connect5.1297281152908"
+ name="Gomoku 4"/></item>
+ <item><ggp-game match_id="connect5.1297281195920"
+ name="Gomoku 5"/></item>
+ <item><ggp-game match_id="connect5.1297281206285"
+ name="Gomoku 6"/></item>
+ <item><ggp-game match_id="connect5.1297281221465"
+ name="Gomoku 7"/></item>
+ <item><ggp-game match_id="connect5.1297281224813"
+ name="Gomoku 8"/></item>
+ <item><ggp-game match_id="connect5.1297281227319"
+ name="Gomoku 9"/></item>
+ <item><ggp-game match_id="connect5.1297281243181"
+ name="Gomoku 10"/></item>
+ <item><ggp-game match_id="connect5.1297281310683"
+ name="Gomoku 11"/></item>
+ <item><ggp-game match_id="connect5.1297281313978"
+ name="Gomoku 12"/></item>
+ <item><ggp-game match_id="connect5.1297281334093"
+ name="Gomoku 13"/></item>
+ <item><ggp-game match_id="connect5.1297281339581"
+ name="Gomoku 14"/></item>
+ <item><ggp-game match_id="connect5.1297290598634"
+ name="Gomoku 15"/></item>
+ <item><ggp-game match_id="connect5.1297290600817"
+ name="Gomoku 16"/></item>
+ <item><ggp-game match_id="connect5.1297290603544"
+ name="Gomoku 17"/></item>
+ <item><ggp-game match_id="connect5.1297290606415"
+ name="Gomoku 18"/></item>
+ <item><ggp-game match_id="connect5.1297335418504"
+ name="Gomoku 19"/></item>
+ <item><ggp-game match_id="connect5.1297339843897"
+ name="Gomoku 20"/></item>
+ </itemize>
+ </section>
+
+
+ <section title="Pawn Whopping Games">
+ <itemize>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079331820"
+ name="Pawn Whopping 1"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079335327"
+ name="Pawn Whopping 2"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079338617"
+ name="Pawn Whopping 3"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079342087"
+ name="Pawn Whopping 4"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079344774"
+ name="Pawn Whopping 5"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079349729"
+ name="Pawn Whopping 6"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079352247"
+ name="Pawn Whopping 7"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079356298"
+ name="Pawn Whopping 8"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079360056"
+ name="Pawn Whopping 9"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297079363440"
+ name="Pawn Whopping 10"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111697272"
+ name="Pawn Whopping 11"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111700788"
+ name="Pawn Whopping 12"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111705440"
+ name="Pawn Whopping 13"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111708081"
+ name="Pawn Whopping 14"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111712776"
+ name="Pawn Whopping 15"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111715521"
+ name="Pawn Whopping 16"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111730245"
+ name="Pawn Whopping 17"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297111733976"
+ name="Pawn Whopping 18"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297173802992"
+ name="Pawn Whopping 19"/></item>
+ <item><ggp-game match_id="pawn_whopping_corrected.1297173805830"
+ name="Pawn Whopping 20"/></item>
+ </itemize>
+ </section>
+
</personal>
Property changes on: trunk/Toss/www/reference
___________________________________________________________________
Added: svn:ignore
+ # We are still using .cvsignore files as we find them easier to manage
# than svn properties. Therefore if you change .cvsignore do the following.
# svn propset svn:ignore -F .cvsignore .
*.html
*.html.de
*.html.en
*.png
*.css
reference.pdf
*.ps
*.dvi
*.aux
*.out
*.log
*.bbl
*.blg
*.idx
*.thm
*.snm
*.nav
*.toc
*.flc
*~
Added: trunk/Toss/www/reference/.cvsignore
===================================================================
--- trunk/Toss/www/reference/.cvsignore (rev 0)
+++ trunk/Toss/www/reference/.cvsignore 2011-03-12 17:51:51 UTC (rev 1354)
@@ -0,0 +1,24 @@
+# We are still using .cvsignore files as we find them easier to manage
+# than svn properties. Therefore if you change .cvsignore do the following.
+# svn propset svn:ignore -F .cvsignore .
+
+*.html
+*.html.de
+*.html.en
+*.png
+*.css
+reference.pdf
+*.ps
+*.dvi
+*.aux
+*.out
+*.log
+*.bbl
+*.blg
+*.idx
+*.thm
+*.snm
+*.nav
+*.toc
+*.flc
+*~
Added: trunk/Toss/www/reference/Makefile
===================================================================
--- trunk/Toss/www/reference/Makefile (rev 0)
+++ trunk/Toss/www/reference/Makefile 2011-03-12 17:51:51 UTC (rev 1354)
@@ -0,0 +1,23 @@
+all: reference.pdf index.html
+
+reference.pdf: reference.tex reference.bib
+ pdflatex reference.tex
+ bibtex reference
+ pdflatex reference.tex
+ pdflatex reference.tex
+ rm -f *.aux *.out *.log *.bbl *.blg *.idx *.thm *.snm *.nav \
+ *.toc *.lof *.flc
+
+reference.html: reference.tex reference.bib
+ htlatex reference.tex
+ rm -r reference.dvi *.log *.aux *.4ct *.4tc *.tmp *.idv *.lg *.xref
+
+index.html: reference.html
+ cp reference.html index.html
+ cp reference.html index.html.en
+ cp reference.html index.html.de
+
+.PHONY:
+
+clean:
+ rm -f *~ *.html *.png *.css reference.dvi reference.pdf
Copied: trunk/Toss/www/reference/reference.bib (from rev 1353, trunk/Toss/www/reference.bib)
===================================================================
--- trunk/Toss/www/reference/reference.bib (rev 0)
+++ trunk/Toss/www/reference/reference.bib 2011-03-12 17:51:51 UTC (rev 1354)
@@ -0,0 +1,189 @@
+@article{SUB96,
+ author = {Marcos Salganicoff and Lyle H. Ungar and Ruzena Bajcsy},
+ title = {Active Learning for Vision-Based Robot Grasping},
+ journal = {Machine Learning},
+ volume = {23},
+ year = {1996},
+ pages = {251--278},
+ publisher = {Kluwer Academic Publishers},
+ url = {http://www.springerlink.com/index/L738U7026765L077.pdf}
+}
+
+@book{PLN,
+ author = {Ben Goertzel and Matthew Ikle and Izabela Lyon Freire Goertzel},
+ title = {Probabilistic Logic Networks: A Comprehensive Framework
+ for Uncertain Inference},
+ publisher = {Springer},
+ year = {2008},
+ isbn = {0-387-76871-8}
+}
+
+
+@inproceedings{LG09,
+ author = {Moshe Looks and Ben Goertzel},
+ title = {Program Representation for General Intelligence},
+ booktitle = {Proceedings of AGI'09},
+ year = {2009},
+ url = {http://agi-conf.org/2009/papers/paper_69.pdf}
+}
+
+@inproceedings{K09,
+ author = {{\L}ukasz Kaiser},
+ title = {Synthesis for Structure Rewriting Systems},
+ booktitle = {Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, MFCS '09},
+ publisher = {Springer},
+ series = {LNCS},
+ volume = {5734},
+ year = {2009},
+ pages = {415--427},
+ url = {http://logic.rwth-aachen.de/~kaiser/graph_games_short.pdf},
+}
+
+@misc{toss,
+ title={Toss},
+ howpublished={\url{http://toss.sourceforge.net}}
+}
+
+@inproceedings{AS94,
+ author = {Rakesh Agrawal and
+ Ramakrishnan Srikant},
+ title = {Fast Algorithms for Mining Association Rules in Large Databases},
+ booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
+ Large Data Bases},
+ publisher = {Morgan Kaufmann},
+ year = {1994},
+ pages = {487--499},
+ url = {http://ifsc.ualr.edu/xwxu/Teaching/SciDB/vldb94Apriori.pdf}
+}
+
+@phdthesis{Gel07,
+ author = {Sylvain Gelly},
+ title = {A Contribution to Reinforcement Learning; Application to Computer-Go},
+ school = {University of Paris Sud},
+ type = {Dissertation},
+ year = {2007},
+ url = {http://www.lri.fr/~gelly/paper/SylvainGellyThesis.pdf}
+}
+
+@inproceedings{HP09,
+ author = {Joseph Y. Halpern and Rafeal Pass},
+ title = {Iterated regret minimization: A new solution concept},
+ booktitle = {Proceedings of the 21st International Joint Conference on
+ Artificial Intelligence (IJCAI 2009)},
+ year = {2009},
+ pages = {153--158},
+ url = {http://www.cs.cornell.edu/~rafael/papers/regret.pdf}
+}
+
+@incollection{T97,
+ author = {Wolfgang Thomas},
+ title = {Ehrenfeucht Games, the Composition Method, and the Monadic
+ Theory of Ordinal Words},
+ booktitle = {Structures in Logic and Computer Science},
+ series = {LNCS},
+ year = {1997},
+ publisher = {Springer},
+ pages = {118--143},
+ volume = {1261},
+ url = {http://automata.rwth-aachen.de/download/papers/thomas/ehrfeu.pdf}
+}
+
+@inproceedings{FB08,
+ author = {Hilmar Finnsson and Yngvi Bj{\"o}rnsson},
+ title = {Simulation-based Approach to General Game Playing},
+ booktitle = {Proc.~of AAAI'08},
+ publisher = {{AAAI} Press},
+ year = {2008},
+ url = {http://ru.is/faculty/hif/papers/cadiaplayer_aaai08.pdf}
+}
+
+@article{GLP05,
+ author = {Michael R. Genesereth and Nathaniel Love and Barney Pell},
+ title = {General Game Playing: Overview of the {AAAI} Competition},
+ journal = {AI Magazine},
+ year = {2005},
+ volume = {26},
+ number = {2},
+ pages = {62--72},
+ url = {http://games.stanford.edu/competition/misc/aaai.pdf}
+}
+
+@article{GH06D_ag,
+ author = {Holger Giese and Stefan Henkler},
+ title = {A Survey of Approaches for the Visual Model-Driven Development
+ of Next Generation Software-Intensive Systems},
+ journal = {Journal of Visual Languages and Computing},
+ year = {2006},
+ volume = {17},
+ number = {6},
+ pages = {528--550},
+ month = {12}
+}
+
+@article{BGMOKS06_ag,
+ author = {Sven Burmester and Holger Giese and Eckehard M{\"u}nch and
+ Oliver Oberschelp and Florian Klein and Peter Scheideler },
+ title = {Tool Support for the Design of Self-Optimizing Mechatronic
+ Multi-Agent Systems},
+ journal = {International Journal on Software Tools for Technology Transfer},
+ year = {2008},
+ volume = {10},
+ number = {3},
+ pages = {207--222},
+ month = {6},
+ publisher = {Springer},
+}
+
+@inproceedings{G06,
+ author = {Ben Goertzel},
+ title = {Patterns, Hypergraphs and Embodied General Intelligence},
+ booktitle = {Proceedings of the International Joint Conference on Neural
+ Networks, IJCNN 2006, part of the IEEE World Congress on
+ Computational Intelligence, WCCI 2006, Vancouver, BC, Canada,
+ 16-21 July 2006},
+ year = {2006},
+ pages = {451--458},
+ url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.2741&rep=rep1&type=pdf}
+}
+
+@inproceedings{DRDM03,
+ author = {Mehdi Dastani and
+ Birna van Riemsdijk and
+ Frank Dignum and
+ John-Jules Ch. Meyer},
+ title = {A Programming Language for Cognitive Agents: Goal Directed 3APL},
+ booktitle = {Proceedings of Programming Multi-Agent Systems, First
+ International Workshop, ProMAS 2003, Melbourne, Australia,
+ July 15, 2003, Selected Revised and Invited Papers},
+ pages = {111--130},
+ publisher = {Springer},
+ series = {LNCS},
+ volume = {3067},
+ year = {2003}
+}
+
+@inproceedings{AFHMS03,
+ author = {Luca de Alfaro and
+ Marco Faella and
+ Thomas A. Henzinger and
+ Rupak Majumdar and
+ Mari{\"e}lle Stoelinga},
+ title = {The Element of Surprise in Timed Games},
+ booktitle = {Proceedings of CONCUR 2003, France, 2003},
+ pages = {142--156},
+ publisher = {Springer},
+ series = {LNCS},
+ volume = {2761},
+ year = {2003},
+ url = {http://mtc.epfl.ch/~tah/Publications/the_element_of_surprise_in_timed_games.pdf}
+}
+
+@article{GrGu98,
+ author = {Erich Gr{\"a}del and Yuri Gurevich},
+ title = {Metafinite Model Theory},
+ journal = {Information and Computation},
+ volume = {140},
+ year = {1998},
+ pages = {26--81},
+ url = {http://www.logic.rwth-aachen.de/pub/graedel/infcomp.ps},
+}
Copied: trunk/Toss/www/reference/reference.tex (from rev 1353, trunk/Toss/www/reference.tex)
===================================================================
--- trunk/Toss/www/reference/reference.tex (rev 0)
+++ trunk/Toss/www/reference/reference.tex 2011-03-12 17:51:51 UTC (rev 1354)
@@ -0,0 +1,729 @@
+\documentclass{scrbook}
+
+% Font choice
+\usepackage[sc]{mathpazo}
+\usepackage{bera}
+
+% Abbreviations for \calX, \frakX, \bbX etc. in math mode
+\makeatletter
+\newcommand{\@abbrev}[3]{
+ \def\c@a@def##1{
+ \if ##1.
+ \relax
+ \else
+ \@ifdefinable{\@nameuse{#1##1}}{\@namedef{#1##1}{#2##1}}
+ \expandafter\c@a@def
+ \fi
+ }
+ \c@a@def #3.
+}
+\@abbrev{bb}{\mathbb}{ABCDEFGHIJKLMNOPQRSTUVWXYZ}
+\@abbrev{bf}{\mathbf}{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz}
+\@abbrev{bit}{\boldsymbol}{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz}
+\@abbrev{cal}{\mathcal}{ABCDEFGHIJKLMNOPQRSTUVWXYZ}
+\@abbrev{frak}{\mathfrak}{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz}
+\@abbrev{rm}{\mathrm}{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz}
+\@abbrev{scr}{\mathscr}{ABCDEFGHIJKLMNOPQRSTUVWXYZ}
+\@abbrev{sf}{\mathsf}{ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz}
+\makeatother
+
+% Simple item labels
+\renewcommand{\labelitemi}{--}
+\renewcommand{\labelitemii}{--}
+\renewcommand{\labelitemiii}{--}
+
+% Packages
+\usepackage{amsmath,amssymb,amsthm}
+\usepackage{enumerate}
+\usepackage{xspace}
+\usepackage{tikz}
+\usetikzlibrary{shapes,snakes,arrows}
+\usepackage[draft]{fixme}
+
+% Additional commands
+\newcommand{\cf}{cf.\xspace}
+\newcommand{\ea}{\& al.\xspace}
+\newcommand{\eg}{e.g.\xspace}
+\newcommand{\ie}{i.e.\xspace}
+\newcommand{\mr}[1]{\mathrm{#1}}
+\newcommand{\ol}[1]{\overline{#1}}
+\renewcommand{\phi}{\varphi}
+
+
+% Start
+\newcommand\thetitle{Toss Design and Specification}
+\title{\thetitle}
+\date{}
+\author{Toss Team}
+
+\begin{document}
+
+\maketitle
+
+\setcounter{tocdepth}{1}
+
+\tableofcontents
+\clearpage
+\listoffigures
+
+\cleardoublepage
+
+
+\chapter{Specification}
+
+\section{Discrete Structure Rewriting}
+
+To represent a state of our model in a fixed moment of time
+we use finite relational structures, \ie labelled directed hypergraphs.
+A relational structure $\frakA = (A, R_1, \ldots, R_k)$ is composed of
+a universe $A$ and a number of relations $R_1, \ldots, R_k$.
+We denote the arity of $R_i$ by $r_i$, so $R_i \subseteq A^{r_i}$.
+The \emph{signature} of $\frakA$ is the set of symbols $\{R_1, \ldots, R_k\}$.
+
+The dynamics of the model, \ie the way the structure can change,
+is described by \emph{structure rewriting rules}, a generalized form of
+term and graph rewriting. Extended graph rewriting is recently viewed as
+the programming model of choice for complex multi-agent systems,
+especially ones with real-valued components \cite{BGMOKS06_ag}.
+%Practical utility of such models was verified in a german project developing
+%automomous railway vehicle control, the Collaborative Research Center 614.
+Moreover, this form of rewriting is well suited for visual programming and
+helps to make the systems understandable. %(see \cite{GH06D_ag} for a survey).
+
+In the most basic setting, a rule $\frakL \to_s \frakR$ consists of
+two finite relational structures $\frakL$ and $\frakR$ over the same
+signature and a partial function $s : \frakR \to \frakL$ specifying which
+elements of $\frakL$ will be substituted by which elements of $\frakR$.
+
+Let $\frakA, \frakB$ be two structures, $\tau_{\mr{e}}$ a set of relations
+symbols to be matched exactly and $\tau_{\mr{h}}$ a set of relations to
+be matched only positively. In practice, we also allow some
+tuples in $\frakL$ to be optional; this is a shorthand
+for multiple rules with the same right-hand side. Optional tuples can
+also appear in $\frakR$ if all elements in the tuple have corresponding
+elements in $\frakL$. In such case, the tuple is included in $\frakR$ if
+and only if a corresponding optional tuple appeared in $\frakL$.
+A function $f : \frakA \hookrightarrow \frakB$ is
+a $(\tau_{\mr{e}}, \tau_{\mr{h}})$-\emph{embedding} if $f$ is injective,
+for each $R_i \in \tau_{\mr{e}}$ it holds that
+ $(a_1, \ldots, a_{r_i}) \in R^\frakA_i \Leftrightarrow
+ (f(a_1), \ldots, f(a_{r_i})) \in R^\frakB_i$,
+and for $R_j \in \tau_{\mr{h}}$ it holds that
+ $(a_1, \ldots, a_{r_i}) \in R^\frakA_j \Rightarrow
+ (f(a_1), \ldots, f(a_{r_i})) \in R^\frakB_j$.
+A $(\tau_{\mr{e}}, \tau_{\mr{h}})$-\emph{match} of the rule $\frakL \to_s \frakR$
+in another structure $\frakA$ is an $(\tau_{\mr{e}}, \tau_{\mr{h}})$-embedding
+$\sigma : \frakL \hookrightarrow \frakA$.
+We define the result of an application of $\frakL \to_s \frakR$ to $\frakA$
+on the match $\sigma$ as $\frakB = \frakA[\frakL \to_s \frakR / \sigma]$,
+such that the universe of $\frakB$ is given by
+$(A \setminus \sigma(L)) \dot\cup R$, and the relations as follows.
+A tuple $(b_1, \ldots, b_{r_i})$ is in the new relation $R^\frakB_i$
+if and only if either it is in the relation in $\frakR$ already,
+$(b_1, \ldots, b_{r_i}) \in R^\frakR_i$, or there exists a tuple in
+the previous structure, $(a_1, \ldots, a_{r_i}) \in R^\frakA_i$,
+such that for each $i$ either $a_i = b_i$ or $a_i = \sigma(s(b_i))$,
+\ie either the element was there before or it was matched and $b_i$
+is the replacement as specified by the rule. Moreover,
+if $R_i \in \tau_{\mr{e}}$ then we require in the second case that
+at least one $b_i$ was already in the original structure, \ie $b_i = a_i$.
+To understand this definition it is best to consider an example,
+and one is given in Figure~\ref{fig-rewriting}.
+
+\begin{figure}
+$\phantom{ll}$
+\begin{tikzpicture}[scale=0.7]
+\node (a) at (-6, 1) {Rewriting Rule:};
+\node[draw, circle] (lhs1) at (-2.6, 1) {\tiny $a$};
+\node[draw, circle] (lhs2) at (-1.5, 1) {\tiny $b$};
+\path (lhs1) edge[->] node[above] {\tiny $R$} (lhs2);
+
+\node (t) at (-0.5, 1) {$\leadsto$};
+
+\node[draw, circle, fill=black!15] (rhs1) at (0.6, 1.5) {\tiny $a$};
+\node[draw, circle, fill=black!15] (rhs2) at (1.8, 1.5) {\tiny $b$};
+\node[draw, circle, fill=black!15] (rhs3) at (3, 1.5) {\tiny $b$};
+\node[draw, circle, fill=black!15] (rhs4) at (1.8, 0.5) {\tiny $\phantom{a}$};
+\draw[->] (rhs2) -- (rhs1);
+\draw[->] (rhs2) -- (rhs3);
+\draw[->] (rhs2) -- (rhs4);
+\end{tikzpicture}
+\begin{center}
+\vskip -1em
+\begin{tikzpicture}[scale=0.59]
+\scriptsize
+
+% Graph to be rewritten.
+\node[draw, circle] (v) at (-7, 0) {$a$};
+\node[draw, circle] (v1) at (-6, 2) {};
+\node[draw, circle] (v2) at (-6, -2) {};
+\node[draw, circle] (w) at (-4, 0) {$b$};
+\node[draw, circle] (w1) at (-5, 2) {};
+\node[draw, circle] (w2) at (-5, -2) {};
+\node[draw, circle] (vu) at (-8, 2) {};
+\node[draw, circle] (vd) at (-8, -2) {};
+\node[draw, circle] (wu) at (-3, 2) {};
+\node[draw, circle] (wd) at (-3, -2) {};
+
+\path (v) edge[thick,->] node[midway,above] {$R$} (w);
+\draw[->] (v) -- (v1);
+\draw[->] (v) -- (v2);
+\draw[->] (w1) -- (w);
+\draw[->] (w2) -- (w);
+\draw[->] (vu) -- (v);
+\draw[->] (vd) -- (v);
+\draw[->] (w) -- (wu);
+\draw[->] (w) -- (wd);
+
+\node (lto) at (-2.5, 0) {\normalsize $\leadsto$};
+
+% Resulting graph
+\node[draw, circle, fill=black!15] (rr1) at (-1.2, 0) {};
+\node[draw, circle, fill=black!15] (rr2) at (0.8, 0) {};
+\node[draw, circle, fill=black!15] (rr3) at (2.8, 0) {};
+\node[draw, circle, fill=black!15] (rr4) at (0.8, -1) {};
+
+\node[draw, circle] (rv1u) at (-1.9, 2) {};
+\node[draw, circle] (rv1d) at (-1.9, -2) {};
+\node[draw, circle] (rv2u) at (-0.5, 2) {};
+\node[draw, circle] (rv2d) at (-0.5, -2) {};
+\node[draw, circle] (rw1u) at (2.1, 2) {};
+\node[draw, circle] (rw1d) at (2.1, -2) {};
+\node[draw, circle] (rw2u) at (3.5, 2) {};
+\node[draw, circle] (rw2d) at (3.5, -2) {};
+
+\draw[thick,->] (rr2) -- (rr1);
+\draw[thick,->] (rr2) -- (rr3);
+\draw[thick,->] (rr2) -- (rr4);
+
+\draw[->] (rv1u) -- (rr1);
+\draw[->] (rv1d) -- (rr1);
+\draw[->] (rr1) -- (rv2u);
+\draw[->] (rr1) -- (rv2d);
+
+%\draw[->] (rr2) -- (rv2u);
+%\draw[->] (rr2) -- (rv2d);
+\draw[->] (rr2) .. controls (1.8, 2.5) .. (rw2u);
+\draw[->] (rr2) .. controls (1.8, -2.5) .. (rw2d);
+\draw[->] (rw1u) -- (rr2);
+\draw[->] (rw1d) -- (rr2);
+%\path (rv1u) edge[->,bend left=60] (rr2);
+%\draw[->] (rv1d) .. controls (0.5, -2.5) .. (rr2);
+
+\draw[->] (rw1u) -- (rr3);
+\draw[->] (rw1d) -- (rr3);
+\draw[->] (rr3) -- (rw2u);
+\draw[->] (rr3) -- (rw2d);
+\end{tikzpicture}
+\end{center}
+\caption{Rewriting rule and its application to a structure.}
+\label{fig-rewriting}
+\end{figure}
+
+
+\section{Continuous Evolution}
+
+To model continuous dynamics in our system, we supplement relational
+structures with a number of labeling functions $f_1, \ldots, f_l$,
+each $f_i : A \to \bbR$ ($A$ is the universe).\footnote{In fact $f_i(a)$ is not
+in $\bbR$; it is a function $\epsilon \to (x,x+\delta), \delta < \epsilon$.}
+Accordingly, each rewriting rule is extended by a system of ordinary
+differential equations (ODEs) and a set of right-hand update equations.
+We use a standard form of ODEs:
+$f^k_{i,l} = t(f^0_{i,l}, \ldots, f^{k-1}_{i,l})$, where $f_i$ are
+the above-mentioned functions, $l$ can be any element of the left-hand
+side structure and $f^k$ denotes the $k$-th derivative of $f$.
+The term $t(\ol{x})$ is constructed using standard arithmetic functions
+$+, -, \cdot, /$, natural roots $\sqrt[n]{\phantom{a}}$ for $n > 1$
+and rational numbers $r \in \bbQ$ in addition to the variables $\ol{x}$ and
+a set of parameters $\ol{p}$ fixed for each rule.
+%This form is enough to express most ODEs used in physics and economics.
+The set of right-hand side update equations contains one equation of
+the form $f_{i, r} = t(\ol{f_{i,l}})$ for each function $f_i$ and
+each $r$ from the right-hand side structure.
+
+Let $\calR = \{ (\frakL_i \to_{s_i} \frakR_i, \calD_i, \calT_i) \mid i < n \}$
+be a set of rules extended with ODEs $\calD_i$ and update equations $\calT_i$
+as described above.
+Given, for each rule in $\calR$, a match $\sigma_i$ of the rule in a structure
+$\frakA$, the required parameters $\ol{p_i}$ and a time bound $t_i$, we define
+the result of a \emph{simultaneous application} of $\calR$ to $\frakA$,
+denoted $\frakA[\calR/\{\sigma_i, t_i\}]$, as follows.
+We assume that no two intersecting rules have identical time bounds.
+
+First, the structure $\frakA$ evolves in a continuous way as given by
+the \emph{sum} of all equations $\calD_i$. More precisely, let $\calD$ be
+a system of differential equations where for each $a \in \frakA$ there
+exists an equation defining $f^k_{i,a}$ if and only if there exists an
+equation in some $\calD_j$ for $f^k_{i,l}$ for some $l$ with $\sigma_j(l) = a$.
+In such case, the term for $f^k_{i,a}$ is the sum of all terms for such $l$,
+with each $f^m_{i, l}$ replaced by the appropriate $f^m_{i, \sigma_j(l)}$.
+Assuming that all functions $f_i$ and all their derivatives are given at
+the beginning, there is a unique solution for these variables which satisfies
+$\calD$ and has all other, undefined derivatives set by the starting condition
+from $\frakA$. This solution defines the value of $f_{i,a}(t)$ for
+each $a \in \frakA$ at any time moment $t$.
+
+Let $t^0 = \min_{i<n} t_i$ be the lowest chosen time bound and let
+$i_0, \ldots, i_k$ be all rules with this bound, \ie each $t_{i_m} = t^0$.
+We apply each of these rules independently$^1$ to the structure $\frakA$
+at time $t^0$. Formally, the relational part of
+$\frakA[\calR/\{\sigma_i, t_i\}]$ is equal to
+$\frakA[\frakL_{i_0} \to_{s_{i_0}} \frakR_{i_0}/\sigma_{i_0}] \cdots
+ [\frakL_{i_k} \to_{s_{i_k}} \frakR_{i_k}/\sigma_{i_k}]$ and the function values
+$f_i(a)$ are defined as follows. If the element $a$ was not changed,
+$a \in \frakA$, then we keep the function value from the solution of $\calD$,
+\ie $f_i(a) = f_{i,a}(t^0)$. In the other case $a$ was on the right-hand side
+of some rule, $a \in \frakR_m$. Let $f_{i,a} = t(\ol{f_{j,l}})$ be the
+equation in $\calT_m$ defining $f_{i,a}$. The new value of $f_i(a)$ is then
+computed by inserting the appropriate values for $f_{j,l}$ from the solution
+of $\calD$ into $t(\ol{f_{j,l}})$, \ie $f_i(a) = t(\ol{y_{j,l}})$ where
+each $y_{j,l} = f_{j,\sigma_m(l)}(t^0)$. %with $\ol{p_j}$ used as parameters.
+
+\emph{Example.}
+Let us define a simple two-dimensional model of a cat chasing a mouse.
+The structure we use, $\frakA = (\{c, m\}, C, M, x, y)$, has two elements
+$c$ and $m$, unary relations $C = \{c\}$ and $M = \{m\}$ used to identify
+which element is which and two real-valued functions $x$ and $y$.
+Both rewriting rules have only one element, both on the left-hand side and
+on the right-hand side, and the element is in $C$ for the cat rule and
+in $M$ for the mouse rule. The ODEs for both rules are of the form
+$x' = p_x, y' = p_y$, where $p_x, p_y$ are parameters. The update
+equations just keep the left-hand side values, $x_r = x_l, y_r = y_l$.
+In this setting, simultaneous application of the cat rule with parameters
+$p^c_x, p^c_y$ for time $t^c$ and the mouse rule with parameters $p^m_x, p^m_y$
+for time $t^m$ will have the following effect: The cat will move with
+speed $p^c_x$ along the $x$-axis and $p^c_y$ along the $y$-axis and the mouse
+analogously with $p^m_x$ and $p^m_y$, both for time $t^0 = \min(t^c, t^m)$.
+
+
+\section{Logic and Constraints}
+
+The logic we use for specifying properties of states is an extension of
+monadic second-order logic with real-valued terms and counting operators.
+%(\cf \cite{GrGu98}).
+The main motivation for the choice of such logic is \emph{compositionality}:
+To evaluate a formula on a large structure $\frakA$ which is composed in
+a regular way from substructures $\frakB$ and $\frakC$ it is enough
+to evaluate certain formulas on $\frakB$ and $\frakC$ independently.
+Monadic second-order logic is one of the most expressive logics
+with this property and allows to define various useful patterns such as stars,
+connected components or acyclic subgraphs. (Additional syntactic
+shorthands can be provided for useful patterns.)
+
+In the syntax of our logic, we use first-order variables
+($x_1, x_2, \ldots$) ranging over elements of the structure, second-order
+variables ($X_1, X_2, \ldots$) ranging over \emph{sets} of elements,
+and real-valued variables $(\alpha_1, \alpha_2, \ldots)$ ranging over $\bbR$,
+and we distinguish boolean formulas $\phi$ and real-valued terms $\rho$:
+\begin{eqnarray*}
+ \phi := & \!\!\!\!\! R_i(x_1, \ldots, x_{r_i}) \, |\, x_i=x_j \, |\,
+ x_i \in X_j \, | \, \rho <_\epsilon \rho \, | \, \phi \land \phi \ | \\
+ & \!\!\! \phi \lor \phi \, | \, \neg \phi \, | \,
+ \exists x_i \phi \, | \, \forall x_i \phi \, | \,
+ \exists X_i \phi \, | \, \forall X_i \phi \, | \,
+ \exists \alpha_i \phi \, | \, \forall \alpha_i \phi,
+\end{eqnarray*}
+\vskip -1.1em
+\begin{eqnarray*}
+\rho := & \!\!\!\! \alpha_i \: | \: f_i(x_j) \: | \: %\rho + \rho \ | \
+ \rho \dotplus \rho \: | \: \chi[\phi] \: | \: \min_{\alpha_i}\!\phi \: | \:
+ \sum_{\ol{x} \mid \phi} \rho \: | \: \prod_{\ol{x} \mid \phi} \rho.
+\end{eqnarray*}
+
+Semantics of most of the above operators is defined in the well known way, \eg
+$\rho+\rho$ is the sum and $\rho \cdot \rho$ the product of real-valued terms,
+and $\exists X \phi(X)$ means that there exists a set of elements $S$ such
+that $\phi(S)$ holds. Among less known operators,
+the term $\chi[\phi]$ denotes the characteristic function of $\phi$, \ie
+the real-valued term which is $1$ for all assignments for which $\phi$ holds
+and $0$ for all other. To evaluate $\min_{\alpha_i}\phi$ we take the minimal
+$\alpha_i$ for which $\phi$ holds (we allow $\pm \infty$ as values
+of terms as well). The terms $\sum_{\ol{x} \mid \phi} \rho$ and
+$\prod_{\ol{x} \mid \phi} \rho$ denote the sum and product of the values of
+$\rho(\ol{x})$ for all assignments of elements of the structure to $\ol{x}$
+for which $\phi(\ol{x})$ holds. Note that both these terms can have free
+variables, \eg the set of free variables of $\sum_{\ol{x} \mid \phi} \rho$
+is the union of free variables of $\phi$ and free variables of $\rho$, minus
+the set $\{\ol{x}\}$. Observe also the $\epsilon$ in $<_\epsilon$:
+the values $f(a)$ are given with arbitrary small but non-zero error
+and $\rho_1 <_\epsilon \rho_2$ holds only if the upper
+bound of $\rho_1$ lies below the lower bound of $\rho_2$.
+%both terms queried with error bound $\epsilon$.
+
+The logic defined above is used in structure rewriting rules in two ways.
+First, it is possible to define a new relation $R(\ol{x})$ using a formula
+$\phi(\ol{x})$ with free variables contained in~$\ol{x}$.
+Defined relations can be used on left-hand sides of structure
+rewriting rules, but are not allowed on right-hand sides.
+The second way is to add \emph{constraints} to a rule.
+A rule $\frakL \to_s \frakR$ can be constrained using
+three sentences (\ie formulas without free variables):
+$\phi_{\mr{pre}}$, $\phi_{\mr{inv}}$ and $\phi_{\mr{post}}$.
+In both $\phi_{\mr{pre}}$ and $\phi_{\mr{inv}}$ we allow additional constants $l$
+for each $l \in \frakL$ and in $\phi_{\mr{post}}$ special constants for each
+$r \in \frakR$ can be used. A rule $\frakL \to_s \frakR$ with such constraints
+can be applied on a match $\sigma$ in $\frakA$ only if the following holds:
+At the beginning, the formula $\phi_{\mr{pre}}$ must hold in $\frakA$ with
+the constants $l$ interpreted as $\sigma(l)$. Later, during the whole
+continuous evolution, the formula $\phi_{\mr{inv}}$ must hold in the structure
+$\frakA$ with continuous values changed as prescribed by the solution of
+the system $\calD$ (defined above).
+Finally, the formula $\phi_{\mr{post}}$ must hold in the resulting
+structure after rewriting. During simultaneous execution of a few rules with
+constraints and with given time bounds $t_i$, one of the invariants
+$\phi_{\mr{inv}}$ may cease to hold. In such case, the rule is applied at
+that moment of time, even before $t^0 = \min t_i$ is reached --- but of
+course only if $\phi_{\mr{post}}$ holds afterwards. If $\phi_{\mr{post}}$
+does not hold, the rule is ignored and time goes on for the remaining rules.
+
+
+\section{Structure Rewriting Games}
+
+As you could judge from the cat and mouse example, one can describe
+a structure rewriting game simply by providing a set of allowed rules for
+each player. Still, in many cases it is necessary to have more control
+over the flow of the game and to model probabilistic events.
+For this reason, we use labelled directed graphs with probabilities
+in the definition of the games. The labels for each player are of the form:
+\[ \lambda = (\frakL \to_s \frakR, \calD, \calT,
+ \phi_{\mr{pre}}, \phi_{\mr{inv}}, \phi_{\mr{post}},
+ I_t, \ol{I_p}, \mr{m}, \tau_{\mr{e}}). \]
+Except for a rewriting rule with invariants, the label $\lambda$ specifies
+a time interval $I_t \subseteq [0, \infty)$ from which the player can
+choose the time bound for the rule and, if there are other continuous
+parameters $p_1, \ldots, p_n$, also an interval $I_{p_j} \subseteq \bbR$
+for each parameter. The element $\mr{m} \in \{1, \ast, \infty\}$
+specifies if the player must choose a single match of the rule ($\mr{m} = 1$),
+apply it simultaneously to all possible matches ($\mr{m} = \infty$, useful for
+modeling nature) or if any number of non-intersecting matches might be chosen
+($\mr{m} = \ast$); $\tau_{\mr{e}}$ tells which relations must be matched
+exactly (all other are in $\tau_{\mr{h}}$).
+
+We define a \emph{general structure rewriting game} with $k$ players as
+a directed graph in which each vertex is labelled by $k$ sets of labels
+denoting possible actions of the players.
+For each $k$-tuple of labels, one from each set, there must be an outgoing edge
+labelled by this tuple, pointing to the next location of the game if these
+actions are chosen by the players. There can be more than one outgoing edge
+with the same label in a vertex: In such case, all edges with this label must
+be assigned probabilities (\ie positive real numbers which sum up to~$1$).
+Moreover, an end-point of an interval $I_t$ or $I_p$ in a label can be given
+by a parameter, \eg $x$. Then, each outgoing edge with this label must
+be marked by $x \! \sim \! \calN(\mu,\sigma)$, $x \! \sim \! \calU(a,b)$ or
+$x \! \sim \! \calE(\lambda)$, meaning that $x$ will be drawn from the normal,
+uniform or exponential distribution (these $3$ chosen for convenience).
+Additionally, in each vertex there are $k$ real-valued terms of the logic
+presented above which denote the payoff for each player if the game
+ends at this vertex.
+
+A play of a structure rewriting game starts in a fixed first vertex of
+the game graph and in a state represented by a given starting structure.
+All players choose rules, matches and time bounds allowed by the labels of
+the current vertex such that the tuple of rules can be applied simultaneously.
+The play proceeds to the next vertex (given by the labeling of the edges)
+in the changed state (after the application of the rules).
+If in some vertex and state it is not possible to apply any tuple of rules,
+either because no match is found or because of the constraints, then the play
+ends and payoff terms are evaluated giving the outcome for each player.
+
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.71] \tiny
+% Game Graph
+\node (gg) at (-6.2, 2) {\small Game Graph:};
+\node[draw, circle, fill=black!15] (p0) at (-4, 2) {};
+\node[draw, circle, fill=black!15] (p1) at (-4, 0) {};
+\draw[->] (-4, 2.5) -- (p0);
+\path (p0) edge[bend right=30,->] (p1);
+\path (p1) edge[bend right=30,->] (p0);
+
+\node[draw,circle] (r0l) at (-5.8, 1) {$\phantom{a}$};
+\node (r0m) at (-5.3, 0.98) {$\leadsto$};
+\node[draw,circle] (r0r) at (-4.8, 1) {$P$};
+
+\node[draw,circle] (r1l) at (-3.2, 1) {$\phantom{a}$};
+\node (r0m) at (-2.7, 0.98) {$\leadsto$};
+\node[draw,circle] (r0r) at (-2.2, 1) {$Q$};
+
+% Starting Structure
+\node (ss) at (-1.5, 2) {\small Starting Structure:};
+\foreach \x in {1, ..., 3} \foreach \y in {0, ..., 2} {
+ \node[draw, circle] (n\x\y) at (\x, \y) {$\phantom{a}$};
+}
+
+\foreach \x in {1, ..., 3} \foreach \y / \n in {0/1, 1/2} {
+ \path (n\x\n) edge[->] node[right] {$C$} (n\x\y);
+}
+
+\foreach \y in {0, ..., 2} \foreach \x / \n in {1/2, 2/3} {
+ \path (n\x\y) edge[->] node[above] {$R$} (n\n\y);
+}
+\end{tikzpicture}
+\end{center}
+\caption{Tic-tac-toe as a structure rewriting game.}
+\label{fig-tic-tac-toe}
+\end{figure}
+
+\emph{Example.} Let us define tic-tac-toe in our framework.
+The state of the game is represented by a structure with $9$ elements
+connected by binary row and column relations, $R$ and $C$, as depicted
+on the right in Figure~\ref{fig-tic-tac-toe}. To mark the moves of the players
+we use unary relations $P$ and $Q$. The allowed move of the first player
+is to m...
[truncated message content] |