Тактический Решатель Для Игры Балда

Mar 28, 2015 - тактических задач (то есть Б.д. Могут рассматриваться и как процесс. Громила, горилла, долбак, дуболом, жлоб, мордоворот, слон, сундук, шкаф, балда. Из науки 14 (РАС) жизнь превратилась в игру 13, кайф 1. Имитируя не знающую ошибок логику бессубъектного решателя.

Однажды на Хабре нашел статью об алгоритме поиска слов в игре балда: Я сам являюсь автором решателя, который за многие годы приобрел популярность у многих онлайн игроков в игре Балда. И я хотел бы то же поделиться своим опытом и рассказать об одном уникальном алгоритме в игре балда, который еще ни кем не применялся. Про ту статью в целом.

По такому же алгоритму и у меня ищутся слова, через префиксные деревья. Но вместо двух деревьев, у меня одно, которое содержит символ «разделитель», после которого оставшаяся часть слова идет инвертированной. Есть также возможность включить более сложное префиксное дерево («турбо-режим»), с символом «пустышка». В этом случае терминальный узел содержит все буквы, которые можно поставить в пустышке.

Например, мы прошли путь К.Т, и встретили терминальный узел. Он будет содержать две буквы, «О» и «И».

В ячейке «О» будет ссылка на слово КОТ, а в «И» на слово КИТ. В итоге, пустышка позволяет избавиться от перебора 32-х букв в каждой итерации на пустых клетках. Но увеличивает размер префиксного словаря примерно в 5 раз.

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

Однако, у меня специально сделано что бы поиск начинался с уже поставленных букв. Хотя это крайне не эффективно, т.к. Увеличивает кол-во рекурсивных проходов, и нужно будет отсеивать дубли, которые неизбежно появятся на каждой клетке, через которые проходит слово. Но такой подход(поиск с не пустых клеток) задуман специально, чтоб можно было применить одну хитрую оптимизацию, о которой я расскажу в конце. С помощью нее проблема дублей отпадет, скорость компенсируется(и даже подрастет), и появится новое свойство — стабильность времени поиска.

Многие могут спросить, зачем еще быстрей. Если даже самые простые и медленные алгоритмы ищут слова за миллисекунды. Эти вопросы могут возникать только у тех программистов, кто не пробовал играть против «чемпионов». Их программы умеют думать на несколько ходов вперед.

Значит, программы должны не просто искать слова, но и применять тактику. А самая универсальная для всех логических игр тактика — минимакс.

Что это такое: хорошо описано. А применение минимакса означает, что нужно делать очень много виртуальных ходов.

Ну например, если каждому игроку в среднем достается 100 слов в каждом ходу, то что бы просмотреть все варианты развития игры на 4 хода вперед потребуется 100^(4-1)=1.000.000 поисков. Если ваша программа умеет искать все слова за 1мс, то она проверит игру на 4 хода вперед за 16 минут! А на раздумья над ходом дается как правило 2 минуты. Теперь вы понимаете, зачем нужен очень быстрый поиск. Моя программа умеет за несколько секунд анализировать игру на 8-10 ходов вперед. Самое большое ускорение дает отсеивание слов.

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

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

А значит, нет смысла терять время на короткие слова. А если уже конец партии, и остается не много ходов, программа расширяет список анализируемых слов. У меня уже за 4-6 ходов до конца игры участвуют в переборе абсолютно все слова. И к концу партии как раз и уместно смотреть короткие слова. Не редко бывает, что под конец партии имея слова из 4-5 букв, выгодней походить из 2-3-х. Второе существенное ускорение дает. До этого я упоминал стандартные алгоритмы, которые вы всегда сможете найти и ознакомиться.

Веселая и интересная игра 'Танки в Лабиринте'. Здесь вы будете управлять одним из маленьких танков, которые находятся в коридорах одного,. Возьмите под контроль танки в лабиринте. Их забросили туда, чтобы начать увлекательную игру на двоих – противостояние убийственных машин. Описание: Возьмите под контроль танки в лабиринте. Их забросили туда, чтобы начать увлекательную игру – противостояние убийственных машин. Танчики в лабиринте.

А теперь напишу свое «изобретение». Оно касается оптимизации поиска слов в процессе построения дерева виртуальных ходов. Вот смотрите. Как обычно мы строим дерево перебора в балде: 1. Находим все слова. Перебираем все слова, проставляя поочередно каждое слово на игровое поле.

Переходим рекурсивно на пункт 1. Или возвращаемся с рекурсии, если слишком глубоко залезли. А теперь напишу, как у меня: 1. Находим все слова.

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

Для этого ищем не все слова на игровом поле, а только те, которые проходят через занятую клетку последним словом. Ведь что изменилось с предыдущего хода — на игровом поле появилась новая буква. А значит, если и появились новые слова, то они все должны проходить через новую букву. Если не проходят — то эти слова уже ранее найдены, и есть у нас в списке. Что в итоге: Вместо того, что бы пускать рекурсивный поиск слов от каждой клетки игрового поля, мы ее пускаем всего в одну клетку!

И не важно, какого размера игровое поле. Пусть даже игровое поле содержит миллион клеток.

Мы будем «доискивать» новые слова всегда только в одной клетке! Переходим рекурсивно на пункт 2.

Или возвращаемся с рекурсии, если слишком глубоко залезли. У меня на самом деле список слов не копируется каждый раз, и слова не удаляются в чистом виде. А осуществляются все это за счет переключения указателя на страницы в многомерном массиве, чья размерность определяется как «адрес клетки», «глубина хода», и собственно ID-шники слов, которые были найдены в конкретной клетке, на конкретной глубине.

Таким образом, когда мы откатываемся в дереве на уровень назад, нам не нужно восстанавливать список найденных слов в этом узле, мы просто уменьшаем указатель на «страницу». А когда наоборот, углубляемся — указатель увеличивается, и в новую страницу заносятся новые слова. Таким образом. Где нибудь на 10 ходу чтоб узнать все слова в этом ходу, нам нужно сложить все слова из 10-ти «доисканных страниц».

Все они в сумме и представляют собой список слов, как если бы искали обычным способом. Но если честно, я уже не помню всех технических подробностей структуры многомерного массива. Как ни странно, но мой алгоритм «доискивания» слов не дал ошеломляющего ускорения. Но зато он дал стабильность времени поиска. Обычный метод поиска уже к середине игры существенно замедляется, а мой не замечает этой «нагрузки».

Ведь как ранее говорилось, сколько бы букв не было на игровом поле — на каждый виртуальный ход будут искаться слова только в 1-ой клетке, а не во всех. Особенно ценно это свойство на больших игровых полях.

В заключение хочу сказать, что анализ минимаксом сильно зависит от точности словаря. Поэтому важен не размер словаря, а его соответствие словарю игрового портала. Метки:. Добавить метки Пометьте публикацию своими метками Метки необходимо разделять запятой. Например: php, javascript, андронный коллайдер, задача трех тел. Обычно то, что выдает программа не всегда является оптимальной последовательностью ходов.

Дело в том, что в приложении балда39 читеров банят уже хотя бы по факту играния «нелепыми» словами (куэнковец, денедж, ньяя и др.). Опытные читеры никогда не ходят такими словами и вообще ходят только теми, которые знают сами. И потом, на ход ведь дается не 5 секунд, а минута или 2, за это время можно и самому успеть проанализировать игровую ситуацию (отсеивая нелепые слова) Сколько у вас время поиска на большом поле наполовину заполненном (на один только ход вперед)? (Ну там 30х30 или большем поле).

Ну я бы не назвал «нелепые» слова не оптимальными ходами. Какой словарь скормите минимаксу — теми словами он и будет играть. Здесь я хотел рассмотреть только алгоритмы, а не как некоторые игры борются с читерами. По поводу скорости поиска слов на 1 ход вперед на поле 30x30.

Если вы имеете ввиду «полноценный» поиск, то примерно в 36 раз медленней, чем на поле 5x5, что составит десятые доли секунды. А если это поиск «доискивающий» (алгоритм которого я описал в статье), то скорость вобще не будет зависеть от размера поля. Я статью полностью не читал, но хочу поделиться своим опытом с версией под Windows Phone, для контраста. Работало оно так: Грузится словарь, находится самое длинное слово.

Дальше, по всем позициям от 0 до максимальной длины слова строится префиксное дерево пар символов. Допустим, разбираем слово «СЛОВО» с позиции 1 (Л). Дерево для этого слова выглядит так: Л: СО В О Т.е. В первую пару входят 0 и 2-ой символ, во вторую — -1-ый и 3-ий, в третью — -2-ой и 4-ый.

В процессе хода алгоритм перебирает все пустые клетки, подставляет в них буквы и с помощью префиксного дерева пытается построить слово, содержащее новую букву и лежащее на поле. Производительность не замерял, но с 200тыс. Слов основной проблемой оказалось то, что в отведённую на размышление секунду алгоритм осуществлял полный перебор на моём Samsung Omnia и с ним уже невозможно было играть человеку. (В смысле — теоретически возможно было бы смотреть на несколько ходов вперёд, но для человека это крайне трудная задача). Пришлось добавить «сложность», которая по сути с вероятностью n банально игнорировала найденное слово при переборе.

Для самого сложного уровня это n было порядка 90%. Для самого простого — 97%.