Bounding game temperature using confusion intervals

DOI10.1016/J.TCS.2020.11.015MaRDI QIDQ2220877zbMATH OpenOpenAlexFDO

Authors Svenja Huntemann, R. J. Nowakowski, Carlos Pereira dos Santos

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.08471

zbMATH Keywords

boiling point combinatorial game domineering snort temperature

Mathematics Subject Classification ID

Combinatorial games (91A46)

Abstract: For combinatorial games, temperature is a measure of the volatility, that is, by how much the advantage can change. Typically, the temperature has been measured for individual positions within specific games. In this paper, we give the first general upper bounds on the temperature for any class of games. For a position

G

, the closure of the set of numbers

g

such that

G - g

is a first player win, is called the confusion interval of

G

. Let

e l l (G)

be the length of this interval. Our first main result is: For a class of games

m a t h s c r S

, if there are constants

J

and

K

such that

e l l (G^{L}), e l l (G^{R}) l e q J

and

e l l (G) l e q K

for for every

G i n m a t h s c r S

, then the temperature of every game is bounded by

K / 2 + J

. We give an example to show that this bound is tight. Our second main result is a method to find a bound for the confusion intervals. In

G^{L} - G

when Left gets to go first, the number of passing moves required by Right to win gives an upper bound on

e l l (G)

. This is the first general upper bound on temperature. As examples of the bound and the method, we give upper bounds on the temperature of subclasses of Domineering and Snort.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Bounding game temperature using confusion intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220877)