login
Table read by ascending antidiagonals. T(n,k) is the Sprague-Grundy value for the Heat Toggle game played on an n X k grid where each vertex has initial weight 1.
2

%I #14 Aug 05 2023 23:52:00

%S 1,1,1,1,1,1,2,2,2,2,2,0,1,0,2,0,3,1,1,3,0,3,1,3,0,3,1,3,1,1,0,1,1,0,

%T 1,1,1,0,2,0,2,0,2,0,1,2,3,0,0,0,0,0,0,3,2,2,3,1,1

%N Table read by ascending antidiagonals. T(n,k) is the Sprague-Grundy value for the Heat Toggle game played on an n X k grid where each vertex has initial weight 1.

%C Heat Toggle is an impartial two-player game played on a simple graph, where each vertex is assigned a weight of -1 or 1.

%C A Heat Toggle move consists of selecting a vertex of weight 1 and switching its weight to -1 as well as switching the weight of each of its neighbors, changing 1 to -1 and -1 to 1. We additionally only allow moves that strictly decrease the sum of all weights.

%C The first row T(1,k) coincides with octal game 0.1337, see A071427.

%C The second row T(2,k) coincides with the octal game 0.137 (Dawson's Chess), see A002187.

%D E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.

%H E. Fiorini, M. Lind, A. Woldar, and T. W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Wong/wong31.pdf">Characterizing Winning Positions in the Impartial Two-player Pebbling Game on Complete Graphs</a>, Journal of Integer Sequences 24(6), (2021).

%e The data is organized in a table beginning with row n = 1 and column k = 1. The data is read by ascending antidiagonals. T(2,3)=2.

%e The table T(n,k) begins:

%e [n/k] 1 2 3 4 5 6 ...

%e ---------------------------------

%e [1] 1, 1, 1, 2, 2, 0, ...

%e [2] 1, 1, 2, 0, 3, 1, ...

%e [3] 1, 2, 1, 1, 3, 0, ...

%e [4] 2, 0, 1, 0, 1, 0, ...

%e [5] 2, 3, 3, 1, 2, 0, ...

%e [6] 0, 1, 0, 0, 0, ...

%o (Sage) SG_value_hash = {}

%o def MEX(S):

%o i = 0

%o while True:

%o if i not in S:

%o return i

%o i += 1

%o def SG_value(G):

%o global SG_value_hash

%o SG_value_hash = {}

%o ons = set(G.vertices())

%o offs = set()

%o return SG_value_helper(G, ons, offs)

%o def SG_value_helper(G, ons, offs):

%o ons_orig = ons.copy()

%o offs_orig = offs.copy()

%o child_SG_values = set()

%o for v in ons_orig:

%o vNeighborhood = set(G.neighbors(v))

%o neighNowOff = ons_orig.intersection(vNeighborhood)

%o neighNowOn = offs_orig.intersection(vNeighborhood)

%o if len(neighNowOff) >= len(neighNowOn):

%o ons.remove(v)

%o offs.add(v)

%o ons.update(neighNowOn)

%o offs -= neighNowOn

%o offs.update(neighNowOff)

%o ons -= neighNowOff

%o result = -1 # placeholder

%o encoded_position = str(offs)

%o if encoded_position in SG_value_hash:

%o result = SG_value_hash[encoded_position]

%o else:

%o result = SG_value_helper(G, ons, offs)

%o SG_value_hash[encoded_position] = result

%o ons.add(v)

%o offs.remove(v)

%o ons -= neighNowOn

%o offs.update(neighNowOn)

%o offs -= neighNowOff

%o ons.update(neighNowOff)

%o child_SG_values.add(result)

%o return MEX(child_SG_values)

%o for sum_of_both in range(2,11):

%o antidiagonal = []

%o for n in range(1, sum_of_both):

%o G = graphs.Grid2dGraph(n, sum_of_both-n)

%o antidiagonal.append(SG_value(G))

%o print(antidiagonal)

%Y Cf. A361517, A071427, A002187.

%K nonn,tabl,more

%O 1,7

%A _Jean-Pierre Appel_, _Patrick G. Cesarz_, _Djeneba Diop_, _Eugene Fiorini_, _Nathan Hurtig_, _Andrew Woldar_, Jun 28 2023