Логические игры

«2048» через несколько недель исполняется 5 лет, а значит, пора написать что-нибудь, посвящённое этой замечательной игре.

Особенно познавательна тема самостоятельной игры искусственного интеллекта в головоломку. Способы реализации есть самые разные и сегодня разберём относительно лёгкий из них. А именно — научим компьютерный разум собирать степени двойки с помощью метода Монте-Карло.

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

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

Невероятный успех AlphaZero, алгоритма с глубинным обучением, провозглашает новую эру мышления, которая может оказаться недолгой для человека

В начале декабря исследователи из компании DeepMind, занимающейся искусственным интеллектом и принадлежащей Alphabet Inc., родительской корпорации, также владеющей и Google, рассказали о происходящем на передних рубежах шахмат.

Годом ранее, 5 декабря 2017 года, команда поразила шахматный мир, объявив о своём алгоритме машинного обучения (МО) AlphaZero, который сумел овладеть не только обычными шахматами, но и японскими шахматами сёги и игрой го. Алгоритм начал работу без какого бы то ни было понятия об играх, кроме базовых правил. Затем он начал играть сам с собой несколько миллионов раз и учиться на своих ошибках. Всего за несколько часов алгоритм стал наилучшим игроком, как среди людей, так и компьютеров, из всех, что видел мир.

День первый. Нам подарили игру «Ticket to ride. Европа». Это моё первое знакомство с игрой данной серии, надо обязательно попробовать и заценить.

День пятый. Как-то надоело регулярно проигрывать, пора бы призвать на помощь математику и попробовать таким образом одержать заслуженную победу.


С помощью гугла, excel и python и чёртовой матери была проведена познавательная экскурсия в механики игры.

Что можно сделать с компьютером на электромагнитных реле у которого нет никаких устройств ввода, а из устройств вывода — только дамп восьми регистров?

Поиграть в игры, конечно! Играли же древние люди на калькуляторах МК-61/52, которые лишь немногим нагляднее.

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

Данная запись — вольный пересказ видео Is it Possible to Upload an Impossible Level in Super Mario Maker?. В ролике есть отсылка на видео The Impossible Level, поэтому перескажу и его. Мой пересказ не претендует на точность, я просто хочу поделиться интересным материалом.

О чём пойдёт речь

Поиск ошибок в ПО бывает очень разным. Я занимаюсь поиском ошибок в исходных кодах, в бинарных файлах, в больших комплексах программ и даже в каких-то железках. Но есть область, в которой я практически никогда ничем не занимался — поиск ошибок в компьютерных играх.

Люди тратят уйму времени, чтобы найти ошибки в играх. Это могут быть логические, математические и даже программистские ошибки. Кто-то делает это, чтобы посмотреть на игру под новым углом, а кто-то пытается пройти игру хоть на несколько секунд быстрее, чем любой другой игрок. Мне кажется именно сообщество спидранеров (людей, проходящих игры на скорость) внесло огромный вклад в дело поиска игровых глюков и ошибок. Но экономить время при прохождении мы будем в другой раз, сегодня просто рассказ о поиске ошибки в игровой логике.

В сентябре 2015 года компания Нинтендо выпустила Super Mario Maker — платформер про известного сантехника Марио. Одной из ключевых особенностей игры стала возможность пользователям самостоятельно создавать уровни (здесь они называются курсы) и делиться ими с другими игроками. Кто-то уровни создаёт, отслеживает процент успешных прохождений, а кто-то, собственно, проходит эти уровни. Именно в этот момент у игроков-исследователей зачесались руки — а можно ли опубликовать непроходимый уровень?


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

Прошлого декабря прошла волна новостей о невероятной силы нового шахматного движка использующего искусственный интеллект AlphaZero компнании DeepMind. Сегодня они выпустили потрясающие результаты обновленной версии этого движка.

Результаты снова не оставляют никаких сомнений в том, что AlphaZero является одним из сильнейших шахматных движков в мире.

Обновленный AlphaZero разгромил Stockfish 8 в новом матче с 1000 партий с результатом: 155 побед, 6 поражений, 839 ничьих.

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

Тем не менее, компания не останавливается на достигнутом, а продолжает работу. Благодаря исследованиям ее сотрудников на свет появилась улучшенная версия AlphaGo, которая получила название AlphaZero. Как и указано в заголовке, система сама смогла научиться играть сразу в три логических игры — шахматы, сеги и го.

Здравствуйте.

Хочу поделиться своей историей знакомства с игровой платформой Gameduino 3, а также немного расскажу о программировании простейшей логической игры под данную платформу, используемой совместно с Arduino Uno.

Что же такое Gameduino 3? Gameduino 3 — это плата расширения, которая позволяет превратить Arduino в современную карманную (имеется в виду размер) игровую консоль. К моему удивлению, мне не удалось найти на хабре какой-либо подробной информации о данной плате. Хотел бы восполнить этот пробел, тем более что плата, на мой взгляд, заслуживает внимания.

Немного истории

Автором проекта под названием Gameduino является Джеймс Боуман (James Bowman), который в 2011 году создал первую версию платы. Тогда она позиционировалась как модуль VGA для Arduino. Плата называлась Gameduino и была выполнена на основе программируемой логической матрицы FPGA компании Xilinx семейства Spartan-3A. На плате были установлены разъемы для подключения VGA монитора и стерео акустики.

Ранее я уже писал, как делал «электрический» конструктор из… картона. Увы проект пока так и остается на стадии прототипа, не перерастая в промышленный «физический» вид и ждет своего времени (и инвестора).

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

Продолжаем изучать шахматные фигуры вместе с ребенком. Теперь наступает очередь коня.

В силу окончания учебного года, произошла некоторая задержка и разрыв между ферзем и конем. С учетом того, что конь – самая сложная фигура в шахматах для изучения, материал готовился несколько дольше, чем обычно. Но вот он и вышел. Все диаграммы с разъяснениями под катом – милости прошу.

Статья с разбором игры известной торговой сети вызвала у нас в Cloud4Y живой интерес. Вот небольшие отрывки, чтобы ввести вас в курс дела:

Однажды, солнечным весенним утром, почитывая городской форум, я наткнулся на ссылку с простенькой игрой от известной торговой сети. Игра (акция), посвящённая чемпионату мира по футболу, представляла собой незамысловатое поле три на три, заполненное футбольными мячами. Кликая по мячу, мы открывали картинку с тем или иным товаром. При открытии трёх одинаковых картинок участнику гарантировалось бесплатное получение данного товара в одном из магазинов сети. Также под одним из мячей имелось изображение красной карточки, открытие которой означало конец игры.

Автор статьи принялся расследовать причины своего проигрыша и по результатам расчетов выяснил следующее:

Быстрый набросок формул на салфетке, и выяснилось, что вероятность выигрыша — 1/4. Для 5 полей пришлось повозиться, но расчётная вероятность получилась также 25%.
...
Запустив скрипт, я получил неожиданный результат — 25% выигрышей. Поиграв с количеством выигрышных элементов и общим количеством полей, я выяснил, что вероятность выигрыша в подобной игре не зависит от количества полей и равна единице, поделенной на количество выигрышных элементов, увеличенных на единицу.

Нас заинтересовала правильность такого расчета и, заменив салфетку на Excel, мы взялись за дело в поисках математической истины. Читателей, увлекающихся теорией вероятности, приглашаем под кат, дабы проверить правильность наших вычислений.

Чтоб я вновь устроил Сампо,
Сделал короб многострунный,
Вновь пустил на небо месяц,
Солнцу снова дал свободу…

                                 «Калевала»

Настольные игры выглядит очень привлекательно для начинающих разработчиков. Здесь нет необходимости в построении фотореалистичных изображений и применении сложных шейдеров (хотя никто не запрещает этим заниматься). Даже использование 3D, в подавляющем большинстве игр, вовсе не обязательно. Сложность настольных игр сосредоточена на не визуальных составляющих. Пользовательский интерфейс выглядит простым и до предела примитивным.

Вот только… он таковым не является! Сегодня я хочу рассказать о своём опыте в разработке дизайна пользовательского интерфейса настольных игр, накопленном более чем за год работы.

Феликс Земдегс установил мировой рекорд по сборке человеком кубика Рубика формата 3×3×3 двумя руками в одной попытке

Люди давно потеряли надежду конкурировать с роботами по скорости сборки кубика Рубика. Так, абсолютный рекорд среди роботов равняется 0,38 секунды, а робоконструкторы ещё хвастались, что специально ставили паузы между движениями, чтобы снизить риск поломки кубика.

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

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

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

Так как же выглядит равновесие Нэша в игре «камень-ножницы-бумага»? Давайте смоделируем ситуацию, в которой есть вы (Игрок A) и ваш противник (Игрок B), снова и снова играющие в игру. В каждом раунде победитель получает очко, проигравший теряет очко, а ничья засчитывается как ноль очков.

Продолжаем изучение шахматных фигур. Следующая фигура — это слон.

Казалось бы, слон фигура которая ходит еще проще чем ладья. Но, тем не менее, при первичном изучении слона с ним связано больше проблем чем с ладьей. Дети легче воспринимают движение по горизонталям и вертикалям, чем по диагоналям. Чтобы научить ребенка ходить слоном – заходите под кат. Вас там ждут диаграммы, некоторые не самые простые (для детей).

Как все знают из новостных лент, мы живём в постоянно эволюционирующей киберпанковской антиутопии. Люди подключают туалеты к Интернету! Если этот гибсоновский мир кажется вам слишком РЕАЛЬНЫМ, то вы можете поиграть в десять лучших видеоигр о взломе, программировании и вычислениях, чтобы сбежать в мета-антиутопию. Которая, я уверен, является намного лучшим местом.

10. TIS-100

[официальный сайт]

Да-а-а, приготовьтесь к тому, что ваш мозг начнёт болеть. TIS-100 — это игра студии Zachtronics, разработчика игр-головоломок, выпустившей Infinifactory и SpaceChem. В маркетинге она позиционируется как «игра о программировании на языке ассемблера, о которой вы не просили», и хотя я обычно игнорирую маркетинговые слоганы, здесь не могу не согласиться.

Игрок получает в своё распоряжение таинственный компьютер из 70-х, найденный в вещах покойного дядюшки. Когда-то он игрался с ним, пытаясь разобраться. Теперь это ваша задача. Если вкратце, то вам нужно получить числа, чтобы провести машину из точки A в точку B, выполнив на каждом уровне «цели» (например, сначала вывести положительное число, а затем отрицательное). Для этого у вас есть список команд, изложенных в смутном руководстве пользователя. Игра советует вам распечатать это руководство в бумажном виде. В нём есть сделанные дядей примечания и пометки маркером, дающие подсказки о сущности этой машины.

— А мне вот чо любопытно, — сказал Угрыз.  
— А зачем у тебя на шляпе пробки?
— Чтобы мух отгонять, — объяснил Ринсвинд.
— И как, получается?
— Ясен перец нет, — фыркнул Клэнси.
— Если бы помогало, кто-нибудь до ентого давно бы уже додумался.
— Ну да. Я и додумался, — сказал Ринсвинд.
— Будь спок.
 
     сэр Терри Пратчетт «Последний континент»

Эта игра символизирует непрерывный духовный поиск, борьбу со стереотипами и примирение со своим альтер эго. Ладно, кого я пытаюсь обмануть? Я просто увидел её во сне.

В последнее время, все больше и больше разговоров о том, что детям начального школьного возраста надо преподавать шахматы. В данном вопросе выступили всевозможные руководители (Илюмжинов, фонд Тимченко, Васильева, Путин). Шахматный курс поступил на опробирование в школы в начальные классы, дети начали по нему обучение. И вот тут хорошие новости заканчиваются… Все на самом, все значительно сложнее чем кажется. И возможно хуже.

Если у Вас дети учатся в школах, и их используют для данного пробного внедрения системы «обучения» шахматам, то вам однозначно под кат. Если нет – то скоро будет ваша очередь.
В этой статье речь пойдет про курс «Шахматы в школе», авторы Э.Э. Уманская, Е.И. Волкова, Е.А. Прудникова. Добро пожаловать в ад…