Pull to refresh

Comments 232

Ходов в го постигнуть суть компьютерам не дано.
Программу писать Форте на если а?
UFO just landed and posted this here
Мне одному кажется очевидным обратное?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В го, вероятно, много нестандартных ситуаций, и их все так быстро не запрограммируешь (если это в вообще возможно). Чтобы обыграть человека, нужно строить алгоритм «на лету», как это делает человек. Переборы ходов, как в шахматах, здесь уже не прокатывают.
Мне кажется прокатывают, просто нужно правильно перебирать. По крайней мере на уровне игроков ~5 дана игра выглядит как конкуренция нескольких (обычно 5-6) групп и игроки внимательно следят за двумя свойствами этих групп: может ли противник их разделить и можно ли построить два глаза. Дальше каждый применяет хитрые трюки (тесуджи) чтобы как то повлиять на эти два свойства. Хитрые трюки, в свою очередь, это перебор интересных ходов в уме. Сложность в том как определить эту интересность и как видеть эти два свойства групп. На уровне 9-го дана наверно всё меняется: во всяком случае когда я смотрю некоторые записи на гокифу, я поражаюсь как группы камней разделяются и сливаются без нарушения баланса на доске (обычно ведь после потери любой группы сдаются).
Все достижения в области искусственного интеллекта прошли мимо Вас? Больше чем пол века назад разработали первую модель обучающейся сети. Википедия.
Извините, но эти «достижения», мягко говоря, не дотягивают до интеллекта. ИНС – это жалкие попытки моделирования работы нейронов, как если бы обезьяны нашли набор радиолюбителя и пытались сделать радиоприемник, не разобравшись в назначении деталей.
Где результат исследования моделей сетей? Почему мы продолжаем программировать большинство приложений, тупо вводя инструкции? Вот пример из статьи:
Поэтому её алгоритм состоял в том, чтобы в ситуации выигрыша делать бессмысленные ходы в собственной зоне, ожидая, когда соперник признает поражение.
Зачем вообще разработчик размещает какой-то алгоритм? Архитектура машины с достижениями в области искусственного интеллекта должна сама выработать подходящий под сложившиеся условия алгоритм.
И дальше.
Реми Кулэм всё равно был счастлив — и пообещал к следующему чемпионату доработать алгоритм действий в концовке.
Машина, проиграв, так ничему и не научилась. А вот разработчик получил некоторый опыт, который пообещал заложить в виде инструкций к следующему разу. Почему он не пользуется обучающейся сетью, а пишет алгоритм? А потому что применение сетей очень ограничено то ли из-за того, что мы их неправильно моделируем, то ли применять не научились.
должен заметить, что у большинства преподавателей постсоветских ВУЗов третий пункт тоже часто не входит в процесс обучения. Даже печально
Чтобы работали if/else нужно им грамотно условия составлять! Вот в этом-то и суть программ подобного рода — в условиях подставленных в if/else. Программа на данном этапе может определить лишь перспективность хода что является аналогом указания точного направления в виде неопределенного взмаха рукой(а куда-то туда) и не гарантирует победы вообще. Пока программы позволяют только не оплошаться с первых ходов сделав изначально невыгодные ходы.
Но человек хитер… сделав невыгодный ход он в итоге может победить…
Тоже засомневался. Вероятно человек играет, оценивая ситуацию сложным нечётким алгоритмом, который пока не удалось хорошо формализовать, не просчитывая множество возможных вариантов. Возможно даже на уровне интуиции — происходит распознавание хороших и не очень позиций на основе опыта игры.
Игра Го не сильно поддаётся явным алгоритмам.
Художники в неё играют порой лучше, чем математики.
Думаю, что дело не в невнятной фигне «художники лучше математиков» и прочей эзотерической ереси типа «поэзия битвы», а просто в том, что в шахматы играет очень много людей и на шахматных турнирах разыгрываются миллионы долларов, а по го только десятки тысяч, да и то в Китае.
Я больше одного раза слышал, что опытные игроки оценивают позицию визуально, распознавая в виде визуальных образов знакомые паттерны. Я почти не умею играть в Го, но даже будучи знакомым поверхностно с игрой, мне это звучит вполне логично.
UFO just landed and posted this here
Я смотрю, идея с объяснением отсутствия вирусов под линукс универсальна.
К примеру, можно заменить «вирус» на «алгоритм», «linux» на «го», а «windows» на шахматы.
Вы серьезно заблуждаетесь. Вы много видели институтов шахмат? А в Японии есть самые настоящие институты Го, со вступительными екзаменами, серьезным отбором и суровыми выпускными екзаменами. Профи — обладатели титулов живут на государственную стипендию, и очень даже не бедствуют.
А учитывая размер Китая, то очень даже может быть что игроков в Го в разы больше игроков в шахматы.
Это всего лишь одна Япония.

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

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

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

Кубок Инга — турнир организованный Ином Чанци — основателем Фонда Инга, изданием 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) — Кун Цзе.

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

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

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

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

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

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

К сожалению очень странная тенденция, мы с Halt имеем представление о игре, но нас минисуют за высказывания простых (может непонятных что ли) истин, а троллей, незнакомых с игрой, плюсуют.
UFO just landed and posted this here
Для анализа и пытался запомнить, лишь как эксперимент. И как раз в этой игре есть хороший пример просчёта партии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В статье же написано:
>Даже игроки не понимают, как они это делают: «Просто смотришь на доску и знаешь», говорят они.
Не из Космоса же они это черпают — это именно нейросети их выдают, не задействуя логическое мышление.
UFO just landed and posted this here
Вы недооцениваете экспоненту. Фактор ветвления 250, среднее кол-во ходов 200. Получаем 250^200 — кол-во комбинаций, которые надо проверить в начале игры, чтобы найти безпроигрышную стратегию, если такая вообще существует. Это число на несколько порядков больше, чем кол-во атомов во Вселенной по оценкам ученых =(
А почему бы заранее не построить всё дерево целиком? Провести предварительную градацию выигрышных и неудачных ветвей… очевидно, что некоторые ветви будут дублироваться…
Построить все дерево целиком? Вы серьезно? Число позиций больше чем кол-во атомов в тысяче вселенных. Пока не изобретут компьютеры, способные хранить информацию на субатомном уровне, мы не можем этого сделать.
Ну когда-то это возможно случится =) Всё ради Го
Упорство, достойное религиозного фанатика. «Может быть» тут не прокатит. Возьмите для примера партию в 186 ходов Crazy Stone vs Zen: количество возможных ходов после каждого раунда — 250, следовательно, количество всех возможных ходов за партию составляет 250^186 (250 в степени 186). Вот и посчитайте, хватит ли материи во Вселенной.
Не понимаю, какое отношение имеет кол-во материи (кол-во чего, атомов или чего?) во Вселенной к кол-ву комбинаций? Понятное дело что в данный момент нету таких технологий хранения и обработки данных, способных построить и перебрать все дерево решений, но это не значит, что их никогда не будет.
Сильное взаимодействие потому и называется сильным, что для его преодоления нужно огромное количество энергии. Если во Вселенной не хватает адронов, придётся работать с кварками, что даст всего лишь в несколько раз больший выигрыш в количестве «частиц» для хранения дерева ходов. А если экономить на материи, потребуется огромное время для инкрементального построения дерева. К тому же, скорость взаимодействия материи ограничена скоростью света, так что при росте количества задействованной в расчётах материи скорость работы такого «компьютера» будет пропорционально падать.

Короче, в подобных задачах разумнее использовать нейронные сети, эвристики, а также генетические и прочие алгоритмы, которые нацелены не на точный, а на оптимальный результат — удовлетворительный результат за небольшое время.
Насколько мне известно, работать с кварками не получится, потому что кварков как таковых не существует, их никто не видел — это не более чем модель. Но вы ведь не знаете что там мельче кварков. Никто пока что не знает, но это не значит что там ничего нету и это что-то невозможно будет использовать для вычислений и хранения данных.
К слову, электроны тоже никто не видел. А "дырки", как самостоятельные частицы, вообще не существуют. Что не мешает их использовать во всей электронике.
Нельзя сравнивать кварк с электроном. Электроны вполне себе осязаемые объекты. Их можно запустить из пушки и наблюдать свечение люминесцентного вещества. И при помощи этого поиграть в CS1.5 на стареньком компе с ЭЛТ монитором. С кварками такого не пройдет. Кварки это не более чем красивая модель, по крайней мере пока.
Я извиняюсь за ссылку на википедию, но там пишут вот что.
Может быть ошибался насчет кварков.
Супер, спасибо за ссылку!
UFO just landed and posted this here
UFO just landed and posted this here
Да и в таком случае — а хватит ли материи?
Можно дождаться квантовых компьютеров.
Если использовать элементарные частицы, то, конечно же, материи не хватит. Но что есть материя? Ученые пока не знают что там внутри элементарных частиц.
Какая разница? Мы с вами живём в макромире, а для манипуляции теми же кварками нужны просто чудовищные количества энергии. И я говорю даже не об одном грамме вещества, а о миллионных долях. Законы физики не обманешь.
Вы утверждаете, что существование носителей, хранящих информацию на субатомном уровне и таким образом имеющим бОльшую плотность информации чем кол-во атомов из которых они состоят, невозможно? Какие законы физики вы имеете ввиду?
Вот за что я люблю хабр. Комменты заминусованы, а в дискуссию вступать никто не хочет.
Как соотношение неопределенности связано с теоретическим пределом плотности носителей информации?
Во-первых, на определенной плотности возникнет вероятность произвольного перехода ячейки в другое состояние (спасибо туннельному эффекту). Во-вторых на планковской длине до одной ячейки будет уже не дотянутся (сигналы схлопнутся в черные дыры).
Вы говорите про конкретную ячейку памяти, которая построена из известных нам элементарных частиц. Но это ведь не значит, что в природе не существует других более плотных механизмов хранения информации, которые мы еще не понимаем потому что не знаем что там творится на субатомном уровне?
То, что мы знаем на текущий момент, указывает нам, что планковская длина это предел.
У определенного кол-ва ентропии (т.е. информации) есть вполне конкретная площадь поверхности, способная её уместить. Плотнее упаковать информацию невозможно.
Что творится на субатомном уровне — мы прекрасно знаем. Вот сублептонный и субкварковый — проблема. Но все известные явления следуют принципу неопределенности (сам принцип следует из формулировки КМ). И нет абсолютно никаких причин думать, что какие-то неизвестные элементарные частицы его нарушают.
Вы так говорите, как будто единица материи может хранить только один бит.
Я могу вам одной единицей материи сохранить любой объем информации, вплоть до бесконечности.
Так что совершенно не важно, сколько там материи во вселенной. Важно, сколько мы фактически можем хранить данных в данный момент времени.
Что такое единица материи? Как вы планируете сохранить любой объем информации в единице материи?
Ладно. Вы правы. В одну не уложусь. Мне понадобится две.
А информация — это расстояние между этими двумя единицами.
Т.к. вселенная бесконечна — расстояние может быть сколь угодно большим. А значит и число, которое мы можем хранить — может быть сколь угодно большим.

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

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

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

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

Сами ведь ISO нотацию привели по поводу правильного написания.
Стандартизированное написание != правильное написание. Все указанные в таблице — правильные.
А я математик, и мне не режет.
Похоже я тоже немного недооценил. Снизу forgotten меня поправил.
UFO just landed and posted this here
Если верить wolfram alpha, то количество позиций в Go ещё меньше (примерно в 40 раз):
Ну норм, 200 порядков скостили, осталось еще всего-то сотня порядков до кол-ва атомов в Вселенной =)
Так производительность то вообще мизерная, до сих пор пароль больше 8 символом генеренный рандомом нельзя подобрать за вменяемое время, это примерно аналогично с 8 ходами го, то есть нельзя просчитать дальше 9 ходов
, так ли сложно человеку просчитать на 9 ходов вперед?
да легко
Человек не перебирает ходы, а вспоминает аналогичные случаи из предыдущих партий (так же и в шахматах). Поэтому ветвление влияет на кривую обучения, но не на предельное мастерство. А вычислительные мощности компьютеров очень даже ограничены.
Что мешает компьютерам вспоминать аналогичные случае из предыдущих партий? Лучшие шахматные программы это делают с большим успехом?

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

Вот, к примеру цитаты о 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
Нет. Человек смотрит на доску и оценивает.
Мозг принципиально заточен под то, чтобы оценивать результат операции, даже если он вообще не понимает её смысла. Каждый из нас легко оценит, где упадёт брошенный камень, не строя никаких парабол и не вспоминая гравитационную постоянную.
Каждый из нас легко оценит, где упадёт брошенный камень

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

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

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

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

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

Данное представление о вопросе составлено по этим книгам:
* Крис ФРИТ. Мозг и душа. Как физиология формирует наш внутренний мир
* Эрик Ричард КАНДЕЛЬ. В поисках памяти. Возникновение новой науки о человеческой психике
в мозгу формируется (буквально прорастает) нейронная сеть

Подскажите, пожалуйста, где об этом почитать?
По определению же.
Биологическая нейронная сеть — система соединённых между собой нейронов мозга животных, человека.

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

Дальнейшие поиски привели к elementy.ru/news/431207 («Оказалось, что при обучении дендриты (ветвящиеся «входные» отростки нейронов) образуют множество новых веточек, количество которых коррелирует с эффективностью обучения. „) — а в самой статье речь лишь про рост дендритных шипиков, то есть скорее про ваше мнение, нежели про моё.
Помимо количества ветвлений, сложность го для компьютера имеет ещё одну причину, которая почти не изложена в статье. Это функция оценки позиции.

Что значит перебор ходов? Их же нужно не просто перебирать, а на каждом шаге оценивать полученную позицию, как хорошую/плохую, перспективную/неперспективную. В шахматах функция оценки сравнительно проста, в го — гораздо сложнее и хуже поддается алгоритмизации. То есть дело даже не вычислительных ресурсах, а в том, что даже теоретически пока не удалось построить такую функцию, качественно сравнимую с человеческой.

Шахматы — по большей части счётная игра. Го — шаг в сторону к ИИ.
Похоже, что просто никто не применяет суперкомпьютеры для этого. Просто никому этот го не сдался. Какой-то одиночка без серьезного финансирования (сравните с IBM) время от времени выпускает свою программу. Для тех же шахмат наверняка не один человек программу писал и мощности вычислительные соответствующие.
К сожалению все упирается в цифры. На поле 19х19 где каждая точка может быть занята белым, черным камнем или не занята, возможно несколько меньше 1.7e+172 миллионов комбинаций.

В одной игре на каждому ходу возможно около 250 варианта хода в среднем, что дает дерево возможного развития ситуации на 128 ходу с 8e306 ветвями ( если кто вспомнит про симметрию, можете поделить это число на 4 ).

В итоге современные алгоритмы на компьютерах с почти неограниченными вычислительными мощностями не могут не то, что хранить возможные результаты партии в памяти, они даже не могут посчитать варианты до конца игры.
UFO just landed and posted this here
На самом деле все очень просто. Чтобы компьютер выиграл с практически 100% вероятностью, ему нужна возможность полностью просчитать ходы, а игру го так до сих пор и не просчитали — не увидел этого казалось бы очень важного факта в статье.
Т.е. вообще не просчитали, даже не то что во время игры в реальном времени, а вообще :) Ибо сложность экспоненциально растет с каждым ходом, об этом в статье есть, ага. Поэтому и пишутся алгоритмы, суть которых сводится к очень простой вещи — решить задачу с минимальными потерями точности. И выигрывает соответственно та программа, которая наиболее удачно откинула ненужные вычисления.
Упс, кажется я немного опоздал…
Человек при игре в Го не просчитывает все ходы. Он использует образное мышление, задействуя правое полушарие мозга, которое ЭВМ не в состоянии смоделировать.
>>«Требуется некий ментальный прыжок, чтобы снять эту блокировку»
Где-то в древней Японии:
— Ребят, го в го.

// и пофиг, что там не знали английского
«Я расставил!» — часто слышал и говорил эту фразу в детстве.

Правда, в го партия начинается с пустой доски.
Го в го на го? (языке программирования).
>Несмотря на рост вычислительной мощи компьютеров — чемпион мира по шахматам сегодня, вероятно, проиграет даже вашему домашнему ПК
Эта фраза меня помножила на ноль.
В статье, много ошибок, я даже начал копировать их для отправки автору, но потом увидел кто автор… и руки опустились.
Несмотря на рост вычислительной мощи компьютеров (чемпион мира по шахматам сегодня, вероятно, проиграет даже вашему домашнему ПК) алгоритмы игры в го на экспертном уровне остаются нерешённой и одной из самых интересных задач ИИ.

А так? Понятнее стало?
§ 174
Спасибо понятнее.
Только чемпион мира не проиграет домашнему ПК. Впрочем стоит слово вероятно и не указано какова вероятность, проигрыша. Которая в случае домашнего ПК стремиться к нулю.
Если я ничего не забыл только Deep Blue смог выиграть у гроссмейтесра, а это был кластер из 30 стоек.
Не стоек 30, а процессоров, 120 MHz каждый. Плюс 480 специальных чипов.
Но это всё было в 1997 году.
А в 2006 Deep Fritz играл против Крамника на обычном настольном компьютере с двумя Intel Core 2 DUO. Из 6 игр матча компьютер выиграл 4.
4 из 6 как-то всё же побольше нуля, не считаете?
В 1997 году. Учтём ещё, что не только железо эволюционировало, но и, что намного важнее, алгоритмы.
Кроме шашек (русских и международных), шахмат и го, есть еще масса игр этого класса.
Хотя занимаются ими меньше го, но даже с такой поправкой больших успехов там не заметно.
Отличная задача для ИИ — по описанию правил сгенерировать программу, играющую в заданную игру лучше, чем продвинутый новичек.
Кстати, и для людей интересно проверить, как они в таких условиях себя ведут — перед соревнованием более-менее рандомно генерятся правила, дается месяц по этим правилам попрактиковаться, потом проводится турнир.
Вы не поверите, но такое есть — соревнование программ, играющих в сгенерированную случайно игру. К сожалению, я тут в Беларуси забанен в гугле, чтобы найти необходимые ссылки: NAT, будь он неладен.
Что-то не получалось в нем ничего найти лучше Яндекса. Ошибаюсь?
Вы так говорите, как будто Яндекс плохо ищет.
Ну, мне не нравится как он ищет. Сложные запросы, в которых нету ключевиков он как-то не очень умеет. Я часто не знаю как называется то что я ищу, и гугл мне очень помогает.
Ну, знаете, он вас хотя бы не забанил, как я понял.
Да, и я честно попробовал найти это в яндексе, но не получилось
Найдите, пожалуйста! Очень-очень хочется на это посмотреть.
Не совсем то что я имел ввиду. Чуть выше в этом треде ссылочкой поделился
Ага, я когда-то немного увлекался Arimaa, забавная игра с относительно простыми правилами на шахматной доске, но специально спроектированную как сложную для компьютерных игроков.
Я бы переписал на Go банально ради стилистической целостности.
Возможно даже если переписать его программу на Go, то все эти надуманные сложности с множеством вариантов игры пропадут сами собой :)
Суть игры такова, что нельзя оценивать успешность каждого хода по каждой фигуре. Очень часто противник может специально «сливать» свои позиции, чтобы потом отыграть большее. В отличие от тех же шахмат, где чем дальше в партии, тем четче ситуация, и вероятность исхода для каждого из игроков начинает напоминать перетягивание каната, который уже оказался на чьей-то стороне. В Го можно на последней четверти партии ситуацию переломить таким образом, как будто превратившись в лебедку и резко отмотав на себя канат, уже перетянутый соперником.

Было хорошее аниме про Го — Hikaru no Go, заинтересовавшимся советую посмотреть, там именно о психологическом аспекте игры сказано на порядок больше чем во всех подобных статьях.

P.S. да и культура Го, это прежде всего — психология, и уже только потом математика.
Поддерживаю, посмотрите Hikaru no Go, в этом сериале раскрывается вся суть этой игры и культуры с ней связанной.
>> В отличие от тех же шахмат, где чем дальше в партии, тем четче ситуация…

Не совсем верно. Шахматные движки до сих пор не научились безошибочно оценивать эндшпильные позиции (окончания). Бывает движок показывает будто бы на доске битая ничья, хотя на самом деле у одной из сторон в доску проиграно. Поэтому спортивные комментаторы-гроссмейстеры далеко не всегда во время комментирования турниров в окончаниях полагаются на компьютер.
UFO just landed and posted this here
А почему нет ссылки на оригинальную статью? И выдрано из неё как-то кусками…
Потому, что за перевод дают 500 р, а за статью — 1000.
Ну не стоит говорить о «последней игре с полной информацией». Например, есть сомнения, что компьютеры могут хорошо играть в шведские шахматы (bughouse). По крайней мере, о таких программах пока ничего не слышно.
Комментариев столько и шутки ни одной о Йоде мастере
Падаван юнный комментария первые два читал ли?
В зелёном кимоно…
Одна из лучших игр, в которые я играл) Дошел до 1 кю на КГС сервере, потом перестал играть. Было это года два назад, с тех пор иногда решаю щадачки или просматриваю партии про.
Всем всегда советую начать играть в го. Ощущения просто чудесные :)
Да, прочитаешь такую статью и понимаешь что пора сдуть пыль с гобана :)

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

Играть в древнюю национальную игру сидя на этих дурацких стульях за этим неудобным столом — контрмедитативно.



В го серьезно не играл, не было оказии (буду благодарен, если подскажете площадку, где можно попробовать без особых хлопот). Зато отыграл в рейтинговых турнирах в шахматы на мастера и хорошо(реально хорошо) играю в преферанс. По своему опыту могу сказать, что сильный игрок играет не против позиции, а против противника, стараясь распознать его тактики и эвристики учитывая и эмоциональные аспекты, Скажем, если противник по своему складу не склонен жертвовать качество за темп я буду отсекать такие деревья продолжений при переборе. Это и сокращает перебор. При игре с неизвестным или заведомо слабым игроком сильный игрок играет против себя. При игре с машиной я лично также стараюсь распознать эвристики алгоритмов и спрогнозировать тактики машины. Для слабых программ это вполне работает.
www.gokgs.com/ — один из самых популярных сайтов. Сильное коммьюнити. Мощный клиент.
Совершенно верно, все это применимо и к го. Более того, мастер уровня дана может оценить уровень противника буквально за 5-10 ходов.
>буду благодарен, если подскажете площадку, где можно попробовать без особых хлопот
Советую играть на KGS.
На самом деле вот это «компьютер до сих пор не обыграл человека» звучит несколько страшно, потому что какой-нибудь хитроумной сволочи наверняка придёт на ум сделать из этой игры капчу.

«Чтобы доказать, что Вы не робот, пожалуйста, одержите победу в го над нашей игровой программой, имея фору в три камня».
Пока решишь капчу, забудешь зачем вообще на сайт приходил :)
На ресурсах, посвященных Го иногда встречаются такие капчи при регитстрации) Там просят решить простенькие задачи в 1 ход, чтобы доказать что ты не робот :)
Я их решаю с помощью своей программы игры в Го :)
> Сегодня компьютеры превосходят людей абсолютно во всех играх с полной информацией, кроме одной — го.
Ну как же так? Например, сёги — еще одна такая игра.
Таких игр много, выше в комментах уже возражали, но ализар такой ализар…
Если Ализар публикует только низкокачественную желтуху, почему он сам и его посты всегда в плюсе?
Может, высококачественной? :)
Т.е. по поводу желтухи возражений нет? :)
Наверное, потому, что даже на Хабре большинству лень искать источники, проверять приводимые в статьях факты и т.п. Я никого не обвиняю, ведь люди приходят сюда за информацией, а не для того, чтобы потратить своё свободное время на детальный разбор чьего-то поста. Однако с оценками многим неплохо было бы не торопиться.
В начале игры вариантов первого хода намного меньше. Примерно 1/8 доски — 55 вариантов. Есть же оси симметрии. Второй ход имеет около 180 вариантов. Итого после двух ходов вариантов доски будет 9900. А вовсе не 129 тысяч, как написал автор статьи. Но все равно в дальнейшем количество вариантов возрастает эекпонициально.
Есть классическая задачка на тему экспоненциального роста. Пусть есть колония в банке, популяция которой удваивается каждую минуту. За сутки банка заполняется (полностью). Сколько времени понадобится колонии, заполнившей банку, на восстановление объема, если удалить 75% (50%, если хочется попроще)?

Количество людей, неспособных решить эту «задачку», меня в своё время поразило.
Я так понимаю, в первом приходящем на ум ответе (в случае про 50%) — «одна минута», есть какой-то подвох, неочевидный неспециалисту? Ну и 75% — «две минуты».
Это верные (в рамках данной задачи) ответы. Вы не поверите, но значительное количество народу считает, что 12 часов (для случая 1/2) и 18 часов (для случая 3/4).
очень хорошая игра… если проголодался, то можно m&m'ку заточить…
Sign up to leave a comment.

Articles