Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?


    Реми Кулом (слева) с компьютерной программой 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.

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

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

    Обидное поражение Crazy Stone потерпела в самой концовке. Выигрывая 11 камней, любой человек сделал бы несколько очевидных защитных ходов, чтобы не дать противнику отыграться и сохранить преимущество. Но Crazy Stone была запрограммирована только на победу. Поэтому её алгоритм состоял в том, чтобы в ситуации выигрыша делать бессмысленные ходы в собственной зоне, ожидая, когда соперник признает поражение. Но здесь такой фокус не прошёл — и Ёда сумел отыграться. Во втором матче против Zen он уже выглядел получше и выиграл у программы четыре камня.



    Реми Кулэм всё равно был счастлив — и пообещал к следующему чемпионату доработать алгоритм действий в концовке.

    Судя по всему, скоро компьютер выиграет в последнюю игру с полной информацией, которая пока остаётся за человеком. По оценке Кулома, программа выиграет без форы в течение 10 лет. Эксперты, знающие силу лучших игроков, не так уверены. Дело в том, что на высших уровнях игра выходит на качественно иной уровень, ходы перестают быть предсказуемыми. В то же время качество игры программ до сих пор полагается не столько на вычислительную мощь, сколько на качество кода: например, те же Crazy Stone и Zen на 64-ядерных стандартных серверах легко побеждали 2048-ядерные кластеры противников. То есть программы могут снова уткнуться в стену.

    Но даже если компьютеры и выиграют в го, нельзя говорить о «падении последнего интеллектуального бастиона», где доминирует человек, как это писали газеты после победы Deep Blue в шахматах. Программы для го — это просто узкоспециализированные инструменты для решения конкретных задач. Они весьма далеки от человеческого разума и не пытаются эмулировать работу мозга. «Для меня это просто развлечение, — говорит Кулом, — не более того».
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 232
    • +57
      Ходов в го постигнуть суть компьютерам не дано.
      • +34
        Программу писать Форте на если а?
        • НЛО прилетело и опубликовало эту надпись здесь
        • +2
          Мне одному кажется очевидным обратное?

          Что игра, в которой ветвление и разнообразие ходов столь велики, должна современным компьютерам с почти неограниченными вычислительнмыи мощностями даваться гораздо легче, чем человеку?
          • +5
            да вот и я об этом подумал сперва: что при супер вычислениях, все будет по плечу, но потом подумал еще и о том, что вероятно есть какие-то стратегические аспекты… аля человек будет сразу на двух частях доски игру вести… ну или пытаться как то запутать, делая не перспективные ходы, которые остались вне рамок дерева ходов машины(я фантазирую) т.е. машину нужно будет именно научить играть, а не рассказать правила и заставлять просчитывать ходы.

            В статье так и сказано «доработать алгоритм действий в концовке» — т.е. «научить» стратегии.
            • +3
              В статье так и сказано «доработать алгоритм действий в концовке» — т.е. «научить» стратегии.

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

              Чесно говоря я не понимаю важности всех этих «прорывов компьютерной техники» — компьютер не становится умнее или как то лучше — тот же самый процессор с тем же самым набором инструкций, просто человек составил грамотный алгоритм который позволяет делать верные решения в рамках одной единственной игры. Этот алгоритм можно установить на любой компьютер, переписать, изменить — к ИИ это не имеет никакого отношения, просто грамотный набор if/else. Так что не понимаю этого трепета перед победами/поражениями компьютера — просто человек который написал алгоритм не предусмотрел или наоборот — предусмотрел все варианты, и все. Никакого чуда или прорыва в рамках развития ИИ или компьютерной _техники_ здесь нет и быть не может.
              • 0
                А разве алгоритмы не могут считаться прорывом, пусть не именно в «компьютерной технике», но в Computer Sciense в целом?
                • –5
                  Любой алгоритм сам по себе — банальный набор предельно простых инструкций. Ценность представляет только его содержание. В данном случае содержание алгоритма 100% заточено под решение абсолютно частной задачи — выиграть у человека в го. Является ли прорывом в computer science алгоритм который умеет исключительно выигрывать в го и никаким образом не применим к другим задачам (а судя по тому как автор написал о подкручивании действий в конце игры — так оно и есть). Мне кажется нет.

                  Конечно возможно что в нем будут уникальные элементы применимые в обычном программировании, но судя по тому что я вижу все скорее наоборот — это применение всем известных принципов и алгоритмов в программе которая умеет играть в го.
                  • +5
                    Скажем, Monte Carlo Tree Search, о котором идет речь в статье, вряд ли чрезмерно заточенная под го штука.

                    Да и Quick Sort, например, по вашей логике, тоже никаким достижением CS не является, т.к. его содержание — сортировка массивов — совсем неуникальна и решается тем же очевидным Bubble Sort, да и вообще представляет собой «банальный набор предельно простых инструкций».

                    Есть инженерные задачи — скомбинировать известное для получения результата, а есть научные, где для достижения цели требуется создать что-то новое. И, судя по статье, научить компы играть в го — это задача именно научная, требующая разработки новых подходов.
                    • 0
                      Борьба в основном идет за время анализа, ведь по прежнему остается возможным простой как пробка алгоритм — перебор всех вариантов, но он понимаешь ли не устраивает по времени выполнения чуть меньшее чем бесконенчость.
                      • 0
                        Не спорю. Но время анализа можно уменьшить, только применяя новые алгоритмические решения.
                • 0
                  Вот-вот. Компьютерная программа — это знания программиста, записанные им в алгоритм. Программист как бы пишет последовательность действий, как если бы он сам выполнял шаги решения задачи (с условиями). Но почему эти условия и действия именно такие, в алгоритме не поясняется. Разве что в комментариях — для себя и для других программистов.
                  Подходя к обучению компьютера через «программирование», мы не даем компьютеру шансов почувствовать смысл.
                  • +2
                    Какое-то неправильное понятие у вас программирования. Программист не решает задачи, он объясняет компьютеру как их решить. Все ухищрения направлены на минимизацию количества используемых ресурсов(время исполнения и точность решения тоже являются ресурсами) на решение задачи — вот это цель работы программиста.
                    • +1
                      При обучении человека, если мы хотим, чтобы обучаемый понял смысл, мы говорим:
                      1. в случае (условие)
                      2. сделай (действие)
                      3. потому что (объяснение)
                      В компьютерной программе третьего пункта нет. Только условия и действия. Поэтому я бы не сказал, что программист при программировании что-то объясняет.
                      • 0
                        часто этим «потому что» вы вносите человеку элемент случайности, так как в зависимости от нештатной ситуации понять как сработает такое условие невозможно, оно основывается на опыте конкретного человека, его заблуждениях, предпочтениях, страхах… Поэтому 3-я приписка лишняя для человека действующего по инструкции.
                        В реальности, для программы, 3-й пункт просто дополняет условие системой более сложных условий, и не просто условий а часто и условий с обратными связями во времени.
                        • 0
                          Конечно же, инструкции для человека часто пишутся без 3-го пункта (без объяснений почему) – рецепты приготовления блюд, инструкции к бытовой технике, как оказать первую медицинскую помощь – примеров можно привести много. Здесь нужны четкие инструкции, и объяснения будут только мешать.

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

                          Теперь вернемся к программированию. Программист узнал, что его программе будет противостоять любитель ферзей. Программист не может объяснить компьютеру, что противник любит играть ферзем. Вместо этого он пишет в программе «если ферзи под боем, нужно делать размен ферзей». Если бы вам как человеку дали такой совет, у вас бы возникло желание как минимум разобраться в причине такого совета – а зачем делать размен ферзей?
                          У компьютера же архитектура проста – выполнять инструкции программиста. А вот если бы компьютер по базе данных фактов об окружающем мире, заложенных людьми и на основе собственного опыта, сам себе составлял бы алгоритмы, возможно, мы бы имели более сильного игрока в го.
                          • 0
                            Сдается мне, вы просто пропускаете промежуточные звенья.

                            Вы берете зонт потому, что когда-то получили следующую информацию:

                            1. Ущерба надо избегать.
                            2. Дождь может нанести ущерб.
                            3. Зонт помогает от дождя.
                            4. В доме есть зонт.
                            5. Перед выходом нужно думать, что из находящегося дома поможет действовать после выхода с максимальной эффективностью.

                            (Это если в упрощенном виде).
                            Если добавить к этому

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

                            Занудствовать и приводить развернутый пример для ферзя не буду — принцип, как вы понимаете, тот же.
                            • 0
                              В прикладных программах никто не программирует полный логический вывод.
                              Причина в том, что для доказательства 2+2=4 из аксиом элементарной арифметики требуется пара десятков логических выводов. А для нахождения доказательства (в общем случае, не заточенном на доказательстве верности сложений) обширный поиск с экспоненциальным взрывом возможностей, какие аксиомы в каком порядке применить.

                              Гораздо проще закодить правило «если игрок действовал так — иди на размен ферзя», чем закодить общую возможность прийти к такому выводу, потратив гигантское кол-во машинных ресурсов. Кроме одного этого вывода, программе нужно успеть сделать массу других.
                              • 0
                                Вы говорите немного о другом.

                                Я хотел сказать, что большинство разумных поступков человека не так нелинейны, как кажется на первый взгляд.
                              • 0
                                Дело не в количестве информации, а в том, как ее обрабатывать.

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

                                Но вот новая нестандартная ситуация:
                                4.1. Тот зонт, который в доме – дырявый.
                                4.2. Дырявый зонт не помогает от дождя.
                                4.3. Зонт можно попросить у соседа.
                                И робота опять нужно тащить на перепрошивку.

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

                                В го, вероятно, много нестандартных ситуаций, и их все так быстро не запрограммируешь (если это в вообще возможно). Чтобы обыграть человека, нужно строить алгоритм «на лету», как это делает человек. Переборы ходов, как в шахматах, здесь уже не прокатывают.
                                • 0
                                  Мне кажется прокатывают, просто нужно правильно перебирать. По крайней мере на уровне игроков ~5 дана игра выглядит как конкуренция нескольких (обычно 5-6) групп и игроки внимательно следят за двумя свойствами этих групп: может ли противник их разделить и можно ли построить два глаза. Дальше каждый применяет хитрые трюки (тесуджи) чтобы как то повлиять на эти два свойства. Хитрые трюки, в свою очередь, это перебор интересных ходов в уме. Сложность в том как определить эту интересность и как видеть эти два свойства групп. На уровне 9-го дана наверно всё меняется: во всяком случае когда я смотрю некоторые записи на гокифу, я поражаюсь как группы камней разделяются и сливаются без нарушения баланса на доске (обычно ведь после потери любой группы сдаются).
                          • –2
                            Все достижения в области искусственного интеллекта прошли мимо Вас? Больше чем пол века назад разработали первую модель обучающейся сети. Википедия.
                            • 0
                              Извините, но эти «достижения», мягко говоря, не дотягивают до интеллекта. ИНС – это жалкие попытки моделирования работы нейронов, как если бы обезьяны нашли набор радиолюбителя и пытались сделать радиоприемник, не разобравшись в назначении деталей.
                              Где результат исследования моделей сетей? Почему мы продолжаем программировать большинство приложений, тупо вводя инструкции? Вот пример из статьи:
                              Поэтому её алгоритм состоял в том, чтобы в ситуации выигрыша делать бессмысленные ходы в собственной зоне, ожидая, когда соперник признает поражение.
                              Зачем вообще разработчик размещает какой-то алгоритм? Архитектура машины с достижениями в области искусственного интеллекта должна сама выработать подходящий под сложившиеся условия алгоритм.
                              И дальше.
                              Реми Кулэм всё равно был счастлив — и пообещал к следующему чемпионату доработать алгоритм действий в концовке.
                              Машина, проиграв, так ничему и не научилась. А вот разработчик получил некоторый опыт, который пообещал заложить в виде инструкций к следующему разу. Почему он не пользуется обучающейся сетью, а пишет алгоритм? А потому что применение сетей очень ограничено то ли из-за того, что мы их неправильно моделируем, то ли применять не научились.
                            • 0
                              должен заметить, что у большинства преподавателей постсоветских ВУЗов третий пункт тоже часто не входит в процесс обучения. Даже печально
                        • 0
                          Чтобы работали if/else нужно им грамотно условия составлять! Вот в этом-то и суть программ подобного рода — в условиях подставленных в if/else. Программа на данном этапе может определить лишь перспективность хода что является аналогом указания точного направления в виде неопределенного взмаха рукой(а куда-то туда) и не гарантирует победы вообще. Пока программы позволяют только не оплошаться с первых ходов сделав изначально невыгодные ходы.
                          Но человек хитер… сделав невыгодный ход он в итоге может победить…
                      • +5
                        Тоже засомневался. Вероятно человек играет, оценивая ситуацию сложным нечётким алгоритмом, который пока не удалось хорошо формализовать, не просчитывая множество возможных вариантов. Возможно даже на уровне интуиции — происходит распознавание хороших и не очень позиций на основе опыта игры.
                        • 0
                          Игра Го не сильно поддаётся явным алгоритмам.
                          Художники в неё играют порой лучше, чем математики.
                          • +5
                            Думаю, что дело не в невнятной фигне «художники лучше математиков» и прочей эзотерической ереси типа «поэзия битвы», а просто в том, что в шахматы играет очень много людей и на шахматных турнирах разыгрываются миллионы долларов, а по го только десятки тысяч, да и то в Китае.
                            • +10
                              Я больше одного раза слышал, что опытные игроки оценивают позицию визуально, распознавая в виде визуальных образов знакомые паттерны. Я почти не умею играть в Го, но даже будучи знакомым поверхностно с игрой, мне это звучит вполне логично.
                              • +1
                                В го играют в основном в японии, а не Китае, енсмотря на историческое происхождение игры. Кроме того играют в нее и в Корее.
                                Что в го особенно приятно, так это простота правил и сложность стратегии. Удивительный баланс. Скажем, есть игры, которые может и сложнее го, но вот как-то люди в них не играют. Например: en.wikipedia.org/wiki/Ko_shogi
                                • –2
                                  В точках еще проще правила, а стратегия тоже сложная.
                                • +6
                                  Я смотрю, идея с объяснением отсутствия вирусов под линукс универсальна.
                                  К примеру, можно заменить «вирус» на «алгоритм», «linux» на «го», а «windows» на шахматы.
                                  • +4
                                    Вы серьезно заблуждаетесь. Вы много видели институтов шахмат? А в Японии есть самые настоящие институты Го, со вступительными екзаменами, серьезным отбором и суровыми выпускными екзаменами. Профи — обладатели титулов живут на государственную стипендию, и очень даже не бедствуют.
                                    А учитывая размер Китая, то очень даже может быть что игроков в Го в разы больше игроков в шахматы.
                                    • 0
                                      Это всего лишь одна Япония.

                                      Что бы заниматься обучением компьютера игре в Го, надо что бы это достижение можно было продать не одной лишь Японии, а Америке + Европе.
                                      • 0
                                        Ну в СССР шахматы тоже были на господдержке, лучшие гроссмейстеры так же далеко не бедствовали.
                                      • +4
                                        …на шахматных турнирах разыгрываются миллионы долларов, а по го только десятки тысяч, да и то в Китае

                                        Простите, вы вообще в теме ориентируетесь, чтобы такие утверждения давать?

                                        Существующие титулы

                                        Кубок Инга — турнир организованный Ином Чанци — основателем Фонда Инга, изданием Yomiuri Shimbun, Нихон Киин и Кансай Киин. Соревнования проводятся каждые 4 года. Главный приз составляет $500000. В розгрыше кубка участвуют 24 профессиональных игрока из четырёх стран: Кореи, Китая, Тайваня и Японии по олимпийской системе (на выбывание). Последним обладателем кубка (2008) является Чхве Чхоль Хан.

                                        BC Card Cup World Baduk Championship — турнир, организованный BC Card. Соревнования проводятся каждый год. Главный приз составляет $300000. Текущий победитель (2010) — Ли Седол.

                                        Кубок LG — турнир, спонсируемый LG Group. Сумма главного приза составляет $250000. Текущий обладатель кубка (2011) — Пяо Вэньяо.

                                        Кубок Samsung — турнир, спонсируемый Samsung Fire & Marine Insurance (подразделением Samsung Group) и Корейской ассоциацией бадук. Сумма главного приза составляет $250000. Текущий обладатель кубка (2010) — Гу Ли.

                                        Кубок Chunlan — турнир, спонсируемый Chunlan Group и проводящийся каждые два года. Сумма главного приза составляет $170000. Текущий обладатель кубка (2011) — Ли Седол.

                                        Кубок Fujitsu — турнир, спонсируемый Fujitsu и Yomiuri Shimbun. Сумма главного приза — $141000. Участники турнира отбираются по следующему принципу: 3 игрока, занявшие три призовых места в турнире прошлого года; 7 игроков из Японии, 5 игроков из Китая, 4 игрока из Южной Кореи, 2 игрока из Тайваня, 1 игрок из Северной Америки, 1 игрок из Южной Америки, 1 игрок из Европы. 24 игрока сначала играют предварительный турнир. Затем играется основной турнир, по системе плей-офф (на выбывание). 8 игроков с лучшими результатами в предварительном турнире переходят сразу во второй тур основного, а остальные 16 играют в первом туре. Текущий обладатель титула (2010) — Кун Цзе.

                                        Плюс к тому, го в азиатских странах очень популярно. Выходят регулярные издания, матчи транслируются и активно обсуждаются. Количество клубов в одной только японии достигает нескольких тысяч.
                                    • 0
                                      Да, называется такой алгоритм «если не знаю что делать надо тыкнуть пальцем в небо и будь что будет».
                                    • +4
                                      Так там сложность перебора растёт по экспоненте. В шахматах ещё не так страшно, число ходов возможных поменьше. Человек же при выборе хода перебор не использует.
                                      • +2
                                        Человек в некотором смысле наверное использует перебор. Очевидно, что игроки строят неполное дерево на ближайший ход- два…
                                        • +2
                                          Вы ошибаетесь. Даже любитель с уровнем 10 кю способен видеть партию не меньше чем на 8-10 ходов вперед. Профессионалы оценивают партию до конца, а это может быть еще сотня ходов.

                                          P.S.: Мне есть с чем сравнивать.
                                          • +45
                                            Оценивают партию до конца? Но Холмс, откуда у них столько оперативки?
                                            • 0
                                              Учатся с 9 лет в специализированных школах, с очень жестоким отбором доходят до экзаменов, сертификат про получают гении, единицы из сотен и даже тысяч учеников.

                                              Ватсон, они не только просчитывают до конца, большинство успешных профессионалов помнят все рейтинговые партии, которые сыграли в жизни.
                                              • +5
                                                Запомнить сыгранную партию как раз гораздо легче, чем просчитать 250^200 вариантов развития партии. 200 ходов — это примерно с десяток четверостиший по объёму.
                                                • +1
                                                  Человек — не компьютер, он не перебирает наугад, а видит, как просчитывать правильно. Это не 250^200 вариантов, но тоже солидный объём, требующий усилий.

                                                  В ёсе и тюбане человеку просчитать игру достаточно просто. Профи уже знают исход игры с погрешностью до 1 очка за сотню ходов до конца.
                                                  • 0
                                                    Полагаю тут подразумевалось, что «про» в игре с любителем, после нескольких ходов понимает противника и ведет игру к логическому заключению. В этом случае действительно не так сложно просчитать игру до конца.
                                                    • +3
                                                      Нет, подразумевается «про» против «про». Поэтому сдаться до конца игры считается более благородным, чем терпеть до конца.
                                                    • +5
                                                      Десяток четверостиший?
                                                      Очевидно, вы не играли в Го.
                                                      Напомню вам, что поле 19на19.
                                                      Я запоминаю свои десятизначные сгенерированные пароли и держу в уме постоянно около 10ти. Имею 11 кю на ГоКГС сервере. В течении двух недель каждый день просматривал и пытался запомнить матч века Сюсаи против Сэйгена, до 50-го хода ещё легко повторить, но осилил лишь до 100-го с ошибками. В партии было 252 хода. Это просто мой личный пример, стихи в школе сдавал на 5.
                                                      • +1
                                                        А при чем здесь ваши «кю» и пароли?
                                                        Я лишь только констатировал факт, что 200 ходов на доске 19х19 содержат примерно столько же информации, сколько десять четверостиший.
                                                        Другое дело, что запоминать стихи обычному человеку гораздо проще.
                                                        Сопоставьте каждой из 361 позиции на доске какое-то слово по какому-то правилу, составьте из них стихотворение или просто рассказ — и запоминайте его, а не сложную последовательность типа «e2, e4»
                                                        • +20
                                                          Я лишь привёл свой пример.

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

                                                          И констатирую факт я, а вы лишь предположение, вы же не играли в Го.

                                                          К сожалению очень странная тенденция, мы с Halt имеем представление о игре, но нас минисуют за высказывания простых (может непонятных что ли) истин, а троллей, незнакомых с игрой, плюсуют.
                                                          • +11
                                                            А мне кажется, что вы очень странно играете в го. 11 кю это неплохо, конечно, но рейтинг на КГС это еще не все. Ваши слова о том, что профессионал за сотню ходов до конца игры знает результат с погрешностью до очка звучит абсолютно глупо и говорит о том, что вы сами слабо представляете себе оценку позиции на доске. Посчитать сотню ходов наперёд невозможно, даже зная своего соперника, как облупленного и играя с ним уже далеко не первую партию. В ёсе, не говоря уже о фусеки, существует огромный простор для фантазии и непредсказуемых ходов, которые никак нельзя было предусмотреть и просчитать. Профессионалы лишь на невероятно глубоком уровне анализируют выживаемость групп и количество очков, которые может принести жизнь той или иной группы или ход в конкретный пункт доски. А сдаются профессионалы не потому что просчитали всю партию до последнего хода, а в тех случаях, когда полученный ущерб перевешивает все доступные для получения очки, то есть когда свести ёсе к близкому результату и побороться в тюбане просто нет шансов.
                                                            Зачем вы пытались наизусть запомнить матч Сюсаи и Сейгена — я просто не могу понять. Это то же самое, что пытаться научиться играть в футбол, как Пеле, просматривая видеозаписи его игр и пытаясь повторять движения. Пока вы не проанализируете каждый конкретный ход и не попытаетесь понять, какая идея зрела в голове у игрока, когда он ставил на доску камень — толку не будет.
                                                            • +1
                                                              Для анализа и пытался запомнить, лишь как эксперимент. И как раз в этой игре есть хороший пример просчёта партии.

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

                                                              Непредсказуемость есть всегда, в этом и суть, когда ты просчитал плохой ход соперника, а он его сделал, но ты понимаешь, что он сделал это осознанно, и далее тебе предвидеть его игру сложней, и скорее всего, именно поэтому он и сделал этот ход, чтобы запутать.
                                                              • +1
                                                                Почему Вы решили, что математик «считает», а не «видит»?
                                                                • 0
                                                                  Решил по активированным полушариям.
                                                    • +10
                                                      Партии запоминаются ассоциативно. Это не просто набор коррдинат камней.
                                                    • +30
                                                      Дело не в оперативке а в анализе. Подобно тому, как в шахматах есть варианты розыгрыша в дебюте, миттельшпиле и эндшпиле, в го существует огромное количество разобранных тактических и стратегических решений. Есть базовые начала партии — фусэки. Есть тактические — джосэки — розыгрыши на захват, освобождение и соединение камней, выживания в углу и передел влияния. По каждой из тем написаны стопки книг. Это сотни и сотни позиций, которые игрок разбирает и анализирует в разное время. Типичная фусэки может занимать порядка 15 ходов, джосэки в зависимости от сложности от 3 до пары десятков. Каждый ход в такой цепочке оптимален и как правило известен обоим игрокам. Поэтому даже мне, со своим 10 кю, хватает мозгов следить за партиями, скажем Тё Тикуна (конечно «следить» далеко не значит «понимать полностью»). Сложности начинаются на склейке и адаптации вариантов.

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

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

                                                      Хочу обратить еще внимание на то, что типичная разница по очкам в конце это 0,5 — 5,5 очков. Хотя один неверный ход может стоить 12-20 очков. Вот и думайте, откуда оперативка.

                                                      P.S.: Господам минусующим советую хотя бы немного познакомиться с игрой, прежде чем делать выводы.
                                                    • +2
                                                      Конечно это не так, если просто подсчитать, сколько человек перебирает ходов в секунду, то количество будет удручающе малым и полный перебор даже на несколько ходов в глубину займет уйму времени. Но если в го верна аналогия с шахматами — я думаю человек пользуется реперными точками и паттернами, которые он узнает по предыдущему опыту (особенно вначале, когда разыгрываются гамбиты). Это можно считать интуицией.
                                                      • +1
                                                        >> Профессионалы оценивают партию до конца, а это может быть еще сотня ходов.

                                                        Что-то мне кажется, вы сильно преувеличиваете. Я, конечно, не играл никогда в го, но шахматах опыт у меня очень большой. И могу с уверенностью зуб дать на то, что никакой супер чемпион чемпионов чемпионов чемпионов по шахматам никогда не посчитает позицию не то что на 100, даже на 30 ходов. А на практике посчитать даже на 10 ходов со всеми адекватными разветвлениями — это очень круто. Не говоря уже о том, что никто никогда за реальной партией с часами не будет такого делать, потому что времени банально не хватит.

                                                        >> даже на 30 ходов

                                                        Тут, конечно, с оговоркой, что позиция не стоит специфическая. А так, с лишней ладьей, и я могу сказать, что у меня выиграно во всех вариантах на 100 ходов вперед.
                                                        • +2
                                                          Не забывайте, что в шахматах фигуры двигаются, а в го нет. В го проще держать картинку, набрасывая на нее виртуальные камни. Плюс, в го очень сильно работает правое полушарие. Анализ ведется как количественно (подсчет очков, разбор позиции) так и качественно (беглый анализ, визуальное определение слабых мест). Профессиональные игроки прокачивают именно аппаратное ускорение правого полушария.

                                                          В шахматах вам приходится помнить именно что дерево вариантов, со всеми возможными хитрыми «ходами конем» и дальним действием фигур. В го 5-10 ходов тэсудзи — это небольшой пятачок на доске. Держать в уме приходится несколько иные вещи: условия жизни групп, слабые места в форме противника, возможные ответы при определенных ходах, ну и, конечно, области, где можно сыграть ко.

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

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

                                                          Го игра довольно сложная для восприятия неподготовленным человеком, поэтому и мои утверждения кажутся неправдоподобными. Тут нет ничего удивительного. Мне самому пришлось потратить два года только на то, чтобы начать адекватно чувствовать игру и ориентироваться в пространстве большой доски.
                                                          • 0
                                                            И все-таки непонятно, как можно оценивать позицию на 100 ходов вперед (судя по этому треду партии в го длятся до 200 с лишних ходов, т.е. получается почти на 50% партии). Если так легко оценить позицию до конца партии, может тогда и смысла нет играть дальше 80-100 хода? Видишь, что не выиграно, сразу на ничью согласился.

                                                            Все, что вы написали, безусловно применимо и к шахматам. Никто не считает на каждом ходу горы вариантов. Точно так же во многих позициях есть свои методики разыгрывания. Если я вижу, что у противника после некоторого хода образуется очень слабая пешка, и сразу не видно, как он может это компенсировать, я просто шлепаю, а конкретные варианты потом считать буду, в любом случае у меня будет не хуже. Некоторые позиции вообще «руками» играются чисто на понимании. Но даже этого недостаточно, чтобы вот так однозначно сказать, что через 20-30 ходов партия закончится в мою пользу.
                                                            • +2
                                                              Ну во-первых, я не утверждаю, что всегда и во всех партиях игроки могут просчитать варианты до последнего хода. Я просто говорю, что это не является физически невозможным.

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

                                                              В-третьих, действительно, многие партии заканчиваются примерно в середине игры. Например, описанная в википедии партия Го Сейгена и Китани Минору:

                                                              image

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

                                                              Если подобный рассчет не был бы возможен, игрокам очень редко удавалось бы заканчивать игру с разницей меньше 6 очков. Но тем не менее это считается нормой. В каждый момент времени игрок точно знает, на сколько очков он опережает/опаздывает и сколько очков может принести тот или иной ход. Существенная часть тактики и стратегии в конце игры посвящена этому подсчету и соответствующим трюкам.
                                                              • 0
                                                                Прошу прощения, форовые очки даются белым. Заболтался :)
                                                    • 0
                                                      Так и есть. В шахматах движки используют базы дебютов, которые уже просчитаны достаточно далеко. На долю алгоритма приходится миттельшпиль и эндшпиль, когда вариантов ходов не так много. А в го скорее визуальное восприятие паттернов.

                                                      Интересно как получится играть у многослойной нейронной сети которую обучать на партиях го. По нейрону на клеточку. Связи для обработки сдвигов и поворотов паттерна.
                                                      • +1
                                                        Мне кажется, что эффективность НС для такой задачи будет близка к эффективности НС на задаче получения строки по ее md5-хешу.
                                                        • 0
                                                          Может кто-нибудь вдохновится этим постом и начнет писать свою нейронную сеть для игры в ГО. :) Без предмета обсуждения трудно что-то предсказывать.
                                                          • +1
                                                            Прежде чем о чем-то писать, нужно это изучить хотя бы немного. Работы по нейросетям применительно к игре «го» есть. Вот например: Co-Evolving a Go-Playing Neural Network. Также рекомендую ознакомиться со статьей в википедии: Computer Go.
                                                    • +24
                                                      Это кажется. Представьте себе фотографию, на которой изображен лес. Сколько времени нужно человеку, чтобы понять, что изображен именно лес? Это практически моментальное осознание. А вот алгоритм, распознающий лес на фотографии — совсем другая история. В го то же самое. Возможность целостного осознания на полуинтуитивном уровне происходящего на доске ценнее возможности просчитать миллиард комбинаций, которые ни к чему не приведут.
                                                      • –7
                                                        При чем тут компьютерное зрение?

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

                                                        Во времена Deep Blue читал, что шахматный гроссмейстер просчитывает два хода в секунду. Компьютер же может просчитывать тысячу, миллион, миллиард ходов в секунду — верхнего потолка нет (покуда он не введен регламентом турнира).

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

                                                        Так что, возможно, дело в качестве алгоритмов. И когда появится гроссмейстер го, который одновременно является талантливым программистом, ситуация изменится.
                                                        • +7
                                                          А чем Вам доска не пиксели?
                                                          Смысл в том, что распознавание ситуаций — дело сложное для компутера, но легкое для человека. У него же куча нейрончиков, которые работают параллельно. Возможно, можно добиться успеха, используя нейросети. Но это уже не алгоритм, а подражание человеку, и говорить о победе компьютера будет уже не так легко.
                                                          • –32
                                                            А чем Вам доска не пиксели?

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

                                                            UPD: Интересы: 3d графика, котики, программирование. Дизайнер, все понятно.
                                                            • +2
                                                              Я помню, как начиналось GPGPU. Тогда были только пиксельные шейдеры, данные загружались в текстуру и снимались с видеопамяти.
                                                              Только потом появился человеческий интерфейс, подразумевающий, что мы обрабатываем не пиксели, а любые четырёхмерные вектора.

                                                              И ещё, на Хабре была статья, описывающая симуляцию игры жизнь в терминах свёртки (фильтров к изображениям). Так что, если поднапрячь воображение, наверное можно уловить связь зрения с играми на дискретной доске.
                                                              • +14
                                                                >Дизайнер, все понятно.
                                                                А еще там есть такая очень неприметная прям ссылочка ни гитхабчик.

                                                                >Разница настолько принципиальная
                                                                Ну давай, разъясни мне глупенькому, что тут за разница такая. Я вижу в обоих случаях матрицу, каждый элемент матрицы имеет какое-то значение. В случае с картинкой могут быть варианты от ч/б до полноцветной, а в Го, как я понял, могут быть три значения: Ч, Б и Пусто. Не вижу никаких препятствий для оценки позиции с помощью нейросети.
                                                                Должен сказать, что я не говорю вовсе о нахождении контуров, препроцессинге, нахождении фич и прочей АЛГОРИТМИЧЕСКОЙ лабуде, которая сейчас используется в КЗ, ибо ПЭВМ наши пока только такое потянут. Я говорю исключительно о нейросетях.
                                                                • –1
                                                                  Контуры для го разве неважны?
                                                                  • +2
                                                                    Понятия не имею. Да это и не важно, нейросеть сама разберется.
                                                                  • +7
                                                                    А еще там есть такая очень неприметная прям ссылочка ни гитхабчик.

                                                                    Посмотрел еще раз, не нашел. Извините.

                                                                    давай, разъясни мне глупенькому, что тут за разница такая. Я вижу в обоих случаях матрицу, каждый элемент матрицы имеет какое-то значение. В случае с картинкой могут быть варианты от ч/б до полноцветной, а в Го, как я понял, могут быть три значения: Ч, Б и Пусто. Не вижу никаких препятствий для оценки позиции с помощью нейросети.

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

                                                                    Распознавание изображений — поиск приближенного сходства в месиве пикселов. В го же изенение положения (или наличия/отсутствия) хотя бы одного камня может привести к кардинальной смене ситуации на доске. В компьютерном зрении картинка изначально сырая — неизвестно, что на ней изображено — и задача сводится к ее усвоению. В го позиция на доске изначально оцифрована с абсолютной точностью, и поиск соответствий по базе фрагментов является тривиальной задачей.
                                                                    • +1
                                                                      >Посмотрел еще раз, не нашел. Извините.
                                                                      Действительно, её вижу только я почему-то. Может из-за кармы.

                                                                      >Можно шариковой ручкой написать любовное письмо, а можно медицинскую справку. Но это не значит, что опыт по составлению медицинских справок поможет вам признаться в любви.
                                                                      Он как минимум мне пригодится навыком письма. Да, может получиться неразборчиво, но сейчас нам это не важно :)
                                                                      Но если я писал справки, я смогу научиться и письма писать. Мне для этого голову менять не надо. Конечно я не предлагаю взять нейросеть, которая всю жизнь картинки смотрела и сказать ей — давай-ка играй в Го. Надо ее перетренировать как минимум, а то и добавить слойцов.

                                                                      >Распознавание изображений — поиск приближенного сходства в месиве пикселов.
                                                                      Мне это определения не совсем понятно. Поиск сходства между парой массивов (если я правильно понял) — это не есть распознавание, это обнаружение корреляций, и решается вполне неплохо без нейросетей. Не для того неокогнитроны придумывали. Задача распознавания — это задача классификации. Т.е. есть некоторый набор входов, а на выходе надо сказать, что это такое. Это намного сложнее, чем сопоставить два массива. Распознавание изображений — это лишь частный случай распознавания образов. А образом может быть что угодно, об этом даже Википедия говорит ru.wikipedia.org/wiki/Теория_распознавания_образов.

                                                                      В общем, моя позиция такова, что нейросети типа (нео)когнитрона или чего-то такого же нетривиального можно применять для оценки ситуации на доске. Они вполне способны позиции на доске сопоставить какую-то категорию из множества {победа, очень хорошо, хорошо, средне, плоховато, п-ц, полный п-ц}. Хотя я и затрудняюсь сказать, как их для этого обучать :)
                                                                      • +1
                                                                        Разве нейросети пригодны для задач, неустойчивых по входным данным? lolmaus как раз утверждает, что такой устойчивости в го даже близко нет:
                                                                        В го же изенение положения (или наличия/отсутствия) хотя бы одного камня может привести к кардинальной смене ситуации на доске.

                                                                        В случае с компьютерным зрением ситуация кардинально противоположная, мы и так получаем на вход сильно зашумленные данные, но на результат это особо не влияет (в идеале).
                                                                        • +1
                                                                          Хоть кто-то за меня вступился, спасибо. Ато налетели, заклевали заминусовали. :) Даже плюсануть вас уже не могу.

                                                                          В качестве примера, как один камень кардинально меняет исход партии, привожу интересный роман "Мейдзин" нобелевского лауреата Ясунари Кавабаты.
                                                                          • 0
                                                                            >Разве нейросети пригодны для задач, неустойчивых по входным данным?
                                                                            Если в сети достаточно нейронов — то вполне.

                                                                            В статье же написано:
                                                                            >Даже игроки не понимают, как они это делают: «Просто смотришь на доску и знаешь», говорят они.
                                                                            Не из Космоса же они это черпают — это именно нейросети их выдают, не задействуя логическое мышление.
                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                • 0
                                                                  >При чем тут компьютерное зрение?
                                                                  habrahabr.ru/post/140244/#comment_4691594
                                                            • +18
                                                              Вы недооцениваете экспоненту. Фактор ветвления 250, среднее кол-во ходов 200. Получаем 250^200 — кол-во комбинаций, которые надо проверить в начале игры, чтобы найти безпроигрышную стратегию, если такая вообще существует. Это число на несколько порядков больше, чем кол-во атомов во Вселенной по оценкам ученых =(
                                                              • –22
                                                                А почему бы заранее не построить всё дерево целиком? Провести предварительную градацию выигрышных и неудачных ветвей… очевидно, что некоторые ветви будут дублироваться…
                                                                • +18
                                                                  Построить все дерево целиком? Вы серьезно? Число позиций больше чем кол-во атомов в тысяче вселенных. Пока не изобретут компьютеры, способные хранить информацию на субатомном уровне, мы не можем этого сделать.
                                                                  • –8
                                                                    Ну когда-то это возможно случится =) Всё ради Го
                                                                    • +2
                                                                      Упорство, достойное религиозного фанатика. «Может быть» тут не прокатит. Возьмите для примера партию в 186 ходов Crazy Stone vs Zen: количество возможных ходов после каждого раунда — 250, следовательно, количество всех возможных ходов за партию составляет 250^186 (250 в степени 186). Вот и посчитайте, хватит ли материи во Вселенной.
                                                                      • –6
                                                                        Не понимаю, какое отношение имеет кол-во материи (кол-во чего, атомов или чего?) во Вселенной к кол-ву комбинаций? Понятное дело что в данный момент нету таких технологий хранения и обработки данных, способных построить и перебрать все дерево решений, но это не значит, что их никогда не будет.
                                                                        • +7
                                                                          Сильное взаимодействие потому и называется сильным, что для его преодоления нужно огромное количество энергии. Если во Вселенной не хватает адронов, придётся работать с кварками, что даст всего лишь в несколько раз больший выигрыш в количестве «частиц» для хранения дерева ходов. А если экономить на материи, потребуется огромное время для инкрементального построения дерева. К тому же, скорость взаимодействия материи ограничена скоростью света, так что при росте количества задействованной в расчётах материи скорость работы такого «компьютера» будет пропорционально падать.

                                                                          Короче, в подобных задачах разумнее использовать нейронные сети, эвристики, а также генетические и прочие алгоритмы, которые нацелены не на точный, а на оптимальный результат — удовлетворительный результат за небольшое время.
                                                                          • –4
                                                                            Насколько мне известно, работать с кварками не получится, потому что кварков как таковых не существует, их никто не видел — это не более чем модель. Но вы ведь не знаете что там мельче кварков. Никто пока что не знает, но это не значит что там ничего нету и это что-то невозможно будет использовать для вычислений и хранения данных.
                                                                            • +7
                                                                              К слову, электроны тоже никто не видел. А "дырки", как самостоятельные частицы, вообще не существуют. Что не мешает их использовать во всей электронике.
                                                                              • –4
                                                                                Нельзя сравнивать кварк с электроном. Электроны вполне себе осязаемые объекты. Их можно запустить из пушки и наблюдать свечение люминесцентного вещества. И при помощи этого поиграть в CS1.5 на стареньком компе с ЭЛТ монитором. С кварками такого не пройдет. Кварки это не более чем красивая модель, по крайней мере пока.
                                                                                • +4
                                                                                  Я извиняюсь за ссылку на википедию, но там пишут вот что.
                                                                                  • 0
                                                                                    Может быть ошибался насчет кварков.
                                                                              • +3
                                                                                > их никто не видел — это не более чем модель
                                                                                wrong
                                                                                ru.wikipedia.org/wiki/T-кварк
                                                                                • +1
                                                                                  Супер, спасибо за ссылку!
                                                                              • –5
                                                                                Дойч писал в том духе, что квантовая механика может помочь, т.к. квантовый компьютер будет проводить вычисление во множестве вселенных одновременно. Как-то так. За точность пересказа не ручаюсь.
                                                                                • 0
                                                                                  И за что минусы? Почитайте лучше Дэвида Дойча «Структуру реальности», там он много пишет про квантовые компьютеры и гипотезу Эверетта.
                                                                        • 0
                                                                          Да и в таком случае — а хватит ли материи?
                                                                          • +3
                                                                            Можно дождаться квантовых компьютеров.
                                                                            • –1
                                                                              Если использовать элементарные частицы, то, конечно же, материи не хватит. Но что есть материя? Ученые пока не знают что там внутри элементарных частиц.
                                                                              • +2
                                                                                Какая разница? Мы с вами живём в макромире, а для манипуляции теми же кварками нужны просто чудовищные количества энергии. И я говорю даже не об одном грамме вещества, а о миллионных долях. Законы физики не обманешь.
                                                                                • –3
                                                                                  Вы утверждаете, что существование носителей, хранящих информацию на субатомном уровне и таким образом имеющим бОльшую плотность информации чем кол-во атомов из которых они состоят, невозможно? Какие законы физики вы имеете ввиду?
                                                                                  • –3
                                                                                    Не?
                                                                                    • –3
                                                                                      Вот за что я люблю хабр. Комменты заминусованы, а в дискуссию вступать никто не хочет.
                                                                                    • +1
                                                                                      2×Δx×Δp≥ħ, например.
                                                                                      • 0
                                                                                        Как соотношение неопределенности связано с теоретическим пределом плотности носителей информации?
                                                                                        • +1
                                                                                          Во-первых, на определенной плотности возникнет вероятность произвольного перехода ячейки в другое состояние (спасибо туннельному эффекту). Во-вторых на планковской длине до одной ячейки будет уже не дотянутся (сигналы схлопнутся в черные дыры).
                                                                                          • –1
                                                                                            Вы говорите про конкретную ячейку памяти, которая построена из известных нам элементарных частиц. Но это ведь не значит, что в природе не существует других более плотных механизмов хранения информации, которые мы еще не понимаем потому что не знаем что там творится на субатомном уровне?
                                                                                            • +1
                                                                                              То, что мы знаем на текущий момент, указывает нам, что планковская длина это предел.
                                                                                              У определенного кол-ва ентропии (т.е. информации) есть вполне конкретная площадь поверхности, способная её уместить. Плотнее упаковать информацию невозможно.
                                                                                              • +1
                                                                                                Что творится на субатомном уровне — мы прекрасно знаем. Вот сублептонный и субкварковый — проблема. Но все известные явления следуют принципу неопределенности (сам принцип следует из формулировки КМ). И нет абсолютно никаких причин думать, что какие-то неизвестные элементарные частицы его нарушают.
                                                                                  • 0
                                                                                    Вы так говорите, как будто единица материи может хранить только один бит.
                                                                                    Я могу вам одной единицей материи сохранить любой объем информации, вплоть до бесконечности.
                                                                                    Так что совершенно не важно, сколько там материи во вселенной. Важно, сколько мы фактически можем хранить данных в данный момент времени.
                                                                                    • +1
                                                                                      Что такое единица материи? Как вы планируете сохранить любой объем информации в единице материи?
                                                                                      • +3
                                                                                        Ладно. Вы правы. В одну не уложусь. Мне понадобится две.
                                                                                        А информация — это расстояние между этими двумя единицами.
                                                                                        Т.к. вселенная бесконечна — расстояние может быть сколь угодно большим. А значит и число, которое мы можем хранить — может быть сколь угодно большим.

                                                                                        Вы можете заметить, что метод не имеет практической ценности. Совершенно верно.
                                                                                        Задача этого примера показать, что количество единиц используемой материи никак не корелирует с количеством хранимой информации. И высказывание в духе «мы не можем хранить определенный объем, потому что у нас не хватит материи» — совершенно бессмысленно в своей сути.
                                                                                        • 0
                                                                                          Уже почти сто лет, как физики обнаружили, что природа не поддерживает подобные трюки на хардварном уровне.
                                                                                          Вы не сможете определить расстояние между любыми двумя физическими сущностями точнее, чем планковская длина. А на практике принцип неопределенности и нехватка энергии ограничит Вас ещё на несколько десятков порядков раньше.
                                                                                          • 0
                                                                                            Я с вами согласен.
                                                                                            Гипербола позволяет точнее передать идею.
                                                                                            Я же обозначил что практической ценности у данного примера нет.
                                                                                            Его задача не предложить готовое решение, а отвязать объем от количества материи.
                                                                                            Зависимость все равно есть, мы же материю используем, но не прямая в духе «у нас 5 единиц материи, значит мы можем хранить 5 единиц информации»
                                                                                            • +1
                                                                                              Технически, зависимость именно прямая — у нас есть площать поверхности в N планковских квадратов, значит в этой площади может содержаться энтропии не больше чем N бит (и ещё коэффициент пропорциональности, не помню его сходу). Это строгий результат, полученный несколькими способами.
                                                                                              Грубо говоря — кол-во состояний наблюдаемой вселенной — не просто меньше мощности действительных чисел, и даже не просто меньше мощности множества натуральных чисел — оно вообще счётно!
                                                                                              • 0
                                                                                                Интересно было бы увидеть вычисления на эту тему.
                                                                                                • +3
                                                                                                  Гуглится по «энтропия черной дыры»
                                                                                                  В научно-популярных книгах о физике (например Браяна Грина) это тоже обсуждается.
                                                                                                  • 0
                                                                                                    Спасибо.
                                                                                                    • +3
                                                                                                      Вот это круто! Посыпаю голову пеплом
                                                                                                  • 0
                                                                                                    Технически, зависимость именно прямая — у нас есть площать поверхности в N планковских квадратов, значит в этой площади может содержаться энтропии не больше чем N бит

                                                                                                    Это в статике. Насколько я знаю, в одной единице пространства может быть сколько угодно фотонов и они между собой не взаимодействуют. Если их как-то зациклить (пустить по орбите вокруг чёрной дыры), такое облако может хранить больше информации, чем предусмотрено планковской длиной?
                                                                                                    • 0
                                                                                                      Как вы их адресовать будете?
                                                                                                      • 0
                                                                                                        Увы, неверно.
                                                                                                        Как минимум, есть ограничение на енергию — кол-во фотонов явно ограниченно сверху доступной вам енергией.
                                                                                                        Есть и множество других эффектов, например, слишком большое кол-во фотонов будет иметь массу, которая превысит предел и схлопнет область обитания Ваших фотонов в черную дыру.
                                                                                                      • +3
                                                                                                        даже не просто меньше мощности множества натуральных чисел — оно вообще счётно
                                                                                                        Множество натуральных чисел — счетно, по определению счетного множества. Счетное множество — это множество равномощное множеству натуральных чисел.
                                                                                                        • 0
                                                                                                          Я имел ввиду «конечное», прошу прощения.
                                                                                                        • 0
                                                                                                          deleted
                                                                                        • +13
                                                                                          «На несколько»? о_О
                                                                                          Юмор с большими числами состоит в том, что можно оптимизировать перебор в два, десять, миллион раз — это ничего не изменит.
                                                                                          250^200 = 10^(200 * log 250) = 10^480

                                                                                          Число элементарных частиц (даже не атомов, а именно частиц) составляет 10^80. Это, на секундочку, на 400 порядков меньше.
                                                                                          Очень некисло надо алгоритм оптимизировать, ага.
                                                                                          • –4
                                                                                            там, кажется, степень надо складывать, а не умножать. В итоге получается 250^100 = 10^202, разве нет? Но таки да, я почему-то неправильно прикинул. Почему-то решил, что 10^202 на пару порядков больше чем 10^100 =)
                                                                                            • +3
                                                                                              Нет. 250 = 10^(log 250), т.е. 250^200 = (10^(log 250))^200.
                                                                                              • +1
                                                                                                Похоже вы правы =)
                                                                                                • –1
                                                                                                  Только давайте так: lg — десятичный логарифм, ln — натуральный логарифм. А если пишете log — пишите основание логарифмирования. Я не математик, но глаза режет.
                                                                                                  • 0
                                                                                                    В разных областях науки и техники, равно как и в разных странах, разные общепринятые обозначения. Это не считая того, что изменения базы логарифмирования меняет не более чем константу.

                                                                                                    См.
                                                                                                    • 0
                                                                                                      Сами ведь ISO нотацию привели по поводу правильного написания.
                                                                                                      А на тему «не более чем константу»:
                                                                                                      «Любое число равно любому числу с точностью до целочисленного множителя» (С)
                                                                                                      Если у вас патологическое желание делать по принципу «и так сойдет» и обижаться на исправления — мое Вам нижайшее с кисточкой.
                                                                                                      • 0
                                                                                                        Если у вас патологическое желание делать по принципу «и так сойдет» и обижаться на исправления — мое Вам нижайшее с кисточкой.
                                                                                                        Учитесь различать хабрапользователей хотя бы по аватарке, если по нику не получается.

                                                                                                        Сами ведь ISO нотацию привели по поводу правильного написания.
                                                                                                        Стандартизированное написание != правильное написание. Все указанные в таблице — правильные.
                                                                                                    • +3
                                                                                                      А я математик, и мне не режет.
                                                                                              • +2
                                                                                                Похоже я тоже немного недооценил. Снизу forgotten меня поправил.
                                                                                              • 0
                                                                                                Количество возможных позиций на доске — 3^(19*19), это гораздо меньше чем 250^200.
                                                                                                • 0
                                                                                                  Если верить wolfram alpha, то количество позиций в Go ещё меньше (примерно в 40 раз):
                                                                                                  • +2
                                                                                                    Ну норм, 200 порядков скостили, осталось еще всего-то сотня порядков до кол-ва атомов в Вселенной =)
                                                                                              • –4
                                                                                                Так производительность то вообще мизерная, до сих пор пароль больше 8 символом генеренный рандомом нельзя подобрать за вменяемое время, это примерно аналогично с 8 ходами го, то есть нельзя просчитать дальше 9 ходов
                                                                                                , так ли сложно человеку просчитать на 9 ходов вперед?
                                                                                                да легко
                                                                                                • –1
                                                                                                  Человек не перебирает ходы, а вспоминает аналогичные случаи из предыдущих партий (так же и в шахматах). Поэтому ветвление влияет на кривую обучения, но не на предельное мастерство. А вычислительные мощности компьютеров очень даже ограничены.
                                                                                                  • –1
                                                                                                    Что мешает компьютерам вспоминать аналогичные случае из предыдущих партий? Лучшие шахматные программы это делают с большим успехом?

                                                                                                    Может, дело в том, что программы го этому еще не обучены?
                                                                                                    • 0
                                                                                                      Насколько я знаю, шахматные программы как раз перебирают. В шахматах перебор возможен благодаря меньшему ветвлению. Вспоминать аналогичные случаи мешает отличная от человека организация памяти.
                                                                                                      • +2
                                                                                                        Вы ошибаетесь, в шахматных программах используются оба подхода.

                                                                                                        Вот, к примеру цитаты о Houdini 3, самой сильной программой семейства Fritz (истончик):

                                                                                                        online access to the world’s largest analysis database “Let’s Check”* and the use of the ChessBase Engine Cloud.

                                                                                                        The DeepFritz 13 database management system

                                                                                                        A database with over 1.5 million games
                                                                                                    • 0
                                                                                                      Нет. Человек смотрит на доску и оценивает.
                                                                                                      Мозг принципиально заточен под то, чтобы оценивать результат операции, даже если он вообще не понимает её смысла. Каждый из нас легко оценит, где упадёт брошенный камень, не строя никаких парабол и не вспоминая гравитационную постоянную.
                                                                                                      • +9
                                                                                                        Каждый из нас легко оценит, где упадёт брошенный камень

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

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

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

                                                                                                        Ничто принципиально не мешает программистам алгоритмов игры в шахматы и го использовать аналогичные приемы. Просто это очень сложно, и брутфорс остается основным методом.
                                                                                                        • +4
                                                                                                          Ок, убедили.
                                                                                                          Пойду напишу статью, про то, что принципииально мешает программистам написать алгоритм игры в го.
                                                                                                          • 0
                                                                                                            Можно вопрос в тему? Какими понятиями оперирует человек, который способен распознать фальшь в движении персонажей, созданных при помощи компьютерной графики? Мы ведь можем определить, «достоверно» ли движется не человекоподобный робот или инопланетное существо, никогда не видев его ранее. Да, для создания анимации часто используют паттерны движения реальных живых существ, но, не всегда же. Даже один неверно анимированный жест может разрушить иллюзию достоверности. Как мы это определяем?
                                                                                                          • 0
                                                                                                            в мозгу формируется (буквально прорастает) нейронная сеть

                                                                                                            Подскажите, пожалуйста, где об этом почитать?