How to become an author
Search
Write a publication
Pull to refresh

Comments 80

Наконец-то про игру ГО начали писать на хабре.
Сейчас интересуюсь данной тематикой и пытаюсь придумать и реализовать ИИ для гораздо менее популярной и исследованной игры «Точки». Интересно, что сложнее?
Total votes 17: ↑15 and ↓2+13
точки явно попроще, в го есть варианты отыграть полу-открытые захваченные области, а в точках любая территория обводится непрерывной линией
Total votes 2: ↑2 and ↓0+2
Ну я бы не сказал, что явно — это еще доказать нужно.

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

Все это анализировать надо.
Total votes 10: ↑5 and ↓50
Вы явно не играли в го хотя бы на любительском уровне, пустые обведенные области в го допускаются и очень часто так и есть, если внутри области не построить 2 глаза то в ней не выжить и в неё не ходят, в Го сложнее тем что в ней стратегия переходит в тактику а тактика в стратегию. и в отличии от точек поле в го абсолютно динамично.
Total votes 6: ↑6 and ↓0+6
Да, наверное не играл. Но я понял о чем вы сказали.

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

И в точках игра развивается более вяло, по сравнению с Го, поскольку нужно сразу начинать с глобала, чтобы не уйти в ничью. А в Го все начинается с краев и да, игра более динамичная и быстроразвивающаяся.
Total votes 3: ↑1 and ↓2-1
Все же, настоятельно советую изучить го чуть глубже, чем «рассмотрел доску с камнями». Это очень серьезная игра с бесконечной глубиной.

Касательно жизни и сметри групп вообще нельзя ничего однозначно говорить. Количество вариантов там такое, что делать подобные заявления неразумно. Группа может иметь дыхательные пункты и тем не менее быть обреченной при правильной игре оппонента.
This comment wasn’t rated yet0
Ещё важный момент — захваченные камни сразу снимаются с доски и это свободное место можно снова использовать (ко-борьба).
Total votes 6: ↑4 and ↓2+2
Ну это не совсем ко-борьба, ко-борьба это когда вынуждаешь противника делать невыгодный ход, потому что выгодный он не может сделать из-за правила ко. Что кстати тоже добавляет сложности :) А освобождённое место можно и без ко-борьбы использовать)
Total votes 2: ↑2 and ↓0+2
И вы не правы, ко-борьба это игра Ко, чаще всего на угрозы, не кто не кого не заставляет делать не выгодный ход, по своему названию не выгодных ход не сулит выгоды по этому игрок просто закроет Ко или отдаст, в замен получив что то другое.

Ту ситуацию что описали вы это Ко в начале партии его редко играют сразу.
Total votes 1: ↑1 and ↓0+1
Да, действительно, хотя бы из-за того, что в го есть ко, оно уже сложнее точек :) Ну, и по многим другим причинам тоже.
Total votes 1: ↑1 and ↓0+1
Смотря какое поле в точках, обе игры сложная задача для ИИ
Total votes 2: ↑2 and ↓0+2
Если сравнивать при одинаковых размерах полей.
Total votes 1: ↑1 and ↓0+1
Это наверное первая серьезная статья, которую прочитывают люди, занимающиеся данной темой.
И написана она, кстати, Павлом Торгашовым, который есть на хабре :)
Total votes 1: ↑1 and ↓0+1
Как специалист по точкам, скажу Вам, что там очень много мини игр. И если знать как ходить, то даже казалось бы серьезный противник раскалывается на части :)
Total votes 2: ↑2 and ↓0+2
Я недавно писал ИИ для игры в гомоку (крестики-нолики до 5 в ряд), но с немного модифицированными правилами: игра идет не до первого зачеркивания, а до заполнения всего игрового поля. За каждое зачеркивание плюсуются очки. По окончании кто больше набрал очков, тот и победил. Мы в такую игру развлекались в студенчестве на бумаге, ибо до первого зачеркивания все было вообще легко и скучно.

Алгоритм на самом деле получился не очень сложный, но вполне себе сильный. Мне с ним очень тяжело соперничать, хотя опыт игры в такой вариант у меня приличный.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Есть еще «6 в ряд», справедливая для обоих игроков
Total votes 1: ↑1 and ↓0+1
Легко и просто было, потому что я всех обыгрывал, начиная либо крестиками либо ноликами. Поэтому мы слегка модифицировали правила, а стратегия при этом поменялась очень сильно, потому что пришлось думать не только о том как первому зачеркнуть, но и взвешивать что выгодней: зачеркнуть сейчас или поставить еще одну вилку, или залочить возможность поставить вилку сопернику и т.д. И вот в новой стратегии уже не так важно было как быстро ты поставишь первый 5 в ряд.
Total votes 1: ↑1 and ↓0+1
Очень давно находил довольно красивую программу/игру Dots — как понятно из названия это те самые точки. Но сейчас как ни пытался — найти заново именно ту не могу.
А вообще гугл даёт очень много вариантов реализации данной игры.
Total votes 2: ↑2 and ↓0+2
Вы хоть во что-нибудь играли из этого?
Если бы поиграли во все, то поняли, что проблема ИИ для точек остается открытой.
ИИ в Го развит куда лучше сейчас.
Total votes 5: ↑3 and ↓2+1
Базы эндшпилей в шахматах — это не ошибка?
Про дебютные таблицы слышал, а эндшпили, как мне кажется, можно и полностью рассчитывать.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Да, и еще интересный вопрос:
а дан точно присваивается по результатам всего одной партии?
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Разница между профессиональными данами не соответствует количеству камней форы, считается что разница между 1д и 9д около 3-х камней, так что можно сказать, что программа играет на уровне очень сильного любителя. Но тем не менее это все равно очень круто… Когда я начинал играть лет 5 назад, программы даже на 1-й разряд не играли, а сейчас получается уже на уровне гроссмейстера могут играть.
Total votes 1: ↑1 and ↓0+1
А почему без форы не играли?
Total votes 1: ↑1 and ↓0+1
Ну пока что текущего уровня явно недостаточно чтобы без форы с профессионалом играть.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Странно, что даны идут на понижение. В Японских боевых искусствах отсчет идет от «кю» до «дан», к примеру от 10 кю до 1 кю и затем — 1 дан, 2 дан, 3 дан… Неужели в «го» — традиции решили подменить?
Total votes 1: ↑1 and ↓0+1
Нет все так же, кю понижаются от 30-го до 1-го а даны растут от 1-го до 9-го
Total votes 3: ↑3 and ↓0+3
На момент прочтения статьи и написания коммента было сказано, что дан повысился с 8 или 9 на 5 (если правильно запомнил цифры). Возможно я не верное прочитал, тогда извиняйте.
Total votes 1: ↑1 and ↓0+1
В го даны бывают любительские и профессиональные (признанные, с дипломом), может отсюда пошло недоразумение.
Total votes 1: ↑1 and ↓0+1
Вы запутались. Фору давал игрок, а не программа.
Total votes 2: ↑2 and ↓0+2
Я кстати играл с этой программкой, причем я как раз брал у неё фору 4 камня. Она меня разделала :( Правда я утешал себя тем что игра была с очень неудобным для меня контролем времени, почти блиц, а я не люблю быстрые партии играть, но факт остается фактом, играет она сильно…
Total votes 1: ↑1 and ↓0+1
Не подскажете хорошую реализацию Го для айпада? Почитал, понравилось — хочу поиграть.
Total votes 5: ↑4 and ↓1+3
SmartGo для игры в одиночку (ещё и задачек по го содержит кучу), Tetsuki для игры по сети.
Total votes 4: ↑3 and ↓1+2
Спасибо сейчас поставлю, редко встречаю приложения за 20 баксов :)
Total votes 1: ↑1 and ↓0+1
О, оно того стоит, если вы действительно увлеклись го :)
Total votes 2: ↑2 and ↓0+2
Где-то была клёвая картинка по поводу текущей ситуации с уровнем игры компьютера против человека — там еще Го были намного выше шахмат и было много других игр. Не могу найти — кто-то подскажет?
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
seven minutes in heaven — это наша бутылочка, как оказалось :)
Total votes 3: ↑3 and ↓0+3
Только с одной поправкой: поцелуй против семи минут в закрытом шкафу :)
Total votes 3: ↑3 and ↓0+3
Можно начинать бояться роботов.
Total votes 2: ↑2 and ↓0+2
В реверси имхо забыли дописать «нг» и опустить в самый низ
Total votes 1: ↑1 and ↓0+1
Я бы вот не зарекался насчет never.
Total votes 1: ↑1 and ↓0+1
Между прочим, недавно появилась программа (под названием Xuan Xuan Go), которая решает локальные позиции лучше профессионалов. Она даже нашла больше десятка ошибок в классических задачках, придуманных профессиональными игроками.
Так что прогресс в области алгоритмизации го однозначно не топчется на месте :)
Total votes 5: ↑5 and ↓0+5
Очень круто. Особенно круто то, что использовался сравнительно небольшой кластер, что косвенно указывает на то, что программа не основана на Монте-Карло (детальной инфы по программе пока не нашел, может кто-то в курсе как она работает?). А это большой прорыв, монте-карло алгоритмы все-таки тупой брутфорс, а тут (возможно) действительно по настоящему интеллектуальный алгоритм…

Занятно, что автор на самом деле ещё и является тем самым знаменитым игроком со своим крайне специфическим «космическим» стилем игры ;)

А ещё было было бы очень интересно посмотреть на игру без форы. Даже если программа играет действительно сильно и вначале будет выигрывать, то профи игрок после несколько игр наверняка сможет подстроиться под её стиль игры и найти контрмеры. И вот тут вопрос — сумеет ли программа забороть эти контрмеры… Если да — поздравляю всех с сингулярностью ;)
Total votes 3: ↑3 and ↓0+3
Насколько я знаю, все сильные программы используют метод монте-карло. Естественно, он сочетается с другими алгоритмами — например, алгоритмами оценки позиции. При этом, варианты просчёта в монте-карло тоже выбираются не случайным образом, а наиболее перспективные.
При этом, в фусэки (начале игры) все программы пользуются базами фусэки и дзёсэки (стандартных розыгрышей в углах). Также, есть и базы стандартных форм групп камней, которые составляются при помощи самообучающихся алгоритмов.
Так что нельзя говроить о том, что используется «чистый метод монте-карло». В этом случае программа вряд ли смогла бы играть сильнее 15-го кю.
Но в той или иной степени монте-карло однозначно используется.

К сожалению, ссылок дать не могу. Это всё из памяти, я по этой теме много чего читал какое-то время назад.
Total votes 3: ↑3 and ↓0+3
Вот есть такой документ про генерирование ходов из паттернов и других эвристик для последующего использования их в алгоритме UCT.

Total votes 2: ↑2 and ↓0+2
Нашел, таки Монте-Карло ;(
У таких алгоритмов существенный недостаток — при увеличении размера поля сложность расчетов растет очень сильно. На поле 25x25 программа опять будет сливать человеку, если не научиться играть интеллектуально, без брутфорса.
Total votes 2: ↑2 and ↓0+2
Правда, поля 25х25 нет :) Ну, то есть, стандартное поле — 19х19.
Кстати, не думаю, что для программы будет большая разница, 19х19 поле или 25х25. Начало игры точно так же можно будет играть по базам, а локальные позиции вряд ли будут намного сложнее.
И опять же, в этих программах много разных алгоритмов заложено. Монте-Карло — это всего лишь метод оптимизированного перебора вариантов, когда их слишком много.
Total votes 3: ↑3 and ↓0+3
Официального поля нет, разумеется, но Го такая особенная игра, что её можно играть и на 1000x1000.
Разница для брутфорса как раз будет существенная, площадь поля определяет кол-во возможных ходов, увеличения площади в 4 раза увеличит среднюю длительность игры (общее кол-во ходов за игру) приблизительно во столько же, плюс на каждый ход потребуется перебрать пропорционально большее кол-во вариантов, можете сами прикинуть вырастет сложность перебора, еквивалентного оному на поле 19x19…
Разумеется, для человека сложность тоже возрастет, но не на многие порядки, а всего лишь в разы.
Total votes 2: ↑2 and ↓0+2
Вообще, это очень интересная тема. Мне кажется, что если брать такие крайности, как 1000х1000, то там игра распадётся на множество несвязанных друг с другом позиций, которые друг на друга практически не влияют.
19х19 — это вообще, как мне кажется, оптимальный размер доски, потому что там практически каждый поставленный камень всё ещё влияет на ситуацию в целом.
Так вот, мне кажется, что если взять доски 1000х1000 и 2000х2000, то что программе, что человеку будет одинаково сложно играть на любой из таких больших досок. Увеличится только время партии, просто потому, что нужно будет сделать больше ходов.

Их этого примера, вроде как, следует вывод, что зависимость между сложностью игры и размером доски, как минимум, не линейная.
Total votes 2: ↑2 and ↓0+2
Не линейная, разумеется. Что я пытаюсь сказать, так это то, что разные типы алгоритмов будут по разному реагировать на увеличение поля. Для брутфорсовых небольшое увеличение размера поля сильно увеличивает требуемую мощность при сохранении качества перебора (глубины, % покрытия и т.д.), т.е. на одном и том же оборудовании сильно деградирует в качестве по сравнении с игрой 19x19.
В то время как для интелектуальных алгоритмов, оперирующих обьектами и их связями, типа групп камней и их взаимного месторасположения, сложность вырастет пропорционально полиному небольшой степени от увеличения размера поля.
В этом плане человек пока ещё ведет в игре Го, за счет интеллектуального подхода игрок может победить брутфорс алгоритм при определенных условиях, в т.ч. выработать стратегию специально против него. В шахматах же такого шанса у него, похоже, уже нет.
Total votes 3: ↑3 and ↓0+3
UFO just landed and posted this here
UFO just landed and posted this here
Я бы сказал, что это влияние не зависит от размера доски. К тому же, это такое себе однобитное влияние — или работает лестница, или нет.
Я же имел в виду наличие неподалёку ацуми (плотностей/стенок), мойо и т.п. В этом смысле на локальную позицию могут значительно влиять только соседние локальные позиции, но не глобальная позиция по доске.
Это если говорить о чрезмерно больших размерах досок.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Спасибо за пост!

Кстати, с каким контролем времени они играли?
Total votes 1: ↑1 and ↓0+1
Полчаса времени + беёми 1 минута на ход. Относительно быстрая партия.
Total votes 1: ↑1 and ↓0+1
Всего четыре компьютера для обработки программы? А как же суперкомпьютеры, ibm, bluegene как это было с шахматами и Каспаровым?
Total votes 2: ↑1 and ↓10
Алгоритмы улучшились с тех пор. :) Если я не ошибаюсь знаменитый суперкомпьютер Deep Blue в свое время так и не обыграл Каспарова, а сделала это уже программа Fritz на обычном четырех-процессорном серваке.
Total votes 1: ↑1 and ↓0+1
Каспаров с горя ушел в политику после того как его обыграл компьютер?
Total votes 3: ↑1 and ↓2-1
Только я вижу связь с обработкой изображений, в частности, медианным фильтром?
Total votes 3: ↑2 and ↓1+1
Поломал голову немного и всё-таки сломал =). Сдаюсь. Что общего, по-вашему?
Total votes 1: ↑1 and ↓0+1
Скажу сразу, далее только предположения. Некоторые необходимые условия победы в го(японский вариант):
рядом с моей группой более нуля свобод, внутри окружения: (у каждого пустого пересечения рядом должно быть: (больше нуля моих камней, менее 3 свобод), у всех пустых суммарно свобод хотя бы на 4 меньше удвоенного числа пустых(два глаза — туннеля)). Пусть мои камни — черные пиксели, противника — белые, пустые — серые. Т.е. одна из стратегий победы состоит в построении структуры — вокруг каждого свободного: моих камней больше, чем — противника. Медианный фильтр берет значение пикселя, находящегося посередине упорядоченного множества окружающих(для го — четыре соседа), т.е. если большинство соседей — черные, то пиксель черный, и наоборот. Вообще, тут нужна маленькая модификация: если соседей поровну, то изменяем пиксель на противоположный; серые соседи не учитываются. Рассмотрим ситуацию простого захвата
_Х_
Х0Х
_Х_
Как бы мы не усложняли(предположение!) захватываемую группу, при многократном применении медианного фильтра захватываемая группа изменит цвет на цвет захватчика.
Т.е. применяя циклически фильтр ко всей доске получаем вероятного победителя.
С глазами небольшая неувязка, но, во-первых, модифицированная версия фильтра позволяет интерференцию волн захвата, а, во-вторых, я говорил про связь, а не про высшее мастерство.
Для точек, где нет глаз, область 8-связная, ситуация лучше.
Total votes 1: ↑1 and ↓0+1
Своеобразный аналог правила ко:
_Х0_->_0X_
Х0Х0->X0X0
_Х0_->_0X_
Разумеется, в го, как и в большинстве игр(почему не всех?), у первого(начинающего) игрока есть преимущество — «эффект неожиданности», что фильтр совершенно не учитывает.
This comment wasn’t rated yet0
Я не силён в го (более того, даже правил полных не знаю :)), но описываемое больше похоже на обычную эвристику в стиле Монте-Карло с простой функцией оценки позиции. Вы пробовали такое гонять против людей/ботов? Думаю, должны существовать реализации го, позволяющие писать своих ботов — проверьте, если нетрудно, мне очень интересно, как далеко оно сможет зайти.
This comment wasn’t rated yet0
«должны существовать реализации го» — Они есть тут. Бот для игры го — это не на один вечер, если и возьмусь, только после накопления должного уровня мотивации. «как далеко оно сможет зайти» — оно не сможет ходить:)
This comment wasn’t rated yet0
Всем привет из 2018-го. У нас тут уже программы людям скоро 4 камня форы давать начнут…
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Change theme settings

Your account

Sections

Information

Services

Support
© 2006–2024, Habr