Author name cluster

Marek Szykuła

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

AAAI Conference 2026 Conference Paper

Regular Games -- an Automata-Based General Game Playing Language

Radosław Miernik
Marek Szykuła
Jakub Kowalski
Jakub Cieśluk
Łukasz Galas
Wojciech Pawlik

We propose a new General Game Playing (GGP) system called Regular Games (RG). The main goal of RG is to be both computationally efficient and convenient for game design. The system consists of several languages. The core component is a low-level language that defines the rules by a finite automaton. It is minimal with only a few mechanisms, which makes it easy for automatic processing (by agents, analysis, optimization, etc.). The language is universal for the class of all finite turn-based games with imperfect information. Higher-level languages are introduced for game design (by humans or Procedural Content Generation), which are eventually translated to a low-level language. RG generates faster forward models than the current state of the art, beating other GGP systems (Regular Boardgames, Ludii) in terms of efficiency. Additionally, RG's ecosystem includes an editor with LSP, automaton visualization, benchmarking tools, and a debugger of game description transformations.

PDF Details DOI

AAAI Conference 2024 Short Paper

Fast and Knowledge-Free Deep Learning for General Game Playing (Student Abstract)

Michał Maras
Michał Kępa
Jakub Kowalski
Marek Szykuła

We develop a method of adapting the AlphaZero model to General Game Playing (GGP) that focuses on faster model generation and requires less knowledge to be extracted from the game rules. The dataset generation uses MCTS playing instead of self-play; only the value network is used, and attention layers replace the convolutional ones. This allows us to abandon any assumptions about the action space and board topology. We implement the method within the Regular Boardgames GGP system and show that we can build models outperforming the UCT baseline for most games efficiently.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Split Moves for Monte-Carlo Tree Search

Jakub Kowalski
Maksymilian Mika
Wojciech Pawlik
Jakub Sutowicz
Marek Szykuła
Mark H. M. Winands

In many games, moves consist of several decisions made by the player. These decisions can be viewed as separate moves, which is already a common practice in multi-action games for efficiency reasons. Such division of a player move into a sequence of simpler / lower level moves is called splitting. So far, split moves have been applied only in forementioned straightforward cases, and furthermore, there was almost no study revealing its impact on agents’ playing strength. Taking the knowledge-free perspective, we aim to answer how to effectively use split moves within Monte-Carlo Tree Search (MCTS) and what is the practical impact of split design on agents’ strength. This paper proposes a generalization of MCTS that works with arbitrarily split moves. We design several variations of the algorithm and try to measure the impact of split moves separately on efficiency, quality of MCTS, simulations, and action-based heuristics. The tests are carried out on a set of board games and performed using the Regular Boardgames General Game Playing formalism, where split strategies of different granularity can be automatically derived based on an abstract description of the game. The results give an overview of the behavior of agents using split design in different ways. We conclude that split design can be greatly beneficial for single- as well as multi-action games.

PDF Details

TCS Journal 2019 Journal Article

Complexity of bifix-free regular languages

Robert Ferens
Marek Szykuła

We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that there exist universal bifix-free languages that meet all the bounds for the state complexity of basic operations (Boolean operations, product, star, and reversal). This is in contrast with suffix-free languages, where it is known that there does not exist such languages. Then we present a stream of bifix-free languages that is most complex in terms of all basic operations, syntactic complexity, and the number of atoms and their complexities, which requires a superexponential alphabet. We also complete the previous results by characterizing the state complexity of product, star, and reversal, and establishing tight upper bounds for atom complexities of bifix-free languages. Moreover, we consider the problem of the minimal size of an alphabet required to meet the bounds and the problem of attainable values of state complexities (magic numbers).

Details DOI

AAAI Conference 2019 Conference Paper

Regular Boardgames

Jakub Kowalski
Maksymilian Mika
Jakub Sutowicz
Marek Szykuła

We propose a new General Game Playing (GGP) language called Regular Boardgames (RBG), which is based on the theory of regular languages. The objective of RBG is to join key properties as expressiveness, efficiency, and naturalness of the description in one GGP formalism, compensating certain drawbacks of the existing languages. This often makes RBG more suitable for various research and practical developments in GGP. While dedicated mostly for describing board games, RBG is universal for the class of all finite deterministic turn-based games with perfect information. We establish foundations of RBG, and analyze it theoretically and experimentally, focusing on the efficiency of reasoning. Regular Boardgames is the first GGP language that allows efficient encoding and playing games with complex rules and with large branching factor (e. g. amazons, arimaa, large chess variants, go, international checkers, paper soccer).

PDF Details

TCS Journal 2019 Journal Article

Syntactic complexity of bifix-free regular languages

Marek Szykuła
John Wittnebel

We study the properties of syntactic monoids of bifix-free regular languages. In particular, we solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a bifix-free language with state complexity n is at most ( n − 1 ) n − 3 + ( n − 2 ) n − 3 + ( n − 3 ) 2 n − 3 for n ⩾ 6. The main proof uses a large construction with the method of injective function. Since this bound is known to be reachable, and the values for n ⩽ 5 are known, this completely settles the problem. We also prove that ( n − 2 ) n − 3 + ( n − 3 ) 2 n − 3 − 1 is the minimal size of the alphabet required to meet the bound for n ⩾ 6. Finally, we show that the largest transition semigroups of minimal DFAs which recognize bifix-free languages are unique up to renaming the states.

Details DOI

I&C Journal 2018 Journal Article

Syntactic complexity of suffix-free languages

Janusz A. Brzozowski
Marek Szykuła

We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with n left quotients (that is, with state complexity n) is at most ( n − 1 ) n − 2 + n − 2 for n ⩾ 6. Since this bound is known to be reachable, this settles the problem. We also reduce the alphabet of the witness languages reaching this bound to five letters instead of n + 2, and show that it cannot be any smaller. Finally, we prove that the transition semigroup of a minimal deterministic automaton accepting a witness language is unique for each n.

Details DOI