login
A363934
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
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, 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
OFFSET
1,7
COMMENTS
Heat Toggle is an impartial two-player game played on a simple graph, where each vertex is assigned a weight of -1 or 1.
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.
The first row T(1,k) coincides with octal game 0.1337, see A071427.
The second row T(2,k) coincides with the octal game 0.137 (Dawson's Chess), see A002187.
REFERENCES
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
LINKS
E. Fiorini, M. Lind, A. Woldar, and T. W. H. Wong, Characterizing Winning Positions in the Impartial Two-player Pebbling Game on Complete Graphs, Journal of Integer Sequences 24(6), (2021).
EXAMPLE
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.
The table T(n,k) begins:
[n/k] 1 2 3 4 5 6 ...
---------------------------------
[1] 1, 1, 1, 2, 2, 0, ...
[2] 1, 1, 2, 0, 3, 1, ...
[3] 1, 2, 1, 1, 3, 0, ...
[4] 2, 0, 1, 0, 1, 0, ...
[5] 2, 3, 3, 1, 2, 0, ...
[6] 0, 1, 0, 0, 0, ...
PROG
(Sage) SG_value_hash = {}
def MEX(S):
i = 0
while True:
if i not in S:
return i
i += 1
def SG_value(G):
global SG_value_hash
SG_value_hash = {}
ons = set(G.vertices())
offs = set()
return SG_value_helper(G, ons, offs)
def SG_value_helper(G, ons, offs):
ons_orig = ons.copy()
offs_orig = offs.copy()
child_SG_values = set()
for v in ons_orig:
vNeighborhood = set(G.neighbors(v))
neighNowOff = ons_orig.intersection(vNeighborhood)
neighNowOn = offs_orig.intersection(vNeighborhood)
if len(neighNowOff) >= len(neighNowOn):
ons.remove(v)
offs.add(v)
ons.update(neighNowOn)
offs -= neighNowOn
offs.update(neighNowOff)
ons -= neighNowOff
result = -1 # placeholder
encoded_position = str(offs)
if encoded_position in SG_value_hash:
result = SG_value_hash[encoded_position]
else:
result = SG_value_helper(G, ons, offs)
SG_value_hash[encoded_position] = result
ons.add(v)
offs.remove(v)
ons -= neighNowOn
offs.update(neighNowOn)
offs -= neighNowOff
ons.update(neighNowOff)
child_SG_values.add(result)
return MEX(child_SG_values)
for sum_of_both in range(2, 11):
antidiagonal = []
for n in range(1, sum_of_both):
G = graphs.Grid2dGraph(n, sum_of_both-n)
antidiagonal.append(SG_value(G))
print(antidiagonal)
CROSSREFS
KEYWORD
nonn,tabl,more
STATUS
approved