Фора в семь камней и соперник девятого про-дана вам о чём-то говорят? Нам тоже. Между тем речь идёт о старейшей игре в мире, ведущейся на доске. И мир взбудоражен: программы смогли побороть профессиональных игроков самого высокого уровня. За результатом, который интересен, казалось бы, только фанатам, стоит колоссальный труд в области искусственного интеллекта. Мы сдаём «кремнию»?
Китайские легенды датируют рождение го началом второго тысячелетия до нашей эры. Эта древняя игра, пожалуй, даже более сложна, чем шахматы. Уж для машинного интеллекта она определённо сложнее. Тем ярче достижение компьютерщиков.
В феврале на престижном турнире по го Taiwan Open 2009 компьютерная программа MoGo (смотрите также эту страницу) обыграла двух профессионалов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).
Девятый дан, заметим, это предел мастерства, профи высшей пробы. Учитывая фору, данную машине, можно сказать, что она выступила на уровне если не профессионала, то самого сильного любителя.
И это впечатляющее достижение. Лет пять назад программы го могли уверенно выигрывать исключительно у детишек, недавно приступивших к изучению этой мудрой стратегической игры. С обычными любителями те же программы играли на равных, ну а профессионалам машины бесславно «сливали», даже имея гандикап в 25 камней.
И ещё год-полтора назад уровень программ оставался сравнительно скромным. Несколько случаев побед машин в отдельных партиях над суперпрофи имели место при большем (чем в 2009-м) гандикапе, либо при играх на уменьшенном поле (9 х 9).
Последнее радикально снижает число возможных вариантов развития событий по ходу сражения, что упрощает задачу для компьютера. А тут сразу несколько прорывов.
В те же февральские дни 2009-го другая программа го — Many Faces — на конференции-выставке Американской ассоциации продвижения науки (AAAS meeting 2009), проведённой в Чикаго обыграла одного из сильнейших (если не сильнейшего) американских игроков в го Джеймса Кервина (James Kerwin, первый дан), хотя и опять-таки с предоставленным машине существенным гандикапом (7 камней).
Да, программы начали играть в го на несколько тысяч лет позже людей. Можно сказать, они сделали ход вторыми. Но зато у машин намного выше скорость обработки информации, чем в живом мозге. В глобальной партии разумов посчитаем это коми.
Можно констатировать: пал бастион, который долгое время считался одним из последних примеров превосходства живого разума над машинным. Пусть программы для игры в го (Computer Go, смотрите также computer-go.info) практически не уступают в длительности своей эволюции шахматным программам, многие специалисты утверждали, что в го машина никогда не победит игрока-человека, входящего в число сильнейших в данной дисциплине на планете.
Причина в том, что особенности игры (в сравнении с теми же шахматами) позволяют человеку сравнительно просто видеть очень длинные последовательности возможных ходов, выстраивая на этой основе хитроумные тактику и стратегию (а вот это уже совсем непросто). Но программа не может мыслить как человек, она механистична, а её выбор ответного хода — результат перебора вариантов, а не творческое решение проблемы.
И всё же программы стали куда ближе к людям по стилю и способу обдумывания игры. Ведь в случае с го буквальным перебором всех последующих позиций нельзя добиться ровным счётом ничего. Почему? Прежде чем вернуться к MoGo и Many Faces, нам просто необходим экскурс в историю. Для начала — в историю битвы человек-машина на шахматном поле.
«Софтинки», способные хоть как-то играть против человека, появились очень давно, но что важнее — уже в конце 1990-х были созданы программы, способные сражаться с чемпионами мира и даже выигрывать у них. Легендарная первая игра в матче Гарри Каспарова против машины (Deep Blue – Kasparov 1996) тому пример.
Чемпион, упустив эту одну игру, выиграл в том году весь матч, но через год усовершенствованная Deep Blue победила Каспарова уже окончательно (Deep Blue – Kasparov 1997).
Интуиция, опыт, знание огромного числа игр прошлого, подкреплённые образным, чисто человеческим мышлением, которое так трудно формализовать, уступили в тот раз «железке» Deep Blue, способной перебирать по 200 миллионов позиций в секунду.
Перебирать, впрочем, не тупо. Ведь общее число возможных положений фигур в шахматах колоссально, а значит, машине нужен был алгоритм, позволяющий «разумно» выбирать среди множества вариантов продолжения наиболее перспективные.
Естественно, что программу компьютерщикам помогали готовить люди, досконально знающие шахматную теорию. Так что можно сказать, что в 1997 году гроссмейстер проиграл не суперкомпьютеру, но коллективному разуму множества людей, и это некоторое утешение для человечества в целом. А слабым утешением лично для Каспарова оказались ничейные матчи с двумя другими, не менее коварными программами, проведённые в 2003-м.
Вообще же после матча 1997 года новые игры сильнейших шахматистов-людей против сильнейших программ продолжились, но уже не вызывали такого высокого интереса, как раньше. В 2002 году «кремниевый шахматист» Deep Fritz сыграл с Владимиром Крамником вничью, а в 2006-м та же программа победила-таки и этого чемпиона.
Менее известна история сражения искусственного интеллекта с человеком на поле шашек.
Не представляет собой головоломки создание программы, которая играла бы как среднестатистический человек, но выигрывать у сильнейших шашистов мира — это уже задача совсем нетривиальная, несмотря на относительную простоту игры.
Примерно на равных с сильнейшими «сапиенсами» бездушные игроки научились выступать в 1990-м. Но позже компьютерным гениям удалось пойти ещё дальше, чем в шахматах. В последних у человека всегда остаётся шанс на выигрыш у машины. А вот в шашках такого шанса у нас уже нет.
В 2007 году шашки оказались полностью «взломанными», то есть были просчитаны на суперкомпьютере все их возможные ходы и комбинации. Благодаря этому последняя версия шашечной программы Chinook – она, кстати, и играла в 1990-х с чемпионом мира Мэрионом Тинсли (Marion Tinsley) – стала беспроигрышной. То есть ни один человек у неё не сможет выиграть никогда, поскольку машина в абсолютно любой позиции всегда знает самый лучший ход.
С шахматами такой «взлом» едва ли возможен в обозримом будущем. Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 1046 (в шашках порядок куда скромнее — 1020), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.
Сможем ли мы лет через 50 нарастить производительность суперкомпьютеров на много-много порядков или придумать способ «взлома» шахмат в обход полного перебора?
Это большой вопрос. Но что уж тогда говорить об игре в го? Тут магия больших чисел просто подавляет любого, кто пытается «с линейкой» измерить глубину возможных ходов.
По словам Дэвида Дошея (David Doshay) из Калифорнийского университета в Санта-Круз (UCSC), ведущего собственное исследование го и к тому же создавшего ещё одну го-программу SlugGo, число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10171. И к ним можно прийти одним из 101100 путей!
Это число столь велико (сравните — сумма всех элементарных частиц во Вселенной составляет «всего» 1080), что прямой перебор всех вариантов игры абсолютно невозможен.
Но и «минимаксное» дерево поиска, которое хорошо зарекомендовало себя в шахматных программах, – в го работает плохо.
В такой стратегии компьютер перебирает все возможные ходы из данной позиции, но на конечное число ходов вперёд (в лучших программах на 12, то есть вовсе не до конца вымышленной партии, это важно). Полученные позиции оцениваются на предмет качества (выгодности).
С немногочисленными лучшими вариантами программа отыгрывает назад, снова мысленно делает ходы, но уже ведущие именно к отобранным позициям (и также ряд последующих ходов на энное число шагов), снова вычисляет все варианты получившихся состояний и опять отбирает из них несколько самых удачных. И так по кругу.
Специфика го не позволяет данному подходу давать хорошие результаты. Дерево возможных состояний на гобане (доске для го) ветвится слишком быстро. Настолько, что в отличие от шахмат быстро «забивает» способности всех современных компьютеров.
Как же компьютерщики нашли выход?
Создатели Many Faces, американская компания Smart Games и её лидер Дэвид Фотланд (David Fotland), воспользовались алгоритмом Monte Carlo Tree Search, то есть «Деревом поиска Монте-Карло», который был развит французскими специалистами по искусственному интеллекту в 2006-2007 годах. MoGo (а точнее, большая группа компьютерщиков из нескольких французских университетов и лабораторий, написавших эту программу) пользуется сходным же методом, хотя и отличным в деталях.
Как явствует из названия, его можно отнести к так называемым «методам Монте-Карло» (Monte Carlo method) — это общее наименование большой семьи численных методов, в которых изучаемый процесс (задача) моделируется таким образом, что решается не «в лоб», а путём просчёта конечных результатов огромного числа случайных событий.
Есть дамэ! Наша точка свободы. Постигнем гармонию через рукотворный хаос.
Самый примитивный пример. Вы хотите вычислить вероятность того, что подброшенная монетка упадёт решкой (предположим, вы не знаете, какова эта вероятность). Вместо применения формул и законов теории вероятности, рассуждений о физике движения тела, вы просто бросаете монетку десять тысяч раз и, подсчитав число событий, обнаруживаете, что искомый ответ — ровно 50%.
На деле же самые разнообразные вариации метода Монте-Карло применяют для моделирования куда более сложных вещей: динамики молекулярных систем, поведения квантовых частиц или даже социальных процессов. А разработан был этот метод (в целом) в Лос-Аламосе, в ходе работ над атомной бомбой.
А как он заработал в го? Программы-победители, стартуя из имеющейся позиции, сначала перебирают случайным образом несколько миллионов игр, которые могут быть сыграны из этого положения. Число большое, но вполне конечное. Причём каждую игру машина проигрывает до конца, совершенно не заботясь о разумности или выгодности ходов, как своих, так и виртуального визави (лишь бы правила не нарушались).
Получив запись ходов для каждой игры из этих миллионов, программа составляет статистику – какие первые ходы с большей вероятностью ведут к выигрышу. Помните пример с монетой? Вы бросали её без системы, но, посмотрев на большое число результатов, установили, что вероятность выпадения одной стороны равна 50%.
Скажете – ко – вы повторяетесь! Но в программах го дело обстоит схожим образом.
По статистике миллионов совершенно безумных, хаотичных игр, в которых машина не «думала» над ходами, но игр просчитанных до конца, программа устанавливает, что следующий ход такой-то приведёт к выигрышу с вероятностью, скажем, 3%, такой-то — 1,5%, а вот этот – 0,02% и так далее. А ведь возможных ходов даже на чистом поле го (19 х 19) – всего 361, а на частично заполненном – куда меньше.
Далее компьютер просто выбирает ход с наибольшей вероятностью выигрыша и проверяет ещё несколько миллионов игр уже из нового положения. Это позволяет уточнить вероятность победы, в конечном счёте сделав выбор – какой ход следует произвести в реальной игре с человеком.
Роберт Хирн (Robert Hearn), математик и компьютерщик из Дартмутского колледжа, а также – сильный игрок в го, прогнозирует, что пройдёт менее 30 лет, и программы (главным образом за счёт роста мощности суперкомпьютеров) начнут обыгрывать в го лучших профи даже без гандикапа. Арпад Риммель (Arpad Rimmel), один из авторов MoGo, оценивает этот срок и вовсе в 10 лет.
Но это не приблизит нас к разгадке того, как мыслит человек, играющий в го. Он-то не перебирает миллионы ходов.
«Удивлением, загадкой для меня является то, что эти алгоритмы работают», — говорит Хирн, комментируя новые достижения MoGo и Many Faces. Поясним: даже сами авторы этих программ прекрасно знают – как они работают, но при этом не знают – почему это срабатывает.
У человека за выбор хода в го отвечает интуиция, помноженная на распознавание образов. Работает визуальная аналогия (эта форма группы влияет на эту часть доски, эта конфигурация опасна, и так далее). Человек мыслит категориями жизни, эволюции и смерти групп камней на доске. Он узнаёт знакомые конфигурации, даже если они лишь близки к когда-то виденным. Он учится обобщать образы (вот камни выстроены в цепочку, вот кольцо с разрывом на боку, вот ещё что-то). Образность и помогает человеку принимать решения за разумное время.
Майкл Атертон (Michael Atherton) и его коллеги из университета Миннесоты (University of Minnesota) однажды просканировали мозги игроков в шахматы и го в процессе этих игр. Выяснилось, что у игроков го особенно сильно активировались теменные доли, отвечающие за обработку восприятия пространственного положения объектов.
Сходные японские опыты показали также, что у игроков-профи к концу игры сильно активируются и регионы, отвечающие за восприятие положения тела и за движения.
Атертон всё это обобщил так: «Игроки в го упрощают дерево поиска решений до эстетического чувства. У них есть чувство игры».
Потому наше очень даже скромное число нейронов легко справляется с тем, на что компьютеру, даже с новым «монте-карловским» подходом, требуются тонны чипов и терафлопы производительности.
Этикет го предусматривает спокойное и сдержанное поведение во время игры. Вот мы и говорим: спокойно, у нас всё ещё есть преимущество перед машинами.
Так произошёл ли прорыв? Нет, перед нами только фусэки. «Люди думают — как же далеко мы уже зашли, — говорит Дошей. — Но в действительности мы только начали программировать компьютеры».
Да и вообще их поражающая мир поступь в значительной мере, — лишь иллюзия. Ведь за каждой программой стоят люди, её написавшие. А значит, в общем матче со своими детищами мы сохраняем сэнтэ и всегда сможем позволить себе дать машинам «фору в семь камней».
это прогрессирующий альцгеймер :(
рархер пытается купировать свою болезнь, внушая себе и людям тупую идею, что неподвластность законам и определяет интеллект. т.е. плевать рархер хотел на все законы..
что с него взять — альцгеймер же))
эт рархер сладостно вспоминает свою молодость, первый гоп-стоп, чувство безнаказанности и вседозволенности при нарушении закона... становление своего криминального «интеллекта» короче..
эт рархер сладостно вспоминает свою молодость, первый гоп-стоп, чувство безнаказанности и вседозволенности при нарушении закона... становление своего криминального «интеллекта» короче..
--------------------------------------------------------------------------------------------
Кто б чего не говорил он говорит о себе...
ну, да, этот баг за тобой всем известен.-- ты не удержался еще разок полностью процитировать мой пост о тебе)))
Хорошо, а еще прошу Вас уточнить, что Вы подразумеваете под «интеллектом» в Вашей фразе «И как бы вы там себе это не представляли к интеллекту отношения не имеет»? Спасибо!
Однако, мне хочется понять, что Вы подразумевали, применяя это слово.
Правильно ли я понимаю, что по-Вашему, интеллект есть генератор алгоритмов? Ведь после нахождения решения и пути достижения (пусть заранее не известного) мы имеем известный алгоритм достижения известной цели.
Правильно ли я понимаю, что по-Вашему, интеллект есть генератор алгоритмов?
----------------------------------------------------------------------------------
Да, так сказать можно. Это рефлексы и «навыки» у человека... А так же образ поведения в социальной среде. Я б даже сказал что самого интеллекта мы и не видим. Только продукты его деятельности,...
а вот не подскажешь ли нам, рархер, существует ли закон (алгоритм) построения фрактала. и существует ли фрактал в конечном реальном мире?
Конечно, у этого понятия более благополучная судьба, чем у «сознания», ... до того момента, как возникло понятие ИИ. Дальше стало еще хуже — вмешалось неопознанное сознание: не то реальность, не то дух. Так, например, последовали предложения рассматривать сознание — как разновидность ИИ, а остальное отнести к Душе.
Вобщем, каша.
Однако, неформально, если остановится на Гегеле, то «интеллект», на мой взгляд, это то, что философ называл «чистым разумом». В современной интерпритации, «чистый» — надо понимать, как реализуемый алгоритмически с использованием формальной логики. Т.е. рафинированный, очищенный от неформализуемой «грязи».
Такой интеллект (чистый разум) приводит, согласно Гегелю, к антиномиям, которые уже не может разрешить. Как известно, из-за этого погиб от голода буриданов осел — носитель чистого разума.
А вот «нечистый разум» — т.е. сознание, антиномии снимает, и делает это постоянно. Поэтому, когда Александр говорит о формализуемом мире — это не наше, а для буридановых ослов. В таком мире нет антиномий — все формализовано. (Сразу прошу меня ивинить, я никого не хотел оскорбить — мы все ослы и часто занимаемся не своим делом: считаем в уме, играем с машинами, сортируем, ранжируем и т.д., т.е. делаем то, что должен делать чистый прагматичный разум).
Вот поэтому машины и побеждают нас в своих играх. Ну а человеческое — это всегда нечто неповторимое, апериодическое.
Короче, формализованного определения интеллекта не знаю, но философское сформулировано Гегелем в труде про «чистый разум». Т.е. «Чистый разум» — это и есть Интеллект.
А можно ли еще уточнить по поводу неформализуемой системы? Пример, или аналогию опять же...
Можно ли рассматривать растущую сеть фракталом, спрашиваете вы.
По форме — да, но не по содержанию, точнее, по конечному результату.
Действительно, первым наглядным примером существования фракталов в природе, обычно называют лист папоротника.
Но есть принципиальное отличие, на которое сразу обратили внимание биологи. Рассматривая пааоротник или «красивый рисунок», мы видим все его самоподобные элементы, пока они еще различимы (см. опять на рис С.Дали www.membrana.ru/particle/18526 )
А при формировании сети все промежуточные элементы распадаются при делении — когда формируется двоичное дерево. Остается только крона. Поэтому говорить о том, что она, подобно фракталу, имеет дробную размерность, некорректно. И сформированная на ней сеть, тоже конечно не фрактал.
Можно, влезу, спасибо.
Если представить окружающую реальность в двоичном коде (теперь это не проблема), то в такой реальности каждый шаг — это выбор одного из двух направлений: лев/прав.
Когда система формализуема — о чем говорил Александр, вы можете расчитать веса и выбрать направление логически. Но если неформализуема — как в приведенном примере, то выбирать, в лучшем случае придется по старому — методом монтекарло.
Здесь лев/прав — это и есть взаимоисключающие решения, т.е. антомия поведения. При этом, каждое решение, взятое в отдельности, справедливо.
То есть «фрактальная волна»? :)
-------
Ну, если посмотреть на неокортекс снаружи (как китайцы за ужином), то действительно, поверхность этого органа волнистая :)
Стало быть, неформализуемость мира такова исключительно потому, что он бесконечен (по крайней мере, теоретически), и мы можем формализовать только доступную нам часть его. Так? Всегда остается вероятность, что мы в расчетах не учли влияние недостижимой для нас в данный момент неформализованной детали. Тут вступает в дело вероятность со всеми ее последствиями.
Угу. Ага. Ага.
Стало быть, неформализуемость мира такова исключительно потому, что он бесконечен (по крайней мере, теоретически), и мы можем формализовать только доступную нам часть его. Так? Всегда остается вероятность, что мы в расчетах не учли влияние недостижимой для нас в данный момент неформализованной детали.
-----------------------------------------------------------------------------------------------
Ещё может случится что он (мир то есть. а если точнее — реальность) неформальзуем принципиально. «Законов» попросту не существует (не может быть закономерностей в хаосе). Так же не может быть их и в бьекте обладающем абсолютной полнотой состояний. Я там раньше говорил о таком. Есть основания полагать что такой обьект и хаос полностью эквивалентны...
ага. любимая присказка старого гоп-стопщика, когда рархер идет «на дело»))
только тогда и фракталов не существует..