Tic Tac Toe AI with Neural Network

Анонс компьютерной игрушки, кодинг которой доставил автору немало удовольствия… хм, собственно, на фоне огромного числа консольных Tic Tac Toe (крестики-нолики, если по-нашему) — заведомо невозможно придумать эксклюзив, количество такого рода поделок на всех живых и неживых языках программирования поистине несметно сегодня… можно только в очередной раз «велосипедить», как обожают формулировать программисты.


Дознание пилота Пиркса, 1978 г.

Да, все так; но вот вариаций этой игрушки, позволяющих игру не человека с человеком, но — человека с роботом (AI, Artificial Intelligence) — значительно меньше: это сложнее. Количество же скриптов, использующих для игры в Tic Tac Toe нейронные сети, Neural Network — еще того меньше… ок, тем интереснее, согласитесь, попробовать.

В ходе работы спецом избегал чтения документации аналогов приложений для игры в Tic Tac Toe, дабы уберечься от соблазна попросту форкнуть чужой проект: лицензии, под которыми опубликован программный код — как правило, позволяют подобное, используй и учись на здоровье… да, но что за интерес в чужой колее и чужом алгоритме. Тем более, мелькнула в голове забавная идея реализации логики игры… что получится в итоге — Бог весть, но уже вполне можно показать и рассказать то, что получилось на данный момент.

Идея на редкость проста, и берет начало от т. н. «грубого брутфорсинга», т. е. прямого перебора вариантов ходов, на подобном когда-то строились неуклюжие и медлительные аппараты (да, задолго до появления персональных компьютеров) для игры в шахматы. Но Tic Tac Toe ведь не шахматы, так что — в самый раз.


Tic Tac Toe AI with Neural Network (ruby-fann)

Взгляните видео; нет, не фрагмент из «Дознания пилота Пиркса», который мне попросту было приятно опубликовать здесь, а — второе. При запуске программа проверяет наличие текстового файла с записями разнообразных положений на доске Tic Tac Toe, также — сделанных при этом ходов; каждая строка включает в себя, помимо перечисленного, еще и некоторую иную информацию: порядковый номер хода, псевдоним (Human / AI) участника, количество ходов, за которые игра пришла к завершению, также итог игры — кто в итоге выиграл или проиграл, либо ничья, etc.

«Программа проверяет», хм. Что происходит далее, если не находит? — а очень просто: начинает рандомно играть в крестики-нолики сама с собой… что же еще, как не это. Через несколько дней, свершив по возможности некоторый (крайне необходимый, надо признаться) рефакторинг — опубликую код в своем гитхабе, откуда крайне несложно его загрузить и, запустив на своем (правда, понадобится установленный Ruby) компьютере — проверить сказанное, а пока что поверьте на слово: даже на медленном ПК проиграть таким образом десять — двадцать тысяч партий, автоматически (никаких дополнительных действий не требуется, всего только запустить скрипт) логировав в csv-файл — занимает одну или две минуты, не более.


11.12.2019: ruby-скрипт под эффектным названием Tic-Tac-Toe-AI-with-Neural-Network доступен на GitHub, по ссылке. Опубликовал, несмотря на то, что логику показанной нейронной сети на основе ruby-fann возможно в значительной степени усовершенствовать и дополнить: я постараюсь это сделать в самом ближайшем будущем.


А хотите, проверим теперь вашу способность к алгоритмическому мышлению? Предположим, играя со мной к Tic Tac Toe, компьютерная программа на очередном ходе нашла в csv-файле актуальную позицию, причем не одну, а несколько, и для каждой — свой ход. Скажите, 1) как выбрать оптимальный ход, обладая информацией, перечисленной выше? 2) как определить наихудший ход из всех возможных, заведомо приводящий к проигрышу?

Спойлер: все не просто, а очень просто. Не читайте дальше, если хотите догадаться самостоятельно. Потому что я объясню, и вы моментально поймете: самый лучший ход — тот, на котором игра заканчивается, т.е. номер хода равен количеству ходов в игре. Пусть так случится хотя б один-единственный раз на любое количество партий, что это меняет? — ничего; если подобный ход возможен — он единственно верен. А вот наихудший ход — это, вероятно, тот, порядковый номер которого разнится от количества ходов в игре на единицу (опять-таки: хотя бы в одной из многих игре! здесь, как и в реальной жизни, имеет место быть приоритет: один правильный ответ стоит заведомо больше, нежели терабайты демагогии). Думаю, нет сейчас необходимости в подробных рассуждениях, почему так происходит; — в игре, в жизни?

Помимо этих несложных правил, существуют (либо появятся в следующих релизах скрипта) и другие, логика которых аналогична описанной. Пока что из моих экспериментов следует, что просчитывать вилки подобным образом — излишне ресурсоемко (следовало ожидать) даже в Tic Tac Toe, но… тем интереснее попробовать решить проблему, не слишком отдаляясь от первоначального замысла. А пока что — вот так, как на скринкасте: для игрока, играющего вторым номером (т.е ноликами) — вполне сносно играет Artificial Intelligence. Хотя и не всегда одинаково: случайно, пусть и в большом количестве, отыгранные партии способны ощутимо влиять на различия в игре нашей нейронной сети, созданной посредством ruby-fann, рубиновой обертки FANN (Fast Artificial Neural Network)… что же, совсем несложно пересоздать csv-файл (попросту удалив старый и запустив скрипт снова), попутно изменив, при желании, количество «тренировочных» партий.

Попробовав сформулировать подоплеку данной программной логики и попытавшись провести, шутливой иронии ради, некоторую аналогию… — а почему нет, спроецировали же мы ранее на современный технологический стек понятие сугубо из биологии «нейронная сеть»! — приходим к красивому выводу: на любой вопрос уже существует ответ, нужно только уметь этот ответ отыскать, применив крайне несложные механизмы; также и личность человека в наибольшей степени определяется, возможно, именно эмпирическим опытом. Это как бы взгляд на тебя со стороны… такой вот панегирик старому доброму эмпиризму. Попытайтесь проанализировать подлинные (а не поверхностные) причины разрыва любых отношений в своей жизни, и придете к странному выводу: вы расстаетесь с человеком именно в тот момент, когда его восприятие — то, каким он вас видит — перестает вас устраивать. Нет? Наиболее выпукло подобное свойство нашей самости проявляет себя в знаковой ситуации, известной в психологии отношений как «третий лишний»: вот собрались вместе трое знакомых, и каждый из них чувствует себя немного, что называется, «не в своей тарелке»… разгадка же психологической коллизии проста: восприятие вас «каждым другим» всегда несколько разнится, и попытка свести в одно целое несколько, по сути, разных ваших «я» — приводит к внутреннему конфликту.

Иллюстрацией именно подобного взгляда на мир служит, по мысли автора, демонстрация этой компьютерной игрушки для кодеров, взгляда почти что эзотерического… хм, не много ли на себя беру? Ну, что поделать: знаковые произведения Станислава Лема и Айзека Азимова, на которых росло не одно поколение программистов — представляются мне сегодня попыткой продолжить все тот же старый-престарый разговор, начавшийся… Бог весть когда, но по самым скромным оценкам — за сотню-другую тысячелетий до появления на нашей планете «неуклюжих и медлительных аппаратов для игры в шахматы» или крестики-нолики…

Ваш комментарий

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