• Подарков мешок

               – Ящик! – рявкнул отец Кабани и надолго замолчал, делая странные движения щеками... 
               – Ящик… – повторил отец Кабани упавшим голосом. – Это мы говорим, будто мы выдумываем. На самом деле все давным-давно выдумано. Кто-то давным-давно все выдумал, сложил все в ящик, провертел в крышке дыру и ушел… Ушел спать... 
       
      А. и Б. Стругацкие "Трудно быть богом"
       
       
      На носу Новый год и время дарить подарки. За год было сделано немало. Мой проект растёт на глазах и, что самое главное, становится умнее. Как именно он это делает — отдельная история, которую я обязательно расскажу, как нибудь, в другой раз. Сейчас — время заглянуть в мешок и посмотреть, что приготовил для нас Dagaz.
      Читать дальше →
    • Разработчики объяснили, как ИИ обыграл покерных профессионалов в безлимитный холдем на дистанции 120 000 рук


        Профессиональный игрок в покер Джейсон Лес (Jason Les) разговаривает с профессором Туомасом Сэндхольмом (Tuomas Sandholm) из университета Карнеги — Меллон во время хедзапа с ботом Libratus. Джейсон проиграл программе почти миллион условных долларов, больше всех остальных профессионалов

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

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

        Пожалуй, техасский холдем — самая популярная в мире игра с неполной информацией. Ежедневно в онлайне разыгрывают миллиарды долларов. Использование ботов и раньше было строго воспрещено, а сейчас у владельцев покеррумов появилась новая причина для мониторинга процессов на компьютере игрока, поскольку программа Libratus надёжно забирает стеки в хедзапах даже у лучших профессионалов.
        Читать дальше →
      • Генерация кроссвордов с помощью SAT солвера

          На Хабре было несколько статей про генерацию кроссвордов. В одной из них «Самый сложный кроссворд, составленный компьютером» говорилось про очень сложный кроссворд, составленный компьютером, которому «пришлось немного помочь» вручную. Во второй статье «Алгоритм формирования кроссвордов» рассказывается про алгоритм, созданный автором для составления кроссвордов, и отмечается, что этот «самый сложный кроссворд» остался непокоренным и говорится, что «может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!». Что же, можно принять вызов. Что из этого получилось, смотрите под катом.
          Читать дальше →
          • +10
          • 6,3k
          • 2
        • 3х5х7 Cuboid или пилим Кубик Рубика

          • Tutorial


          Некоторое время назад я увлекся коллекционированием всевозможных головоломок. Я не увлекаюсь спидкубингом и не могу самостоятельно решить бОльшую часть головоломок в своей коллекции. Мне просто нравится пополнять коллекцию чем нибудь интересненьким.

          Сначала я покупал всякие кубики Рубика на aliexpress и ebay, но там ассортимент хоть и широкий, но все равно конечный. Но однажды я попал на парочку ютуб каналов (раз, два), где ребята с помощью напильника и такой-то матери изготавливают из 30 лет назад надоевшего всем кубика весьма интересные головоломки. При этом на выходе получается совершенно новая головоломка, требующая совершенно иных подходов к решению. Я тоже начал пилить свои кубики изготавливая различные модификации для своей коллекции.

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

          В статье пошаговая инструкция как делаются подобного рода модификации. Технология в общем-то несложная — посмотрите упомянутые видео и все поймете. Статью можно после этого даже не читать — в ней не будет ничего нового по сравнению с видео :)
          Читать дальше →
        • 10 лучших игр о хакинге, кодинге и вычислениях

          • Перевод

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


          10. TIS-100


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

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

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

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


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

              Однажды попалась мне игра пентамино, где было необходимо уложить 13 фигурок в квадрат 8 на 8. После некоторого периода времени, в течение которого я безуспешно пытался решить эту задачу, я решил, что необходимо написать программу, которая бы делала это за меня. Для этого необходимо было выбрать алгоритм решения. Первое, что приходит на ум — это обычный алгоритм ветвей и границ, когда фигурки укладываются одна за другой примыкая друг к другу (алгоритм с танцующими ссылками здесь не подходит, поскольку фигурки разные). Для ускорения этого алгоритма обычно используются различные эвристики, например, предпочтение отдается ветвлению с наименьшим количеством вариантов. Можно придумать и реализовать и другие эвристики в этом алгоритме, но тут я подумал, что множество различных ухищрений для ускорения решения подобных задач уже реализовано в SAT солверах. Поэтому, необходимо перевести задачу на соответствующий математический язык и воспользоваться каким-либа SAT солвером. О том, как это было реализовано и какие получились результаты можно почитать под катом.
              Читать дальше →
            • Бойтесь шахмат, Вам навязываемых



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

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

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


                Читать дальше →
                • +22
                • 16,3k
                • 6
              • ИИ-платформа AlphaGo Zero отточила мастерство игры в го без участия человека



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

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

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

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

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


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

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

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

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

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


                      Читать дальше →
                    • Выращивание искусственного интеллекта на примере простой игры



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

                      Результатом работы стало то, что ИИ, не зная правил, самостоятельно освоил игру крестики-нолики и нашел слабости ботов, которые играли против него. Но начал я с еще более простой задачи.
                      Читать дальше →
                    • Новый рекорд в сборке кубика Рубика: всего 4,69 секунды

                      • Новость

                      Несмотря на то, что кубик Рубика был создан в 80-х годах прошлого века, его популярность не снижается. Люди продолжают собирать кубик, причем многие участвуют в соревнованиях по сборке на скорость. Новичкам очень сложно сориентироваться, поскольку они не используют созданные ранее алгоритмы сборки, а пытаются действовать наугад. Но профессиональные «игроки», а таких немало, могут решить головоломку в считанные секунды.

                      Рекорд, поставленный 15-летним американским подростком Патриком Понсом, сложно будет побить в ближайшем будущем. Он справился с заданием всего за 4,69 секунды. Процесс сборки кубика Рубика опубликован на YouTube.
                      Читать дальше →
                    • Задачу о N ферзях признали NP-полной задачей


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

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

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

                        • Перевод

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


                        image

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

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

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

                          *почти

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

                          Volvox




                          Осторожно, пропаганда употребления наркотиков
                        • Побеждая «математическое чудище»: дело не в числах, а в том, чтобы учиться думать

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

                          image

                          Жители Питтсбурга не смогли найти нашумевший магазин, потому что на самом деле он находится в Коннектикуте. Впрочем, это не помешало юмористам принять новость за чистую монету и поверить, что это настоящая табличка, якобы действительно помещенная в заведении кассиром, которому надоело, что какие-то всезнайки спорят с ним по поводу итоговой суммы. А так все и было?

                          На самом деле нет, ничего подобного (в качестве подтверждения можете почитать про эту историю). Но в целом это объяснение вполне правдоподобно. Кассиры в наши дни не умеют делать расчеты в уме, не так ли?

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

                          Это утверждение, опять же, неверно. Неверно, но популярно? Что ж, вполне может быть.
                          Читать дальше →
                        • Задачка для пятилетних детей, ставшая «вирусной»

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



                          В честь юбилея этой колонки интернет любезно предоставил мне сингапурскую математическую задачку, ставшую вирусной. В середине мая веб был взволнован задачей, которую, якобы дают решать первоклассникам Сингапура, а это дети возрастом от 5 до 7 лет, и которая оказалась настолько сложной, что никто не может её решить.
                          Читать дальше →
                        • AlphaGo против Кэ Цзе: оценки профессиональных игроков в го

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

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

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

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

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