Пользователь
0,0
рейтинг
19 марта 2012 в 14:40

Разработка → Программа Zen обыграла в го профессионального игрока 9 дана с форой в 4 камня

17 марта были сыграны две партии в го между программой Zen19, созданной японским программистом Ёдзи Одзимой и профессиональным игроком Такэмия Масаки, обладателем 9 дана, одним из лучших игроков мира. В первой партии, с форой в 5 камней, программа победила с преимуществом в 11 очков, во второй — с форой всего в 4 камня ей удалось опередить Масаки на 20 очков. В любительском го каждый камень форы соответствует очередному уровню мастерства, а в профессиональном — разница в 1 камень соответствует 3 данам. В рейтинге популярного игрового сервера KGS Zen19 сейчас имеет 6 дан. Это значит, что программа уже почти достигла высшего любительского уровня и скоро может перейти в «высшую лигу» го. После матча Такэмия Масаки признался, что не ожидал такого высокого уровня от компьютера. Zen работала на мини-кластере из четырёх компьютеров (dual 6-core Xeon X5680/4.2 GHz, 6-core Xeon W3680/4 GHz и два 4-core i7 920/3.5 GHz), соединённых гигабитной сетью.

Компьютерное го — намного более сложная задача для искусственного интеллекта, чем шахматы. Лучшие шахматные программы сегодня намного превосходят уровень человека. Рекорд Гарри Каспарова в рейтинге Эло — 2851 пункт, тогда как у лидера по рейтингу Эло среди компьютеров — Houdini — 3310. Это значит, что из 10 партий лучшему в рейтинге шахматисту мира вероятно удастся выиграть у компьютера лишь одну.

Доска для игры в го имеет размеры 19х19 клеток, количество возможных ходов в большинстве позиций тоже намного выше, кроме того, если в шахматах в процессе игры число фигур уменьшается, делая задачу проще, то в го — всё наоборот. Это делает создание сильной игровой программы в го гораздо более трудной задачей. Например, в шахматных программах широко используются базы эндшпилей — предварительно просчитанные варианты завершения партии, когда на доске осталось мало фигур. Для го составить подобную базу практически невозможно. Таким образом, сейчас го — эталонная задача для отработки алгоритмов искусственного интеллекта и теории принятия решений.
Илья Сименко @ilya42
карма
524,7
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (79)

  • +13
    Наконец-то про игру ГО начали писать на хабре.
    Сейчас интересуюсь данной тематикой и пытаюсь придумать и реализовать ИИ для гораздо менее популярной и исследованной игры «Точки». Интересно, что сложнее?
    • +2
      точки явно попроще, в го есть варианты отыграть полу-открытые захваченные области, а в точках любая территория обводится непрерывной линией
      • 0
        Ну я бы не сказал, что явно — это еще доказать нужно.

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

        Все это анализировать надо.
        • +6
          Вы явно не играли в го хотя бы на любительском уровне, пустые обведенные области в го допускаются и очень часто так и есть, если внутри области не построить 2 глаза то в ней не выжить и в неё не ходят, в Го сложнее тем что в ней стратегия переходит в тактику а тактика в стратегию. и в отличии от точек поле в го абсолютно динамично.
          • –1
            Да, наверное не играл. Но я понял о чем вы сказали.

            Я вообще-то имел ввиду, что в Го нельзя уничтожить группу камней, если кроме них есть еще свободные позиции.

            И в точках игра развивается более вяло, по сравнению с Го, поскольку нужно сразу начинать с глобала, чтобы не уйти в ничью. А в Го все начинается с краев и да, игра более динамичная и быстроразвивающаяся.
            • 0
              Все же, настоятельно советую изучить го чуть глубже, чем «рассмотрел доску с камнями». Это очень серьезная игра с бесконечной глубиной.

              Касательно жизни и сметри групп вообще нельзя ничего однозначно говорить. Количество вариантов там такое, что делать подобные заявления неразумно. Группа может иметь дыхательные пункты и тем не менее быть обреченной при правильной игре оппонента.
      • +2
        Ещё важный момент — захваченные камни сразу снимаются с доски и это свободное место можно снова использовать (ко-борьба).
        • +2
          Ну это не совсем ко-борьба, ко-борьба это когда вынуждаешь противника делать невыгодный ход, потому что выгодный он не может сделать из-за правила ко. Что кстати тоже добавляет сложности :) А освобождённое место можно и без ко-борьбы использовать)
          • +1
            И вы не правы, ко-борьба это игра Ко, чаще всего на угрозы, не кто не кого не заставляет делать не выгодный ход, по своему названию не выгодных ход не сулит выгоды по этому игрок просто закроет Ко или отдаст, в замен получив что то другое.

            Ту ситуацию что описали вы это Ко в начале партии его редко играют сразу.
        • +1
          Да, действительно, хотя бы из-за того, что в го есть ко, оно уже сложнее точек :) Ну, и по многим другим причинам тоже.
    • +2
      Смотря какое поле в точках, обе игры сложная задача для ИИ
      • +1
        Если сравнивать при одинаковых размерах полей.
        • +2
          Вероятнее всего вам интересно будет прочитать Игра «Точки». Методы и алгоритмы.
          • +1
            Это наверное первая серьезная статья, которую прочитывают люди, занимающиеся данной темой.
            И написана она, кстати, Павлом Торгашовым, который есть на хабре :)
      • +2
        Как специалист по точкам, скажу Вам, что там очень много мини игр. И если знать как ходить, то даже казалось бы серьезный противник раскалывается на части :)
    • +1
      Я недавно писал ИИ для игры в гомоку (крестики-нолики до 5 в ряд), но с немного модифицированными правилами: игра идет не до первого зачеркивания, а до заполнения всего игрового поля. За каждое зачеркивание плюсуются очки. По окончании кто больше набрал очков, тот и победил. Мы в такую игру развлекались в студенчестве на бумаге, ибо до первого зачеркивания все было вообще легко и скучно.

      Алгоритм на самом деле получился не очень сложный, но вполне себе сильный. Мне с ним очень тяжело соперничать, хотя опыт игры в такой вариант у меня приличный.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          Есть еще «6 в ряд», справедливая для обоих игроков
        • +1
          Легко и просто было, потому что я всех обыгрывал, начиная либо крестиками либо ноликами. Поэтому мы слегка модифицировали правила, а стратегия при этом поменялась очень сильно, потому что пришлось думать не только о том как первому зачеркнуть, но и взвешивать что выгодней: зачеркнуть сейчас или поставить еще одну вилку, или залочить возможность поставить вилку сопернику и т.д. И вот в новой стратегии уже не так важно было как быстро ты поставишь первый 5 в ряд.
    • +7
      Записи партий Такемия Масаки

      19x19 Нормальное игровое поле

      Zen(5d)-Takemiya_Masaki(9p) 5 Камней
      Zen(5d)-Takemiya_Masaki(9p) 4 Камня

      9x9 маленькое игровое поле Ohashi_Hirofumi
      20120317-Zen(5d)-Ohashi_Hirofumi(5p)
      20120317-Ohashi_Hirofumi(5p)-Zen(5d)
    • +2
      Очень давно находил довольно красивую программу/игру Dots — как понятно из названия это те самые точки. Но сейчас как ни пытался — найти заново именно ту не могу.
      А вообще гугл даёт очень много вариантов реализации данной игры.
      • +1
        Вы хоть во что-нибудь играли из этого?
        Если бы поиграли во все, то поняли, что проблема ИИ для точек остается открытой.
        ИИ в Го развит куда лучше сейчас.
  • +1
    Базы эндшпилей в шахматах — это не ошибка?
    Про дебютные таблицы слышал, а эндшпили, как мне кажется, можно и полностью рассчитывать.
  • +1
    Да, и еще интересный вопрос:
    а дан точно присваивается по результатам всего одной партии?
    • +1
      Я не знаю, присваивают ли вообще какие-либо даны программам официально. Возможно, формулировка не очень удачная. Сейчас переделаю.
      • +1
        Разница между профессиональными данами не соответствует количеству камней форы, считается что разница между 1д и 9д около 3-х камней, так что можно сказать, что программа играет на уровне очень сильного любителя. Но тем не менее это все равно очень круто… Когда я начинал играть лет 5 назад, программы даже на 1-й разряд не играли, а сейчас получается уже на уровне гроссмейстера могут играть.
        • +1
          А почему без форы не играли?
          • +1
            Ну пока что текущего уровня явно недостаточно чтобы без форы с профессионалом играть.
    • +1
      Кстати, вот график рейтинга zen19 на KGS.
    • +1
      Странно, что даны идут на понижение. В Японских боевых искусствах отсчет идет от «кю» до «дан», к примеру от 10 кю до 1 кю и затем — 1 дан, 2 дан, 3 дан… Неужели в «го» — традиции решили подменить?
      • +3
        Нет все так же, кю понижаются от 30-го до 1-го а даны растут от 1-го до 9-го
        • +1
          На момент прочтения статьи и написания коммента было сказано, что дан повысился с 8 или 9 на 5 (если правильно запомнил цифры). Возможно я не верное прочитал, тогда извиняйте.
          • +1
            В го даны бывают любительские и профессиональные (признанные, с дипломом), может отсюда пошло недоразумение.
      • +2
        Вы запутались. Фору давал игрок, а не программа.
        • +1
          Я кстати играл с этой программкой, причем я как раз брал у неё фору 4 камня. Она меня разделала :( Правда я утешал себя тем что игра была с очень неудобным для меня контролем времени, почти блиц, а я не люблю быстрые партии играть, но факт остается фактом, играет она сильно…
  • +3
    Не подскажете хорошую реализацию Го для айпада? Почитал, понравилось — хочу поиграть.
    • +2
      SmartGo для игры в одиночку (ещё и задачек по го содержит кучу), Tetsuki для игры по сети.
      • +1
        Спасибо сейчас поставлю, редко встречаю приложения за 20 баксов :)
        • +2
          О, оно того стоит, если вы действительно увлеклись го :)
    • +1
      CrazyStone должен неплохо играть. На KGS у него почти 6 дан.
      Хотя, конечно, на мобильном устройстве он будет играть послабее.
  • +1
    Где-то была клёвая картинка по поводу текущей ситуации с уровнем игры компьютера против человека — там еще Го были намного выше шахмат и было много других игр. Не могу найти — кто-то подскажет?
    • +2
    • +10
      image
      • НЛО прилетело и опубликовало эту надпись здесь
        • +3
          seven minutes in heaven — это наша бутылочка, как оказалось :)
          • +3
            Только с одной поправкой: поцелуй против семи минут в закрытом шкафу :)
            • +2
              Можно начинать бояться роботов.
      • +1
        В реверси имхо забыли дописать «нг» и опустить в самый низ
      • +1
        Я бы вот не зарекался насчет never.
  • +5
    Между прочим, недавно появилась программа (под названием Xuan Xuan Go), которая решает локальные позиции лучше профессионалов. Она даже нашла больше десятка ошибок в классических задачках, придуманных профессиональными игроками.
    Так что прогресс в области алгоритмизации го однозначно не топчется на месте :)
  • +3
    Очень круто. Особенно круто то, что использовался сравнительно небольшой кластер, что косвенно указывает на то, что программа не основана на Монте-Карло (детальной инфы по программе пока не нашел, может кто-то в курсе как она работает?). А это большой прорыв, монте-карло алгоритмы все-таки тупой брутфорс, а тут (возможно) действительно по настоящему интеллектуальный алгоритм…

    Занятно, что автор на самом деле ещё и является тем самым знаменитым игроком со своим крайне специфическим «космическим» стилем игры ;)

    А ещё было было бы очень интересно посмотреть на игру без форы. Даже если программа играет действительно сильно и вначале будет выигрывать, то профи игрок после несколько игр наверняка сможет подстроиться под её стиль игры и найти контрмеры. И вот тут вопрос — сумеет ли программа забороть эти контрмеры… Если да — поздравляю всех с сингулярностью ;)
    • +3
      Насколько я знаю, все сильные программы используют метод монте-карло. Естественно, он сочетается с другими алгоритмами — например, алгоритмами оценки позиции. При этом, варианты просчёта в монте-карло тоже выбираются не случайным образом, а наиболее перспективные.
      При этом, в фусэки (начале игры) все программы пользуются базами фусэки и дзёсэки (стандартных розыгрышей в углах). Также, есть и базы стандартных форм групп камней, которые составляются при помощи самообучающихся алгоритмов.
      Так что нельзя говроить о том, что используется «чистый метод монте-карло». В этом случае программа вряд ли смогла бы играть сильнее 15-го кю.
      Но в той или иной степени монте-карло однозначно используется.

      К сожалению, ссылок дать не могу. Это всё из памяти, я по этой теме много чего читал какое-то время назад.
      • +2
        Вот есть такой документ про генерирование ходов из паттернов и других эвристик для последующего использования их в алгоритме UCT.

    • +2
      Нашел, таки Монте-Карло ;(
      У таких алгоритмов существенный недостаток — при увеличении размера поля сложность расчетов растет очень сильно. На поле 25x25 программа опять будет сливать человеку, если не научиться играть интеллектуально, без брутфорса.
      • +3
        Правда, поля 25х25 нет :) Ну, то есть, стандартное поле — 19х19.
        Кстати, не думаю, что для программы будет большая разница, 19х19 поле или 25х25. Начало игры точно так же можно будет играть по базам, а локальные позиции вряд ли будут намного сложнее.
        И опять же, в этих программах много разных алгоритмов заложено. Монте-Карло — это всего лишь метод оптимизированного перебора вариантов, когда их слишком много.
        • +2
          Официального поля нет, разумеется, но Го такая особенная игра, что её можно играть и на 1000x1000.
          Разница для брутфорса как раз будет существенная, площадь поля определяет кол-во возможных ходов, увеличения площади в 4 раза увеличит среднюю длительность игры (общее кол-во ходов за игру) приблизительно во столько же, плюс на каждый ход потребуется перебрать пропорционально большее кол-во вариантов, можете сами прикинуть вырастет сложность перебора, еквивалентного оному на поле 19x19…
          Разумеется, для человека сложность тоже возрастет, но не на многие порядки, а всего лишь в разы.
          • +2
            Вообще, это очень интересная тема. Мне кажется, что если брать такие крайности, как 1000х1000, то там игра распадётся на множество несвязанных друг с другом позиций, которые друг на друга практически не влияют.
            19х19 — это вообще, как мне кажется, оптимальный размер доски, потому что там практически каждый поставленный камень всё ещё влияет на ситуацию в целом.
            Так вот, мне кажется, что если взять доски 1000х1000 и 2000х2000, то что программе, что человеку будет одинаково сложно играть на любой из таких больших досок. Увеличится только время партии, просто потому, что нужно будет сделать больше ходов.

            Их этого примера, вроде как, следует вывод, что зависимость между сложностью игры и размером доски, как минимум, не линейная.
            • +3
              Не линейная, разумеется. Что я пытаюсь сказать, так это то, что разные типы алгоритмов будут по разному реагировать на увеличение поля. Для брутфорсовых небольшое увеличение размера поля сильно увеличивает требуемую мощность при сохранении качества перебора (глубины, % покрытия и т.д.), т.е. на одном и том же оборудовании сильно деградирует в качестве по сравнении с игрой 19x19.
              В то время как для интелектуальных алгоритмов, оперирующих обьектами и их связями, типа групп камней и их взаимного месторасположения, сложность вырастет пропорционально полиному небольшой степени от увеличения размера поля.
              В этом плане человек пока ещё ведет в игре Го, за счет интеллектуального подхода игрок может победить брутфорс алгоритм при определенных условиях, в т.ч. выработать стратегию специально против него. В шахматах же такого шанса у него, похоже, уже нет.
            • 0
              > множество несвязанных друг с другом позиций, которые друг на друга практически не влияют

              Влияние ситё («лестницы») распространяется по диагонали на всё доску — при отсутствии ситё-атари, камня-прерывателя.
              • 0
                * на всю
              • +1
                Я бы сказал, что это влияние не зависит от размера доски. К тому же, это такое себе однобитное влияние — или работает лестница, или нет.
                Я же имел в виду наличие неподалёку ацуми (плотностей/стенок), мойо и т.п. В этом смысле на локальную позицию могут значительно влиять только соседние локальные позиции, но не глобальная позиция по доске.
                Это если говорить о чрезмерно больших размерах досок.
                • +1
                  Пожалуй, да — ацуми будет не ацуми, принцип баланса территории/влияния сломан, первый ход в пункт 146-147 совсем не то, что в 3-4 — и всё такое.
  • +3
    Сингулярность все ближе и ближе…
  • +1
    Спасибо за пост!

    Кстати, с каким контролем времени они играли?
    • +1
      Полчаса времени + беёми 1 минута на ход. Относительно быстрая партия.
  • 0
    Всего четыре компьютера для обработки программы? А как же суперкомпьютеры, ibm, bluegene как это было с шахматами и Каспаровым?
    • +1
      Алгоритмы улучшились с тех пор. :) Если я не ошибаюсь знаменитый суперкомпьютер Deep Blue в свое время так и не обыграл Каспарова, а сделала это уже программа Fritz на обычном четырех-процессорном серваке.
  • –1
    Каспаров с горя ушел в политику после того как его обыграл компьютер?
  • +1
    Только я вижу связь с обработкой изображений, в частности, медианным фильтром?
    • +1
      Поломал голову немного и всё-таки сломал =). Сдаюсь. Что общего, по-вашему?
      • +1
        Скажу сразу, далее только предположения. Некоторые необходимые условия победы в го(японский вариант):
        рядом с моей группой более нуля свобод, внутри окружения: (у каждого пустого пересечения рядом должно быть: (больше нуля моих камней, менее 3 свобод), у всех пустых суммарно свобод хотя бы на 4 меньше удвоенного числа пустых(два глаза — туннеля)). Пусть мои камни — черные пиксели, противника — белые, пустые — серые. Т.е. одна из стратегий победы состоит в построении структуры — вокруг каждого свободного: моих камней больше, чем — противника. Медианный фильтр берет значение пикселя, находящегося посередине упорядоченного множества окружающих(для го — четыре соседа), т.е. если большинство соседей — черные, то пиксель черный, и наоборот. Вообще, тут нужна маленькая модификация: если соседей поровну, то изменяем пиксель на противоположный; серые соседи не учитываются. Рассмотрим ситуацию простого захвата
        _Х_
        Х0Х
        _Х_
        Как бы мы не усложняли(предположение!) захватываемую группу, при многократном применении медианного фильтра захватываемая группа изменит цвет на цвет захватчика.
        Т.е. применяя циклически фильтр ко всей доске получаем вероятного победителя.
        С глазами небольшая неувязка, но, во-первых, модифицированная версия фильтра позволяет интерференцию волн захвата, а, во-вторых, я говорил про связь, а не про высшее мастерство.
        Для точек, где нет глаз, область 8-связная, ситуация лучше.
        • 0
          Своеобразный аналог правила ко:
          _Х0_->_0X_
          Х0Х0->X0X0
          _Х0_->_0X_
          Разумеется, в го, как и в большинстве игр(почему не всех?), у первого(начинающего) игрока есть преимущество — «эффект неожиданности», что фильтр совершенно не учитывает.
          • 0
            _Х0_->_0X_
            Х0Х0->0Х0Х
            _Х0_->_0X_
            • 0
              Я не силён в го (более того, даже правил полных не знаю :)), но описываемое больше похоже на обычную эвристику в стиле Монте-Карло с простой функцией оценки позиции. Вы пробовали такое гонять против людей/ботов? Думаю, должны существовать реализации го, позволяющие писать своих ботов — проверьте, если нетрудно, мне очень интересно, как далеко оно сможет зайти.
              • 0
                «должны существовать реализации го» — Они есть тут. Бот для игры го — это не на один вечер, если и возьмусь, только после накопления должного уровня мотивации. «как далеко оно сможет зайти» — оно не сможет ходить:)
              • 0
                вот пример, показывающий логику
              • 0
                Тот же пример, но медленнее и с крупными ячейками

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