На прошлой неделе наткнулся на забавную игру в слова – contexto.me, смысл прост: нужно отгадать секретное слово. При этом после каждой попытки видно, насколько близко по смыслу ваше слово было к ответу. Поиграв пару дней, захотелось написать такую игру самому, а также автоматизировать процесс решения, про что и данная статья.

Дисклеймер: на хабре есть две публикации про написание подобной игры: одна больше про код, другая про запуск и продвижение приложения. Текущая статья писалась независимо от указанных выше, а также, помимо создания игры, рассматривает алгоритм ее решения.

Правила игры

После ввода слова мы можем увидеть его порядковый номер. Например, попробуем «cat»:

Получаем число 5014 – значит, есть 5012 слов, которые будут ближе по смыслу к секретному, оно, в свою очередь, под номером 1. Таким образом, по принципу «горячо-холодно» постепенно двигаемся к ответу. Игра проводится каждый день, а количество попыток не ограничено.

Схема данных

В качестве базы данных возьмем PostgreSQL.

Под каждый день у нас должен быть отсортированный список слов:

CREATE TABLE word (
	word VARCHAR NOT NULL, -- само слово
	rank INTEGER NOT NULL, -- позиция, у секретного – 1
	date DATE    NOT NULL, -- дата игры
	CONSTRAINT word_word_date_pk PRIMARY KEY (word, date)
);

Также необходимо сохранять попытки пользователей:

CREATE TABLE guess (
	user_id    VARCHAR   NOT NULL, -- идентификатор пользователя
	word       VARCHAR   NOT NULL, -- введенное слово
	date       DATE      NOT NULL, -- дата игры
	CONSTRAINT guess_user_id_date_word_pk PRIMARY KEY(user_id, date, word),
    CONSTRAINT guess_date_word_word_date_word_fk FOREIGN KEY (date, word)
  	    REFERENCES word (date, word)
);

Сервер

Одностраничное приложение на Next.js, стили – Tailwind, ORM – Drizzle.

Чтобы сайт работал без аутентификации и попытки игроков не терялись после перезагрузки страницы, при первом посещении устанавливаем cookie с уникальным идентификатором пользователя.

Логика проверки введенного слова:

export async function tryGuess({
  date,
  userId,
  word,
}: {
  date: Date
  userId: string
  word: string
}) {
  try {
    const foundWord = await findWord({ word, date })
    if (foundWord == null) {
      // слова нет в нашем словаре
      return undefined
    }
    // сохраняем отгаданное слово
    await db
      .insert(guess)
      .values({
        date,
        userId,
        word,
      })
      // если такая попытка уже была, ничего не делаем
      .onConflictDoNothing()
    return foundWord
  } catch (error) {
    logger.error('Failed to insert guess in database')
    throw error
  }
}

Можно сделать одним SQL запросом, но Drizzle активно сопротивлялся такому подходу.

Откуда брать слова?

Для игры будем использовать только существительные русского языка. Находим подходящий датасет на github и вооружаемся «nouns.csv».

Запускаем jupyter lab (версия питона 3.10 нужна для одной из библиотек)

uv run --python 3.10 --with jupyter jupyter lab

Устанавливаем необходимые зависимости

!uv pip install navec pymorphy2 pandas

• navec – эмбеддинги русских слов, то есть векторные представления; полезное свойство такого формата – у близких по смыслу слов вектора будут похожи друг на друга (что именно это значит, рассмотрим позже)

• pymorphy2 – морфологический анализ слов, поможет отфильтровать имена, фамилии и другие слова, которые есть в «nouns.csv», но не должны быть в игре

• pandas – манипуляции с данными

from navec import Navec
import pandas as pd
import pymorphy2

# существительные, нам понадобиться только колонка с начальной формой – bare
nouns = pd.read_csv('nouns.csv', sep='\t')[['bare']]
# переименуем колонку под наше обозначение
nouns = nouns.rename(columns={"bare": "word"})

# эмбеддинги, файл доступен в репозитории библиотеки
navec = Navec.load('navec_hudlit_v1_12B_500K_300d_100q.tar')

# морфологический анализ слов
morph = pymorphy2.MorphAnalyzer()

Фильтруем лишние слова:

def is_proper_noun(word):
    parsed = morph.parse(word)[0]
    # должно быть в датасете эмбеддингов
    if (word not in navec):
        return False
    # фильтруем географические названия
    if ('Geox' in parsed.tag):
        return False
    # фильтруем имена
    if ('Name' in parsed.tag):
        return False
    # фильтруем фамилии
    if ('Surn' in parsed.tag):
        return False
    # убеждаемся, что точно существительное
    return 'NOUN' == parsed.tag.POS

filtered_nouns = nouns[nouns['word'].apply(is_proper_noun)]
# убираем дубликаты
filtered_nouns = filtered_nouns.sort_values('word').drop_duplicates('word', keep='last')
filtered_nouns = filtered_nouns.reset_index(drop=True)

Осталось 19874 слова из 26982.

Добавим колонку с эмбеддингами:

def to_vec(word):
    return navec[word]

filtered_nouns['embeddings'] = filtered_nouns['word'].apply(to_vec)

Посмотрим на результат:

Выбор секретного слова доверим великому рандому:

secret_word = filtered_nouns.sample(n=1)

После пары запусков получил «программист», остановимся на нем.

Теперь необходимо отсортировать остальные слова согласно правилам игры. Как говорилось выше, полезное свойство эмбеддингов – у близких по смыслу слов вектора будут похожи друг на друга, то есть, чем ближе по смыслу слова, тем меньше угол между их векторами.

Чтобы не оперировать углами, возьмем их косинусы: чем меньше угол, тем значение ближе к 1 (угол в 0 градусов), что будет указывать на сходство по смыслу/контексту, чем больше угол – тем значение ближе к -1 (угол в 180 градусов), что будет указывать на отсутствие связи между словами. Подобная величина называется косинусным сходством двух векторов.

Считаем:

import math

def cosine_similarity_manual(vec1, vec2):
    dot_product = sum(v1 * v2 for v1, v2 in zip(vec1, vec2))
    magnitude_vec1 = math.sqrt(sum(v1**2 for v1 in vec1))
    magnitude_vec2 = math.sqrt(sum(v2**2 for v2 in vec2))

    if magnitude_vec1 == 0 or magnitude_vec2 == 0:
        return 0

    return dot_product / (magnitude_vec1 * magnitude_vec2)
  
# берем вектор секретного слова
secret_word_vec = secret_word['embeddings'].values[0]
# считаем косинусное сходство с ним для всех остальных слов
filtered_nouns['cosine_similarity'] = filtered_nouns['embeddings'].apply(lambda emb: cosine_similarity_manual(secret_word_vec, emb))
# сортируем по полученному значению
filtered_nouns = filtered_nouns.sort_values(by='cosine_similarity', ascending=False)
filtered_nouns = filtered_nouns.reset_index(drop=True)

Получаем отсортированный список слов:

Добавим порядковый номер, дату и сохраним результат в файл:

from datetime import datetime

filtered_nouns['rank'] = filtered_nouns.index + 1
filtered_nouns['date'] = datetime.today().strftime('%Y-%m-%d')

filtered_nouns[['word', 'rank', 'date']].to_csv('words.csv', index=False)

Остается загрузить данные в бд:

psql --command "\copy word FROM 'путьдопапки/words.csv' WITH (FORMAT csv, HEADER);"

Мы подготовили слова на один день игры, но аналогичным образом можно сгенерировать файл со словами и на год вперед.

Автоматизация решения

Переходим к самому интересному – как научить машину отгадывать слово?

Мысль первая: брать случайное слово и затем корректировать его вектор в сторону решения. Но как понять, в какую сторону необходимо наклонять? Осложняет задачу еще и тот факт, что размерность наших эмбеддингов – 300, то есть изменять можно 300 различных координат.

Мысль вторая: что, если нам снизить размерность эмбеддингов, например, до 2? Пробуем, используя метод главных компонент (PCA), и быстро убеждаемся, что точность сразу теряется (оно и понятно – мы привели 300-мерное пространство к 2-мерному).

Мысль третья: попробовать делить на группы похожих векторов и с каждой итерацией отбрасывать какие-то из них. Здесь есть свои нюансы. Как видно на примере ниже, несмотря на то, что вектор номер 5 в общем списке достаточно низко (5/6), его ближайший сосед – 1 слово. Соответственно, в какой-то из итераций мы можем отфильтровать и само решение. Наверное, можно как-то учитывать величину угла, но ничего дельного я придумать не смог, да и математический аппарат хромает.

Мысль четвертая: вводим случайное слово, получаем порядковый номер, например 500, перебираем все возможные решения, для которых после сортировки по косинусному сходству на 500 месте то же самое слово (если получили несколько вариантов, добавляем еще один номер). Великолепный план. Надёжный, как швейцарские часы. Однако он требует, чтобы у нас на руках была точная копия датасета игры, что не очень честно.

Финальная мысль: не попробовать ли нам смотреть на относительный порядок слов? То есть перебирать решения, для которых после сортировки относительный порядок наших попыток сохраняется.

Поставим необходимые зависимости:

!uv pip install numpy scikit-learn

• numpy – пригодится для операций с матрицами

• scikit-learn – отсюда возьмем расчет косинуса

Чтобы перебор всех возможных решений не занимал много времени, векторизуем расчет косинусного сходства (разом будем считать для целого батча потенциальных ответов)

import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

# количество введенных слов
N_SAMPLES = 10
# размер батча для поиска решений
BATCH_SIZE = 5000

solution_nouns = filtered_nouns.copy()
embeddings = np.vstack(solution_nouns['embeddings'].to_list())

# узнаем ранг случайных слов в количестве = N_SAMPLES
samples = solution_nouns.sample(n=N_SAMPLES)
sample_indices = samples.index.to_numpy()

potential_first = set()

# перебираем все слова, для которых относительный порядок samples сохраняется
for start in range(0, len(solution_nouns), BATCH_SIZE):
    end = min(start + BATCH_SIZE, len(solution_nouns))
    similarities = cosine_similarity(embeddings[start:end], embeddings)
    print(f"Обработка батча {start}-{end}")
    
    for i, idx in enumerate(range(start, end)):
        sorted_indices = np.argsort(similarities[i])[::-1]
        sample_positions = [np.where(sorted_indices == si)[0][0] for si in sample_indices]

        # если в том же порядке
        if np.array_equal(np.argsort(sample_indices), np.argsort(sample_positions)):
            # слово может быть решением
            potential_first.add(solution_nouns.iloc[idx]['word'])

print("Введенные слова:")
print(samples[['rank', 'word']].values)
print(f"Потенциальные решения за {N_SAMPLES} попыток: {potential_first}")

Пробуем запустить:

Для поиска решения мы используем тот же датасет и эмбеддинги, однако это необязательное условие, нам важем лишь относительный порядок слов, он будет схожим и в других случаях. Главное, чтобы сортировка строилась по тому же принципу и было значительное количество общих слов.

Код можно доработать, чтобы он постепенно увеличивал количество вводимых слов, вдруг найдем за 9 попыток?

import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

def find_solution(original_nouns, solution_nouns, n_samples, batch_size, random_state):
    """
    Аргументы:
        original_nouns: датасет из которого было загадано слово
        solution_nouns: датасет слов для поиска решений
        n_samples: начальное количество вводимых слов
        batch_size: размер батча для поиска решения
        random_state: настройка случайного выбора слов
    """
    embeddings = np.vstack(solution_nouns['embeddings'].to_list())
    
    while True:
        print(f"Пробуем за {n_samples} попыток...")
        
        # узнаем ранг случайных слов в количестве = n_samples
        # random_state позволяет не терять предыдущие слова при инкременте n_samples
        samples = original_nouns.sample(n=n_samples, random_state=random_state)
        sample_indices = samples.index.to_numpy()
        
        potential_first = set()
        
        # находим все потенциальные решения, для которых относительный порядок сохраняется
        for start in range(0, len(solution_nouns), batch_size):
            end = min(start + batch_size, len(solution_nouns))
            print(f"Обабатываем батч {start}-{end}")
            
            # разом считаем косинусное сходство для всего батча потенциальных решений
            similarities = cosine_similarity(embeddings[start:end], embeddings)
            
            for i, idx in enumerate(range(start, end)):
                sorted_indices = np.argsort(similarities[i])[::-1]
                sample_positions = [np.where(sorted_indices == si)[0][0] for si in sample_indices]

                # если относительный порядок сохранился, то добавляем в список потенциальных решений
                if np.array_equal(np.argsort(sample_indices), np.argsort(sample_positions)):
                    potential_first.add(solution_nouns.iloc[idx]['word'])
        
        print(f"Нашли {len(potential_first)} потенциальных решений за {n_samples} попыток")
        
        # выходим, если осталось только 1 решение или исчерпали весь датасет
        if len(potential_first) <= 1 or n_samples >= len(solution_nouns):
            print(samples[['word', 'rank']])
            return n_samples, potential_first
        
        # потенциальных решений > 1, продолжаем с дополнительным словом
        n_samples += 1

# начальное количество введенных слов
N_SAMPLES = 5
# размер батча для поиска решений
BATCH_SIZE = 5000
# чтобы введенные слова не обновлялись
RANDOM_STATE = 42

solution_nouns = filtered_nouns.copy()
used_samples, potential_first = find_solution(filtered_nouns, solution_nouns, N_SAMPLES, BATCH_SIZE, RANDOM_STATE)

print(f"Решение {potential_first} найдено за {used_samples} попыток")

Результат

Попробовать игру в деле можно на 1context.ru.

Исходный код приложения вместе с jupyter notebook для подготовки данных и автоматизации решения доступны на github.

P.S. В оригинальной игре есть подсказки, возможность сдаться и сыграть за предыдущие дни, в нашей версии – только основной сценарий.