Author name cluster

Urban Larsson

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.

6 papers

1 author row

TCS Journal 2024 Journal Article

Subtraction games in more than one dimension

Urban Larsson
Indrajit Saha
Makoto Yokoo

This paper concerns two-player alternating play combinatorial games (Conway 1976) in the normal-play convention, i. e. last move wins. Specifically, we study impartial vector subtraction games on tuples of nonnegative integers (Golomb 1966), with finite subtraction sets. In case of two move rulesets we find a complete solution, via a certain P -to- P principle (where P means that the previous player wins). Namely x ∈ P if and only if x + a + b ∈ P, where a and b are the two move options. Flammenkamp (1997) observed that, already in one dimension, rulesets with three moves can be hard to analyze, and still today his related conjecture remains open. Here, we solve instances of rulesets with three moves in two dimensions, and conjecture that they all have regular outcomes. Through several computer visualizations of outcomes of multi-move two-dimensional rulesets, we observe that they tend to partition the game board into periodic mosaics on very few regions/segments, which can depend on the number of moves in a ruleset. For example, we have found a five-move ruleset with an outcome segmentation into six semi-infinite slices. In this spirit, we develop a coloring automaton that generalizes the P -to- P principle. Given an initial set of colored positions, it quickly paints the P -positions in segments of the game board. Moreover, we prove that two-dimensional rulesets have row/column eventually periodic outcomes. We pose open problems on the generic hardness of two-dimensional rulesets; several regularity conjectures are provided, but we also conjecture that not all rulesets have regular outcomes.

Details DOI

TCS Journal 2021 Journal Article

Golden games

Urban Larsson
Yakov Babichenko

We consider extensive form 2-player win-lose games, with alternating moves, of perfect and complete information. The games are played over a complete binary-tree of depth n, where 0/1 payoffs in the leaves are drawn according to an i. i. d. Bernoulli distribution with probability p. Whenever p differs from the golden ratio, asymptotically as n → ∞, the winner of the game is determined. In the case where p equals the golden ratio, we call such a random game a golden game. In golden games the winner is the player that acts first with probability equal to the golden ratio. We suggest the notion of fragility as a measure for “fairness” of a game's rules. Fragility counts how many leaves' payoffs should be flipped in order to convert the identity of the winning player. Our main result provides a recursive formula for asymptotic fragility of golden games. Surprisingly, golden games are extremely fragile. For instance, with probability ≈0. 77 a losing player could flip a single payoff (out of 2 n ) and become a winner. With probability ≈0. 999 a losing player could flip 3 payoffs and become the winner.

Details DOI

TCS Journal 2018 Journal Article

Game comparison through play

Urban Larsson
Richard J. Nowakowski
Carlos P. Santos

Absolute Universes of Combinatorial Games, as defined in a recent paper by the same authors, include many standard short Normal- Misère- and Scoring-play monoids. Given G and H in an Absolute Universe U, we define a dual Normal-play game, called the Left Provisonal Game [ G, H ], and show that G ≽ H if and only if Left wins [ G, H ] playing second. As an example of our construction, we show how to compare Dicot Misère-play games in Siegel's computer program CGSuite and illustrate by including the partial order of all games of rank 2. We also show that Joyal's Normal-play Category generalizes to every Absolute Universe U, and we define the associated categories LNP ( U ).

Details DOI

TCS Journal 2018 Journal Article

The switch operators and push-the-button games: A sequential compound over rulesets

Eric Duchêne
Marc Heinrich
Urban Larsson
Aline Parreau

We study operators that combine combinatorial games. This field was initiated by Sprague–Grundy (1930s), Milnor (1950s) and Berlekamp–Conway–Guy (1970–80s) via the now classical disjunctive sum operator on (abstract) games. The new class consists in operators for rulesets, dubbed the switch-operators. The ordered pair of rulesets ( R 1, R 2 ) is compatible if, given any position in R 1, there is a description of how to move in R 2. Given compatible ( R 1, R 2 ), we build the push-the-button game R 1 ⊚ R 2, where players start by playing according to the rules R 1, but at some point during play, one of the players must switch the rules to R 2, by pushing the button ‘⊚’. Thus, the game ends according to the terminal condition of ruleset R 2. We study the pairwise combinations of the classical rulesets Nim, Wythoff and Euclid. In addition, we prove that standard periodicity results for Subtraction games transfer to this setting, and we give partial results for a variation of Domineering, where R 1 is the game where the players put the domino tiles horizontally and R 2 the game where they play vertically (thus generalizing the octal game 0. 07).

Details DOI

TCS Journal 2012 Journal Article

The ⋆ -operator and invariant subtraction games

Urban Larsson

An invariant subtraction game is a 2-player impartial game defined by a set of invariant moves ( k -tuples of non-negative integers) M. Given a position (another k -tuple) x = ( x 1, …, x k ), each option is of the form ( x 1 − m 1, …, x k − m k ), where m = ( m 1, …, m k ) ∈ M, and where x i − m i ≥ 0, for all i. Two players alternate in moving and the player who moves last wins. The set of non-zero P-positions of the game M defines the moves in the dual game M ⋆. For example, in the game of (2-pile Nim) ⋆ a move consists in removing the same positive number of tokens from both piles. Our main results concern a double application of ⋆, the operation M → ( M ⋆ ) ⋆. We establish a fundamental ‘convergence’ result for this operation. Then, we give necessary and sufficient conditions for the relation M = ( M ⋆ ) ⋆ to hold, as is the case for example with M = k -pile Nim.

Details DOI

TCS Journal 2011 Journal Article

Invariant and dual subtraction games resolving the Duchêne–Rigo conjecture

Urban Larsson
Peter Hegarty
Aviezri S. Fraenkel

We prove a recent conjecture of Duchêne and Rigo, stating that every complementary pair of homogeneous Beatty sequences represents the solution to an invariant impartial game. Here invariance means that each available move in a game can be played anywhere inside the game board. In fact, we establish such a result for a wider class of pairs of complementary sequences, and in the process generalize the notion of a subtraction game. Given a pair of complementary sequences ( a n ) and ( b n ) of positive integers, we define a game G by setting { { a n, b n } } as invariant moves. We then introduce the invariant game G ⋆, whose moves are all non-zero P -positions of G. Provided the set of non-zero P -positions of G ⋆ equals { { a n, b n } }, this is the desired invariant game. We give sufficient conditions on the initial pair of sequences for this ‘duality’ to hold.

Details DOI