Реми Кулом (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото Ёды

В 1994 году компьютер обыграл чемпиона мира по шашкам, в 1997 году - по шахматам. Сегодня компьютеры превосходят людей абсолютно во всех популярных играх с полной информацией , кроме одной - го.

У классической игры с 2500-летней историей очень простые правила, но компьютерные программы даже близко не могут подобраться к победе над лучшими гроссмейстерами, пишет Wired.

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

Несмотря на рост вычислительной мощи компьютеров (чемпион мира по шахматам сегодня, вероятно, проиграет даже вашему домашнему ПК), алгоритмы игры в го на экспертном уровне остаются нерешённой и одной из самых интересных задач ИИ. Проблема ещё и в том, что очень немногие способны подняться до девятого дана в игре. Для этого нужно несколько лет обучаться в Японии или Корее. Там талантливых детей забирают из дома для обучения в академии го примерно с 9 лет.

Продвинутые любители почти всегда застревают на определённом уровне игры и не могут улучшить результат: «Требуется некий ментальный прыжок, чтобы снять эту блокировку, и в разработке программ та же проблема, - объясняет Дэвид Фотлэнд (David Fotland), главный разработчик процессора PA-RISC в компании Hewlett Packard в 70-е годы. Он тестировал программу го на процессоре своей разработки. - Вопрос в том, как оценивать всю доску, а не отдельные фрагменты».

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

Компьютерные программы для го разрабатывают уже 45 лет, этой проблеме уделяли почти столько же внимания, сколько и шахматным программам. Первую написал гений теории игр Альфред Зобрист в 1968 году. Она могла обыграть абсолютного новичка, который только что познакомился с правилами (запись первой игры человек-компьютер). Начало казалось оптимистичным. В следующие четыре десятилетия было потрачено огромное количество времени и интеллектуальных усилий, но даже с учётом прогресса в вычислительной мощности программы так и не смогли одолеть даже продвинутого любителя.

Причину можно понять, если сравнить го с шахматами. В начале шахматной партии у белых есть 20 возможных ходов, а у чёрных - 20 возможных вариантов ответа. После первого хода на доске может быть 400 различных позиций. А теперь сравните цифры в го: на доске 19х19 у чёрных есть 361 возможных начальных ходов, а у белых 360 вариантов ответа. Это означает 129 960 возможных комбинаций только после первого раунда.

Так называемый «фактор ветвления» - среднее количество ходов, доступных в каждом раунде - в шахматах составляет 35, в го - 250. Игры с сильным ветвлением затрудняют работу стандартных алгоритмов, использующих правило минимакса для создания дерева возможных комбинаций. Даже с учётом анализа не всех, а только перспективных ветвлений для более глубокого анализа. То, что работает в шашках и шахматах, не работает в го. Выбор перспективных ветвлений в дереве возможных комбинаций го - часто совершенно таинственный процесс. Даже игроки не понимают, как они это делают: «Просто смотришь на доску и знаешь», говорят они.

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

Среднее количество ходов в игре: в шахматах - около 40, в го - 200. Учитывая фактор ветвления и эту статистику, становится понятным бессилие компьютеров.

Талантливый французский программист Реми Кулом (Rémi Coulom) добился первого успеха с программой Crazy Stone в 2006 году, когда догадался совместить минимакс и метод Монте-Карло. Новый алгоритм расчёта дерева ветвлений он назвал Monte Carlo Tree Search или MCTS. Француз выиграл чемпионат среди компьютерных программ UEC Cup в 2007 и 2008 годах, но это так и не принесло ему известности, и Реми забросил разработку. Но в 2010 году он получил предложение от японского игрового разработчика Unbalance - и в 2011 году вышла первая коммерческая версия Crazy Stone. В 2013 году Реми победно вернулся на чемпионат.

Однако, в 2014 году случилась неудача. В финальном противостоянии против программы Zen зрители поняли, что творится нечто странное уже после третьего хода. Программа Zen, после стандартной постановки двух камней по углам вдруг поставила третий камень около центра. Так никто не играл, это было явно «нечеловеческое» решение. Вскоре уровень победных ожиданий у Crazy Stone вырос до неприлично высоких значений, более 60%. Судя по всему, программа считала безопасной группу камней в правом верхнем углу, хотя она не была безопасной. Поскольку успешная стратегия напрямую зависит от правильной оценки доски, зрители начали шептаться о возможном поражении Crazy Stone. Так оно и вышло: на 186 ходу Crazy Stone признала поражение, а Zen стал новым чемпионом UEC Cup.

Впрочем, у Кулома осталась возможность реванша. Как финалист, он получил право играть против настоящего гроссмейстера-человека с форой в четыре камня. В этом году на турнир приехал Норимото Ёда. Японский гроссмейстер сел за стол в традиционном зелёном кимоно. Реми Кулом - в очках без оправы и синем свитере, в которых был и на прошлом чемпионате.

Правила игры Го очень просты. Для их освоения вам потребуется несколько минут.

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

Для игры Го используют камни белого и черного цвета и доску 19х19 линий (361 игровая точка)

Партия начинается на пустой доске, первыми ходят черные. Ходом считается постановка камня на точку пересечения линий. Ставить камень можно в любую точку, без ограничений, в том числе на боковые и угловые точки. Поставленные камни не передвигаются и остаются на своем месте до конца игры, если не будут съедены. Основная задача - окружать территорию (пустые точки) или камни другого цвета.

Главное правило Го

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

(;ABMAC[Камень, стоящий не на стороне и не в углу имеет 4 точки свободы, которые называются "степень" или "дамэ" . Пока у камня есть хотя бы одно дамэ, он остается стоять на доске, независимо от позиции.]SZ;AWMAC[В этой позиции у черного камня осталось 1 дамэ. Это значит, что камень находится в атари , т.е. до полного его окружения остался 1 ход - в пункт Х .] ;WC[Белые ставят камень на место последнего дамэ черного камня и снимают его с доски.])

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

(;ABAWCRTRMAC[Х отмечены пункты, сделав ход в которые черные могут окружить камень или группу камней. О отмеченные пункты, сделав ход в которые белые могут окружить камень или группу камней. Треугольником отмечены камни, имеющее одно дамэ, т.е. они могут быть захвачены следующим ходом. ] SZMULTIGOGM ;BCRC[Черные 1 - этот ход черных полностью лишает белый камень дамэ. Камень, не имеющий дамэ, снимается с доски.];WCRC[Белые 2 - аналогичная ситуация, у двух черных камней не осталось дамэ, поэтому они снимаются с доски.];BCRC[Черные 3 - съедает один белый камень, стоящий на стороне. Для окружения одинокого камня на стороне достаточно трех камней противоположного цвета.];WCRC[Белые 4 - полностью лишает дамэ два черных камня, стоявших на стороне.];BCRC[Черные 5 - забирает один камень, стоявший в углу. Для окружения одинокого углового камня достаточно двух камней.] ;WCR;BCRC[Черные 7 - забирает три камня.];WCRC[Белые 8 - лишает дамэ два камня, стоявших отдельно друг от друга, т.е. не образовавших единой группы.];BCRC[Черные 9 - забирает одним ходом две группы белых, состоявших из двух и одного камня.];WCRTRC[Белые 10 - забирает черный камень, при помощи которого черные при своем ходе могли бы съесть один из трех отмеченных треугольниками камней белых. Белые снимают окруженный камень и обеспечивают себе временную безопасность.];BCRC[Черные 11 - одним ходом забирает сразу 4 белых камня.]];WMAC[Х - отмечены съеденные камни.])

Правила завершения партии Го

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

Правила подсчета территории

Территорией считается окруженная со всех сторон область, которая не может быть оспорена.
Каждое пересечение (точка) приносит одно очко, каждый съеденный камень - тоже одно очко.

(;ABAWCRMASZMULTIGOGM)

На диаграмме изображена законченная партия.

О - отмечена территория белых. Х - отмечена территория черных.

Обратите внимание: в территории белых находятся 3 черных камня. Это пленные камни, в данном случае тратить ход на полное окружение не надо. Но бывают ситуации, когда доигрывание обязательно. Со временем вы научитесь различать эти ситуации. Три камня черных в данном случае считаются пленными. При подсчете очков они просто снимаются с доски. Так же, во избежание патовых ситуаций, белые получают компенсацию за то, что черные делают первый ход. Эта компенсация называется "коми " и составляет 6,5 очков, если играют равные по силе игроки. Коми может быть больше или меньше, в зависимости от разницы в силе игроков, но всегда добавляется или отнимается 0,5 очка, чтобы не было ничей (подробней в разделе "Как строить территорию").

Очки белых:

Территория = 22 очка

Пленные = 3 очка

Коми = 0.5 очка

Съеденные = 0 очков

2+3+0.5+0=25.5 очков

Очки черных:

Территория = 24 очка

Пленные = 0 очков

Снятые = 1 очко (черные захватили за партию 1 камень белых, он снят с доски)

Коми = нет

24+0+1=25 очков

Результат партии: белые выиграли 0.5 очка (пол-очка)

Выигрывает игрок, набравший большее количество очков

За право первого хода игрок отдает 0.5 очка напарнику. Дробная часть приводит к отсутствию ничейного результата.

Запрещается

Намеренно ставить камни в полное окружение.

Повторять позицию.

Общие советы по освоению правил

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

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

В го обычно играют на доске размером 19 на 19. На Д.1 показана пустая доска. Обратите внимание на девять отмеченных точек пересечения линий. Они называются «хоси». (латинская транскрипция hoshi, дословный перевод с японского на русский – звезда). Эти отметки на доске используются для удобства и для расположения форовых камней.

Для игры используются фишки белого и чёрного цветов, которые выполнены в виде двояковыпуклой линзы. Называются они «камни». Обычно эти камни изготавливаются из пластмассы или стекла. В дорогих комплектах белые камни делают из морских раковин, а чёрные из сланца. Вне зависимости от того, из чего сделаны фишки, их называют просто камнями. В начале партии у игрока, играющего чёрными – 181 чёрный камень, а у играющего белыми 180 белых камней. Общее количество камней (361) соответствует общему количеству пересечений линий на стандартной доске 19х19. Принято держать камни в деревянных или пластиковых чашах рядом с доской.

В начале партии доска пустая. Один игрок берёт чёрные камни, второй белые. Чёрные делают первый ход. Ход – это выставление камня в точку пересечения линий доски. Можно ходить на любое незанятое пересечение, но в начале партии первые ходы обычно делают ближе к точкам хоси в углах доски. Ходят по очереди. Камень, выставленный на доску, не перемещается. Он может быть снят с доски в случае взятия. На Д.2 показано типичное начало партии. Чёрные сделали первый ход в правом верхнем углу. Белые поставили камень 2 в левом верхнем. Далее, в соответствии с правилами, ходы делались по очереди. Обратите внимание – ни одна сторона в начале не ходила далеко от углов.

Четыре основных правила игры го

Цель игры – захват территории

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

На примере партии на доске размером 9х9 посмотрим, как захватывается территория. Партия на такой маленькой доске не богата стратегическими приёмами, но правила и даже некоторые тактические приёмы не отличаются от игры на большой доске. Рекомендуется осваивать правила именно в игре на доске 9х9. Затем можно перейти к игре на доске 13х13. Вскоре, сыграв около 100 коротких партий, вы начнёте чувствовать себя уверенно в игре на стандартной доске.

На F.1 чёрные сделали первый ход вверху справа. Потом ход сделали белые. Обе стороны продолжали ходить по очереди, в соответствии с правилами игры.

К ходу б.6 территория обеих сторон начинает обретать форму. Чёрные застолбили правую сторону, белые возлагают надежды на левую.

После того, как оба игрока обозначили свои претензии на территорию, возникают две основные стратегии. Первая – увеличить свою территорию, одновременно уменьшая территорию противника. Вторая – вторгнуться в сферу влияния противника.

Ход ч.7 на F.2 следует первой стратегии. Чёрные расширяют свою территорию внизу справа, и не позволяют белым расширить свою территорию ходом «а». Белым следует защититься 8, чтобы остановить продвижение чёрных глубже в свою территорию. Далее чёрные укрепляют границу ходом 9.

Настала очередь белых расширить свои владения. Сначала они добавляют территории в центре б.10 и 12 (F.3 ), затем вверху слева б.14. Чёрные должны защищаться 15. Теперь разыгрываются очки вокруг точек «а» и «b».

Разыграна стандартная последовательность б.16-ч.19 (F.4 ). Аналогично сыграно внизу б.20-ч.23. Играя таким образом, белые расширили свою территорию, одновременно уменьшив территорию чёрных.

Ходы от б.24 до ч.26 – последние в партии. Теперь можно определить победителя. В данном случае подсчитать результат просто.

Территория чёрных состоит из всех незанятых пунктов, которые они контролируют на правой стороне, а территория белых состоит из контролируемых ими пунктов на левой. Конкретнее, все пункты, отмеченные буквой "b" на F.6 , составляют территорию чёрных, а все пункты, отмеченные буквой "w", являются территорией белых. Если вы сосчитаете их, то обнаружите, что у чёрных 28 очков, а у белых 27. Таким образом, чёрные выиграли с разницей в одно очко. Обратите внимание, что точки занятые белыми и чёрными камнями в расчёт не принимаются.

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

Мыслить и побеждать: игра Го для начинающих Гришин Игорь Алексеевич

ЧТО ТАКОЕ СТРАТЕГИЯ И ТАКТИКА?

Стратегия - искусство руководства, основанного на грамотном и глубоком владении ситуацией.

Тактика - совокупность средств и приемов для достижения намеченной цели.

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

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

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

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

Игра Го позволяет оттачивать мастерство тактики и стратегии на уровне абстрактного мышления и применять постигаемые закономерности в любой сфере жизни.

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