Pull to refresh

Comments 18

Чтобы не путаться с терминами, давайте договоримся, что сторона, начинающая партию называется сенте, а защищающаяся сторона готэ.


Ну да, с такими терминами стало значительно проще. =)

По теме:
1. Выйгранной партия считается когда съёли короля?
2. У фигур есть какие-то графические обозначения? По себе почувствовал, если досконально не знаешь правил — начать играть будет невозможно.
1. Да партия заканчивается, когда съедают короля, но т.к. игра японская, то существуют определённые традиции. Крайне редко игру доводят до такого момента, чаще всего игрок сдаётся за несколько ходов до мата.
2. В игре фигуры обозначаются иероглифами, в которых разобраться ещё сложнее, чем в буквенных обозначениях.
В шахматах сейчас тоже часто не доходят до конца, и сдаются.
В последнем предложении всплывают некие «полноценные сёги». А это, стало быть, какой-то упрощённый вариант игры? В чём отличие?
Да. Я ещё в самом начале поста написал, что пишу программу для игры в упрощённый вариант. В полноценных сёги сражение идёт на доске 9 на 9, и у каждой стороны по 9 пешек, по 2 золота и серебра, и, помимо описанных фигур, есть ещё стрелы и кони.
это одна из сложнейших игр, и лучшие компьютерные программы по-прежнему не могут победить сильнейших игроков-людей

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

Да и метод монте-карло так или иначе используется во всех ии где пространство слишком велико для детерминированного поиска. Например, в покере. Да даже в шахматном ии, я уверен, есть подзадачи которые эффективно решаются именно методом монте-карло.

PS: Я это все не к тому, чтобы выяснять кто же сложнее там и круче. Просто такое вот дежа-вю. Даже цитата с википедии какбэ намекает.
Среди множества настольных игр, го выделяется ещё и тем, что она оказалась наиболее сложной для компьютера.
Го сложна в первую очередь масштабами. Доска имеет размер 19х19; при игре камни снимаются очень редко, так что конфигурация постоянно усложняется: «Если в шахматах в начальной позиции существует 20 разных ходов, то в го — 361. Дерево вариантов с каждым ходом растет стремительно: так, если в шахматах после четвертого хода может возникнуть около 100 тысяч позиций, то в го — более 16 миллиардов»

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

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

По поводу уменьшения количества ответных ходов: это конечно имеет место, но как мне кажется, оно очень мало влияет на качество игры бота.

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

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

Собственно зачем я тут распинаюсь? Мне хотелось бы услышать от вас, в чем именно заключается ключевое отличие рассчета в сёги от шахмат. Я понимаю, что в статье вы затронули вопросы переворота, но хотелось бы услышать что-то большее :)

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

Но реализовали хотя бы технику хеширования Зобриста, а то статья коротковатой получилась. По идее она здесь себя будет хорошо проявлять, потому что поле небольшое. Если что не понятно — обращайтесь ко мне :)
что-то со ссылкой :-) или там просто на вики?
Вы, наверное, и списки ходов быстрой сортировкой упорядочиваете?
А если серьёзно, меня всегда немного удивляли люди, которые в простенькие по сути задачи пытаются впихнуть все известные алгоритмы.
О способе сортировки ходов рассказывать не нужно — сортировка итак хорошо известная вещь, к тому же простая.

Простенькая задача? А может тогда и альфа-бета отсечение делать не нужно и сортировку?

Может для доски 5*5 она и простенькая, но для большей доски уже нужно будет изобретать что-то новое.

Просто вы описываете вещи, которые в общем-то много где расписаны на русском языке. Это конечно хорошо, но хотелось бы чего-нибудь нового. А впихнуть все известные вещи я не старался и не хотел вас обижать.
Only those users with full accounts are able to leave comments. Log in, please.