Всем привет. Я не нашел подходящего раздела, чтобы задать интересующий меня вопрос,
поэтому зашел сюда.
   Не могу назвать себя любителем игры Гомоку, тем не менее испытываю к ней огромный интерес.
В чем заключается этот интерес, вы можете узнать из моей статьи, посвященной вопросу формализуемости игр, в которой Гомоку занимает центральное место Статья
   Сама статья вряд ли покажется вам увлекательной, но если вы прочитаете несколько последних предложений, то поймете, чем вызван мой интерес Окончание
   Вопрос простой : гарантирована ли победа игроку, который ходит первым (при условии, что оба играют идеально).
Я имею в виду "чистый" вариант этой игры, без наворотов типа фолов и свопов.
В поисках ответа я избороздил просторы интернета, но результаты этих поисков меня не устраивают.
Первый ход, понятное дело, дает преимущество. Большинство источников говорят о том, что оно фатально для второго игрока. Но я не нашел этому ни одного четкого обоснования - все на уровне догадок и предположений.
Я понимаю, что первый ход дает большое преимущество, гораздо большее, чем, например, в шахматах - именно поэтому правила пришлось наворачивать и появилось Рендзю. Но ведь "большое" и "абсолютное" -
это разные вещи, и мне бы очень хотелось знать, как оно на самом деле.
   Буду благодарен, если кто-нибудь просветит мое невежество в этом вопросе.

преимущество именно что абсолютное, поскольку есть доказанный выигрыш, более того сильная программа найдёт его за чёрных даже с фолами
условно говоря есть всего два варианта второго хода (в рэндзю применяется "скозная нумерация" то есть второй ход это первый ход белых) (остальные совсем просты)
- по вертикали - этот дебют называется в рэндзю цветок или 4в
и
- по диагонали- этот дебют называется в рэндзю бухта или 7д

оба дебюта разобраны в дебютниках рэндзю с ограничениями на черных (то есть крестиков) и не смотря на это в обоих случаях черные имеют победу.
могу отослать, например, сюда http://renju.gambler.ru/?page=newbie в Сакате есть какой-то разбор обоих дебютов, причём в самом начале, хотя для человека далекого от рэндзю он наверно может показаться недостаточным, как не шахматисту надо думать над матом двумя слонами, в то время как опытный игрок делает это на автомате...

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

может кто-то и делал всевозможный анализ до постановки пятёрки крестиками - но сомневаюсь... это вряд ли кому-то нужно...

с уважением, Алексей.

Отредактировано Fracass (2009-06-23 22:22:43)

из вашей статьи...

не верное утверждение... явно меньше 100...

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

Есть некоторая разница между моими умозаключениями и моим субъективным отношением к шашкам.
Не стоит слишком всерьез принимать "лирические отступления", которые я иногда делаю, чтобы статья не показалась совсем уж скучной. А что касается логических обоснований, то я подошел к этому вопросу довольно скурпулезно. Размер поля не меняет сути игры, которая остается неизменной хоть для поддавков ( даже если поставить "с ног на голову" цель игры ). Я использую понятие игрового разнообразия, которое мы хоть и не можем измерить, скажем, в байтах, но можем оценить интуитивно. Здесь, конечно, возможны разногласия - меня действительно удивляет, как шашки могут показаться разнообразнее шахмат ? Но ведь я пытаюсь найти подход для оценки игры не по принципу "нравится - не нравится", а с объективных позиций. Если это можно выразить числом, значит я могу это сравнить с другим числом и дать объективную оценку результату : больше, меньше или равно. Количество всех (!) вариантов развития игры в шашки - что-то порядка 17 нулей, поэтому 50-ти компьютерам удалось их перебрать за 20 лет. Я склонен доверять этим данным, поскольку они не противоречат моим представлениям. Мне ведь приходилось играть в шашки, но мне они не понравились тем, что там слишком мало места. Теперь я могу обосновать причину такой " клаустрофобии" : 18-ти значное число - это слишком тесное пространство игровых ситуаций. Конечно, для любого человека это достаточно много, чтобы не ощущать этого предела, поэтому я вполне могу представить, как в нее можно шпилить всю жизнь, так и не наигравшись. Сам я, например, фанат преферанса. Количество всех возможных раскладов в этой игре - 16-ти значное число - формально она где-то в 100 раз примитивней шашек, но меня это нисколько не смущает.
Я не могу дать абсолютную оценку шашкам, но могу сравнить ее с другой игрой - например такой, как уголки.        Я довольно регулярно в нее играю, то есть имею представление об особенностях ее стратегии. Кроме того, у меня есть представление о возможностях современных информационных технологий. Так вот, я могу с уверенностью утверждать, что если на шашки ушло 20х50=1000 компо-лет, так сказать, то на уголки не хватит и миллиона.
Я понимаю, что игру можно наворотить такими правилами, что и триллиона не хватит. Но ведь шашки и уголки находятся в равных условиях в этом отношении. Физически фигуры идентичны, их количество тоже равно
( по крайней мере я играю по правилам для 4*3 фигуры, а не 3*3, как в классическом варианте). Чтобы все было честно, поле тоже берем стандартное - 8х8. Правила шашек и углов можно считать одинаково лаконичными - в них нет никаких наворотов. Выходит, что при равных "начальных условиях" углы однозначно рулят в плане разнообразия. Конечно, я не могу привести этому строгое обоснование, но субъективно не понимаю, как можно играть в шашки, если есть такая игра, как уголки.
Интересно было бы услышать ваше мнение : во что сложнее играть - в шашки или в углы ?
Насколько это серьезная игра ? Полагаю, что вы хорошо знакомы со многими играми на доске.

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

Спасибо Вам, Алексей, за то что предоставили мне информацию в такой удобочитаемой форме. Разбирать доказательства, коих несколько вариантов, причем это все английском - занятие довольно утомительное и мне проще самому написать программу, чтобы в этом убедиться. В применении к вопросу, затронутом в статье, это означает, что "игра по умолчанию" должна называться не "5 в ряд", а "6 в ряд".

  Отсюда вопрос : есть ли у кого-нибудь опыт игры в "6 в ряд" ? Я предполагаю, что если оба игрока играют достаточно хорошо, то партия будет слишком длинной и во многих случаях будет заканчиваться ничьей по взаимному согласию. Или все-таки в "6 в ряд" играть вполне приемлемо ? Может даже, черные гарантированно выигрывают на 1000-м ходу, если играют безошибочно ? Но это, конечно, не проверишь. Мне интересно, из каких соображений пришлось наворачивать правила гомоку вместо того, чтобы слегка изменить цель и играть до шести ?

  Тут я вижу 2 принципиальных варианта :

1. Играть до шести не интересно, поскольку приходится рассчитывать только на грубую ошибку соперника.
2. Играть до шести интересно, но рендзю интереснее тем, что там больше нюансов, возникающих из-за асимметрии правил для игроков.

Какому из них вы бы отдали предпочтение ?

С точки зрения объективной качественной оценки, примитивность игры и примитивность ее правил - это не только
разные вещи, но и противоположные. Собственно, это два базовых критерия оценки, все остальные либо следуют из них, либо не столь значимы. Приведу определение, от которого я отталкиваюсь в своих рассуждениях :
Наиболее удачной будет та игра, которая  наиболее оптимально сочетает в себе лаконичность правил с разнообразием игровых ситуаций.
Игра "5 в ряд" примечательна тем, что ее правила настолько просты, что невозможно придумать игру, в которой они были бы еще проще. То есть требование лаконичности правил здесь соблюдено на все 100. Но поскольку черные, как оказалось, имеют абсолютное преимущество, приходится делать поправку, чтобы сохранился смысл игры. Заменяя "5" на "6" мы изменяем цель, но не увеличиваем количество информации, как если бы мы изменили правила. В конце концов не важно, 5 это или 6, можно обозначить это число буквой N и сформулировать задачу так : найти число N, начиная с которого игра " N в ряд" будет иметь смысл, т.е. первый ход не будет гарантировать черным абсолютного преимущества. То, что методом тыка определили, что это число больше пяти ничего не    значит - метод тыка не поможет решить эту задачу. Возможно ли найти аналитический способ доказать или опровергнуть, что N=6 ? Формулировка задачи проста, как и теоремы о простых числах, которая, кстати, до сих пор не доказана. Во всяком случае а приори можно полагать, что есть такое число N, начиная с которого игра "N в ряд" будет бесконечно разнообразной и при этом осмысленной. И тогда мы имеем
Бесконечное разнообразие игры с самыми примитивными правилами из всех возможных

Примитивность правил - это то, что "делает честь" любой игре, а не наоборот. Если предельная простота правил делает игру беспредельно разнообразной - согласитесь, здесь есть о чем задуматься

Я тут по ходу отвлек вас от исходной темы, но могу перечислить основные критерии, которые желательно учитывать при выборе того или иного варианта правил Гомоку :

1. Лаконичность.
2. Разнообразие, непредсказуемость игровых ситуаций, обусловленных данными правилами.
3. Стремление к "равноправию" возможностей для черных и белых.

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

Отредактировано axby (2009-06-24 17:01:26)

Уважаемый автор темы.Можно я тож немножко встряну. Как Вы увлеклись голыми цифрами, количесвом вариантов и т.д.. Но есть еще например в гомоку существующие регламенты, которые позволяют достичь некоторого уравнения позиции по крайней мере в дебюте. За счет этого в гомоку при существующей простоте правил, благодаря дебютным регламентам по крайней мере нет выигрышной стратегии ни  для одной из сторон. Хотя конечно определенное преимущество все же есть, Но ведь например в шахматах у белых тоже есть дебютное преимущество.
Больше все в этом плане повезло как нистранно шашкам. Там такого преимущества очевидно нет. К тому же шашечная партия очень сложна в плане оценки позициии, иногда опытный мастер шашечной игры не вполне правильно может оценить возникшую позицию на доске. В шахматах, гомоку, рэндзю, в плане оценки позиции все гораздо проще.
Опыт в гомоку на доске 19 на 19 и 6 в ряд у многих игроков гомоку конечно есть. В том числе и у меня. Игра не стала от этого сложнее и интереснее.

Боюсь, что на это что у вас уйдет не один год
Голландский математик Виктор Аллис для получения своих результатов нанимал программистов и использовал японские наработки. Что существенно упростило задачу.

Перевод его статьи на русский (allis1994.rar), кстати, должен быть на 
http://forum.sources.ru/index.php?showtopic=146870
(требуется регистрация)

Еще можете скачать с
сайта "5 stones"
программу с названием Gomoku Terminator. И попробовать сделать с ней хотя бы ничью.

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

Отредактировано expert (2012-02-26 22:25:25)

Врядли. В гомоку тоже не все позиции возможны (например,  с несколькими построенными "пятерками"). Хотя в блице и такое случается

Число Game-tree complexity (объем дерева вариантов)   225^30 ~ 10^70 автор оценивает как среднее число возможных ходов в позиции (225)
возв. в степень средняя длина партии (30).

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

Нечисто с этим Аллисом.
1) Подозрительно маленькое количество узлов в оптимальном дереве.
2) Отсутствие в открытом доступе базы с оптимальным деревом.
3) Неизвестная судьба программы Victoria
4) Отсутствие дальнейших шагов в этом направлении. (Аллис переключился на другие игры.)

Отредактировано Pavlovsky (2009-08-07 13:08:22)