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

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

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

18 октября в журнале Nature была опубликована статья компании DeepMind о новых достижениях AlphaGo. Новая версия программы получила название Zero, так как была обучена с нуля без использования данных, полученных от человека, кроме правил самой игры Го. Для тренировок прошлой версии, победившей в чемпионатах с людьми, изначально использовался метод обучения с учителем (supervised learning), и лишь потом обучение с подкреплением (reinforcement learning). То есть изначально программа тренировалась, изучая человеческий опыт и лишь потом на игре против своих же версий. То есть прежняя версия изначально училась предсказывать человеческие ходы. AlphaGo Zero стала своим собственным учителем: нейронная сеть тренировалась предсказывать свой собственный выбор, а также выбор версии-чемпиона.

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

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

В «базе знаний» AlphaGo Zero — правила го и больше ничего. Тем не менее, программа очень быстро совершенствуется, играя сама с собой. Разработчики утверждают, что Zero освоила правила игры всего за несколько часов. Спустя три дня самообучения AlphaGo Zero победила AlphaGo Lee, версию ИИ, которая победила Ли Седоля со счетом 4:1 в 2016 году.

Всё страньше и страньше!
Всё чудесатее и чудесатее!
Всё любопытственнее и любопытственнее!
Всё страннее и страннее!

Льюис Кэрролл «Алиса в Стране чудес»

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

Первый вариант головоломки 1850 года, когда два ферзя заранее установлены на доску, а игрок должен расставить остальных ферзей (два решения задачи см. под катом)

Задача о N ферзях состоит в том, чтобы разместить N ферзей на доске размером N×N таким образом, чтобы ни один ферзь не находился под боем другого, при этом на доске заранее установлены несколько ферзей. То есть в итоге никакие два ферзя не должны находиться на одной линии или диагонали. Впервые задачку сформулировали в 1848 году, а в 1850 году придумали вариант головоломки, когда некоторое количество ферзей заранее поставлено на доску, а игрок должен расставить остальных, если это возможно.

Исследователи из Сент-Эндрюсского университета (Шотландия) опубликовали научную статью, в которой доказывают, что задача о N ферзях является не только #P-полной задачей, но также NP-полной задачей. Более того, Математический институт Клэя (США) готов заплатить миллион долларов любому, кто сможет оптимизировать решение этой задачи как задачи на доказательство P=NP.

История дуэли двух людей, один из которых умирает, и поиски способа создать искусственный интеллект

Марион Тинсли – профессор математики, священник, лучший игрок в шашки в мире – сидел за столом напротив компьютера и умирал.

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

Его оппонентом был "Chinook" («Шинук»), программа, играющая в шашки, созданная Джонатаном Шеффером, человеком с вьющимися волосами, пухлым, занимающим должность профессора Альбертского университета. В тот день он управлял машиной. Благодаря маниакальной работе над «Шинук», она стала очень хорошим игроком. Она не проиграла ни одной игры за последние 125 игр – и с тех пор, когда они близко подошли к победе над Тинсли в 1992 году, Шеффер с командой потратили тысячи часов на улучшение программы.

*почти

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

Volvox

Вся правда о новейшей вирусной задачке из Сингапура и ещё одной исторической загадке с числами



В честь юбилея этой колонки интернет любезно предоставил мне сингапурскую математическую задачку, ставшую вирусной. В середине мая веб был взволнован задачей, которую, якобы дают решать первоклассникам Сингапура, а это дети возрастом от 5 до 7 лет, и которая оказалась настолько сложной, что никто не может её решить.

В марте 2016 года один из сильнейших из людей игроков в го впервые проиграл компьютерной системе, играя без форы. До этого момента лучшем достижением считали выигрыш при 4 камнях форы, а игра на равных была ещё далеко — возможно, где-то в следующем десятилетии. Внезапно на сцене появилась система AlphaGo от британской DeepMind, которая со счётом 4:1 обыграла одного из самых известных игроков последних лет Ли Седоля.

Год назад южнокорейский игрок 9-го профессионального дана проиграл компьютерной системе подразделения Google, и в восприятии многих го перешла в разряд игры, в которую машины играют сильнее лучших из людей. Больше AlphaGo почти никак не «светилась». В апреле этого года DeepMind разразилась объявлением: AlphaGo сыграет с игроком первой строчки рейтингов Кэ Цзе. Сам он сообщал о намерении сыграть против ИИ ещё летом прошлого года, но лишь в этом году была объявлена точная дата матча. DeepMind пообещала, что программа дополнительно сыграет против сразу пяти мастеров.

Игры прошли в запланированные дни, и их результат окончательно показал, что уровень AlphaGo значительно выше человеческого. Та четвёртая игра матча Ли Седоль — AlphaGo, наверное, останется последней победой человека над этим ИИ: по завершении игр разработчики заявили об уходе системы из го.

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

На фото: почти готовые признать поражение пять мастеров го недоумевают — система AlphaGo, их оппонент, начала играть лениво, словно предчувствуя победу.

Пять профессиональных игроков в го не смогли ничего противопоставить натиску AlphaGo

Представители компании DeepMind на днях заявили о том, что игра с Кэ Цзе была последним сражением компьютерной системы AlphaGo с человеком. После победы во всех трех матчах подряд стало понятно, что с компьютером человеку уже не совладать, поэтому для системы играть с другими чемпионами в го просто нет смысла, исход будущих матчей можно считать предрешенным. По словам главы DeepMind Демиса Хассабиса, AlphaGo достигла уже всех возможных высот в го, поэтому время сменить профиль и попробовать себя в новой сфере.

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

Разбор полетов во время игры от профессионалов

В первой игре матча по го компьютерная система AlphaGo, разработанная сотрудниками DeepMind, победила сильнейшего в мире игрока в го Кэ Цзе. Чемпион из Китая ранее заявлял, что считает возможным переиграть компьютер. Но пока что у него это не получилось сделать. Спустя четыре часа и 15 минут после старта матча 19-летний мастер го был вынужден признать поражение. Сейчас счет 1-0 в пользу компьютера.

Глава компании DeepMind заявил, что сейчас с чемпионом играла обновленная система, архитектура которой была существенно модифицирована. Благодаря этому AlphaGo постоянно учится, причем, в основном, обучение происходит при игре с собой же. Так что от информации по результатам матчей чемпионов-людей система сейчас зависит гораздо меньше. В теории, платформа от DeepMind может обучиться почти всему, далеко не только игре в го.

Вниманию всех игроманов, настольщиков и им сочувствующих. 23 апреля в московском офисе Mail.Ru Group пройдёт открытая большая игра D&D Epics: Relics of Khundrukar (Реликвии Кундракара) от организаторов фестиваля Ролекон. Приглашаем принять участие всех желающих, вход бесплатный. Игра рассчитана на персонажей начальных уровней, так что новички получат отличную возможность попробовать формат organized play в рамках программы D&D Adventurers League.

Но если захотите играть героем выше первого уровня, то придётся предъявить зарегистрированного персонажа и номер DCI. У вас такого нет? Не беда, вы сможете выбрать перса из базовых вариантов и зарегистрировать его на месте. Чтобы попасть на игру, заранее запишитесь и заполните небольшую анкету. Игровую легенду читайте под катом.

Компания DeepMind, сейчас входящее в состав холдинга Alphabet, несколько лет работает над программной платформой AlphaGo. В прошлом году она выиграла в го у одного из чемпионов мира Ли Седоля. Таким образом, разработчики этой нейросети смогли доказать, что компьютер вполне в состоянии соревноваться с человеком в сферах, которые считались ранее прерогативой людей.

Та же игра го входила в рейтинг сложнейших для «понимания» компьютером игр. Эксперты считали, что в ближайшее время ИИ (слабая его форма) не сможет победить не то, что чемпионов мира, но и обычных игроков высокого уровня. Тем не менее, случилось то, что случилось, Alpha Go побил Ли Седоля в четырех партиях из пяти. А сейчас настал черед сразиться с еще одним чемпионом, Кэ Цзе, игроком в го 9 дана. Цзе занимает первую строчку рейтинга Китая и мира по набранным баллам.

Джимми Вейтерс (Jimmy Waters) — школьный учитель из города Кноксвилль, Теннесси, США. Обычный человек, который любит читать книги. Прошлым летом ему в руки попал роман «Выкрикивается лот 49» писателя Томаса Пинчона. Это произведение считается одним из ярких примеров постмодернистской литературы.

Книга примечательна и сама по себе. Но, как оказалось, она связана с одним интересным объектом — San Jose Semaphore. Так называется световая инсталляция на верхнем этаже офиса Adobe. Эта инсталляция работает уже более десяти лет, притом известно, что она несет в себе какое-то сообщение, которое, никто не мог разгадать в течение долгого времени. Так вот, книга помогла Вейтерсу разгадать световую криптограмму.

Я люблю разные игры. Например, те, что могут меня удивить. В этой подборке я перечислил игры и почти игры, в хорошем смысле этого слова странные. Я сознательно игнорирую в обзоре симуляторы козлов и хлебушка, игры с необычным графическим дизайном (иначе статья лопнет по швам) и очень известные игры, такие как Dear Esther. И ни в коем случае не претендую при этом на полноту изложения. Просто предлагаю скоротать часок-другой во время праздников, если вам станет любопытно.

*почти

Бодрый день, дамы и господа. Я наконец решил, что негоже мне сидеть в рид-онли, когда у меня в голове зреет столько полезных и нужных комментариев, и пора получить инвайт. А значит, надо писать пост. О чём? Конечно же, о том, что я люблю и знаю — об играх. Конкретно — о головоломках.

Огромный недостаток головоломки по сравнения с какими-нибудь ММОРПГ — очень малая реиграбельность. Я всегда думал, что технология стирания памяти в «Вечном сиянии чистого разума» использовалась не по назначению. Вместо того, чтобы изжить из воспоминаний какую-то женщину, не лучше ли забыть своё прохождение любимой игры, а потом пройти её заново? К сожалению, пока что это фантастика. Поэтому всё, что я могу — изнывая от ностальгии, в письменной форме вспоминать все эти прекрасные вещи, вернуться к которым мне, увы, не суждено.

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

Искусственный интеллект (слабая его форма), разработанная представителями Школы информатики университета Карнеги-Меллон, обыграл четырех профессиональных игроков в покер. Речь идет о турнире в Техасский холдем, который проходил в питтсбургском казино Rivers. Это одна из наиболее популярных разновидностей покера. В ходе турнира было сыграно около 120 тысяч раздач. ИИ взял банк в $1,7 миллиона.

Авторы программы — Томас Сэндхолм и Ноам Браун. По словам разработчиков, покер — игра, участники которой не знают, какие карты у всех остальных. По этой причине просчитать что-то крайне сложно. Джимми Чу, один из участников турнира, пожаловался на то, что он с коллегами недооценил возможности Libratus: «Бот каждый день играл все лучше. Он как будто более умелая наша версия».

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

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

Свою работу «Комбинаторная теория музыки» инженер-программист и музыкант Эндрю Дункан начинает со слов о том, что нет профессий более далеких, чем музыкант и математик — однако, как это ни парадоксально для самих музыкантов и математиков, музыка и ее создание может служить отличным примером работы ряда математических концепций.

В материалах из этой серии мы вспомним некоторые интересные примеры и явления, связывающие музыку, математику (в данном случае — комбинаторику) и даже историю.

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

Вопрос 1

В классической задаче построения нависающей фигуры все блоки должны быть однородными, одинаковыми по размеру и форме, и их длина принимается за единицу. На каждом уровне фигуры может быть только один блок. Блоки нельзя соединять или склеивать. Если у вас есть пять таких блоков, на какую максимальную длину может высунуться конец верхнего блока за край стола, на котором они лежат? Можете ли вы вывести формулу для максимального нависания при использовании n блоков?