company_banner

ИИ: блеф, отъем денег у населения и победа над неопределенностью



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

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

    Самые большие игры



    Дисклеймер: для понимания материала из этой статьи не требуется никаких знаний в покере, однако для более глубокого погружения в тему необходимо знать хотя бы основы игры.

    В фантастике роботы часто бьются с роботами («хорошие» против «плохих»), но в реальности чемпионаты машин, за исключением всем известных механических «боев», привлекают мало зрителей. Поединки ботов между собой лишены эмоциональности, духа состязаний, и представляют интерес только для узкой аудитории специалистов. То ли дело борьба с людьми! К 2016 году компьютеры смогли выиграть (или найти математическое решение выигрышных позиций) у человека в две дюжины интеллектуальных игр: ним, крестики-нолики, призрак, четыре в ряд, гомоку (15х15), мельница (с 9 фишками), лентомино, овалху, кварто, тико, пангки, рендзю (без дебютных правил), авари (семейство манкала), магараджа, «тигры и козы», фанарона, английские шашки, «три мушкетера», хекс (8х8), калах (6х6), китайские палочки, пентаго, го (5х5 и классическая игра против Ли Седоля).

    Не все из этих игр могут быть вам знакомы, но о каждой можно написать отдельную статью с драматической главой о борьбе с машинами. Пожалуй, одним из самых интересных и напряженных противостояний (помимо всем известных перипетий с игрой «го») стала битва за шашечную корону. Подробнее об этом периоде можно прочитать в нашей первой статье из цикла об ИИ, а сейчас просто вспомним одно интересное число: английские шашки — самая большая из игр, полностью решенных до настоящего времени. Размер ее поискового пространства 5×1020. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (от 50 до 200 штук) произвела 1014 вычислений.

    Если вы читали наши предыдущие статьи на тему ИИ, то уже знаете, что в сложных играх машина не побеждает полным перебором всех возможных комбинаций ходов. Одно только оценочное минимальное количество неповторяющихся шахматных партий, вычисленное в 1950 году американским математиком Клодом Шенноном, составляет приблизительно 10118. Для сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4×1079 до 1081, то есть в 1040 раз меньше числа Шеннона.

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

    Какое место покер занимает на фоне других достойных игр? Возьмем для примера самую популярную на сегодняшний день разновидность покера — техасский холдем с лимитированными ставками. Лимитный холдем в силу ограниченных ставок весьма зависим от математики и хорошо подходит для алгоритмизации: для игры один на один в нем существует порядка 1018 игровых ситуаций. Если будем учитывать, что некоторые карточные комбинации эквивалентны между собой (например, два туза разной масти будут идентичны любой другой паре тузов), получим порядка 1014 различных игровых комбинаций. Для сравнения, в безлимитном холдеме их 10160, а в игре «го» вариантов развития 10170.

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

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

    Боты против человечества




    Первые серьезные попытки создать покерного бота были предприняты еще в начале 80-х. В 1984 году известный специалист по покеру Майк Каро представил программу Orac, поразившую многих своими возможностями. Orac, например, мог относительно удачно вычислить блеф противника, всего лишь замеряя время, которое потребовалось противнику для хода — чем дольше задумывался человек, тем выше была вероятность блефа.

    В 1991 году в Альбертском университете (Канада) началась разработка программы Polaris, предназначенной для игры в холдем один на один. После 16 лет работы над проектом, представлявшим собой комбинацию нескольких покерных ботов, учитывающих целое семейство алгоритмов поиска равновесных стратегий, в 2007 году состоялся матч против нескольких покерных профессионалов. По условиям игры, человеку и компьютеру раздавали одни и те же карты, поэтому влияние случайности в игре свели к минимуму. Сначала Polaris ощутимо выигрывал, но после анализа нескольких партий игроки нашли повторяющиеся особенности игры программы и смогли победить.

    В июле 2008 года Polaris смог наконец-то выиграть чемпионат между людьми и машиной. Общий счет сессий составил 3 победы, 2 поражения, 1 ничья. Однако эта победа не стала началом эры доминирования машин и гибели онлайн-покера. Как уже упоминалось, «машинный покер» играется при ряде ограничений, которые не соблюдаются в реальных онлайн-играх людей.

    Первым серьезным испытанием для людей стал турнир 2015-го года, в котором четверым из ТОП-10 лучших игроков в техасский холдем противостояла программа Claudico. В соревновании Brains Vs. Artificial Intelligence люди оказались сильнее.

    Другая покерная программа Tartanian7 университета Карнеги-Меллона в 2014 году смогла победить нескольких новичков и компьютерных ботов. Особенность этой программы в том, что после десяти лет разработки, она научилась сносно играть в безлимитный холдем с новичками.

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

    Машина зарабатывает в играх




    Один бот может уступить человеку, но сотня ботов математически повышает шансы на победу. В 2010 году разразился большой скандал, когда на известной покерной площадке были выявлены боты, суммарно заработавшие более двухсот тысяч долларов. Специалисты сайта PokerTableRatings обнаружили поразительное сходство всех параметров на длительной дистанции у нескольких игроков. Статистически удалось доказать, что все эти подозрительные игроки во всех ситуациях действовали идентично.

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

    В среднем, размер платы за игру в покер составляет 5 % и не может превышать 3–5 у.е. за 1 игру. Рэйкбэк является достаточно большой статьей прибыли для ботов: за счет него можно играть в 0 с людьми, но при этом зарабатывать за счет процентов от покер-рума. Наличие ботов, успешно играющих против новичков — это факт. Но они никак не влияют на глобальный рынок развития искусственного интеллекта.

    Холистическая победа на поле неопределенности




    После успехов Tartanian7 в университете Карнеги-Меллона приступили к созданию нового, гораздо более совершенного покерного бота — Libratus. В то время как программа DeepStack из конкурирующего Альбертского университета показала весьма неплохие результаты в предварительных тестах, Libratus в январе 2017 года выступил против настоящих покерных профессионалов. Вычисления в процессе разработки Libratus заняли 15 млн ядро-часов (Claudico обошлась 2–3 млн ядро-часов. В процессе игры Libratus использует мощности суперкомпьютера Bridges (1.35 петафлопс/сек).

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

    11 января стартовал турнир, в котором Libratus суммарно играет 120 тыс. раздач в безлимитный техасский холдем один на один. Игра идет на виртуальные деньги, но приз за победу — 200 000 долларов — абсолютно реален для четверых профессиональных игроков в покер, двое из которых уже имели опыт игры против бота, выиграв в 2015 году у Claudico. Чтобы исход соревнований не оказался слишком случайным, каждый матч дублируется так, чтобы игрок А получал карты, которые получил компьютер в партии с игроком В и наоборот.

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

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

    Как на самом деле работает Libratus? Ответа на этот вопрос пока нет. Ученые не будут раскрывать секрет, каким образом выигрывает программа, как минимум до конца турнира. Мы знаем, что в основе программы лежит специально созданный алгоритм по вычислению оптимальных стратегий для игр с неполной информацией. Используется также новая технология достижения равновесия Нэша — стратегия, когда ни один из игроков не увеличит свой выигрыш изменив стратегию, если другой, в свою очередь, стратегию не меняет.

    А не уничтожит ли Libratus онлайн-покер?




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

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

    Источники:

    Mail.Ru Group 255,64
    Строим Интернет
    Поделиться публикацией
    Комментарии 15
    • +2
      Ранее ИИ не мог победить там, где присутствует элемент неопределенности.

      Да ладно.
      • +2
        К стати да, интуитивными решениями вероятностных задач человеки не блещут, в отличии от тупо считающих, тупо ботов!
      • 0
        Как заядлый ботовод, замечу, онлайн-покер он уже того, и для этого не надо суперхитроделаных ботов (хотя это действительно весьма занятная область), достаточно хотя-бы паре оказаться за одним столом с «мясом» и роботы уже имеют статистическое преимущество… И таких виртуальных катал, онлайн покеррумы сами-же и плодили с начала времён, для понятных целей…
        ИМХО смысл покера в психологии, в него интересно играть лишь с живыми людьми за реальным столом, лудоманам-же всё равно что фрукты, что три семи сегментных индикатора за пятачок, что покер рум в тырьнете!
        • 0
          Смерть онлай-покера, как следствие победы Libratus — это, мягко говоря, туфта полная.

          Во первых, как корректно указано в статье, хедзап (1 оппонент) на котором бот показал победу, и 6-9 оппонентов за столом — это просто космическая разница по требуемым вычислительным мощностям. На очень-очень много порядков.

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

          Далее. Сам используемый алгоритм, судя по косвенной информации, вычисляет оптимальную стратегию в каждой точке принятия решений. Т.е. прогоняет туеву хучу возможных стратегий, возможных вариантов адаптации к ним, и находит оптимум. Это такой титанический брутфорс что он в принципе не масштабируется на обычные PC или даже небольшие кластеры из оных. И это останется так по меньшей мере в ближайшие 10-15 лет, ну или до появления доступных по стоимости квантовых компьютеров (бгггггг).
          А представить себе суперкомпьюетр на котором постоянно крутится покербот для игры на лимитах ниже NL10000 совершенно невозможно (тупо никогда не отобьется, не рентабельно).

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

          Так что шуму много — а повода шуметь особо нет. Исходя из доступной инфы по покерботам, онлайн-покеру еще долго ничего не будет грозить (в смысле опасности от ботов — прочие факторы не обсуждаю).
          • +3
            Ну дык раньше для шахмат тоже нужен был суперкомпьютер. А сейчас простой i3 легко в сухую порвет Карлсена. Так что появление ботов легко обыгрывающих людей это дело времени. Причем не факт что далекого. Та же программа для го из среднячка в чемпиона всего за год превратилась.
            • 0
              появление ботов легко обыгрывающих людей это дело времени


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

              P.S. ну и да, если даже случится чудо — все равно дальше остается Омаха, где на руках в 2 раза больше карт — а это очередной взрыв вычислительной сложности.
              • 0
                А сейчас простой i3 легко в сухую порвет Карлсена.

                Не знаток шахмат, но мне почему-то кажется, что рвать в сухую Карлсена сейчас способны только суперкомпьютеры, никаким i3-5-7 это не под силу.
                • 0
                  Не знаток шахмат
                  . В этом и дело, даже телефон уже выиграет у Карлсена, даже при 15 секундах на ход, просто компьютер считает гораздо быстрее, чем человек и оперативная память большая. В общем текущие программы имеют очень хорошие алгоритмы.
              • 0
                > Дальнейший рост мощностей суперкомпьютеров жестко лимитирован и в целом практически себя исчерпал.
                «640 килобайт хватит всем!» (с) Билл Гейтс. Никто (даже в майкрософт) тогда не думал, что всего через пару десятков лет у людей дома будут стоять терабайтники, поэтому ваше утверждение:

                > как до луны пешком
                Как минимум настолько же ошибочно, как и людей из майкрософт. Никто не знает, какие компьютеры будут через 20 лет, а вот то, что в покер всё еще будут играть — сомневаться не приходится.

                > для того чтобы повысить мощность суперкомпьютеров на 3-4 порядка
                А зачем суперкомпьютеру увеличивать мощность еще на 3-4 порядка, если он и так всех обыграл?

                > Далее. Сам используемый алгоритм, судя по косвенной информации, вычисляет оптимальную стратегию в каждой точке принятия решений
                Вы этого точно не знаете.
                • 0
                  Это как с биткоином — будет выгодно — выпустят ASIC«и, заточенные специально под покер и ничего кроме этого не умеющие и в плане пользы человечеству бесполезные.
                • 0
                  Лимитный холдем не является самым популярным видом покера
                  • 0
                    >У ИИ остается только теория игр для поиска оптимальных стратегий
                    да я и с этим не соглашусь.
                    • +3
                      А гибирид человек+машина возможен? Возможно в этом случае требования к вычислительным мощностям были бы на порядки меньше, а эффективность выше.
                      Возможный вариант реализации: компьютер показывает человеку дополнительную информацию, которую он в принципе может просчитать (например возможные карты у оппонентов, исходя из того, что уже было, может быть время реакции оппонентов). А человек уже имея эту расширенную информацию принимает решения.
                      • 0
                        По сути именно так сейчас и происходит. Есть приложения, которые имеют общую базу собранной статистики, в процессе игры продолжают ее собирать и предоставлять своим пользователям. Даже если вы видите оппонента первый раз, вы все равно будете видеть его статистику за столом, потому что он когда-то играл с другими пользователями, у которых было это приложение.
                      • 0
                        К сожалению не смотрел турниры с ИИ, но играл ли там кто то из обладателей серьезных браслетов?
                        Интересен был бы результат против интуитивщиков типа Даниэль Негреану, хотя он еще и людей шикарно читает. Но особенно интересно какой результат был бы против супер тайтовых игроков типа Криса Фергюсона котрой к тому же профессор математики а диссертация была посвящена алгоритмам для виртуальных сетей.

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое