%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