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

Думаю, ни для кого не секрет, что "Дурак" (далее это слово будет написано с маленькой буквы и без кавычек) — это самая популярная карточная игра в России и странах бывшего СССР (хотя и почти неизвестная за его пределами). Несмотря на свое название и довольно несложные правила, выигрыш в ней все-таки зависит больше от мастерства игрока, чем от случайного расклада карт (в английской терминологии игры того и другого типов называются соответственно game of skill и game of chance. Так вот — дурак в большей степени game of skill).

Целью статьи является написание простого ИИ для игры. Под словом "простого" подразумевается следующее:

• интуитивно понятный алгоритм принятия решений (то есть, как следствие, никакого машинного обучения, в котором этот алгоритм скрыт глубоко "под капотом");
• отсутствие состояния (то есть, алгоритм руководствуется только данными на текущий момент времени, проще говоря, ничего не запоминает (например, не "считает" вышедшие из игры карты).

Уровни сложности чтения

• Я слишком молод, чтобы думать

  
  
  • Введение и правила игры
  • Как они это делают?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Сделай мне умно

  
  
  • Введение и правила игры
  • Как они это делают?
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Кошмар

  
  
  • Введение и правила игры
  • Как они это делают?
  • Конечная геометрия для грудничков
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Как построить проективную плоскость?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

Введение и правила игры

Несколько лет назад я купил игру Доббль (Dobble, оригинальное название “Spot It!”). Это очень простая, быстрая и весёлая игра, которую я считаю одной из лучших настольных игр вообще.

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

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

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

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

В 2017 году покерный бот Libratus попал в заголовки СМИ, когда обыграл четырёх профессионалов в безлимитный холдем на дистанции 120 000 рук. Теперь технологию адаптировали для военного применения.

Разработчики систем слабого ИИ часто сравнивают эффективность своих программ в игровом противостоянии против человека. В играх с полной информацией в любой момент игры все игроки имеют полную информацию о состоянии игры, то есть о позиции и всех возможных ходах любого из игроков. В отличие от таких детерминированных ситуаций, в играх с неполной информацией часть информации о состоянии игры скрыта от игрока — например, карты оппонента. Безлимитный холдем как раз одна из таких игр. Кроме закрытых карт оппонента, добавляется здесь элемент неопределённости за счёт произвольного размера каждой ставки. С учётом этого количество возможных исходов оценивается в 10¹⁶¹. Выработка оптимальной стратегии в условиях неопределённости с учётом тактики оппонента — именно то, что нужно военным.

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

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

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

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

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


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

Теория ходов

«Мы сыграли в гляделки, и, по-моему, противник моргнул», — сказал государственный секретарь США Дин Раск на пике кубинского ракетного кризиса в октябре 1962 года. Он имел в виду сигналы, которые подавал Советский Союз, желая разрешить самую опасную ядерную конфронтацию между двумя сверхдержавами, которую многие аналитики интерпретировали как классический пример игры в ядерного «цыплёнка» (на русском аналог этой игры называется «ястребы и голуби»).

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

Хотя с виду карибский ракетный кризис похож на игру в «цыплёнка», на самом деле он плохо моделируется этой игрой. Другая игра более точно описывает действия лидеров США и Советского Союза, но даже для этой игры стандартная теория игр не полностью описывает доступные им варианты выбора.

С другой стороны, воспроизводит или предсказывает прошлое действий лидеров «теория ходов» (theory of moves), основанная на теории игр, но радикально меняющая стандартные правила игры. Что ещё более важно, эта теория проливает свет на динамику игры, основываясь на предположении, что игроки думают не только о непосредственных последствиях их действий, но и об их влиянии на игру в будущем.

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

Поиграть в игры, конечно! Играли же древние люди на калькуляторах МК-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. Как и указано в заголовке, система сама смогла научиться играть сразу в три логических игры — шахматы, сеги и го.

^{Ханойские башни}
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)

Крестики-нолики… в них играли все, я уверен. Игра притягательна своей простотой, особенно когда ты тянешь часы где-нибудь на уроке, паре, а под рукой нет ничего, кроме тетрадного листа и простого карандаша. Уж не знаю, кто первым когда-то догадался рисовать кресты и кружки в 9 квадратах, но с тех пор игра нисколько не потеряла в востребованности, тем более, что народ придумал огромное множество её вариаций.



Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:

1. Поле может быть сколь угодно большим (На сколько хватит тетради)
2. Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.

Все просто… и в то же время сложно: исход игры не может быть просчитан заранее, как в классическом аналоге. Этот «маленький проектик» отнял у меня много времени и нервов. Надеюсь, что вам будет интересно.

Привет всем, я Никита Куртин, куратор израильской высшей школы IT и безопасности HackerU.

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

Для тех, кто пропустил первый пост расскажу, этим летом Checkpoint, опубликовала серию кибер испытаний.
Челлендж официально завершился к концу сентября 2018-го.

Задачи поделили на шесть категорий:

• Logic
• Web
• Programming
• Networking
• Reversing
• Surprise

По две задачки на каждое направление. Как я уже писал, Checkpoint до этого уже успел завоевать уважение и интерес с мой стороны, поэтому я решил принять эти вызовы. Однако ввиду занятости, смог позволить себе взяться лишь за 8 из 12 заданий (из четырёх разных категорий). И решить мне удалось 7 из них.

И так:

Челлендж: «Пазл»

Описание:

Наконец-то мы тебя нашли!

Привет всем, я Никита Куртин, куратор израильской высшей школы IT и безопасности HackerU

Этим летом ведущая израильская компания в области информационной безопасности Checkpoint, опубликовала серию кибер испытаний.

Задачи поделили на шесть категорий:

• Logic
• Web
• Programming
• Networking
• Reversing
• Surprise

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

Checkpoint до этого уже успел завоевать уважение и интерес с мой стороны, поэтому я решил принять эти вызовы. Однако ввиду занятости, смог позволить себе взяться лишь за 8 из 12 заданий (из четырёх разных категорий). И решить мне удалось 7 из них.

Челлендж официально завершился к концу сентября 2018-го.



Поэтому теперь я с чистой совестью могу рассказать пошагово о том, как я прорывался к решению следующих задач:

• Логический челлендж «PNG++»
• Web челлендж «Роботы возвращаются»
• Web челлендж «Галерея Диего»
• Задача на программирование «Осторожные шаги»
• Задача на программирование «Пазл»
• Нетворкинг челлендж «Пинг Понг»
• Нетворкинг челлендж «Протокол»

Челлендж: PNG++

Описание:

Это (ссылка на зашифрованный файл PNG) изображение было закодировано с использованием пользовательского шифра.

Нам удалось считать большую часть этого кода здесь (ссылка на python код).
К несчастью, кто-то нерасторопный пролил кофе на весь key_transformator.py.

Путешественники, привет.

Если вы это читаете предлагаю продолжение того "занимательного" материала, который я писал перед этим. Если вы немного проследили за мыслью, которая изветвилась в три статьи, а основной то посыл — был, только в том, чтобы показать интерес к декларативному подходу. Он почему то не велик, как будто эСКюэЛ не стал общедоступным и обязательным, ведь без него невозможно подумать, а как можно обработать данные иначе. Правда, ведь лучше сформулировать задачу и не заботиться о том, во что это воплощается.

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

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

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

Хватит вызывать заинтересованность, начинаю...