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.

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

Author

Jean-Pierre Appel, Patrick G. Cesarz, Djeneba Diop, Eugene Fiorini, Nathan Hurtig, Andrew Woldar, Jun 28 2023

Keywords

• nonn
• tabl
• more

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.

Examples

			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,  ...
		

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).

Crossrefs

Cf. A361517, A071427, A002187.

Programs

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)