Комментарии 80
Наконец-то про игру ГО начали писать на хабре.
Сейчас интересуюсь данной тематикой и пытаюсь придумать и реализовать ИИ для гораздо менее популярной и исследованной игры «Точки». Интересно, что сложнее?
Сейчас интересуюсь данной тематикой и пытаюсь придумать и реализовать ИИ для гораздо менее популярной и исследованной игры «Точки». Интересно, что сложнее?
точки явно попроще, в го есть варианты отыграть полу-открытые захваченные области, а в точках любая территория обводится непрерывной линией
Ну я бы не сказал, что явно — это еще доказать нужно.
В точках зато размер окружения может быть гораздо больше, чем в Го, т.к. в ней допускаются пустые позиции, в отличие от Го. Ну и как следствие, точки являются более стратегической игрой, там размах обычно больше. А у ИИ проблемы со стратегическим планированием.
Все это анализировать надо.
В точках зато размер окружения может быть гораздо больше, чем в Го, т.к. в ней допускаются пустые позиции, в отличие от Го. Ну и как следствие, точки являются более стратегической игрой, там размах обычно больше. А у ИИ проблемы со стратегическим планированием.
Все это анализировать надо.
Вы явно не играли в го хотя бы на любительском уровне, пустые обведенные области в го допускаются и очень часто так и есть, если внутри области не построить 2 глаза то в ней не выжить и в неё не ходят, в Го сложнее тем что в ней стратегия переходит в тактику а тактика в стратегию. и в отличии от точек поле в го абсолютно динамично.
Да, наверное не играл. Но я понял о чем вы сказали.
Я вообще-то имел ввиду, что в Го нельзя уничтожить группу камней, если кроме них есть еще свободные позиции.
И в точках игра развивается более вяло, по сравнению с Го, поскольку нужно сразу начинать с глобала, чтобы не уйти в ничью. А в Го все начинается с краев и да, игра более динамичная и быстроразвивающаяся.
Я вообще-то имел ввиду, что в Го нельзя уничтожить группу камней, если кроме них есть еще свободные позиции.
И в точках игра развивается более вяло, по сравнению с Го, поскольку нужно сразу начинать с глобала, чтобы не уйти в ничью. А в Го все начинается с краев и да, игра более динамичная и быстроразвивающаяся.
Все же, настоятельно советую изучить го чуть глубже, чем «рассмотрел доску с камнями». Это очень серьезная игра с бесконечной глубиной.
Касательно жизни и сметри групп вообще нельзя ничего однозначно говорить. Количество вариантов там такое, что делать подобные заявления неразумно. Группа может иметь дыхательные пункты и тем не менее быть обреченной при правильной игре оппонента.
Касательно жизни и сметри групп вообще нельзя ничего однозначно говорить. Количество вариантов там такое, что делать подобные заявления неразумно. Группа может иметь дыхательные пункты и тем не менее быть обреченной при правильной игре оппонента.
Ещё важный момент — захваченные камни сразу снимаются с доски и это свободное место можно снова использовать (ко-борьба).
Ну это не совсем ко-борьба, ко-борьба это когда вынуждаешь противника делать невыгодный ход, потому что выгодный он не может сделать из-за правила ко. Что кстати тоже добавляет сложности :) А освобождённое место можно и без ко-борьбы использовать)
И вы не правы, ко-борьба это игра Ко, чаще всего на угрозы, не кто не кого не заставляет делать не выгодный ход, по своему названию не выгодных ход не сулит выгоды по этому игрок просто закроет Ко или отдаст, в замен получив что то другое.
Ту ситуацию что описали вы это Ко в начале партии его редко играют сразу.
Ту ситуацию что описали вы это Ко в начале партии его редко играют сразу.
Да, действительно, хотя бы из-за того, что в го есть ко, оно уже сложнее точек :) Ну, и по многим другим причинам тоже.
Смотря какое поле в точках, обе игры сложная задача для ИИ
Если сравнивать при одинаковых размерах полей.
Вероятнее всего вам интересно будет прочитать Игра «Точки». Методы и алгоритмы.
Это наверное первая серьезная статья, которую прочитывают люди, занимающиеся данной темой.
И написана она, кстати, Павлом Торгашовым, который есть на хабре :)
И написана она, кстати, Павлом Торгашовым, который есть на хабре :)
Как специалист по точкам, скажу Вам, что там очень много мини игр. И если знать как ходить, то даже казалось бы серьезный противник раскалывается на части :)
Я недавно писал ИИ для игры в гомоку (крестики-нолики до 5 в ряд), но с немного модифицированными правилами: игра идет не до первого зачеркивания, а до заполнения всего игрового поля. За каждое зачеркивание плюсуются очки. По окончании кто больше набрал очков, тот и победил. Мы в такую игру развлекались в студенчестве на бумаге, ибо до первого зачеркивания все было вообще легко и скучно.
Алгоритм на самом деле получился не очень сложный, но вполне себе сильный. Мне с ним очень тяжело соперничать, хотя опыт игры в такой вариант у меня приличный.
Алгоритм на самом деле получился не очень сложный, но вполне себе сильный. Мне с ним очень тяжело соперничать, хотя опыт игры в такой вариант у меня приличный.
НЛО прилетело и опубликовало эту надпись здесь
Есть еще «6 в ряд», справедливая для обоих игроков
Легко и просто было, потому что я всех обыгрывал, начиная либо крестиками либо ноликами. Поэтому мы слегка модифицировали правила, а стратегия при этом поменялась очень сильно, потому что пришлось думать не только о том как первому зачеркнуть, но и взвешивать что выгодней: зачеркнуть сейчас или поставить еще одну вилку, или залочить возможность поставить вилку сопернику и т.д. И вот в новой стратегии уже не так важно было как быстро ты поставишь первый 5 в ряд.
Записи партий Такемия Масаки
19x19 Нормальное игровое поле
Zen(5d)-Takemiya_Masaki(9p) 5 Камней
Zen(5d)-Takemiya_Masaki(9p) 4 Камня
9x9 маленькое игровое поле Ohashi_Hirofumi
20120317-Zen(5d)-Ohashi_Hirofumi(5p)
20120317-Ohashi_Hirofumi(5p)-Zen(5d)
19x19 Нормальное игровое поле
Zen(5d)-Takemiya_Masaki(9p) 5 Камней
Zen(5d)-Takemiya_Masaki(9p) 4 Камня
9x9 маленькое игровое поле Ohashi_Hirofumi
20120317-Zen(5d)-Ohashi_Hirofumi(5p)
20120317-Ohashi_Hirofumi(5p)-Zen(5d)
Очень давно находил довольно красивую программу/игру Dots — как понятно из названия это те самые точки. Но сейчас как ни пытался — найти заново именно ту не могу.
А вообще гугл даёт очень много вариантов реализации данной игры.
А вообще гугл даёт очень много вариантов реализации данной игры.
Базы эндшпилей в шахматах — это не ошибка?
Про дебютные таблицы слышал, а эндшпили, как мне кажется, можно и полностью рассчитывать.
Про дебютные таблицы слышал, а эндшпили, как мне кажется, можно и полностью рассчитывать.
Нет, не ошибка. ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B7%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D1%8D%D0%BD%D0%B4%D1%88%D0%BF%D0%B8%D0%BB%D1%8F — описание баз данных эндшпиля.
НЛО прилетело и опубликовало эту надпись здесь
Да, и еще интересный вопрос:
а дан точно присваивается по результатам всего одной партии?
а дан точно присваивается по результатам всего одной партии?
НЛО прилетело и опубликовало эту надпись здесь
Разница между профессиональными данами не соответствует количеству камней форы, считается что разница между 1д и 9д около 3-х камней, так что можно сказать, что программа играет на уровне очень сильного любителя. Но тем не менее это все равно очень круто… Когда я начинал играть лет 5 назад, программы даже на 1-й разряд не играли, а сейчас получается уже на уровне гроссмейстера могут играть.
НЛО прилетело и опубликовало эту надпись здесь
Странно, что даны идут на понижение. В Японских боевых искусствах отсчет идет от «кю» до «дан», к примеру от 10 кю до 1 кю и затем — 1 дан, 2 дан, 3 дан… Неужели в «го» — традиции решили подменить?
Не подскажете хорошую реализацию Го для айпада? Почитал, понравилось — хочу поиграть.
SmartGo для игры в одиночку (ещё и задачек по го содержит кучу), Tetsuki для игры по сети.
CrazyStone должен неплохо играть. На KGS у него почти 6 дан.
Хотя, конечно, на мобильном устройстве он будет играть послабее.
Хотя, конечно, на мобильном устройстве он будет играть послабее.
Где-то была клёвая картинка по поводу текущей ситуации с уровнем игры компьютера против человека — там еще Го были намного выше шахмат и было много других игр. Не могу найти — кто-то подскажет?
Между прочим, недавно появилась программа (под названием Xuan Xuan Go), которая решает локальные позиции лучше профессионалов. Она даже нашла больше десятка ошибок в классических задачках, придуманных профессиональными игроками.
Так что прогресс в области алгоритмизации го однозначно не топчется на месте :)
Так что прогресс в области алгоритмизации го однозначно не топчется на месте :)
Очень круто. Особенно круто то, что использовался сравнительно небольшой кластер, что косвенно указывает на то, что программа не основана на Монте-Карло (детальной инфы по программе пока не нашел, может кто-то в курсе как она работает?). А это большой прорыв, монте-карло алгоритмы все-таки тупой брутфорс, а тут (возможно) действительно по настоящему интеллектуальный алгоритм…
Занятно, что автор на самом деле ещё и является тем самым знаменитым игроком со своим крайне специфическим «космическим» стилем игры ;)
А ещё было было бы очень интересно посмотреть на игру без форы. Даже если программа играет действительно сильно и вначале будет выигрывать, то профи игрок после несколько игр наверняка сможет подстроиться под её стиль игры и найти контрмеры. И вот тут вопрос — сумеет ли программа забороть эти контрмеры… Если да — поздравляю всех с сингулярностью ;)
Занятно, что автор на самом деле ещё и является тем самым знаменитым игроком со своим крайне специфическим «космическим» стилем игры ;)
А ещё было было бы очень интересно посмотреть на игру без форы. Даже если программа играет действительно сильно и вначале будет выигрывать, то профи игрок после несколько игр наверняка сможет подстроиться под её стиль игры и найти контрмеры. И вот тут вопрос — сумеет ли программа забороть эти контрмеры… Если да — поздравляю всех с сингулярностью ;)
Насколько я знаю, все сильные программы используют метод монте-карло. Естественно, он сочетается с другими алгоритмами — например, алгоритмами оценки позиции. При этом, варианты просчёта в монте-карло тоже выбираются не случайным образом, а наиболее перспективные.
При этом, в фусэки (начале игры) все программы пользуются базами фусэки и дзёсэки (стандартных розыгрышей в углах). Также, есть и базы стандартных форм групп камней, которые составляются при помощи самообучающихся алгоритмов.
Так что нельзя говроить о том, что используется «чистый метод монте-карло». В этом случае программа вряд ли смогла бы играть сильнее 15-го кю.
Но в той или иной степени монте-карло однозначно используется.
К сожалению, ссылок дать не могу. Это всё из памяти, я по этой теме много чего читал какое-то время назад.
При этом, в фусэки (начале игры) все программы пользуются базами фусэки и дзёсэки (стандартных розыгрышей в углах). Также, есть и базы стандартных форм групп камней, которые составляются при помощи самообучающихся алгоритмов.
Так что нельзя говроить о том, что используется «чистый метод монте-карло». В этом случае программа вряд ли смогла бы играть сильнее 15-го кю.
Но в той или иной степени монте-карло однозначно используется.
К сожалению, ссылок дать не могу. Это всё из памяти, я по этой теме много чего читал какое-то время назад.
Вот есть такой документ про генерирование ходов из паттернов и других эвристик для последующего использования их в алгоритме UCT.
Нашел, таки Монте-Карло ;(
У таких алгоритмов существенный недостаток — при увеличении размера поля сложность расчетов растет очень сильно. На поле 25x25 программа опять будет сливать человеку, если не научиться играть интеллектуально, без брутфорса.
У таких алгоритмов существенный недостаток — при увеличении размера поля сложность расчетов растет очень сильно. На поле 25x25 программа опять будет сливать человеку, если не научиться играть интеллектуально, без брутфорса.
Правда, поля 25х25 нет :) Ну, то есть, стандартное поле — 19х19.
Кстати, не думаю, что для программы будет большая разница, 19х19 поле или 25х25. Начало игры точно так же можно будет играть по базам, а локальные позиции вряд ли будут намного сложнее.
И опять же, в этих программах много разных алгоритмов заложено. Монте-Карло — это всего лишь метод оптимизированного перебора вариантов, когда их слишком много.
Кстати, не думаю, что для программы будет большая разница, 19х19 поле или 25х25. Начало игры точно так же можно будет играть по базам, а локальные позиции вряд ли будут намного сложнее.
И опять же, в этих программах много разных алгоритмов заложено. Монте-Карло — это всего лишь метод оптимизированного перебора вариантов, когда их слишком много.
Официального поля нет, разумеется, но Го такая особенная игра, что её можно играть и на 1000x1000.
Разница для брутфорса как раз будет существенная, площадь поля определяет кол-во возможных ходов, увеличения площади в 4 раза увеличит среднюю длительность игры (общее кол-во ходов за игру) приблизительно во столько же, плюс на каждый ход потребуется перебрать пропорционально большее кол-во вариантов, можете сами прикинуть вырастет сложность перебора, еквивалентного оному на поле 19x19…
Разумеется, для человека сложность тоже возрастет, но не на многие порядки, а всего лишь в разы.
Разница для брутфорса как раз будет существенная, площадь поля определяет кол-во возможных ходов, увеличения площади в 4 раза увеличит среднюю длительность игры (общее кол-во ходов за игру) приблизительно во столько же, плюс на каждый ход потребуется перебрать пропорционально большее кол-во вариантов, можете сами прикинуть вырастет сложность перебора, еквивалентного оному на поле 19x19…
Разумеется, для человека сложность тоже возрастет, но не на многие порядки, а всего лишь в разы.
Вообще, это очень интересная тема. Мне кажется, что если брать такие крайности, как 1000х1000, то там игра распадётся на множество несвязанных друг с другом позиций, которые друг на друга практически не влияют.
19х19 — это вообще, как мне кажется, оптимальный размер доски, потому что там практически каждый поставленный камень всё ещё влияет на ситуацию в целом.
Так вот, мне кажется, что если взять доски 1000х1000 и 2000х2000, то что программе, что человеку будет одинаково сложно играть на любой из таких больших досок. Увеличится только время партии, просто потому, что нужно будет сделать больше ходов.
Их этого примера, вроде как, следует вывод, что зависимость между сложностью игры и размером доски, как минимум, не линейная.
19х19 — это вообще, как мне кажется, оптимальный размер доски, потому что там практически каждый поставленный камень всё ещё влияет на ситуацию в целом.
Так вот, мне кажется, что если взять доски 1000х1000 и 2000х2000, то что программе, что человеку будет одинаково сложно играть на любой из таких больших досок. Увеличится только время партии, просто потому, что нужно будет сделать больше ходов.
Их этого примера, вроде как, следует вывод, что зависимость между сложностью игры и размером доски, как минимум, не линейная.
Не линейная, разумеется. Что я пытаюсь сказать, так это то, что разные типы алгоритмов будут по разному реагировать на увеличение поля. Для брутфорсовых небольшое увеличение размера поля сильно увеличивает требуемую мощность при сохранении качества перебора (глубины, % покрытия и т.д.), т.е. на одном и том же оборудовании сильно деградирует в качестве по сравнении с игрой 19x19.
В то время как для интелектуальных алгоритмов, оперирующих обьектами и их связями, типа групп камней и их взаимного месторасположения, сложность вырастет пропорционально полиному небольшой степени от увеличения размера поля.
В этом плане человек пока ещё ведет в игре Го, за счет интеллектуального подхода игрок может победить брутфорс алгоритм при определенных условиях, в т.ч. выработать стратегию специально против него. В шахматах же такого шанса у него, похоже, уже нет.
В то время как для интелектуальных алгоритмов, оперирующих обьектами и их связями, типа групп камней и их взаимного месторасположения, сложность вырастет пропорционально полиному небольшой степени от увеличения размера поля.
В этом плане человек пока ещё ведет в игре Го, за счет интеллектуального подхода игрок может победить брутфорс алгоритм при определенных условиях, в т.ч. выработать стратегию специально против него. В шахматах же такого шанса у него, похоже, уже нет.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Я бы сказал, что это влияние не зависит от размера доски. К тому же, это такое себе однобитное влияние — или работает лестница, или нет.
Я же имел в виду наличие неподалёку ацуми (плотностей/стенок), мойо и т.п. В этом смысле на локальную позицию могут значительно влиять только соседние локальные позиции, но не глобальная позиция по доске.
Это если говорить о чрезмерно больших размерах досок.
Я же имел в виду наличие неподалёку ацуми (плотностей/стенок), мойо и т.п. В этом смысле на локальную позицию могут значительно влиять только соседние локальные позиции, но не глобальная позиция по доске.
Это если говорить о чрезмерно больших размерах досок.
Сингулярность все ближе и ближе…
Спасибо за пост!
Кстати, с каким контролем времени они играли?
Кстати, с каким контролем времени они играли?
Всего четыре компьютера для обработки программы? А как же суперкомпьютеры, ibm, bluegene как это было с шахматами и Каспаровым?
Каспаров с горя ушел в политику после того как его обыграл компьютер?
Только я вижу связь с обработкой изображений, в частности, медианным фильтром?
Поломал голову немного и всё-таки сломал =). Сдаюсь. Что общего, по-вашему?
Скажу сразу, далее только предположения. Некоторые необходимые условия победы в го(японский вариант):
рядом с моей группой более нуля свобод, внутри окружения: (у каждого пустого пересечения рядом должно быть: (больше нуля моих камней, менее 3 свобод), у всех пустых суммарно свобод хотя бы на 4 меньше удвоенного числа пустых(два глаза — туннеля)). Пусть мои камни — черные пиксели, противника — белые, пустые — серые. Т.е. одна из стратегий победы состоит в построении структуры — вокруг каждого свободного: моих камней больше, чем — противника. Медианный фильтр берет значение пикселя, находящегося посередине упорядоченного множества окружающих(для го — четыре соседа), т.е. если большинство соседей — черные, то пиксель черный, и наоборот. Вообще, тут нужна маленькая модификация: если соседей поровну, то изменяем пиксель на противоположный; серые соседи не учитываются. Рассмотрим ситуацию простого захвата
_Х_
Х0Х
_Х_
Как бы мы не усложняли(предположение!) захватываемую группу, при многократном применении медианного фильтра захватываемая группа изменит цвет на цвет захватчика.
Т.е. применяя циклически фильтр ко всей доске получаем вероятного победителя.
С глазами небольшая неувязка, но, во-первых, модифицированная версия фильтра позволяет интерференцию волн захвата, а, во-вторых, я говорил про связь, а не про высшее мастерство.
Для точек, где нет глаз, область 8-связная, ситуация лучше.
рядом с моей группой более нуля свобод, внутри окружения: (у каждого пустого пересечения рядом должно быть: (больше нуля моих камней, менее 3 свобод), у всех пустых суммарно свобод хотя бы на 4 меньше удвоенного числа пустых(два глаза — туннеля)). Пусть мои камни — черные пиксели, противника — белые, пустые — серые. Т.е. одна из стратегий победы состоит в построении структуры — вокруг каждого свободного: моих камней больше, чем — противника. Медианный фильтр берет значение пикселя, находящегося посередине упорядоченного множества окружающих(для го — четыре соседа), т.е. если большинство соседей — черные, то пиксель черный, и наоборот. Вообще, тут нужна маленькая модификация: если соседей поровну, то изменяем пиксель на противоположный; серые соседи не учитываются. Рассмотрим ситуацию простого захвата
_Х_
Х0Х
_Х_
Как бы мы не усложняли(предположение!) захватываемую группу, при многократном применении медианного фильтра захватываемая группа изменит цвет на цвет захватчика.
Т.е. применяя циклически фильтр ко всей доске получаем вероятного победителя.
С глазами небольшая неувязка, но, во-первых, модифицированная версия фильтра позволяет интерференцию волн захвата, а, во-вторых, я говорил про связь, а не про высшее мастерство.
Для точек, где нет глаз, область 8-связная, ситуация лучше.
Своеобразный аналог правила ко:
_Х0_->_0X_
Х0Х0->X0X0
_Х0_->_0X_
Разумеется, в го, как и в большинстве игр(почему не всех?), у первого(начинающего) игрока есть преимущество — «эффект неожиданности», что фильтр совершенно не учитывает.
_Х0_->_0X_
Х0Х0->X0X0
_Х0_->_0X_
Разумеется, в го, как и в большинстве игр(почему не всех?), у первого(начинающего) игрока есть преимущество — «эффект неожиданности», что фильтр совершенно не учитывает.
_Х0_->_0X_
Х0Х0->0Х0Х
_Х0_->_0X_
Х0Х0->0Х0Х
_Х0_->_0X_
Я не силён в го (более того, даже правил полных не знаю :)), но описываемое больше похоже на обычную эвристику в стиле Монте-Карло с простой функцией оценки позиции. Вы пробовали такое гонять против людей/ботов? Думаю, должны существовать реализации го, позволяющие писать своих ботов — проверьте, если нетрудно, мне очень интересно, как далеко оно сможет зайти.
Всем привет из 2018-го. У нас тут уже программы людям скоро 4 камня форы давать начнут…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Программа Zen обыграла в го профессионального игрока 9 дана с форой в 4 камня