Сохранения: хеш Зобриста и цена совпадения

Если ты умеешь обновлять хеш позиции на ходу через XOR и знаешь, когда совпадение хешей станет вероятным, листай до «Теперь сам».

Как думаешь, сколько стоит «уже было?»

ИИ противника перебирает ходы и встречает одну и ту же позицию, пришедшую разными путями: сначала конь, потом слон - или наоборот. Чтобы не оценивать её дважды, он хранит оценённые позиции в словаре. Ключ словаря - вся карта? Сколько стоит такой ключ на каждом шаге перебора?

Ответь себе до чтения. Ключ «вся карта» - это 256 клеток: построить его, захешировать и сравнить стоит сотни операций на КАЖДЫЙ шаг перебора, а шагов миллионы. Между двумя соседними позициями отличаются две клетки. Если хеш позиции можно поправить по этим двум клеткам, а не считать заново, ключ будет стоить несколько операций.

На что это похоже

Касса в магазине. Кассир не пересчитывает всю корзину, когда ты добавил шоколадку: к сумме прибавляется её цена, а если выложил - вычитается. Хеш Зобриста - та же сумма, только «прибавить» и «вычесть» у него одна операция XOR: применённая дважды, она отменяет сама себя.

Механизм: XOR случайных чисел

Заранее, один раз на игру, каждой паре «клетка k, что в ней f» дают случайное число Z[k][f]. Таблицу строят из закреплённого семени генератора или хранят вместе с сохранениями: хеши, посчитанные с разными таблицами, несравнимы. Хеш позиции - XOR чисел всех клеток с тем, что в них стоит. XOR удобен двумя свойствами: он коммутативен (порядок клеток неважен) и x ^ x = 0 (повторное применение отменяет). Ход «фигура f из клетки a в пустую b» меняет хеш так: убрать Z[a][f], добавить Z[a][пусто], убрать Z[b][пусто], добавить Z[b][f] - четыре XOR, и «убрать» и «добавить» - одна и та же операция.

Хеш - не позиция: разные позиции могут получить один хеш. Если числа Z случайны и независимы, хеш ведёт себя как случайное число из 2ᵇ значений, и совпадение двух из n позиций - парадокс дней рождения из раздела 7: оно становится вероятным при n порядка √(2ᵇ). Точнее, среднее число позиций до первого совпадения - около √(π/2 · 2ᵇ). Обратно: чтобы n позиций почти наверняка не совпали, нужно 2ᵇ много больше n², то есть b - около 2 log₂ n с запасом. Поэтому для таблицы позиций ИИ на миллионы позиций берут 64 бита, а в тех местах, где ошибка дорога - запись сохранения, - совпадение хешей проверяют сравнением позиций целиком, как последнюю ступень проверки в разделе 26.

Правило

Хеш позиции, которая меняется понемногу, обновляют на ходу: хеш Зобриста - XOR случайных чисел пар «клетка, содержимое», ход стоит несколько XOR, а не пересчёт карты. Ширину хеша выбирают по числу позиций: совпадение вероятно уже при √(2ᵇ) позиций, поэтому b берут около 2 log₂ n с запасом. Где совпадение недопустимо, равные хеши проверяют сравнением позиций.

Разбор: двести ходов на карте 16 × 16

На карте до 40 фигур трёх видов (случайная клетка может выпасть дважды). Двести случайных ходов; хеш обновляется на ходу и после каждого хода сверяется с хешем, посчитанным с нуля.

import random

N = 16                # карта 16 × 16, в клетке: 0 пусто, 1-3 фигуры
random.seed(77)
# таблица Зобриста: случайное 32-битное число на каждую пару
# (клетка, фигура)
zobrist = []
for k in range(N * N):
    stroka = []
    for f in range(4):
        stroka.append(random.randint(0, 2 ** 32 - 1))
    zobrist.append(stroka)
karta = [0] * (N * N)
for i in range(40):
    karta[random.randint(0, N * N - 1)] = random.randint(1, 3)
rabota = [0, 0]

def hesh_zanovo():
    # хеш с нуля: XOR по всем клеткам - N² операций
    h = 0
    for k in range(N * N):
        rabota[0] = rabota[0] + 1
        h = h ^ zobrist[k][karta[k]]
    return h

h = hesh_zanovo()
rabota[0] = 0
vidennye = set()
vidennye.add(h)
povtory = 0
rashozhdenij = 0
hodov = 0
while hodov < 200:
    # ход: в клетку с соседним номером (по кругу номеров, а не по карте -
    # хешу это безразлично), если та пуста
    k = random.randint(0, N * N - 1)
    cel = (k + random.choice([1, N, N * N - 1, N * N - N])) % (N * N)
    if karta[k] != 0 and karta[cel] == 0:
        hodov = hodov + 1
        f = karta[k]
        # XOR снимает фигуру с клетки и ставит на другую: 4 операции
        h = h ^ zobrist[k][f] ^ zobrist[k][0]
        h = h ^ zobrist[cel][0] ^ zobrist[cel][f]
        rabota[1] = rabota[1] + 4
        karta[k] = 0
        karta[cel] = f
        if h in vidennye:
            povtory = povtory + 1
        vidennye.add(h)
        if h != hesh_zanovo():          # сверка с хешем с нуля
            rashozhdenij = rashozhdenij + 1
print("ходов:", hodov, "| расхождений с хешем с нуля:", rashozhdenij)
print("с нуля:", rabota[0], "операций | на ходу:", rabota[1])
print("разных позиций:", len(vidennye), "| повторов:", povtory)

# фигура шагнула и вернулась: XOR тех же чисел дважды отменяет сам себя
k = 0
while karta[k] == 0 or karta[(k + 1) % (N * N)] != 0:
    k = k + 1
f = karta[k]
do = h
s = (k + 1) % (N * N)                                # соседняя по кругу
h = h ^ zobrist[k][f] ^ zobrist[k][0]                # туда
h = h ^ zobrist[s][0] ^ zobrist[s][f]
h = h ^ zobrist[s][f] ^ zobrist[s][0]                # обратно
h = h ^ zobrist[k][0] ^ zobrist[k][f]
print("туда и обратно - хеш тот же:", h == do, "| позиция уже была:",
      h in vidennye)

ходов: 200 | расхождений с хешем с нуля: 0
с нуля: 51200 операций | на ходу: 800
разных позиций: 201 | повторов: 0
туда и обратно - хеш тот же: True | позиция уже была: True

Хеш на ходу совпал с хешем с нуля на всех двухстах ходах - и стоил 4 операции против 256. Двести одна разная позиция, повторов нет: случайные ходы редко возвращают карту к прошлому. Последние строки - ход туда и обратно: те же четыре числа XOR-ятся дважды и сокращаются, хеш вернулся, и повтор позиции найден одним поиском в множестве. На этом стоят автосохранение без дублей, правило «троекратного повторения» в настольных играх и таблица позиций ИИ. Граница правила: XOR годится, когда позиция - набор независимых клеток. Если в хеш нужно включить порядок (чей ход, история), его тоже кодируют своим числом: «ход белых» - ещё одно Z, которое XOR-ят на каждой смене хода. Если игроков восемь, как в «Архипелаге», у каждого своё Z: смена хода снимает число прежнего игрока и ставит число следующего.

Разбор: когда два хеша совпадут

Моделируем хеш случайным числом из 2ᵇ значений и считаем, сколько разных позиций удаётся запомнить до первого совпадения. Двадцать опытов для 16 и 20 бит; для 32 и 64 - только оценка.

import math
import random

# Сколько разных позиций можно запомнить по хешу, пока два хеша не
# совпадут? Моделируем хеш как случайное число из 2^b значений.
random.seed(4)

def do_sovpadeniya(b):
    vidennye = set()
    while True:
        h = random.randint(0, 2 ** b - 1)
        if h in vidennye:
            return len(vidennye)
        vidennye.add(h)

for b in [16, 20]:
    opytov = 20
    summa = 0
    for i in range(opytov):
        summa = summa + do_sovpadeniya(b)
    ocenka = math.sqrt(math.pi / 2) * 2 ** (b // 2)
    print(b, "бит: в среднем", summa // opytov, "позиций до совпадения",
          "| оценка √(π/2 · 2^b) ≈", round(ocenka))
for b in [32, 64]:
    # 2^b целиком в учебный движок не влезает (предел 2^53),
    # поэтому корень берём по частям: √(2^b) = 2^(b/2)
    ocenka = math.sqrt(math.pi / 2) * 2 ** (b // 2)
    print(b, "бит: оценка ≈", round(ocenka))

16 бит: в среднем 300 позиций до совпадения | оценка √(π/2 · 2^b) ≈ 321
20 бит: в среднем 1153 позиций до совпадения | оценка √(π/2 · 2^b) ≈ 1283
32 бит: оценка ≈ 82137
64 бит: оценка ≈ 5382943231

Опыт подтверждает оценку с точностью до разброса двадцати опытов: при 16 битах совпадение приходит через сотни позиций, а не через 65 536, как подсказывает интуиция «хешей много». При 32 битах - через восемьдесят тысяч: таблица позиций ИИ на миллион позиций с 32-битным хешем совпадёт в среднем около 116 раз за партию - n² / 2ᵇ⁺¹ = 10¹² / 8,6 · 10⁹, - и ходы будут получать чужие оценки. При 64 битах - через пять миллиардов, и для игры это достаточно. Граница правила: оценка верна для СЛУЧАЙНЫХ чисел Z. Если взять их «покрасивее» - например, номера клеток, - XOR разных позиций начнёт совпадать систематически: 1 ^ 2 = 3, и позиция «фигуры в клетках 1 и 2» неотличима от «фигура в клетке 3». Свой бит на каждую пару «клетка, содержимое» совпадений не даёт, но требует бит на каждую пару: 256 · 4 = 1024 бита на модель 16 × 16 и 65 536 на карту 128 × 128. Случайные числа в 64 битах делают почти то же: совпадения возможны, но редки - по оценке выше.

Что ломается без этого

Ключ - вся карта. ИИ тратит большую часть времени не на анализ, а на построение ключей словаря, и думает в десять раз медленнее, чем мог бы.

32 бита на миллионы позиций. ИИ «вспоминает» оценку чужой позиции и делает необъяснимо плохой ход - сотню раз за партию, и воспроизвести это невозможно.

Сохранение по совпадению хеша. Автосохранение решило, что позиция «та же», и не записало её - а она отличалась. Игрок потерял ход.

Зачем это в работе

Шахматные и го-программы, кеш состояний в планировщиках, дедупликация снимков в системах контроля версий, поиск повторов в моделировании - везде, где состояние меняется понемногу, а «уже было?» спрашивают часто. Парадокс дней рождения задаёт ширину любого идентификатора: короткие ссылки, номера заказов, контрольные суммы.

Теперь сам

1. Позиция кодируется 64-битным хешем, ИИ запоминает 10⁸ позиций за партию. Вероятно ли совпадение?
2. В хеш забыли включить «чей ход». К чему это приведёт в таблице позиций?
3. Ход «фигура съела фигуру»: фигура f из a в b, где стояла фигура g. Сколько XOR нужно?