Пятничный JS: квайн, который играет в крестики-нолики
Приветствую всех в своей традиционной рубрике, полной лавкрафтианского безумия.
В процессе написания одной из прошлых статей (не ищите, она была не особенно хороша) я задумался над тем, что квайн… Да, на всякий случай напомню: квайн — это программа, которая выводит свой собственный текст, причём делает это «честно» (не подсмотрев, допустим, этот текст в файле на жёстком диске). В общем, традиционная бессмысленная пузомерка программистов.
Так вот, я задумался над тем, что квайн, в принципе, может нести произвольную полезную нагрузку. То есть — делать ещё что угодно помимо своей основной функции. И в качестве proof-of-concept я решил написать квайн, который играет в крестики-нолики. И написал. Грязные подробности под катом.
«Но как он может делать что-то ещё, кроме вывода своего текста?» — возможно, спросите вы. А легко. Помимо вывода, у программы также есть ввод. Если программа выводит свой текст при отсутствии ввода — значит, она квайн. Если же программа при наличии ввода делает что-то ещё — кто мы такие, чтобы её осуждать?
Пожалуй, выложу сразу карты на стол. Вот ссылка на моё творение. В файле по ссылке присутствуют три сущности:
- Функция quine — это то самое, о чём я говорю.
- Функция evalAndCall — вспомогательная.
- Класс 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
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 поступает состояние поля — массив из девяти элементов. Каждый элемент может быть крестиком, ноликом, подчёркиванием (пустым полем) или восклицательным знаком (пустым полем, на которое стоит поставить крестик при первой же возможности). Мы склеиваем массив в строку и ищем соответствующее правило в объекте rules. Для экономии места правила приведены с точностью до поворота, поэтому для поиска поле поворачивается четыре раза. Когда нужное правило найдено, состояние поля заменяется значением правила, разбитым на символы. Затем функция next возвращает новое состояние поля. При этом к нему может присоединиться дополнительный десятый символ: «w» — если ИИ победил, «d» — если наступила ничья.
Благодаря восклицательным знакам — «подсказкам» и поворотам поля, а также, разумеется, благодаря тому, что ИИ ходит первым, оптимальную стратегию удалось описать всего в 6 правил.
Используя функцию next, функция quine обрабатывает ввод и записывает некоторые поля в объект magicHash. И тут мы плавно переходим ко второй части: как работает «квайновая» составляющая. Вся магия — в объекте magicHash и его свойстве magicString.
Строка magicString, как нетрудно заметить, содержит в себе практически полностью продублированный текст программы. Однако, как знает каждый, кто когда-либо пытался написать квайн, совсем полный текст в неё запихнуть нельзя — ведь тогда ей придётся строго содержать саму себя, что невозможно для строк конечной длины. Поэтому помимо «простого» текста она также содержит «магические» подстановочные последовательности, ограниченные с двух сторон символом »$».
Когда наступает час икс и мы должны вернуть текст функции, мы просто берём magicString и заменяем в ней подстановочные последовательности соответствующими свойствами объекта magicHash. Эти свойства могут быть статическими (backtick), меняться в процессе выполнения (field) или даже добавляться в процессе выполнения (message) — это неважно. Важно, что для каждого «проблемного» куска кода, который нельзя просто продублировать в строке, у нас есть «волшебное» свойство объекта magicHash.
Итог
Я проверил на собственном опыте, что в квайн можно запихнуть что угодно. В принципе, если позаморачиваться, можно сделать квайногенератор — функцию, которая превращает в квайн любую другую чистую функцию и позволяет хранить произвольное состояние, к которому вышеупомянутая чистая функция сможет обращаться. Однако поля этой рукописи слишком узки…
В общем-то, я не претендую на особую новизну своего «открытия». Хардкорные функциональщики наверняка читали этот текст с улыбкой превосходства. Но мне было интересно поковырять это своими руками, вложить, так сказать, персты в раны. И я надеюсь, что вам было интересно про это читать.
До свидания, девочки и мальчики. До новых встреч.
