2012

• Ł. Kaiser. Learning Games from Videos Guided by Descriptive Complexity. In Proceedings of the 26th Conference on Artificial Intelligence, AAAI-12. To appear. AAAI Press, 2012.                                 
  Abstract   BibTeX

  In recent years, several systems have been proposed that learn the rules of a simple card or board game solely from visual demonstration. These systems were constructed for specific games and rely on substantial background knowledge. We introduce a general system for learning board game rules from videos and demonstrate it on several well-known games. The presented algorithm requires only a few demonstrations and minimal background knowledge, and, having learned the rules, automatically derives position evaluation functions and can play the learned games competitively. Our main technique is based on descriptive complexity, the logical means necessary to define a set of interest. We compute formulas defining allowed moves and final positions in a game in different logics and select the most adequate ones. We show that this method is well-suited for board games and there is strong theoretical evidence that it will generalize to other problems.

  @inproceedings{K12,
       author = {\L{}ukasz Kaiser},
       title = {Learning Games from Videos Guided by Descriptive Complexity},
       year = {2012},
       booktitle = {Proceedings of the 26th Conference on Artificial Intelligence, AAAI-12. To appear},
       publisher = {AAAI Press},
       url = {/pub/learning_games_descriptive_complexity.pdf},
  }
  

• Ł. Kaiser and S. Lessenich. A Counting Logic for Structure Transition Systems. In Proceedings of the 21st Annual Conference of the European Association for Computer Science Logic, CSL '12, LIPIcs. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2012.                                 
  Abstract   BibTeX

  Quantitative questions such as “what is the maximum number of tokens in a place of a Petri net?'' or “what is the maximal reachable height of the stack of a pushdown automaton?'' play a significant role in understanding models of computation. To study such problems in a systematic way, we introduce structure transition systems on which one can define logics that mix temporal expressions (e.g. reachability) with properties of a state (e.g. the height of the stack). We propose a counting logic Qmu[#MSO] which allows to express questions like the ones above, and also many boundedness problems studied so far. We show that Qmu[#MSO] has good algorithmic properties, in particular we generalize two standard methods in model checking, decomposition on trees and model checking through parity games, to this quantitative logic. These properties are used to prove decidability of Qmu[#MSO] on tree-producing pushdown systems, a generalization of both pushdown systems and regular tree grammars.

  @inproceedings{KL12,
       author = {{\L}ukasz Kaiser and Simon Lessenich},
       title = {A Counting Logic for Structure Transition Systems},
       booktitle = {Proceedings of the 21st Annual Conference of the European Association for Computer Science Logic, CSL~'12},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
       series = {LIPIcs},
       year = {2012},
       url = {/pub/itrs_qmu.pdf},
  }
  

2011

• Ł. Kaiser and Ł. Stafiniak. Translating the Game Description Langauge to Toss. In Proceedings of the 2nd International General Game Playing Workshop, GIGA'11, 2011.                                 
  Abstract   BibTeX

  We show how to translate games defined in the Game Description Language (GDL) into the Toss format. GDL is a variant of Datalog used to specify games in the General Game Playing Competition. Specifications in Toss are more declarative than in GDL and make it easier to capture certain useful game characteristics. The presented translation detects structural properties of games which are not directly visible in the GDL specification.

  @inproceedings{KS11transl,
       author = {\L{}ukasz Kaiser and \L{}ukasz Stafiniak},
       title = {Translating the Game Description Langauge to Toss},
       year = {2011},
       booktitle = {Proceedings of the 2nd International General Game Playing Workshop, GIGA'11},
       url = {/pub/gdl_to_toss_translation.pdf},
  }
  

• Ł. Kaiser and Ł. Stafiniak. First-Order Logic with Counting for General Game Playing. In Proceedings of the 25th AAAI Conference, 2011.                                 
  Abstract   BibTeX

  General Game Players (GGPs) are programs which can play an arbitrary game given only its rules. Game Description Language (GDL) is a variant of Datalog used in GGP competitions to specify the games. GDL inherits from Datalog the use of Horn clauses as rules and recursion, but it too requires stratification and does not allow to use quantifiers. We present an alternative formalism for game description which is based on first-order logic (FO). States of the game are represented by relational structures, legal moves by structure rewriting rules guarded by FO formulas, and the goals of the players by formulas which extend FO with counting. The advantage of our formalism comes from more explicit state representation and from the use of quantifiers in formulas. We show how to exploit existential quantification in players' goals to generate heuristics for evaluating positions in the game. The derived heuristics are good enough for a basic alpha-beta agent to win against state of the art GGP.

  @inproceedings{KS11,
       author = {\L{}ukasz Kaiser and \L{}ukasz Stafiniak},
       title = {First-Order Logic with Counting for General Game Playing},
       year = {2011},
       booktitle = {Proceedings of the 25th AAAI Conference},
       url = {/pub/first_order_counting_ggp.pdf},
  }
  

2010

• T. Ganzow and Ł. Kaiser. New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures. In Proceedings of the 19th Annual Conference of the European Association for Computer Science Logic, CSL 2010 (A. Dawar and H. Veith, Eds.), vol. 6247 of Lecture Notes in Computer Science, pp. 366–380. Springer, 2010.                                 
  Abstract   BibTeX

  Weak monadic second-order logic is a very expressive logic which has been used successfully for verification of software and hardware systems. Moreover, structures of bounded clique width have a decidable weak MSO theory which allows to specify and verify detailed correctness properties. However, one obstacle to a wide application of WMSO verification techniques in practice is that the prevalent model-checking algorithms are based on tree automata, and hence require to encode the structure of interest in the binary tree which is often a cause of inefficiency. We present a new algorithm for model-checking weak MSO on inductive structures, a certain kind of structures of bounded clique width, together with a proof of its decidability which follows from Shelah's composition method. Our algorithm directly manipulates formulas and checks them on the structure of interest without the need to encode it in the binary tree. In fact, the model-checking problem is reduced to solving a finite reachability game. In addition to the new algorithm, we also show that our method can be extended to obtain decidability of weak MSO extended with the unbounding quantifier on the binary tree, which was open before.

  @inproceedings{GK10,
       author = {Tobias Ganzow and {\L}ukasz Kaiser},
       title = {New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures},
       booktitle = {Proceedings of the 19th Annual Conference of the European Association for Computer Science Logic, CSL~2010},
       editor = {Anuj Dawar and Helmut Veith},
       volume = {6247},
       year = {2010},
       series = {Lecture Notes in Computer Science},
       publisher = {Springer},
       pages = {366--380},
       url = {/pub/weak_mso_composition.pdf},
  }
  

• Ł. Kaiser and Ł. Stafiniak. Playing Structure Rewriting Games. In Proceedings of AGI '10. Atlantis Press, 2010.                                 
  Abstract   BibTeX

  Achieving goals in a complex environment in which many players interact is a general task demanded from an AI agent. When goals of the players are given explicitly, such setting can be described as a multi-player game with complete information. We introduce a general model of such games in which states are represented by relational structures (hypergraphs), possibly with real-valued labels, and actions %are given by structure rewriting rules. For this model, we develop an algorithm which computes rational strategies for the players. Our algorithm can be parametrized by a probabilistic evaluation function and we devise a general procedure for learning such evaluations. First tests on a few classical examples substantiate the chosen game model and our algorithm.

  @inproceedings{KS10,
       author = {\L{}ukasz Kaiser and \L{}ukasz Stafiniak},
       title = {Playing Structure Rewriting Games},
       booktitle = {Proceedings of AGI~'10},
       publisher = {Atlantis Press},
       year = {2010},
       url = {/pub/playing_structure_rewriting_games.pdf},
  }
  

2009

• Ł. Kaiser. Synthesis for Structure Rewriting Systems. In Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, MFCS '09, vol. 5734 of LNCS, pp. 415–427. Springer, 2009.                                 
  Abstract   BibTeX

  The description of a single state of a modelled system is often complex in practice, but few procedures for synthesis address this problem in depth. We study systems in which a state is described by an arbitrary finite structure, and changes of the state are represented by structure rewriting rules, a generalisation of term and graph rewriting. Both the environment and the controller are allowed to change the structure in this way, and the question we ask is how a strategy for the controller that ensures a given property can be synthesised. We focus on one particular class of structure rewriting rules, namely on separated structure rewriting, a limited syntactic class of rules. To counter this restrictiveness, we allow the property to be ensured by the controller to be specified in a very expressive logic: a combination of monadic second-order logic evaluated on states and the modal $\mu$-calculus for the temporal evolution of the whole system. We show that for the considered class of rules and this logic, it can be decided whether the controller has a strategy ensuring a given property, and in such case a finite-memory strategy can be synthesised. Additionally, we prove that the same holds if the property is given by a monadic second-order formula to be evaluated on the limit of the evolution of the system.

  @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 = {/pub/graph_games_short.pdf},
  }
  

2012 Talk

• Toss. Learning and Playing Board Games from the FMT Perspective. In FMT Workshop, Les Houches, 2012 Talk.             
  BibTeX

  @inproceedings{KFMT12,
       author = {Toss},
       title = {Learning and Playing Board Games from the FMT Perspective},
       url = {/pub/fmt12_slides.pdf},
       booktitle = {FMT Workshop, Les Houches},
       year = {2012 Talk},
  }
  

• Toss. Quantitative Logics on Structure Rewriting Systems. In EPI Contraintes Seminar, INRIA Paris-Rocquencourt, 2012 Talk.             
  BibTeX

  @inproceedings{KCONSTRAINTES12,
       author = {Toss},
       title = {Quantitative Logics on Structure Rewriting Systems},
       url = {/pub/contraintes_slides.pdf},
       booktitle = {EPI Contraintes Seminar, INRIA Paris-Rocquencourt},
       year = {2012 Talk},
  }
  

2011 Talk

• Toss. First Order Logic with Counting for General Game Playing. In AAAI-11, San Francisco, 2011 Talk.             
  BibTeX

  @inproceedings{KAAAI11,
       author = {Toss},
       title = {First Order Logic with Counting for General Game Playing},
       url = {/pub/aaai11_slides.pdf},
       booktitle = {AAAI-11, San Francisco},
       year = {2011 Talk},
  }
  

• Toss. Artificial General Game Intelligence. In AGI, Mountain View, 2011 Talk.             
  BibTeX

  @inproceedings{KAGI11,
       author = {Toss},
       title = {Artificial General Game Intelligence},
       url = {/pub/agi11_demo_slides.pdf},
       booktitle = {AGI, Mountain View},
       year = {2011 Talk},
  }
  

• Toss. Artificial General Game Intelligence - Poster. In AGI, Mountain View, 2011 Talk.             
  BibTeX

  @inproceedings{KAGI11POSTER,
       author = {Toss},
       title = {Artificial General Game Intelligence - Poster},
       url = {/pub/agi11_poster.pdf},
       booktitle = {AGI, Mountain View},
       year = {2011 Talk},
  }
  

• Toss. First Order Logic with Counting for General Game Playing. In GIGA Workshop, Barcelona, 2011 Talk.             
  BibTeX

  @inproceedings{KGIGA11,
       author = {Toss},
       title = {First Order Logic with Counting for General Game Playing},
       url = {/pub/giga11_slides.pdf},
       booktitle = {GIGA Workshop, Barcelona},
       year = {2011 Talk},
  }
  

2010 Talk

• Toss. Playing Games when States have Rich Structure. In GT Jeux Meeting, Paris, 2010 Talk.             
  BibTeX

  @inproceedings{KGTJ10,
       author = {Toss},
       title = {Playing Games when States have Rich Structure},
       url = {/pub/playing_games_rich_structure_short.pdf},
       booktitle = {GT Jeux Meeting, Paris},
       year = {2010 Talk},
  }
  

• Toss. New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures. In CSL, Brno, and similar at Games Meeting, Oxford, 2010 Talk.             
  BibTeX

  @inproceedings{KCSL10,
       author = {Toss},
       title = {New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures},
       url = {/pub/wmso_composition_alg.pdf},
       booktitle = {CSL, Brno, and similar at Games Meeting, Oxford},
       year = {2010 Talk},
  }
  

• Toss. Games with Structured States. In LIAFA Seminar, Paris, 2010 Talk.             
  BibTeX

  @inproceedings{KLIAFA10,
       author = {Toss},
       title = {Games with Structured States},
       url = {/pub/games_with_structured_states.pdf},
       booktitle = {LIAFA Seminar, Paris},
       year = {2010 Talk},
  }
  

• Toss. Playing General Structure Rewriting Games. In AGI, Lugano, 2010 Talk.             
  BibTeX

  @inproceedings{KAGI10,
       author = {Toss},
       title = {Playing General Structure Rewriting Games},
       url = {/pub/playing_general_games.pdf},
       booktitle = {AGI, Lugano},
       year = {2010 Talk},
  }
  

2009 Talk

• Toss. Playing Games when States have Rich Structure. In Invited talk at STAR Workshop, Kanpur IIT, India, 2009 Talk.             
  BibTeX

  @inproceedings{KSTAR09,
       author = {Toss},
       title = {Playing Games when States have Rich Structure},
       url = {/pub/playing_games_rich_structure.pdf},
       booktitle = {Invited talk at STAR Workshop, Kanpur IIT, India},
       year = {2009 Talk},
  }
  

• Toss. Playing Structure Rewriting Games with Formulas on States. In AlgoSyn Seminar, Aachen, 2009 Talk.             
  BibTeX

  @inproceedings{KALGO09,
       author = {Toss},
       title = {Playing Structure Rewriting Games with Formulas on States},
       url = {/pub/playing_games_formulas.pdf},
       booktitle = {AlgoSyn Seminar, Aachen},
       year = {2009 Talk},
  }
  

• Toss. Synthesis for Structure Rewriting Systems. In MFCS, High Tatras, 2009 Talk.             
  BibTeX

  @inproceedings{KMFCS09,
       author = {Toss},
       title = {Synthesis for Structure Rewriting Systems},
       url = {/pub/structure_rewriting_mfcs.pdf},
       booktitle = {MFCS, High Tatras},
       year = {2009 Talk},
  }
  

• Toss. Structure Rewriting Games. In LSV Seminar (Cachan), and similar at AAL Workshop (Stuttgart), 2009 Talk.             
  BibTeX

  @inproceedings{KLSV09,
       author = {Toss},
       title = {Structure Rewriting Games},
       url = {/pub/structure_rewriting_games.pdf},
       booktitle = {LSV Seminar (Cachan), and similar at AAL Workshop (Stuttgart)},
       year = {2009 Talk},
  }
  

• Toss. Analyzing Structure Rewriting Systems. In AlgoSyn Seminar (Aachen), and similar at Automat (Warsaw), 2009 Talk.             
  BibTeX

  @inproceedings{KAUTO09,
       author = {Toss},
       title = {Analyzing Structure Rewriting Systems},
       url = {/pub/structure_rewriting.pdf},
       booktitle = {AlgoSyn Seminar (Aachen), and similar at Automat (Warsaw)},
       year = {2009 Talk},
  }
  

2008 Talk

• Toss. Games Played with Hypergraphs. In Games Meeting, Warsaw, 2008 Talk.             
  BibTeX

  @inproceedings{KGAMES08,
       author = {Toss},
       title = {Games Played with Hypergraphs},
       url = {/pub/hypergraph_games_warsaw.pdf},
       booktitle = {Games Meeting, Warsaw},
       year = {2008 Talk},
  }
  

• Toss. Analysis of Hypergraph Rewriting Systems. In ZJP Seminar, Wrocław, 2008 Talk.             
  BibTeX

  @inproceedings{KZJP08,
       author = {Toss},
       title = {Analysis of Hypergraph Rewriting Systems},
       url = {/pub/hypergraph_rewriting_systems.pdf},
       booktitle = {ZJP Seminar, Wroc{\l}aw},
       year = {2008 Talk},
  }