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

Пятничный 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 = ; 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, как нетрудно заметить, содержит в себе практически полностью продублированный текст программы. Поэтому помимо «простого» текста она также содержит «магические» подстановочные последовательности, ограниченные с двух сторон символом "$".

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

Итог

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

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

До новых встреч. До свидания, девочки и мальчики.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Минкомсвязи одобрило законопроект об изоляции рунета

Министерство цифрового развития, связи и массовых коммуникаций РФ поддержало законопроект №608767-7 об автономной работе рунета, внесённый в Госдуму 14 декабря 2018 года. Об этом сегодня сообщил замглавы Минкомсвязи Олег Иванов в ходе расширенного заседания комитета Госдумы по информационной политике, информационным технологиям ...

ЦЕРН планирует построить новый ускоритель с протяженностью тоннеля в 100 км

Источник: M.Brice/CERN Располагается она на границе Швейцарии и Франции, рядом с Женевой. ЦЕРН — европейская организация по ядерным исследованиям, которая представляет собой крупнейшей в мире лаборатории физики высоких энергий. БАК помог совершить множество открытий, которые помогли ученым лучше понять строение ...