File size: 7,321 Bytes
b77d5ed
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
"""Batched 2048 on torch tensors. Boards are (B,4,4) int64 tile exponents (0 = empty).

Action order everywhere in this repo: 0=UP 1=DOWN 2=LEFT 3=RIGHT.
Every move is reduced to "slide the rows left" on a transformed view and one
row lookup table (18^4 rows) does the work, so thousands of games step in parallel.
"""
import torch

ACTIONS = ("UP", "DOWN", "LEFT", "RIGHT")
V = 18                      # exponents 0..17 (131072 is the largest possible tile)
POW = torch.tensor([V**3, V**2, V, 1])


def _build_row_table():
    n = V**4
    new = torch.zeros(n, 4, dtype=torch.int64)
    rew = torch.zeros(n, dtype=torch.int64)
    for code in range(n):
        row = [(code // V**(3 - i)) % V for i in range(4)]
        tiles = [t for t in row if t]
        out, r, i = [], 0, 0
        while i < len(tiles):
            if i + 1 < len(tiles) and tiles[i] == tiles[i + 1] and tiles[i] < V - 1:
                out.append(tiles[i] + 1); r += 1 << (tiles[i] + 1); i += 2
            else:
                out.append(tiles[i]); i += 1
        new[code] = torch.tensor(out + [0] * (4 - len(out)))
        rew[code] = r
    return new, rew


_TABLES = {}


def tables(device):
    if device not in _TABLES:
        if "cpu" not in _TABLES:
            _TABLES["cpu"] = _build_row_table()
        _TABLES[device] = tuple(t.to(device) for t in _TABLES["cpu"])
    return _TABLES[device]


def _views(b):  # (B,4,4) -> (B,4,4,4): each action as a left-slide view
    t = b.transpose(-1, -2)
    return torch.stack([t, t.flip(-1), b, b.flip(-1)], 1)


def _unview(v):  # inverse of _views, v: (B,4,4,4)
    return torch.stack([v[:, 0].transpose(-1, -2), v[:, 1].flip(-1).transpose(-1, -2),
                        v[:, 2], v[:, 3].flip(-1)], 1)


def all_afterstates(b):
    """b (B,4,4) -> after (B,4,4,4), reward (B,4), legal (B,4) bool."""
    new_t, rew_t = tables(str(b.device))
    idx = (_views(b) * POW.to(b.device)).sum(-1)          # (B,4,4)
    after = _unview(new_t[idx])
    reward = rew_t[idx].sum(-1)
    legal = (after != b[:, None]).flatten(2).any(-1)
    return after, reward, legal


def spawn(b, gen=None):
    """Put a 2 (p=.9) or 4 at a random empty cell of every board that has one."""
    flat = b.flatten(1).clone()
    empty = flat == 0
    r = torch.rand(flat.shape, device=b.device, generator=gen).masked_fill(~empty, -1)
    pos = r.argmax(1)
    val = 1 + (torch.rand(len(flat), device=b.device, generator=gen) < 0.1).long()
    has = empty.any(1)
    flat[has, pos[has]] = val[has]
    return flat.view_as(b)


def reset(n, device="cpu", gen=None):
    return spawn(spawn(torch.zeros(n, 4, 4, dtype=torch.int64, device=device), gen), gen)


# ---------------------------------------------------------------- features
def board_stats(b):
    """Hand-made geometric features of boards (...,4,4) -> (...,8), roughly in [0,1]."""
    f = b.float()
    empties = (b == 0).flatten(-2).sum(-1).float() / 16
    mx = f.flatten(-2).max(-1).values
    corners = torch.stack([f[..., 0, 0], f[..., 0, 3], f[..., 3, 0], f[..., 3, 3]], -1)
    max_in_corner = (corners.max(-1).values == mx).float()
    dr, dc = f[..., :, 1:] - f[..., :, :-1], f[..., 1:, :] - f[..., :-1, :]
    # monotonicity: per line, how much of the variation goes one way
    def mono(d):
        inc, dec = d.clamp(min=0).sum(-1), (-d).clamp(min=0).sum(-1)
        tot = inc + dec
        return torch.where(tot > 0, torch.maximum(inc, dec) / tot.clamp(min=1e-6), torch.ones_like(tot)).mean(-1)
    mono_r, mono_c = mono(dr), mono(dc.transpose(-1, -2))
    nz_r, nz_c = (b[..., :, 1:] > 0) & (b[..., :, :-1] > 0), (b[..., 1:, :] > 0) & (b[..., :-1, :] > 0)
    smooth = -((dr.abs() * nz_r).sum((-1, -2)) + (dc.abs() * nz_c).sum((-1, -2))) / (24 * 17)
    merges = (((dr == 0) & nz_r).sum((-1, -2)) + ((dc == 0) & nz_c).sum((-1, -2))).float() / 24
    return torch.stack([empties, mx / 17, max_in_corner, mono_r, mono_c, smooth, merges,
                        f.flatten(-2).sum(-1) / (16 * 17)], -1)


N_ACT_FEATS = 2 + 8 + 4   # legal, reward, afterstate stats, "can merge again" per next action


def action_features(b):
    """The 'enriched state': for each of the 4 moves, what the afterstate looks like.
    Returns feats (B,4,N_ACT_FEATS), legal (B,4), after (B,4,4,4), reward (B,4)."""
    after, reward, legal = all_afterstates(b)
    B = b.shape[0]
    stats = board_stats(after)                                      # (B,4,8)
    _, r2, l2 = all_afterstates(after.reshape(B * 4, 4, 4))        # one more ply, no spawn
    look = (r2.float().log1p() / 17 * l2).view(B, 4, 4)
    feats = torch.cat([legal.float()[..., None], (reward.float().log1p() / 17)[..., None], stats, look], -1)
    return feats * legal[..., None], legal, after, reward


# ---------------------------------------------------------------- symmetry (D4)
# Each transform maps a board to a board; PERM[k][a] = the action that a becomes.
def sym(b, k):
    if k >= 4:
        b = b.flip(-1)
    return torch.rot90(b, k % 4, (-2, -1))


def _action_perm():
    perms = []
    probe = torch.arange(16).view(1, 4, 4)
    for k in range(8):
        # find where each action maps by checking the transformed "direction" of a gradient board
        p = []
        for a in range(4):
            g = torch.zeros(1, 4, 4, dtype=torch.int64)
            # board whose only legal move is direction a: a lone tile at the far side
            if a == 0: g[0, 3, 1] = 1
            if a == 1: g[0, 0, 1] = 1
            if a == 2: g[0, 1, 3] = 1
            if a == 3: g[0, 1, 0] = 1
            after, _, _ = all_afterstates(g)
            target = sym(after[:, a], k)
            sb = sym(g, k)
            after2, _, legal2 = all_afterstates(sb)
            hits = [c for c in range(4) if legal2[0, c] and torch.equal(after2[0, c], target[0])]
            p.append(hits[0])
        perms.append(p)
    del probe
    return torch.tensor(perms)


SYM_PERM = None


def sym_perm():
    global SYM_PERM
    if SYM_PERM is None:
        SYM_PERM = _action_perm()
    return SYM_PERM


def score_of(b):
    """Lower bound score implied by a board (assumes every spawn was a 2)."""
    f = b.float()
    return torch.where(b > 1, (f - 1) * torch.exp2(f), torch.zeros_like(f)).flatten(1).sum(1)


if __name__ == "__main__":
    b = torch.tensor([[[1, 1, 2, 2], [0, 0, 0, 0], [3, 0, 3, 0], [1, 2, 1, 2]]])
    after, rew, legal = all_afterstates(b)
    assert after[0, 2].tolist() == [[2, 3, 0, 0], [0, 0, 0, 0], [4, 0, 0, 0], [1, 2, 1, 2]], after[0, 2]
    assert after[0, 3].tolist() == [[0, 0, 2, 3], [0, 0, 0, 0], [0, 0, 0, 4], [1, 2, 1, 2]]
    assert rew[0, 2] == 4 + 8 + 16 and rew[0, 3] == 4 + 8 + 16
    assert after[0, 0, :, 0].tolist() == [1, 3, 1, 0] and legal.all()
    P = sym_perm()
    assert all(sorted(p.tolist()) == [0, 1, 2, 3] for p in P)
    # symmetry consistency on random boards
    g = torch.Generator().manual_seed(0)
    bs = torch.randint(0, 6, (64, 4, 4), generator=g)
    a0, r0, _ = all_afterstates(bs)
    for k in range(8):
        ak, rk, _ = all_afterstates(sym(bs, k))
        for a in range(4):
            assert torch.equal(ak[:, P[k, a]], sym(a0[:, a], k)) and torch.equal(rk[:, P[k, a]], r0[:, a])
    f, l, _, _ = action_features(bs)
    assert f.shape == (64, 4, N_ACT_FEATS) and torch.isfinite(f).all()
    print("env ok", P.tolist())