Балда

Алгоритм быстрого поиска слов в игре балда

Балда

Как-то в одной социальной сети наткнулся на игру балда с нестандартными правилами (большие поля и узелки). Программы-подбиралки в основном работают по классическим правилам и на полях 5х5. Поэтому у меня появился спортивный интерес написать свою подбиралку полностью адаптированную под нестандартные правила.

Причем не просто написать подбиралку, а реализовать максимально быстрый алгоритм поиска слов.

Из нестандартных правил выделяется довольно интересный режим «узелки», в котором составлять слово можно, используя одну букву до 2-х раз (например, на скриншоте сверху можно составить слово ШАЛАШ, буквы Ш и А использованы 2 раза).

Как потом выяснилось, в одной и той же позиции алгоритм ищет все слова в режиме узелки почти ровно в 1.5 раз дольше, чем в классическом режиме без узелков (это и не удивительно, т.к. вариантов составления слов больше и найденные слова длиннее). В конце статьи описанный алгоритм будет протестирован в тестовой позиции в режиме узелки.

Словарь

Для того чтобы ещё больше затруднить жизнь алгоритму будет использоваться один из самых больших словарей в подобных программах. Он насчитывает примерно 110000 слов. Важную роль в алгоритме играет способ хранения словаря в памяти программы. При загрузке каждое слово записывается в структуру в виде дерева.

Каждый узел этого дерева означает конкретную букву слова и ссылается на не более чем 32 поддерева (по количеству букв в алфавите).

Узел дерева в программе выглядит так: typedef TREE *NEXT; //указатель на следующую букву struct TREE { NEXT *next; //массив указателей на все возможные следующие буквы char *str; //строка со всеми возможными следующими буквами char *wrd; //если не NULL, то это слово из словаря };
В поле str содержится строка со всеми буквами, которые выходят из данного узла, размер массива next[] равен длине этой строки.
Поле str используется для нахождения конкретного узла среди массива узлов next[] для данной буквы. Для этого введена функция ind(), основанная на strchr():
int k=ind('и',str); //возвращает индекс (позицию) буквы ‘и’ в строке str
Если kstr == ”адлбкнрусм”; root_inv->next[0]->str == ”бдкм”; root_inv->next[5]->next[0]->wrd == NULL; //АН не является префиксом словарного слова root_inv->next[5]->next[0]->next[1]->wrd != NULL; //МАН является префиксом словарного слова
Оба дерева занимают в памяти 33М, и непосредственно из словаря они строятся примерно за 5 секунд на i5, поэтому было принято решение сохранить образ деревьев в файл и в дальнейшем грузить именно его. Так скорость загрузки составила всего 300 миллисекунд.

Алгоритм поиска

По правилам балды для хода нужно выбрать пустую клетку, и поставить туда любую букву. Скрытый текстВезде пишут, что эта клетка обязательно должна быть смежной хотя бы с одной занятой клеткой, но это лишнее правило, т.к.

даже если поставить букву в несмежную клетку, то в любом случае слово составить не удастся, потому что однобуквенных слов нет в словаре. Затем нужно составить слово, используя поставленную букву. Данная буква может быть как первой буквой в слове, так и не первой буквой (хоть и капитанство, но это важно).

Если бы в правилах было сказано, что поставленная буква должна быть точно первой, то просто используем словарное дерево, двигаясь по полю от поставленной буквы одновременно спускаясь вниз по дереву. Но т.к.

поставленная буква может и не быть первой, словарное дерево использовать нельзя, потому что не известно с какого именно узла начинать поиск. Но у нас ещё есть инвертированное дерево.
Идея такая: из клетки с поставленной буквой движемся по полю, спускаясь по инвертированному дереву.

Если находим узел, у которого wrd!=NULL (красный узел), значит это валидный инвертированный префикс слова. Имея префикс слова, можно в словарном дереве найти узел, соответствующий поставленной букве, и далее просто «донайти» оставшийся кусок слова уже в словарном дереве, начиная с этого узла.

Для того чтобы алгоритм не заходил в клетки, которые ранее для данного слова уже прошёл, в каждой клетке имеется счетчик использования count. Перед началом поиска этот счетчик инициализируется числом 2 (для режима узелки) или 1 (для классического режима) – это единственное отличие режимов с точки зрения алгоритма. Более подробный алгоритм:

  • 1) Перебираем все пустые смежные клетки
  • 2) Для каждой клетки перебираем все буквы алфавита (32 буквы)
  • 3) Заносим в текущую клетку (пусть её координаты будут [x, y]) текущую букву s. Так получаем 32*n разных позиций, где n – число смежных клеток в исходной позиции
  • 4) Занесенную букву считаем первой буквой для инвертированных префиксов. Поэтому среди root_inv->next[] находим узел t_inv, соответствующий текущий букве, т.е. t_inv – поддерево, начинающееся с текущей буквы: int k = ind(s, root_inv->str); //s – текущая букваif(knext[k];
  • 5) Уменьшаем count[x, y] и вызываем функцию поиска в поддереве find (о которой ниже) для t_inv и клетки [x, y]
  • 6) Конец цикла по буквам
  • 7) Конец цикла по смежным клеткам

Естественно после цикла по буквам очищаем текущую смежную клетку.

Функция поиска в поддереве find принимает игровое поле, узел дерева (tree) и координаты клетки (i, j), с которой необходимо начать двигаться по полу, спускаясь по дереву tree:

  • 1) Если tree->wrd!=NULL, то найдена валидная подстрока
    • a. Если этот узел принадлежал словарному дереву, то эта подстрока вообще словарное слово, добавляем tree->wrd в массив найденных слов.
    • b. Если узел принадлежал инвертированному дереву, то эта подстрока является инвертированным префиксом слова. В словарном дереве находим узел t, соответствующий этому префиксу, и вызываем функцию find для t и клетки [x, y] (внимание! Не та клетка, которую передали в эту функцию, а клетка, в которую алгоритм сходил на шаге 3): TREE *t=root; //корень словарного дереваloopi(strlen(prefix)) //prefix содержит найденный инвертированный префикс{ int k=ind(prefix[i],t->str); t=t->next[k];}find(t,x,y);
  • 2) Независимо от значения tree->wrd продолжаем
  • 3) Перебираем клетки, смежные с [i, j] (от 2-х в углу до 4-х в центре поля)
  • 4) Анализируем содержимое текущей смежной клетки [i1, j1]
    • a. Если она пустая, то переходим на шаг (3)
    • b. Если буква, находящаяся в этой клетке, не имеется в tree->str, то переходим на шаг (3)
    • c. Если count[i1, j1]==0, то переходим на шаг (3)
    • d. Иначе переходим на шаг (5)
  • 5) Среди tree->next[] находим узел tnext, соответствующий букве в [i1, j1]
  • 6) Уменьшаем счетчик использования count[i1, j1] и вызываем find для tnext и клетки [i1, j1]
  • 7) Конец цикла по смежным буквам

Рассмотрим работу алгоритма для центральной клетки на примере следующей позиции:
Заносим в эту клетку каждую букву из строки ”адлбкнрусм” (остальные буквы алфавита просто не существуют в root_inv->str и алгоритм для них быстро завершится, даже не начавшись). Для каждой буквы вызываем find. Для буквы А функция быстро завершится, потому что в инвертированном дереве нет веток, начинающихся на АА-, АС- и АКУ-, то же самое и для Д, К, У, С.
Для остальных букв в инвертированном дереве будут найдены валидные префиксы:

Л – лаб, Б – б, Н – наб, Р – раб, М – м. Для каждого префикса находим узел в словарном дереве (как описано в п.1.b) и вызываем для него функцию find.

Префиксу “бал” соответствует узел root->next[0]->next[0]->next[0]:

Следующей смежной буквой может быть С или К, но в поле str этого узла содержится “д”, поэтому сразу завершаем функцию find, т.е. в дереве нет веток, начинающихся на БАЛС- и БАЛК-. Для префикса “б” в словарном дереве нет веток, начинающихся на БК-, БС-, БАБ-, БАЪ-, то же самое и для префиксов “бан” и “м”.

Префиксу “бар” соответствует узел root->next[0]->next[0]->next[2].
Т.к. поле wrd!=NULL, заносим строку wrd (БАР) в массив найденных слов и продолжаем поиск дальше. Для строк БАРК и БАРСЪ нет веток, завершаем для них функцию find, а вот строка БАРСУК содержится в дереве, помещаем её в массив найденных слов.

Результаты

Алгоритм тестировался на следующем поле (естественно уже не на тестовом словаре, а на словаре из 110000 слов): Скрытый текст Это реально игравшаяся партия.

Здесь поле 9х9, и оно наполовину заполнено (пожалуй, это одна из наихудших позиций для любого алгоритма, потому что присутствует достаточно много клеток, куда можно сходить, и достаточно удачное взаимное расположение букв, из-за чего много длинных слов можно составить). В режиме узелки алгоритм находит все слова за следующее время:

  • 1) Mac mini i7 – 7 миллисекунд (не нативное приложение, а в эмуляторе iPhone)
  • 2) Комп. с i5 – 12 миллисекунд
  • 3) iPad 4 – 30 миллисекунд
  • 4) Samsung Galaxy Ace (железо трёхлетней давности) – 50 миллисекунд (с использованием NDK)

Для других позиций время поиска еще меньше.

Приложение

Данный алгоритм применен в приложениях для iOS (доступно в app store) и Android.

Помимо поиска всех слов реализованы ещё два вида поиска:

  • 1) Локальный поиск – если пользователю позарез нужно занять какую-либо определённую пустую клетку (например, призовая клетка, или прикрыть своим ходом клетку, в которой слишком много длинных слов), тогда он делает двойной тап по этой клетке и программа ищет только те слова, которые можно сходить в неё
  • 2) Проверка подстав – двойной тап по букве заставит программу найти все слова, проходящие через эту букву. Применение: сразу после хода соперника проверить его букву (вдруг он жестко подставился), перед своим ходом следует проверить предполагаемый ход на предмет подстав

Ещё одна особенность: одинаковые по длине слова сортируются по редкости добавляемой буквы (например, сходить буквой Ч выгоднее, чем буквой А).

  • алгоритмы
  • балда
  • слова
  • поиск слов

Источник: https://habr.com/post/207734/

Балда — популярная лингвистическая игра, в которой необходимо составлять слова с помощью букв, добавляемых на игровое поле.

Игра ведется на поле 3х3, 5х5 или 7х7 клеток, в зависимости от режима. В начале игры в центре поля появляется выбранное случайным образом слово. Каждый из соперников за ход может добавить одну букву так, чтобы получилось новое слово. Последовательность букв в слове может быть в любом направлении, кроме диагоналей.

За составленное слово даётся количество очков равное его длине.

При игре с компьютером ограничений по времени нет, при игре с реальным соперником на ход даётся 2 минуты (кроме режима «Блиц»). Если не сделать ход в течение 2-х минут, право хода передаётся сопернику. Также вы можете пропустить ход, не дожидаясь истечения отведённого времени, нажав кнопку «Пропустить ход». После пропуска 3-х ходов игроку присуждается поражение.

Если составленного вами или соперником слова нет в словаре, об этом будет написано, и слово засчитано не будет. Однако, если вы уверены в том, что такое слово существует и удовлетворяет правилам игры, вы можете запросить подтверждение у соперника (в случае его согласия, слово будет засчитано).

Как установить букву:

  • перетащить букву с панели на нужную клетку;
  • выделить клетку на поле, затем нажать кнопку на клавиатуре или на букву панели;
  • нажать на букву, а затем на клетку поля.

Как выделить и добавить составленное слово:

  • нажимая на клетки поля, последовательно выделить слово от первой до последней буквы, затем нажать на кнопку под полем. Если дальнейшее выделение невозможно, слово будет принято автоматически;
  • нажать на первую букву слова, а затем, удерживая кнопку мыши, выделить слово до последней буквы.

Панель истории игры

Справа от игрового поля располагается панель истории игры, в которой отображаются имена игроков, общий счет по серии игр и список набранных слов для каждой из игр серии.

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

При нажатии на слово и удержании кнопки мыши отображается его определение.

В нижней части панели расположено поле “Запомнить слово”, предназначенное для заметок, и поле “Проверить слово”, с помощью которого вы можете проверить наличие слова в словаре. Если слово присутствует в словаре, Вы также можете посмотреть его определение.

Панель режимов

3х3, 5х5, 7х7 — переключает текущий размер игрового поля.

5х5 Блиц — включает режим Блиц, в котором при игре с человеком каждому игроку на всю игру отводится 2 минуты. По истечении времени игроку присуждается поражение.

Другие игры — перейти к другим нашим играм.

Верхняя панель кнопок

Ход назад, Ход вперед — позволяет отменить или повторить свой ход в игре с компьютером. Вы можете повторить отменненый ход, нажав на часть кнопки, обозначенную символом >

Пропустить ход — позволяет передать право хода сопернику.

Начать сначала — начинает текущую игру с компьютером заново.

Новая игра — начинает новую игру с компьютером.

Дополнительные кнопки в совместной игре

Предложить ничью — предложить сопернику ничью.

Сдаться — сдаться (засчитывается поражение).

Покинуть игру — позволяет немедленно завершить текущую игру (засчитывается поражение).

Нижняя панель кнопок

Параметры — открывает меню настроек игры, в котором вы можете:

  • Изменить вид панели алфавита;
  • Выбрать режим сложности игры компьютера;
  • Включить или отключить подсветку допустимых для установки новой буквы клеток;
  • Включить или отключить звук;
  • Запретить приглашать вас в совместную игру;
  • Открыть черный список игроков.

Описание — открывает описание игры.

Вопросы и отзывы — открывает гостевую книгу, в которой вы можете оставить отзыв или пожелание к игре.

История – история всех ваших игр с указанием даты игры, противника и его места в рейтинге.

Жёлтым цветом отмечены выигранные вами партии, красным – проигранные, синим – завершенные ничьей.

Звёздочкой отмечены игры, занесённые вами в избранное.

игроков – результаты зарегистрированных игроков, упорядоченных по количеству набранных очков.

Очки начисляются только за победы над противниками (за ничьи и победы над компьютером очки не начисляются).

Начисление очков идет по системе Эло.

Система рейтингов Эло, коэффициент Эло — метод расчёта относительной силы игроков в играх, в которых участвуют двое игроков. Эту систему рейтингов разработал американский профессор физики венгерского происхождения Арпад Эло.

Авторизация / Личный кабинет — возможность войти в личный кабинет (ЛК), произвести авторизацию или зарегистрироваться.

В личном кабинете вы можете указать дополнительную информацию о себе, загрузить фото, изменить пароль, а также хранить и осуществлять личную переписку с другими зарегистрированными игроками.

Вы можете играть без регистрации в качестве гостя. После регистрации и/или авторизации вы получите доступ в личный кабинет и сможете отправлять другим игрокам личные сообщения.

Чтобы зарегистрироваться надо просто ввести имя (от 3 символов) и пароль (не менее 5 символов). Если такое имя уже зарегистрировано в игре, вам придется выбрать другое.

Источник: https://logic-games.spb.ru/balda/

Поделиться:
Нет комментариев

    Добавить комментарий

    Ваш e-mail не будет опубликован. Все поля обязательны для заполнения.

    ×
    Рекомендуем посмотреть