Пятничный JS: квайн, который играет в крестики-нолики

    Приветствую всех в своей традиционной рубрике, полной лавкрафтианского безумия.

    В процессе написания одной из прошлых статей (не ищите, она была не особенно хороша) я задумался над тем, что квайн… Да, на всякий случай напомню: квайн — это программа, которая выводит свой собственный текст, причём делает это «честно» (не подсмотрев, допустим, этот текст в файле на жёстком диске). В общем, традиционная бессмысленная пузомерка программистов.

    Так вот, я задумался над тем, что квайн, в принципе, может нести произвольную полезную нагрузку. То есть — делать ещё что угодно помимо своей основной функции. И в качестве proof-of-concept я решил написать квайн, который играет в крестики-нолики. И написал. Грязные подробности под катом.

    image

    «Но как он может делать что-то ещё, кроме вывода своего текста?» — возможно, спросите вы. А легко. Помимо вывода, у программы также есть ввод. Если программа выводит свой текст при отсутствии ввода — значит, она квайн. Если же программа при наличии ввода делает что-то ещё — кто мы такие, чтобы её осуждать?

    Пожалуй, выложу сразу карты на стол. Вот ссылка на моё творение. В файле по ссылке присутствуют три сущности:

    1. Функция quine — это то самое, о чём я говорю.
    2. Функция evalAndCall — вспомогательная.
    3. Класс Game — ещё более вспомогательный

    Сначала мы поговорим о том, как с функцией quine работать, а затем — как она устроена.

    Как с ней работать


    В самом начале функции quine вы можете увидеть следующее:

    function quine(input){/*
    
    
    
                |1|2|3|
                |4|x|6|
                |7|8|9|
    
    
    
      Привет! Я - квайн, который умеет играть в крестики-нолики. Правда, только за крестики.
      Если выполнить меня без аргументов, я верну собственный текст, поэтому я и называюсь квайном. 
      А если в качестве аргумента передать мне номер свободной клетки на игровом поле, вы сделаете свой ход.
    
        Статистика:
      Ваших побед - 0
      Ваших поражений - 0
      Ничьих - 0
    */
    

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

    Давайте проверим, что функция действительно квайн. Вот тут для удобства я выложил (почти) пустую HTML-страницу с подключенным скриптом quine.js. Открыв инструменты разработчика, можно невозбранно вбить туда следующий код:

    const quineText = quine();
    const evaluatedQuine = eval("(" + quineText + ")");
    //скобки нужны, потому что без них eval не воспринимает объявление функции как выражение
    //и возвращает undefined, собака страшная
    const evaluatedQuineText = evaluatedQuine();
    quineText == evaluatedQuineText; // true
    

    Зануда-мод
    На самом деле, конечно, мы проверили лишь то, что функция quine возвращает текст квайна, а не что она сама является квайном. А если быть совсем точным — мы проверили только то, что функция quine возвращает текст функции, которая в нашем случае сработала как квайн. Нет никаких гарантий, что внутри не содержится что-то типа:

    if(Math.random() < 0.99){
      beAGoodQuine();
    }else{
      haltAndCatchFire();
    }
    


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

    let quineText = quine(1);
    

    Теперь «пользовательский интерфейс» выглядит следующим образом:

    function quine(input){/*
    
    
    
                |o|x|3|
                |4|x|6|
                |7|8|9|
    
    
    
      Привет! Я - квайн, который умеет играть в крестики-нолики. Правда, только за крестики.
      Если выполнить меня без аргументов, я верну собственный текст, поэтому я и называюсь квайном. 
      А если в качестве аргумента передать мне номер свободной клетки на игровом поле, вы сделаете свой ход.
    
        Статистика:
      Ваших побед - 0
      Ваших поражений - 0
      Ничьих - 0
    */
    

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

    let quineText = quine();
    
    //далее в комментах буду писать состояние поля и иную информацию, которую я сочту интересной.
    /*
                |1|2|3|
                |4|x|6|
                |7|8|9|
    */
    
    quineText = evalAndCall(quineText, 1)
    /*
                |x|o|3|
                |4|x|6|
                |7|8|9|
    */
    
    quineText = evalAndCall(quineText, 3)
    /*
                |x|o|o|
                |4|x|6|
                |7|8|x|
    
      В этой игре я победил. Чтобы начать новую игру, передайте мне 0 в качестве аргумента
    */
    
    quineText = evalAndCall(quineText, 0)
    /*
                |1|2|3|
                |4|x|6|
                |7|8|9|
    
        Статистика:
      Ваших побед - 0
      Ваших поражений - 1
      Ничьих - 0
    */
    

    Вуаля! Квайн играет, выигрывает и даже ведёт счёт. Можете поиграть с ним подольше, но для большего удобства я рекомендую использовать класс Game, с помощью которого тестировал игру сам. Думаю, если вы дочитали до этого момента, мне не надо объяснять, как его использовать.

    Как всё устроено


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

    Ядро «искусственного интеллекта» находится на строках 66-90 и силуэтом напоминает упоротую белку:

      const rules = {
        "o___x____": "ox__x__!_",
        "ox__x__o_": "ox!_x_xo_",
        "oxo_x_xo_": "oxo!xxxo_",
        "oxooxxxo_": "oxooxxxoxd",
        "_o__x____": "xo__x___!",
        "xo__x___o": "xo_xx!!_o"
      };
      const next = (field, move) => {
        if(!~"!_".indexOf(field[--move])){
          return null;
        }
        field[move] = "o";
        const win = field.indexOf("!");
        if(~win){
          field[win] = "x";
          return [...field, "w"];
        }
        for(let n = 0; n < 4; n++){
          field = field.map((_, i) => field[[2, 5, 8, 1, 4, 7, 0, 3, 6][i]]);
          rules[field.join("")] && (field = rules[field.join("")].split(""));
        }
        return field;
      }

    Этот код выглядит немного обфусцированным, потому что мне интересно было сделать его как можно более коротким. Суть его такова: на вход функции next поступает состояние поля — массив из девяти элементов, — а также номер клетки, куда делает ход игрок-человек (next проверяет валидность этого хода). Каждый элемент поля может быть крестиком, ноликом, подчёркиванием (пустой клеткой) или восклицательным знаком (пустой клеткой, на которую стоит поставить крестик при первой же возможности). Если на поле есть восклицательный знак, мы немедленно делаем ход туда и выигрываем. В противном случае мы склеиваем массив в строку и ищем соответствующее правило в объекте rules. Для экономии места правила приведены с точностью до поворота, поэтому для поиска поле поворачивается четыре раза. Когда нужное правило найдено, состояние поля заменяется значением правила, разбитым на символы. Затем функция next возвращает новое состояние поля. При этом к нему может присоединиться дополнительный десятый символ: «w» — если ИИ победил, «d» — если наступила ничья.

    Благодаря восклицательным знакам-«подсказкам» и поворотам поля, а также, разумеется, благодаря тому, что ИИ ходит первым, оптимальную стратегию удалось описать всего в 6 правил.

    Используя функцию next, функция quine обрабатывает ввод и записывает некоторые поля в объект magicHash. И тут мы плавно переходим ко второй части: как работает «квайновая» составляющая. Вся магия — в объекте magicHash и его свойстве magicString.

    Строка magicString, как нетрудно заметить, содержит в себе практически полностью продублированный текст программы. Однако, как знает каждый, кто когда-либо пытался написать квайн, совсем полный текст в неё запихнуть нельзя — ведь тогда ей придётся строго содержать саму себя, что невозможно для строк конечной длины. Поэтому помимо «простого» текста она также содержит «магические» подстановочные последовательности, ограниченные с двух сторон символом "$".

    Когда наступает час икс и мы должны вернуть текст функции, мы просто берём magicString и заменяем в ней подстановочные последовательности соответствующими свойствами объекта magicHash. Эти свойства могут быть статическими (backtick), меняться в процессе выполнения (field) или даже добавляться в процессе выполнения (message) — это неважно. Важно, что для каждого «проблемного» куска кода, который нельзя просто продублировать в строке, у нас есть «волшебное» свойство объекта magicHash. Последней производится подстановка самой magicString в себя. Последней — потому что иначе возникли бы дополнительные подстановочные последовательности, которые были бы также заменены.

    Итог


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

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

    До свидания, девочки и мальчики. До новых встреч.
    • +33
    • 4,8k
    • 7
    Поделиться публикацией

    Похожие публикации

    Комментарии 7

      +1
      Если вдруг кому интересно, вот моя аналогичная поделка на платформе 1С: infostart.ru/public/546662

      Только это не квайн, а мультиквайн. Курица и яйцо. Игрушка «курица» кроме прочего имеет функцию выдачи исходника яйца, а игрушка «яйцо» выдаёт исходник курицы.
        +1
        Отлично! К сожалению, не знаю 1С на уровне, достаточном, чтобы оценить детали реализации, но результат радует взгляд.
          +1
          Там я играю на том, что 1Совские формочки можно отрисовывать не только мышкой в конфигураторе, но и генерить программно при отработке текста модуля. А раз так, то и карты в руки.
        +1

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

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

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


          Это позволило разрабатывать разные квайны на C#, среди которых квайн-палиндром, часы, игра "Змейка". В теории такой подход можно обобщить на другие языки и попробовать, например, писать квайновые эстафеты.


          В репозитории всего этого безобразия Freaky-Sources даже IDE есть :)

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

            Польщён, что истинный сотона квайнов заглянул в мои скромные комменты)
            0
            квайн, в принципе, может нести произвольную полезную нагрузку. То есть — делать ещё что угодно помимо своей основной функции.

            Ну еще язык HQ9+ кроме вывода текста программы (одной инструкцией) позволяет вывести 99-бутылочный тест (другой инструкцией), а также «Hello world» (третьей).
            Конечно, не факт, что это можно назвать полезным… Тем более четвертую инструкцию — инкремент внутренней переменной (без возможности вывода).

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

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