• Выигрышная стратегия Гомоку – 35 ходов

    При игре по стандартным правилам Гомоку для выигрыша черным требуется не более 35 ходов. В статье Вашему вниманию представлена полная выигрышная стратегия и соответствующий алгоритм игры.

    Демонстрация полного решения – здесь – можно поиграть и найти самые длинные варианты. Программа всегда выигрывает и затрачивает на это не более 35 ходов. Исходные тексты приложения, само решение и примеры партий в конце статьи.
    Читать дальше →
  • Генератор подземелий на основе узлов графа

    • Перевод
    image

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

    Введение


    Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

    Алгоритм


    Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.
    Читать дальше →
    • +50
    • 9,6k
    • 8
  • Внутри Quake: определение видимых поверхностей

    • Перевод
    image

    Ветеран программирования трёхмерной графики Майкл Абраш на примере разработки первого Quake рассказывает о необходимости творческого мышления в программировании.

    Много лет назад я работал в теперь уже не существующей компании-производителе видеоадаптеров Video Seven. Там я помогал в разработке клона VGA. Мой коллега Том Уилсон, долгие месяцы круглосуточно работавший над разработкой VGA-чипа Video Seven, стремился сделать VGA как можно более быстрым, и был уверен, что его производительность оптимизирована почти по максимуму. Однако когда Том уже вносил в конструкцию чипа последние штрихи, до нас донеслись слухи, что наш конкурент Paradise достиг ещё большей производительности в своём разрабатываемом клоне, добавив в него FIFO.

    На этом слухи заканчивались — мы не знали, ни что это за FIFO, ни насколько он помог, ничего другого. Тем не менее, Том, обычно приветливый и расслабленный человек, превратился в активного, одержимого фанатика со слишком большим процентом кофеина в крови. Исходя из этих крупиц информации, он пытался выяснить, что же удалось сделать Paradise. В конце концов он пришёл к выводу, что Paradise вероятно вставил FIFO-буфер записи между системной шиной и VGA, чтобы когда ЦП выполнял запись в видеопамять, записываемые данные сразу же попадали в FIFO, и это позволяло ЦП продолжать обработку, а не простаивать каждый раз, когда он выполнял запись в память дисплея.

    У Тома не было ни логических элементов, ни достаточно времени на реализацию полного FIFO, но ему удалось реализовать FIFO глубиной в одну операцию, что позволяло процессору обгонять VGA-чип на одну операцию записи. Том не был уверен, что это даст хорошие результаты, но это было единственное, что он смог сделать, поэтому он реализовал эту систему и передал чип в производство.
    Читать дальше →
    • +86
    • 23,7k
    • 6
  • Разработка Adblock Radio

    • Перевод


    tl;dr: Adblock Radio распознаёт аудиорекламу с помощью машинного обучения и Shazam-подобных техник. Основной движок с открытым исходным кодом: используйте его в своих продуктах! Можно объединить усилия для поддержки большего количества радиостанций и подкастов.

    Мало кому нравится слушать рекламу на радио. Я запустил проект AdblockRadio.com, чтобы слушатели могли пропускать рекламу на своём любимом интернет-радио. Алгоритм опубликован с открытым исходным кодом, а в этой статье описывается, как он работает.

    Adblock Radio уже протестировали на реальных данных более 60 радиостанций в семи странах. Он также совместим с подкастами и работает довольно хорошо!
    Читать дальше →
  • Решение японских кроссвордов с помощью SAT солвера

      На Хабре было несколько статей по решению японских кроссвордов, где авторы придумывали различные способы как такие кроссворды решать. В комментарии к статье Решение цветных японских кроссвордов со скоростью света я высказал мысль, что, поскольку, решение японских кроссвордов является NP-полной задачей, то и решать их надо с использованием соответствующего инструмента, а именно SAT солвером. Поскольку моя идея была встречена весьма скептически, я решил попробовать ее реализовать и сравнить результаты с другими подходами. Что из этого получилось можно узнать под катом.
      Читать дальше →
    • Схема разделения секрета Шамира

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

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

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

      Отчаявшись, вы уничтожаете дубликат и решаете разделить исходный ключ пополам. Теперь, вы думаете, два доверенных человека с фрагментами ключей должны физически присутствовать, чтобы собрать ключ и открыть хранилище. Это означает, что вору необходимо украсть два фрагмента, что вдвое труднее кражи одного ключа. Однако вскоре вы понимаете, что эта схема ненамного лучше, чем просто один ключ, потому что если кто-то потеряет половину ключа, полный ключ нельзя восстановить.
      Читать дальше →
    • C++20 и Modules, Networking, Coroutines, Ranges, Graphics. Итоги встречи в Сан-Диего

        До C++20 осталась пара лет, а значит, не за горами feature freeze. В скором времени международный комитет сосредоточится на причёсывании черновика C++20, а нововведения будут добавляться уже в C++23.

        Ноябрьская встреча в Сан-Диего — предпоследняя перед feature freeze. Какие новинки появятся в C++20, что из крупных вещей приняли, а что отклонили — всё это ждёт вас под катом.


        Читать дальше →
      • Методы наименьших квадратов без слёз и боли

        • Tutorial
        Итак, очередная статья из цикла «математика на пальцах». Сегодня мы продолжим разговор о методах наименьших квадратов, но на сей раз с точки зрения программиста. Это очередная статья в серии, но она стоит особняком, так как вообще не требует никаких знаний математики. Статья задумывалась как введение в теорию, поэтому из базовых навыков она требует умения включить компьютер и написать пять строк кода. Разумеется, на этой статье я не остановлюсь, и в ближайшее же время опубликую продолжение. Если сумею найти достаточно времени, то напишу книгу из этого материала. Целевая публика — программисты, так что хабр подходящее место для обкатки. Я в целом не люблю писать формулы, и я очень люблю учиться на примерах, мне кажется, что это очень важно — не просто смотреть на закорючки на школьной доске, но всё пробовать на зуб.

        Итак, начнём. Давайте представим, что у меня есть триангулированная поверхность со сканом моего лица (на картинке слева). Что мне нужно сделать, чтобы усилить характерные черты, превратив эту поверхность в гротескную маску?



        В данном конкретном случае я решаю эллиптическое дифференциальное уравнение, носящее имя Симеона Деми Пуассона. Товарищи программисты, давайте сыграем в игру: прикиньте, сколько строк в C++ коде, его решающем? Сторонние библиотеки вызывать нельзя, у нас в распоряжении только голый компилятор. Ответ под катом.
        Читать дальше →
      • Как создать игровой ИИ: гайд для начинающих

        • Перевод


        Наткнулся на интересный материал об искусственном интеллекте в играх. С объяснением базовых вещей про ИИ на простых примерах, а еще внутри много полезных инструментов и методов для его удобной разработки и проектирования. Как, где и когда их использовать — тоже есть.

        Большинство примеров написаны в псевдокоде, поэтому глубокие знания программирования не потребуются. Под катом 35 листов текста с картинками и гифками, так что приготовьтесь.

        UPD. Извиняюсь, но собственный перевод этой статьи на Хабре уже делал PatientZero. Прочитать его вариант можно здесь, но почему-то статья прошла мимо меня (поиском пользовался, но что-то пошло не так). А так как пишу в блог, посвященный геймдеву, решил оставить свой вариант перевода для подписчиков (некоторые моменты у меня оформлены по-другому, некоторые — намеренно пропущены по совету разработчиков).
        Читать дальше →
      • Парадокс времени ожидания, или почему мой автобус всегда опаздывает?

        • Перевод

        Источник: Wikipedia License CC-BY-SA 3.0

        Если вы часто ездите на общественном транспорте, то наверняка встречались с такой ситуацией:

        Вы приходите на остановку. Написано, что автобус ходит каждые 10 минут. Засекаете время… Наконец, через 11 минут приходит автобус и мысль: почему мне всегда не везёт?

        По идее, если автобусы приходят каждые 10 минут, а вы придёте в случайное время, то среднее ожидание должно составлять около 5 минут. Но в действительности автобусы не прибывают точно по расписанию, поэтому вы можете ждать дольше. Оказывается, при некоторых разумных предположениях можно прийти к поразительному выводу:

        При ожидании автобуса, который приходит в среднем каждые 10 минут, ваше среднее время ожидания будет 10 минут.

        Это то, что иногда называют парадоксом времени ожидания.
        Читать дальше →

      Самое читаемое