Нет-нет :) Под словом «все» имел ввиду те дебюты, которые дают черным преимущество. Кроме 7-Д считал 3-Д, 6-Д, 9-Д и 11-Д. Короче все, без отрыва 3-го хода от черного камня. Здесь оговорюсь, считал ходы и наиболее длинные продолжения, рекомендованные в сборниках. Для меня было важно было определить, что нет решения более короткого, чем в 7-Д.
В отношении спорного национального происхождения игры. Оба слова Гомоку и Рэндзю японские. Исконно это была одна и та же игра и в Японии, и в Китае. Современные дебютные правила и фолы в Рэндзю придуманы только в XX веке японцами. Распространение в мире они получили где-то в конце 80-х. Поэтому, например, в детские годы, называя игру Рэндзю, играл по правилам близким к Гомоку без фолов. Все что касается традиций Рэндзю — сильное преувеличение. На самом деле игра по современным правилам Рэндзю очень молода.
Можно говорить об излишней сложности правил и неоправданных ограничениях в игре. Кай Сун, в частности, считает что для выравнивания шансов игроков в Гомоку достаточно использовать правило swap после первого хода черных.
Не встречал оценок длительности оптимальных игр для Рэндзю. Если найдете, пришлите, пожалуйста. Диагональные дебюты в Гомоку рассчитал все, некоторые даже с альтернативными ходами. Решаются быстрее 45 ходов.
В отношении уверенности — поиск комбинаций, как правило, дает сразу несколько альтернатив для окончаний в зависимости от порядка применения угроз. При глубине поиска более 15 ходов практически всегда встречаются альтернативы с вилкой 4x3. По моему опыту такие вилки находятся быстрее, если при альтернативном выборе идем по пути открытых троек, а не четверок.
В отношении Yixin, думаю, объясняется тем, что ее автор Кай Сун по национальности китаец. Смотрел интервью, в котором он рассказывает о своем вкладе в развитие именно Гомоку. Попробуйте китайцу сказать, что ушу это каратэ, или ханьфу это кимоно, или гомоку это рэндзю. :)
Это очень важно. Однако в описании фигур, в частности для открытой четверки, написано, что свои камни должны отсутствовать на соседних клетках. Возможно Вы были не совсем внимательны.
В реальной игре это меняет правила. Если не проверять наличие своих камней на соседних клетках, то построение длинного ряда считаем выигрышем.
В коде при поиске фигур по шаблонам это обязательно проверяется:
// Поиск выбранных фигур в строке
Line.prototype.findFigures = function (figures, type) {
...
// По черным камням
if ((probe & 2) > 0) {
...
// Нет черного каменя слева
&& (offset > 0 ? (stroke >> ((offset - 1) << 1)) & 2 : 0) === 0
// Нет черного камня справа
&& ((stroke >> ((offset + pattern.length) << 1)) & 2) === 0
...
}
// По белым камням
if ((probe & 1) > 0) {
...
// Нет белого каменя слева
&& (offset > 0 ? (stroke >> ((offset - 1) << 1)) & 1 : 0) === 0
// Нет белого камня справа
&& ((stroke >> ((offset + pattern.length) << 1)) & 1) === 0
...
}
По gomocup условия читал, смотрел код Yixin. Здесь действительно разные задачи. Для турнира важным ограничениям является время расчета, решение может быть приближенным, например, найден ход ведущий к наиболее рейтинговой позиции.
Моя программа, имею ввиду Java-версию, предназначена для нахождения полного решения позиции за заданное количество ходов. Ограничение по времени здесь не так важно. Здесь используется послойное решение — см. метод Vertex.compute (на Java). В программе есть альтернативный метод решения, основанный на алгоритме pn2-поиска, — см. метод Apex.compute (в интерфейсе можно заменить вызываемый метод). Этот алгоритм позволяет сократить число оцениваемых позиций, соответственно время поиска, для нахождения решения без ограничения числа ходов. Однако, для нахождения оптимальных решений он менее пригоден, так как склонен рассчитывать в первую очередь маловариантные позиции, которые редко приводят к быстрой победе. По моему опыту ход со скрытой угрозой позволяет победить быстрее, чем прямая атака.
Опубликованных полных решений (дерева ходов) не нашел. В своей задаче занимался не столько проверкой доказательства, сколько поиском оптимального решения. Важный результат — 35 ходов.
Про Terminator — хорошая программа, но довольно старая. По моей информации там не было ни полного решения, ни оптимального. Обсуждение этой темы см. здесь и пример выигрыша за белых здесь.
По стандартным правилам Гомоку построение длинного ряда не запрещено, в отличии от Рендзю, но победой не считается ни за белых, ни за черных. См., например, здесь wikipedia. Длинный ряд разрешен в так называемом «свободном» Гомоку на бесконечном поле. В некоторых разновидностях Гомоку для черных были запрещены вилки 3x3. Запрет вилок 4x4 есть только в Рендзю. Впрочем, эти ограничения не дают преимущества, а только создают сложности для играющего человека, но не для компьютера. Выше есть ссылка на подобную работу по Рендзю.
Спасибо! Действительно ошибка была в конвертации бинарного графа решений в JSON формат. Перепутал местами аргументы при сложении симметрий позиций. Двойная трансформация симметрий в решениях возникает редко, не удалось сразу обнаружить. Теперь все в порядке. Перед игрой потребуется очистить кэш браузера (Ctrl+Shift+Del).
Спасибо. Нейронные сети обычно используются для аппроксимации решения. Например, AlphaGo использует метод Монте-Карло чтобы избежать полного перебора. В этой задаче требовалось найти полное решение.
Думал, возможно вернусь к теме, если будет свободное время.
В 2001 году такую работу без учета регламентных правил проделали венгры Янус Вагнер и Истван Вираг. Прочитать можно здесь. Как ни странно оценка позиции и поиск комбинаций в Рендзю на компьютере выполняется быстрее, чем в Гомоку из-за меньшего числа допустимых вилок со стороны черных.
С отключенным Auto move и если делать ходы за черных такое возможно. Или были нарушены правила, например, шесть в ряд. Не исключаю также ошибок в демонстрационной javascript версии. Поэтому, если получиться в автоматическом режиме, пришлите, скриншот, пожалуйста.
В отношении спорного национального происхождения игры. Оба слова Гомоку и Рэндзю японские. Исконно это была одна и та же игра и в Японии, и в Китае. Современные дебютные правила и фолы в Рэндзю придуманы только в XX веке японцами. Распространение в мире они получили где-то в конце 80-х. Поэтому, например, в детские годы, называя игру Рэндзю, играл по правилам близким к Гомоку без фолов. Все что касается традиций Рэндзю — сильное преувеличение. На самом деле игра по современным правилам Рэндзю очень молода.
Можно говорить об излишней сложности правил и неоправданных ограничениях в игре. Кай Сун, в частности, считает что для выравнивания шансов игроков в Гомоку достаточно использовать правило swap после первого хода черных.
В отношении уверенности — поиск комбинаций, как правило, дает сразу несколько альтернатив для окончаний в зависимости от порядка применения угроз. При глубине поиска более 15 ходов практически всегда встречаются альтернативы с вилкой 4x3. По моему опыту такие вилки находятся быстрее, если при альтернативном выборе идем по пути открытых троек, а не четверок.
В отношении Yixin, думаю, объясняется тем, что ее автор Кай Сун по национальности китаец. Смотрел интервью, в котором он рассказывает о своем вкладе в развитие именно Гомоку. Попробуйте китайцу сказать, что ушу это каратэ, или ханьфу это кимоно, или гомоку это рэндзю. :)
В реальной игре это меняет правила. Если не проверять наличие своих камней на соседних клетках, то построение длинного ряда считаем выигрышем.
В коде при поиске фигур по шаблонам это обязательно проверяется:
По gomocup условия читал, смотрел код Yixin. Здесь действительно разные задачи. Для турнира важным ограничениям является время расчета, решение может быть приближенным, например, найден ход ведущий к наиболее рейтинговой позиции.
Моя программа, имею ввиду Java-версию, предназначена для нахождения полного решения позиции за заданное количество ходов. Ограничение по времени здесь не так важно. Здесь используется послойное решение — см. метод Vertex.compute (на Java). В программе есть альтернативный метод решения, основанный на алгоритме pn2-поиска, — см. метод Apex.compute (в интерфейсе можно заменить вызываемый метод). Этот алгоритм позволяет сократить число оцениваемых позиций, соответственно время поиска, для нахождения решения без ограничения числа ходов. Однако, для нахождения оптимальных решений он менее пригоден, так как склонен рассчитывать в первую очередь маловариантные позиции, которые редко приводят к быстрой победе. По моему опыту ход со скрытой угрозой позволяет победить быстрее, чем прямая атака.
Опубликованных полных решений (дерева ходов) не нашел. В своей задаче занимался не столько проверкой доказательства, сколько поиском оптимального решения. Важный результат — 35 ходов.
Про Terminator — хорошая программа, но довольно старая. По моей информации там не было ни полного решения, ни оптимального. Обсуждение этой темы см. здесь и пример выигрыша за белых здесь.
В 2001 году такую работу без учета регламентных правил проделали венгры Янус Вагнер и Истван Вираг. Прочитать можно здесь. Как ни странно оценка позиции и поиск комбинаций в Рендзю на компьютере выполняется быстрее, чем в Гомоку из-за меньшего числа допустимых вилок со стороны черных.