Конспект: игроки

Понятия

Пары по одной оси - сортировка и соседи; скрещённые пары не лучше, это доказывает обмен.

Наибольшее паросочетание - больше всего пар при ограничениях «кто с кем»; увеличивающий путь находит свободного соперника или пересаживает партнёра занятого.

Автомат Ахо-Корасик - бор слов, ссылки неудач, счётчик слов с учётом цепочки ссылок; строится один раз на список, текст читается один раз.

Хеш Зобриста - XOR случайных чисел пар «клетка, содержимое»; ход меняет его несколькими XOR.

Альфа-бета отсечение - ветку бросают, как только ясно, что соперник её не допустит. Таблица позиций - запоминание оценок позиций, пришедших разными путями.

Что унести

СОПЕРНИКИ
8 игроков: перебор 105 разбиений = 380, соседи после сортировки = 380,
           жадно по очереди = 440
a ≤ b ≤ c ≤ d: (a, b)(c, d) меньше скрещённых на 2(c - b)
Север - Юг с пингом: жадно 5 пар, Кун 6
пары И равные - паросочетание наименьшей стоимости

ЧАТ
348 символов, 40 слов: наивно 15 178 сравнений, автомат 489 шагов
vsego[u] = konec[u] + vsego[неудача(u)] - иначе «он» в «вороне» потерян
ссылок неудач за текст не больше длины текста
звёздочки: самое длинное слово в конце позиции + проход справа налево

ХЕШ ЗОБРИСТА
Z[клетка][фигура] - случайные; хеш = XOR по клеткам
ход в пустую клетку: 4 XOR (16 × 16: 4 против 256)
туда и обратно - хеш тот же; «чей ход» - своё Z
первое совпадение ~ √(π/2 · 2^b): 16 бит 321, 32 - 82 тыс., 64 - 5 млрд

ИИ СОПЕРНИКА
оценка позиции = max по ходам (- оценка после хода)
16 камней: перебор 23 249, альфа-бета 5601, таблица 46
18 камней: порядок 1-2-3 - 11 204 узла, «лучший первым» - 242
камни 1..m: проигрышны позиции, кратные m + 1

Ловушки джокера

Жадный матчмейкинг. Первые получают равных соперников, последние - разгромные партии.

Сортировка при ограничениях. Пары по рейтингу с разных серверов с пингом 200 мс.

Только слово вершины. Вложенные запрещённые слова проходят фильтр.

32 бита на миллионы позиций. ИИ берёт чужие оценки сотню раз за партию.

Хеш без «чей ход». Оценка для чужой очереди хода.

Альфа-бета с ходами по номеру. Отсечения включены, а выигрыша почти нет.