: Максим Солохин (palaman) wrote,
2018-06-18 13:10:00

Максим Солохин
palaman
2018-06-18 13:10:00

Го и Пустота

Статья об игре Го (Драма, которая изменила мою реальность) была благосклонно воспринято читателем, и у меня возникло желание опубликовать несколько текстов, написанных мною пару лет назад и не опубликованных потому, что я сомневался, будет ли это кому-то интересно.

Го и Гугль

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

[Spoiler (click to open)]
Вычислять наилучший ход, тупо перебирая варианты – дело в Го почти безнадежное. Го интересно именно тем, что здесь гораздо более эффективным является подход эстетический, чем математический. Мастер ставит камни на доску красиво – прежде всего именно красиво! и гармония побеждает тупой математический расчет. Это была одна из главных причин, почему Го привлекло меня в молодости. Другая причина – привкус дальневосточной мистики, который не отделить от этой игры. Игра Го – наглядный пример вечной борьбы и взаимного порождения Инь и Ян. Тем более интересный пример, что его можно изучать и оценивать математически. Возможность измерить алгеброй гармонию Инь и Ян – слишком ценная добыча, чтобы я мог просто пройти мимо.

Надо сразу сказать, что Гугль пошел другим путем. Основа действия его программы – опять-таки не расчет, а подражание человеку. Рассматривая позицию на доске, Гугль сравнивала её с имеющимися в базе данных партиями, и ходила по аналогии, подражая игре мастеров. Это основа! А далее, программа уже несколько лет непрестанно играет сама с собой, накапливая новый и новый опыт. И вот, оказывается, что ТАКОЙ интеллектуальной мощи человек противостоять неспособен. В тот день, когда я осознал это, мой мир изменился. Я поверил в роботов и приготовился к тому, что спустя некоторое время они овладеют всеми человеческими профессиями. Надежды больше нет. Я увидел чемпиона мира по Го побежденным железякой, и осознал, что дивный новый мир уже наступил. Скоро общественный транспорт исчезнет, и все мы будем ездить на беспилотных такси, логистика которых будет определяться каким-нибудь Яндексом. Вышел на перекресток, послал запрос – и через пять минут подойдет микроавтобус, в котором сидят случайные попутчики. Или персональная легковушка, если ты объявил, что готов заплатить больше. Впрочем, скорее всего, Яндекс будет знать тебя как облупленного, все твои привычки. И предвидеть все твои обычные запросы заранее. А может, и необычные – по крайней мере, если за это возьмутся так же основательно, как взялись за Го.

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

А вслед за тем у меня появилось и желание рассказать моему читателю о своих размышлениях по поводу самой игры, безотносительно к вопросу о дивном новом мире. В отличие от шахмат, Го входит в этот новый мир с честью. Пусть программа и победила человека – но создатели этой программы не могу объяснить, как она это сделала. Го было и остается, и скорее всего остается тайной для нас даже после того, как искусственный интеллект постигнет эту тайну. Эта восточная игра продолжает будоражить моё воображение - и оттого, что теперь она прочно связалась в моем уме с вопросом об искусственном интеллекте, её древняя мистика всего лишь становится мистикой современной.
В самом деле, как бы успешно ни развивалась вычислительная техника, едва ли когда-нибудь ядро процессора будет совершать более одной операции за Планковское время. Это естественное ограничение, накладываемое квантовой природой материи. Значит, ядро процессора не может иметь быстродействие более (10**33) операций в секунду. С другой стороны, число таких ядер не может превышать количества элементарных частиц по Вселенной (10**80), а общее время расчета едва ли имеет смысл брать большим, чем время жизни Вселенной (10*17) секунд. Итого, какими бы фантастическими ни были успехи человечества в области Искусственного Интеллекта, мы никогда не сможем перебрать более (10**150) вариантов игры Го. Этого явно недостаточно, чтобы исследовать Го полностью и наконец закрыть эту тему. Следовательно, Го ещё будет преподносить человечеству новые и новые сюрпризы.

Го и Пустота

Мне было бы гораздо удобнее говорить с читателем, который знаком с Го, и я бы предложил читателю, у которого будет свободное время, посмотреть несколько первых серий аниме «Хикару но го». Этот сериал японцы сняли специально для рекламы Го среди своей японской молодежи. Рассказ начинается с того, как обычному школьнику является некий дух, который выдает себя за душу мастера, которая нигде не находит покоя после смерти, кроме как на гобане. Этот дух желает играть и использует мальчика, чтобы играть с современными мастерами. Ну, а для ребенка весьма лестно выходить победителем, делая гениальные ходы по подсказке «свыше». Потом мальчик сам увлекается игрой, и сериал становится скучным, так как история духа отходит на второй план, уступая место зануднейшей бытовухе какого-то провинциального Го-клуба. Но к концу действие опять оживает: дух исчезает, оставляя позврослевшего мальчика тосковать по себе. Только теперь Хикару понимает, как ему повезло и каким он был дурачком. Но все кончается хорошо: оказывается, дух не ушел, а вселился в душу Хикару, и Хикару теперь "сам" проявляет гениальные способности к игре. Короче, начало и конец сериала очень даже неплохие по мой вкус.

Но поскольку подавляющее большинство моих читателей едва ли знают о Го что-то кроме самого названия, мне придется все-таки изложить основы, и по возможности так, чтобы это было не скучно. Мою задачу облегчает то обстоятельство, что игра Го является безусловным и беспрецедентным чемпионом по отношению «сложность игры поделить на сложность её правил». Правил в Го так мало, и они настолько естественны, что порой об их существовании вообще забываешь, будто их и нет.
А что есть? Есть расчерченная доска (гобан) и есть камни двух цветов (Инь и Ян), которые противники по очереди выставляют на доску. Вначале доска пуста. Ставить камень можно на любой свободный пункт. (А если не хочешь, можешь не ставить никуда и просто пропустить ход!) На любой! Этим и обусловлено кошмарное число вариантов игры. Камень не сдвигается с места до конца игры, если только противник его не срубит. Этим объясняется эффективность человеческой интуиции в Го. Вся позиция в текущий момент и все возможные варианты её дальнейшего развития – вот они, перед глазами. Текущая ситуация видна, а будущая вообразима. В шахматах ситуация на доске постоянно меняется, шахматы трехмерны (время – это третье измерение) и потому плохо помещаются в нашем сознании; компьютер с его огромной памятью и быстродействием сразу получает превосходство перед человеком.
Го двумерно. Всё видно, всё открыто, всё предельно обнажено, ничто не препятствует свободной работе воображения – главному преимуществу человеческого ума. Игра развивается поступательно и необратимо. Вначале доска пуста, потом камней становится больше и больше, пока они не заполняют доску в такой мере, что уже можно сказать, кто из противников одержал победу. Труднее всего для человека просчитывать как раз такие варианты игры, когда часть камней снимается с доски и заменяется новыми, особенно если камень заменяется камнем другого цвета снова и снова несколько раз («ко-борьба»). В таких случаях компьютер почти сразу обнаруживает свое превосходство над нами – человеку трудно воображать такие динамичные системы как целое. Мы легко охватываем взором двумерные картины, но плохо вмещаем в своем уме трехмерие. Но, по счастью, в Го такое случается не очень часто и потому не сильно влияет на человеческое качество игры в целом. А Шахматы - они целиком основаны на перемещениях. Вот причина, почему люди так быстро уступили компьютеру в шахматах, но при этом так долго продержались в Го.

Итак, пустая доска постепенно заполняется камнями, камень за камнем, поочередно черный и белый.
Черные (Инь) ставят камень первыми, они начинают игру, символизируя зло, нарушение первоначальной идеальной гармонии (пустота на доске – это и есть идеальная гармония). Белые (Ян) вынуждены отвечать, восстанавливая утраченную гармонию. Конечная цель борьбы – занять территорию. Инь и Ян делят между собой гобан, кому сколько достанется. Пустая территория, окруженная твоими камнями, считается твоей территорией. Но если она окажется слишком большой, белые смогут набросать туда своих камней и построить там живую фигуру. Потому большая территория обязательно должна быть разделена на достаточно маленькие укрепленные участки, куда вторгаться бесполезно. Обычно к концу игры примерно половина пунктов гобана остается незанятой и отходит во владение черных либо белых. Можно сказать, что цель игры – оградить достаточно прочным «забором» как можно больше пустого места. Пустота, незанятая земля – это та ценность, ради которой ведется война. Потому не стоит без особого умысла ставить камни слишком плотно, слишком близко друг ко другу – это нерациональное расходование ресурса.

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

Пустота – это жизнь. По правилам Го, любая фигура живет до тех пор, пока она соприкасается с пустотой. Фигура – это несколько камней, соединенных между собой. Если два камня касаются друг друга, то они принадлежат одной и той же фигуре. Когда мы добавляем камень к фигуре, фигура растет. Если фигура не может больше расти, то она немедленно умирает и снимается с доски. Нет пустоты – нет жизни. Мертвая фигура освобождает место для живительной пустоты. Чем больше пустых пунктов, с которым соприкасается фигура, тем больше в ней жизни. Камни одной фигуры живут общей жизнью до конца игры, или же снимаются с доски одновременно – сразу, как только оказалось, что ни один из них больше не соприкасается с пустотой.

Итак, противники борются между собой за обладание пустотой, пустота же и обеспечивает им жизнь. Этим определяется цель игры, её динамика и её своеобразная эстетика, которую довольно скоро начинаешь ощущать. Заполняя доску, противники постепенно лишают друг друга пустоты, и надо успеть застолбить себе надежную территорию, которая будет гарантировать твоим фигурам жизнь в дальнейшем, когда на доске станет тесно. Кто не успел – тот опоздал. Окруженная и «задушенная» камнями противника фигура снимается с доски и снова превращается в пустоту. Пустоту, окруженную противником и принадлежащую ему, так как она соприкасается лишь с его камнями.

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

Постепенно было осознано, что не обязательно доводить игру до конца, чтобы понять её результат. Японцы научились играть в Го от китайцев, и сразу приняли другие правила подсчета очков, более простые и удобные, но менее строгие в математическом смысле. Игра теперь ведется до тех пор, пока оба противника пропустят ход. После этого они обсуждают ситуацию и соглашаются между собой, что такие-то фигуры являются нежизнеспособными, пленными. Если возникает разногласие, то игра возобновляется и спорная фигура либо снимается с доски, либо доказывает свою жизнеспособность. Если разногласий нет, пленные просто снимаются с доски и добавляются к числу срубленных фишек. Оставшуюся нейтральной территорию просто игнорируют. После этого японцы выставляют обратно на доску все пленные и срубленные камни, заполняя ими территорию своего противника. Чем больше камней ты потерял, тем меньше останется у тебя территории. После этого считают свою территорию - именно пустоту и только пустоту. Так играть и так считать намного быстрее и удобнее.
Профессионалы идут ещё дальше и вообще как правило не доводят игру до конца – кто-то из них признает свое поражение, хотя на взгляд непрофессионала в этой позиции ещё ничего не понятно, надо бы играть и играть. Вот например, здесь черные сдались:

(Го Сэйгэн против Китани Минору, Токио, 1957 г.)

Есть ли разница между китайским и японским Го? Поскольку противники ходят по очереди, количество черных фишек на доске после того как японцы выставили назад всех пленных и убитых равно количеству белых фишек. И потому нет разницы, считать ли только пустоту, как это делают японцы – или считать также и фишки, как это делают китайцы. Разница между двумя способами подсчета может составлять одно очко: в том случае, если черные сделали ход последними, они выставили на доску на один камень больше, чем белые. Японская система подсчета в этом случае оказывается чуть-чуть выгоднее с точки зрения белых, а китайская – с точки зрения черных. Если последний ход был белых, то разницы нет вообще.

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

Го в миниатюре

Давно уже установлено на практике, что черные имеют небольшое преимущество по той же причине, по какой в шахматах преимущество имеют белые. Право первого хода! Легко доказать, что белые в го не могут иметь преимущества ни при каких условиях. Ведь если бы первым ходить было невыгодно, то черные могли бы просто пропустить свой ход и предоставить белым право играть первыми. Из права пропускать ходы логически вытекает преимущество черных или уж по крайней мере отсутствие преимущества у белых.
Это естественное преимущество черных издавна использовалось на Востоке для ранжировки мастеров игры в Го по данам. Белые слабее. И потому если кто-то играл против противника того же дана, то должен был на несколько очков побеждать при игре черными, но проигрывать при игре белыми. Это нормально. Небольшой проигрыш (в несколько очков) для белых не считается поражением. А более высокий дан доказывает свое принципиальное превосходство тем, что побеждает, играя белыми. Самый высокий дан – 9-й, самый низкий – 1-й. Но даже игрок первого дана - это уже мастер.
Мастера сражались между собой на большой доске (19*19). А те, кто ещё не был удостоен дана (звания мастера), соревновались между собой на маленькой учебной доске (13*13). Там использовался отдельный ученический рейтинг, где ранги назывались не «дан», а «кю». Самый высший ученический ранг – это 1-й кю. Продвинутый ученик уровня 1-го кю имеет шанс победить мастера 1-го дана, играя на большой доске черными. Если же это случается регулярно – это значит, что он становится мастером и скоро может получить свой первый дан. Второй, третий и далее кю определялись аналогично. Равные бойцы побеждают, играя черными, но проигрывают, играя белыми. Но 2-й проигрывает 1-му даже того, когда играет черными.
Эта древняя система ранжирования мне нравится, потому что она естественная: даны и кю определяются не произвольным соглашением, но свойствами самой игры. Правда, граница между «данами» и «кю» всегда была условна и зависела от местной традиции – на каком уровне ученику пора переходить на большой гобан. Первый японский дан соответствовал третьему корейскому кю. То есть, в Корее требования к «мастеру» были намного выше.
В наше время всё вообще делается несколько по-другому. Шансы белых и черных на победу теперь сравняли, используя самый простой и естественный способ. Белым дается несколько дополнительных очков в компенсацию за то, что они лишены права ходить первыми. Понятия «дан» и «кю» по-прежнему в ходу, но определяются иначе – подробности можно узнать, например, в Википедии. Современная система практичнее, но древняя интереснее и естественнее.
У современной системы есть и принципиальный недостаток! Дело в том, что никто до сих пор не знает в точности, сколько же именно очков следует давать черным за право первого хода. Игра Го насчитывает уже несколько тысяч лет, но это важное число остается неизвестным. В разных странах приняты несколько разные нормы. Где пять очков, где шесть, а где и семь. В международных соревнованиях белым дают пять с половиной очков. Эта «половина» с точки зрения математики абсурдна, так как преимущество черных – это некое конкретное целое число. Это число теоретически можно было бы вычислить, просто перебрав все варианты игры и найдя, к какому результату пришли бы черные и белые, действуя каждый со своей стороны наиболее оптимальным образом. Поскольку вариантов слишком много (гугль в кубе), эта возможность имеет чисто академический характер. И сколько очков давать белым - это определяется «на глазок», по-разному в разных странах, что довольно некрасиво.

Размышляя об этом числе, я задался вопросом, а нельзя ли его вычислить чисто теоретически, не перебирая варианты игры, но используя математический подход. Эта мысль подтолкнула меня исследовать игру Го средствами математики.
Идея заключалась в том, чтобы изучить свойства Го при игре на гобанах маленького размера, где можно осуществить перебор вариантов. На Востоке используют гобаны 19*19 и 13*13. Можно встретить также детский гобан 7*7. Игра на детском гобане сравнительно проста, здесь количество возможных партий Го не превышает число вариантов в Шахматах. Этот ряд чисел легко экстраполировать: 1, 7, 13, 19, 25, 31… (Кстати, иногда действительно играют на супербольшой доске, размером 25*25.) Это арифметическая прогрессия с шагом 6, которая начинается с тривиального «гобана» размеров в один-единственный пункт. Почему именно шесть? Мне кажется, тут два соображения. Вообще-то, исходя из практики игры, для Го имеет значение тройка. Занять третий пункт от угла значит наверняка овладеть этим углом (достаточно лишь отвечать, притом правильно отвечать на ходы противника), а борьба за углы – основа стратегии в теории Го. Если рассмотреть прогрессию с шагом 3 – 1, 4, 7, 10, 13, 16, 19, 22, 25..., из неё почему-то исключены все четные числа – 4, 10, 16, 22. Восточным людям претит гобан четного размера – было бы интересно понять, почему.
Одним словом, у меня возникло желание исследовать Го более абстрактно, рассматривая «гобаны» самого разного размера и формы. Если на простых примерах удастся понять связь между размером доски и преимуществом черных, то можно будет сказать точно, чему равно это преимущество на большой доске, даже не перебирая всех вариантов игры. Это вовсе не лишняя работа, ведь такой перебор никогда не будет возможным, как мы показали выше.

Го и математика.

Прежде всего, надо сказать, что «пустота» на гобане с точки зрения математики вовсе не является пустотой. Даже совершенно пустой гобан – это вовсе не пустота. Напомню, что графом математики называют любое множество (пунктов), на котором задано какое-то другое множество – множество пар (отрезков), соединяющих эти пункты. Пустой гобан – это граф. И в Го можно с тем же успехом играть на любом графе, любой формы, используя те же самые правила, которые используются в обычном Го.

Возьмем для примера самый-самый простой граф. Два пункта, соединенных между собой. Черные могут занять один из этих пунктов. Но если белые займут свободный пункт, то черный камень лишится «воздуха». Но при этом белый камень и сам лишится «воздуха». Кто-то из них должен умереть, но кто?
Тут возможны два варианта правил, две различных игры.
Можно запретить такие «самоубийственные» ходы, и тогда получится игра в «точки», которая была в моё время довольно популярна в советских школах. Она намного проще и не так интересна как Го, зато в неё можно играть на бумаге. Не нужны ни гобан, ни камни. Достаточно иметь лист бумаги в клеточку из школьной тетрадки и карандаш. Однажды срубленная фигура в этой игре погибает навсегда, так что игра обходится даже без стирательной резинки – срубленные фигуры можно просто зачеркивать. А любая фигура, внутри которой оказался пустой пункт или зачеркнутая фигура противника, тут же становится бессмертной. Её уже невозможно лишить «воздуха», так как она имеет внутреннюю пустоту.
Настоящее Го устроено интереснее. Оно более агрессивно. В описанной ситуации нападающая фигура остается на доске, погибает же фигура обороняющаяся. При игре на минимальном графе (из двух пунктов) это означает, что черный камень снимается, а белый остается.
Но теперь возникает новая проблема: черные могут так же точно «срубить» камень белых. И возникает цикл, повтор, который красиво выглядит, но создает проблему. Игра становится бесконечной и лишается смысла. Чтобы избежать этого бесконечного тупика, в Го вводят дополнительное правило, так называемое «правило Ко». Фактически, это единственное настоящее правило, регулирующее поведение противников. Все до сих пор перечисленные «правила», в сущности, не были в полном смысле правилами, так как они просто описывали ход игры и её цели. Правило же Ко – это настоящее правило, как в шахматах. Оно запрещает! Запрещается делать ход, в результате которого повторяется позиция, которая уже была на доске во ходе данной игры. Правило Ко запрещает повтор и требует необратимого поступательного развития игры. Игра должна двигаться вперед, а не топтаться на месте, возвращаясь назад.
Надо признать, что правило Ко чуть-чуть меня разочаровывает. Игра Го поражает отсутствием запретов. Можно ходить куда угодно и можно пропускать ходы. Можно всё. Но вот повторяться – нельзя. Здесь Го становится чуть-чуть, самую малость похожим на шахматы, ведь шахматные правила состоят в основном из запретов. Конь не может ходить как слон, а слон – как конь, и так далее. Оказывается, в Го тоже можно не всё, но ПОЧТИ всё, и это «почти» немного огорчает.
Итак, го на простейшем графе приводит черных к неизбежной катастрофе. Белые рубят черный камень, а черные не могут ответить тем же, поскольку это привело бы к повтору уже бывшей позиции. Таким образом, граф остается целиком во власти белых, черные проигрывают два очка. Потому единственная разумная стратегия черных – пропустить ход, предоставив белым сделать эту глупость. И белые должны поступить так же точно. Обе стороны пропускают ход, игра закончена. Что же в результате? Мы обнаруживаем, что простейший граф, граф-отрезок, не дает черным никакого преимущества первого хода. Го на отрезке имеет нулевой результат.
(Строго говоря, для полноты картины надо бы рассмотреть и тривиальный граф, состоящий из одной-единственной точки. Жить там невозможно, «дышать» нечем. Потому на тривиальном графе черные тоже не имеют никакого преимущества.)

Следующий по уровню сложности граф состоит из трех пунктов. Тут есть два варианта. Либо это треугольник, либо отрезок с пунктом посередине.
Во втором случае, черные немедленно занимают центр, и белые проиграли. Они не могут срубить черных, потому что у тех в любом случае остается «воздух». В го это называют «фигура с двумя глазами». Глаз – это пункт или маленькая территория, полностью принадлежащая данной фигуре. Если у фигуры два глаза, то она бессмертна. Если только один глаз, то её можно убить, заняв этот глаз. Итак, три точки на одной линии дают черным преимущество в три очка. А как ведет себя треугольник? Задача о треугольнике оказывается непростой.

Я сделал небольшую гифку для иллюстрации этого. Её можно скачать здесь и просмотреть при помощи браузера.

У меня даже возникает соблазн написать, как это принято делать в научных статьях: «недолго подумав, нетрудно убедиться». Так пишут в тех случаях, когда убедиться на самом деле довольно трудно, и авторам статьи неохота тратить силы на объяснения.

Итак, "недолго подумав, нетрудно убедиться", что на треугольник чёрным лезть не рекомендуется. Лучше всего сразу пропустить ход, потому что кто начнет борьбу первым, тот обречен на неминуемое поражение, если только противник не будет делать ошибки. Вы gif-ке сверху на нарисовал, как должны действовать черные, чтобы прожить на доске как можно дольше. И как должны действовать белые, чтобы всё-таки выжить чёрных с треугольника. Повторяю: чёрные допускают непоправимую ошибку, вообще начиная игру. Но если они уж начали её, нужно действовать так, как я показал. При этом на доске последовательно появляются ВСЕ возможные варианты позиции (их 19, включая пустой граф). Черные проигрывают, если белые загоняют их в позицию, когда ответить на удар запрешает правило Ко. Как бы черные ни старались, белым это удастся. Любое уклонение от этой страгегии лишь приближает неминуемую смерть.

Но и белые - если сделают хоть один неверный ход, не добьются победы.

[Кому не лень потратить время на проверку этого утверждения.]Итак, допустим, черные попытаются застолбить себе место и займут одну из вершин треугольника (любую из трех!). Но тогда белые немедленно занимают другую вершину (любую из оставшихся двух!). Если черные рубят белый камень, занимая последний оставшийся свободным пункт, то у них получается фигура с одним глазом, и белые немедленно выбивают этот глаз. Позиция выглядит так, словно это белые сделали ход первыми. Теперь у черных два варианта. Если они займут прежний пункт, то белые немедленно срубят их камень, и черным придется смириться с поражением, так как срубить белых им теперь запрещает правило Ко! Если они займут не прежний, а новый пункт, то они смогут срубить белых, так как ситуация пока не повторяется. На доске будет снова стоять одинокий черный камень, но уже на новом месте. Белым нельзя в ответ занимать старое место, иначе правило Ко обратится против них и приведет их к поражению. Потому они займут новое место, и вся картина игры в точности повторится с поворотом на 120 градусов. А потом ещё раз, и… черные все-таки потерпят поражение, потому что после второго поворота получается поворот на 360 градусов, то есть повтор! Повторяться нельзя, и черные терпят поражение. (Недолго подумав, нетрудно убедиться)
Каков вывод? Если черные заняли пункт, а белые ответили им, то далее черным нельзя рубить белых! Это ведет к неизбежному поражению, если белые не допускают ошибок. Но если черные пропустят ход, то белые их просто срубят, а ответить черным запрещает правило Ко. Таким образом, мы доказали, что черным лучше вообще не лезть и на треугольный граф! Они должны пропустить ход, и если белые сделают глупость и попытаются занять пункт, то неизбежно проиграют при правильных ответах черных. Таким образом, треугольный граф следует оставить пустым. Он не дает черным никакого преимущества так же, как и отрезок.

Что общего между отдельной точкой, отрезком и треугольником? То, и другое, и третье – так называемые полные графы. Полный граф – это граф, в котором каждый пункт связан с каждым пунктом. Возникает гипотеза, что на всяком полном графе тот, кто делает ход первым, терпит неизбежное поражение, если только противник придерживается правильной стратегии. Правильная стратегия заключается в том, чтобы загонять противника в тупик, используя правило Ко. Итак, гипотеза: идеальная стратегия Го на любом полном графе заключается в пропуске хода. Если так, то сама возможность победы в Го обусловлена неполнотой графа. Доказать правильность этой гипотезы в общем виде мне пока не удалось, но не удалось и придумать опровергающего её примера.

Если среди моих читателей найдется кто-то, кого серьезно заинтересовали эти проблемы, могу рекомендовать для дальнейшего чтения исследование http://erikvanderwerf.tengen.nl/pubdown/solving_go_on_small_boards.pdf

Tags: го, математика

deep_econom

June 18 2018, 10:50:29 UTC 1 year ago

Collapse
Expand
New comment

*****И вот, оказывается, что ТАКОЙ интеллектуальной мощи человек противостоять неспособен. В тот день, когда я осознал это, мой мир изменился. Я поверил в роботов и приготовился к тому, что спустя некоторое время они овладеют всеми человеческими профессиями. Надежды больше нет. Я увидел чемпиона мира по Го побежденным железякой, и осознал, что дивный новый мир уже наступил.

как ни странно, эта железка такой же тупой и осталась ни смотря на выигрыш в го )

jambojet

June 18 2018, 13:26:12 UTC 1 year ago

Collapse
Expand
New comment

Точне не тупой, а "надроченной на выполнение одного трюка".

Есть назвать ИИ правильно, "сверхсложный алгоритм", пусть и созданный машинным методом, то он звучит гораздо менее круто.
Под такое инвестиций не получишь!

deep_econom

June 18 2018, 14:25:23 UTC 1 year ago

Collapse
Expand
New comment

*** "надроченной на выполнение одного трюка".

можно и так сказать

palaman

June 18 2018, 18:18:40 UTC 1 year ago

Collapse
Expand
New comment

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

Я не верю в "искусственный разум". Разум и интеллект - это две разные вещи. Но чтобы править миром, достаточно и одного интеллекта.

a_konst

June 18 2018, 11:36:26 UTC 1 year ago

Collapse
Expand
New comment

По Вашему посту естественно возникают два вопроса о противостоянии человека с ИИ в Го:
1) каково это будет на еще бОльшей доске? Может, даже современной мощи ИИ не хватит на доску 25x25, а для человека (мастера) такой огромной разницы не будет, и человек обратно выиграет?

2) как изменится сама игра, и уровень в ней ИИ, если склеить края, сделать топологически тор?

В свое время я написал сапера на торе - обычный с краями был уже очень скушен. И это оказалось очень занятно.

Log in

Го и Пустота

О!

Только целое

Select pictures (pictures will be 640 pixels wide)