Гомоку - Gomoku

Гомоку
Renju.jpg
Жанр (ы)Настольная игра
Абстрактная стратегическая игра
Игроки2
Время установкиМинимальный
Случайный шансНикто
Возрастной диапазон4+
Требуются навыкиСтратегия, тактика

Гомоку, также называемый Пять в ряд, является абстрактная стратегия настольная игра. Традиционно в него играют Идти фигуры (черные и белые камни) на доске го. В нее можно играть на доске 15 × 15.[1] или доску 19 × 19.[2] Поскольку фигуры обычно не перемещаются и не удаляются с доски, Гомоку также можно играть как игра с бумагой и карандашом. Игра известна в нескольких странах под разными названиями.

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

Источник

Гомоку существует в Японии с Реставрация Мэйдзи.[3] Название «Гомоку» происходит от японский язык, в котором он обозначен как гомокунарабе (五 目 並 べ). Идти средства пять, моку это встречное слово за шт и нарабе средства расстановка. Игра также популярна в Корея, где это называется омок (오목 [五 目]), имеющий ту же структуру и происхождение, что и японское имя.

В девятнадцатом веке игра была завезена в Британию, где была известна как Go Bang, считается искажением японского слова гобан, говорят, адаптированы с китайского ки пан (qí pán) "go-board".[4]

Официальные правила

Помимо множества вариаций по всему миру, Swap2 правило (на основе "свопа" из Рэндзю ) в настоящее время адаптирован для турниров среди профессиональных игроков, включая чемпионат мира по гомоку.

В правиле Swap2 первый игрок начинает с размещения трех камней (2 черных и 1 белый, если черный идет первым) на доску. Затем второй игрок выбирает один из трех вариантов: играть черным, играть белым и поместить еще один камень или положить еще два камня и позволить первому игроку выбрать цвет.[5][6] По сути, это немного более сложный правило пирога.

Swap2 решает проблему преимущества первого хода.

Вариации

Большинство вариантов основаны на Гомоку в свободном стиле или же Стандартный гомоку.

  • Гомоку в свободном стиле для победы требуется ряд из пяти или более камней.
  • Стандартный гомоку для победы требуется ряд из пяти камней: ряды из шести и более камней, называемые надводки, не в счет.

Необязательные («домашние») правила

У черных (игрока, который делает первый ход) давно было известно, что они имеют большое преимущество, еще до того, как Л. Виктор Аллис доказал, что черные могут форсировать победу (см. Ниже). Таким образом, разыгрывается ряд вариантов с дополнительными правилами, направленными на уменьшение преимущества черных.

  • Правило три и три запрещает ход, который одновременно формирует два открытых ряда по три камня (ряды, не заблокированные камнем противника с обоих концов).
  • Правило четыре и четыре запрещает ход, который одновременно формирует два ряда по четыре камня (открытые или нет).
  • В качестве альтернативы, гандикап может быть предоставлен таким образом, что после того, как будет сделана первая игра «три и три», противник может поставить два камня в свой следующий ход. Эти камни должны блокировать тройку соперников.
  • Усилия по повышению справедливости за счет уменьшения преимущества первого хода включают правило замена, обобщается как "swap- (Икс,у,z) "и характеризуемый как частично составная и частично повторяющаяся версия правило пирога («один человек нарезает; другой выбирает»): один игрок кладет на доску Икс камни первого движущегося цвета и меньшего числа у камни второго по ходу цвета («разрезание» в метафоре пирога); другой игрок имеет право выбирать между а) игра с начальной позиции, и в этом случае выбирающий игрок также имеет право выбрать, какой цвет играть, и б) размещение z (обычно [(x - y) + 1]) больше камней на доске в местах по выбору этого игрока («пересечение» в метафоре пирога, с ограничениями, созданными существующей настройкой доски, сродни ограничениям, возникающим из существующих срезов в пирог), и в этом случае бывший игрок имеет право выбирать, на какой цветной стороне играть.

Конкретные варианты

  • Рэндзю играется на доске 15 × 15, с правилами трех и трех, четырех и четырех, и оверлейных линий, применяемых только к черным, и с правилами открытия, некоторые из которых следуют замена шаблон.
  • В Каро (также называемый гомоку +, популярный среди вьетнамцев), у победителя должна быть верхняя линия или непрерывный ряд из пяти камней, которые нельзя блокировать на обе заканчивается (надстрочные линии не распространяются на это правило). Это делает Гомоку более сбалансированным и дает белым больше сил для защиты.
  • Омок играется так же, как и в стандартный гомоку; однако он играется на доске 19 × 19 и включает правило три и три. В надводки правила, не в счет.
  • Нинуки-рэндзю или же Ву вариант, который добавляет в игру захват; он был опубликован в США в несколько упрощенном виде под названием рэндзю.

Теоретические обобщения

  • м,п,k-игры площадь обобщение гомоку на доску с м×п перекрестки и k подряд нужно было выиграть.
  • Соединять(м,п,k,п,q) игры другие обобщение гомоку на доску с м×п перекрестки, k подряд нужно побеждать, п камни для каждого игрока, и q камни, которые первый игрок разместит только на первый ход. Каждый игрок может играть только на самом нижнем незанятом месте в столбце. В частности, Connect (м,п, 6,2,1) называется Подключить6.

Пример игры

Первая игра

Эта игра на доске 15 × 15 адаптирована из статьи «Го-Моку и поиск угроз в пространстве».[7]

Первые ходы ясно показывают преимущество черных. Открытый ряд из трех (тот, который не заблокирован камнями противника с обоих концов) должен быть немедленно заблокирован или отражен угрозой в другом месте на доске. Если не заблокировать или противопоставить, открытый ряд из трех будет расширен до открытого ряда из четырех, что может привести к выигрышу двумя способами.

Белые должны блокировать открытые ряды из трех на 10, 14, 16 и 20 ходах, но черные должны сделать это только на 9-м ходу. Ход 20 - грубая ошибка для белых (его следовало сыграть рядом с ходом черных 19). Черные теперь могут добиться победы над любой защитой белых, начиная с 21-го хода.

Вторая игра (продолжение первой игры)

Для черных есть две последовательности принуждения, в зависимости от того, играют ли белые 22 рядом с черными 15 или черными 21. На диаграмме справа показана первая последовательность. Все ходы за белых форсированные. Такие длинные последовательности форсирования типичны для гомоку, и опытные игроки могут быстро и точно прочитать последовательности форсирования от 20 до 40 ходов.

Другая вторая игра

На диаграмме справа показана вторая последовательность форсирования. Эта диаграмма показывает, почему ход белых 20 был ошибкой; если бы он был рядом с черным 19 (в позиции 32-го хода на этой диаграмме), тогда ход черных 31 не был бы угрозой, и поэтому последовательность форсирования не удалась.

Чемпионат мира

Чемпионаты мира по гомоку проводились 2 раза в 1989, 1991 годах.[8]С 2009 года турнир возобновился, разыгрываемое правило открытия было изменено на swap2.

Список прошедших турниров и обладателей титулов следует.

Чемпионат мира
Название годаГород, страна пребыванияЗолотоСереброБронзаПравило открытия
1989 Киото, ЯпонияСоветский союз Сергей ЧерновСоветский союз Юрий ТаранниковЯпония Хиродзи СакамотоPro
1991 Москва, Советский союзСоветский союз Юрий ТаранниковСоветский союз Андо МеритиСоветский союз Сергей ЧерновPro
2009 Пардубице, ЧехияПольша Артур ТамиолаВенгрия Аттила ДемьянЧехия Павел ЛаубеSwap2
2011 Huskvarna, ШвецияВенгрия Аттила ДемьянПольша Артур ТамиолаПольша Михал ЛуковскиSwap2
2013 Таллинн, ЭстонияВенгрия Аттила ДемьянЧехия Павел ЛаубеРоссия Михаил КожинSwap2
2015 Суздаль, РоссияВенгрия Рудольф ДупскиВенгрия Герго ТотРоссия Михаил КожинSwap2
2017 Прага, ЧехияВенгрия Золтан ЛаслоВенгрия Рудольф ДупскиРоссия Денис ОсиповSwap2
2019 Таллинн, ЭстонияЧехия Мартин МузикаУкраина Олег БулатовскийПольша Михал ЛуковскиSwap2
Командный чемпионат мира
Название годаГород размещения, странаЗолотоСереброБронзаПравило открытия
2016 Таллинн, Эстония Польша
Михал Луковски
Михал Зайк
Лукаш Майкснер
Петр Маловейский		 Чехия
Павел Лаубе
Игорь Егед
Štěpán Tesařík
Марек Ханцль		 Китайский Тайбэй
Лу Вэй-Юань
Чен Ко-Хан
Чанг И-Фэн
Сунг Пей-Юнг		Swap2
2018 Плоцк, Польша Россия -1
Эдвард Ризванов
Денис Осипов
Илья Муратов
Максим Карасев
Михаил Кожин		 Венгрия
Золтан Ласло
Герго Тот
Марк Хорват
Габор Гьенеш
Аттила Хегедес		 Польша
Лукаш Майкснер
Михал Луковски
Михал Зайк
Марек Горжецкий
Павел Тарасинский		Swap2
2020
Отменено в связи с COVID-19 пандемия

Компьютеры и гомоку

Люди подавали заявки искусственный интеллект техники игры в гомоку на протяжении нескольких десятилетий. В 1994 г. Л. Виктор Аллис поднял алгоритм поиска по числу доказательств (pn-search) и поиска на основе зависимостей (db-search) и доказал, что, начиная с пустой доски 15 × 15, первый игрок имеет выигрышную стратегию, используя эти алгоритмы поиска.[9] Это относится как к гомоку вольного стиля, так и к стандартному гомоку без каких-либо правил открытия. Похоже, что черные выигрывают и на больших досках. Гомоку для фристайла - это доска любого размера. м,п,k-игра, следовательно, известно, что первый игрок может форсировать победу или ничью. В 2001 году выигрышная стратегия Аллиса была также одобрена для рэндзю, разновидности гомоку, когда не было ограничений на начальной стадии.[10]

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

Райш доказал, что Обобщенный гомоку это PSPACE-полный.[11] Он также заметил, что сокращение может быть адаптировано к правилам k-in-a-Row для фиксированного k. Хотя он не уточнил, какие именно значения k допустимы, сокращение, по-видимому, распространяется на любое k ≥ 5.[12]

С 1989 года существует несколько известных турниров по программам гомоку. Компьютерная олимпиада началось с игры гомоку в 1989 году, но гомоку не было в списке с 1993 года.[13] Компьютерный чемпионат мира по рэндзю стартовал в 1991 году и проводился 4 раза до 2004 года.[14][15] В Гомокубок Турнир проводится с 2000 года и проводится ежегодно, он активен и сейчас, в нем принимают участие более 30 участников из примерно 10 стран.[16] Турнир Hungarian Computer Go-Moku также проводился дважды в 2005 году.[17][18] В Чешской Республике также проводились два турнира «Компьютер против человека» в 2006 и 2011 годах.[19][20] Лишь в 2017 году компьютерные программы смогли превзойти чемпиона мира среди людей в публичных соревнованиях. На чемпионате мира по гомоку-2017 состоялся матч между чемпионами мира по программе Yixin и чемпионом мира по футболу Рудольфом Дупски. Исинь выиграл матч со счетом 2–0.[21][22]

Смотрите также

Рекомендации

  1. ^ «Гомоку - японская настольная игра». Japan 101. Архивировано с оригинал на 2014-03-26. Получено 2013-06-25.
  2. ^ Ласкер, Эдвард (1960). Go and go-moku: восточные настольные игры (2-е изд.). Нью-Йорк: Дувр.
  3. ^ Хуан Цзуньсянь, Чен Чжэн (2005). 《黄遵宪 全集》 第 2 卷 (на китайском языке). Китай: Книжная компания Чжунхуа. ISBN  9787101044904.
  4. ^ Цитаты OED: 1886 ГИЛЬЕМАРДА Круиз «Марчеза» I. 267 Некоторые игры чисто японские .. как запретить. Примечание, Эта игра недавно была представлена ​​в Англии под неправильным названием Go Bang. 1888 Pall Mall Gazette 1. 3/1 ноября. Эти молодые люди ... играли в гоу-бэнг и в кошачью колыбель. На приведенной ниже таблице показаны три типа выигрышных комбинаций, которые могут появиться на доске Петтеи 8x8. Очевидно, что стесненные условия в большинстве случаев приводят к ничьей, в зависимости от правил. Играть будет проще на большой доске Латрункули 12x8 или даже 10x11 ..
  5. ^ «Гомоку - правило swap2». renju.net. Получено 2016-11-09.
  6. ^ http://gomokuworld.com/gomoku/2
  7. ^ Аллис, Л. В., Херик, Х. Дж., И Хунтьенс, М. П. Х. (1993). Го-моку и поиск в пространстве угроз. Лимбургский университет, факультет компьютерных наук.
  8. ^ «Портал Международной федерации рэндзю - RenjuNet». Renju.net. Получено 2012-10-03.
  9. ^ Л. Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте. Кандидат наук. защитил диссертацию в Лимбургском университете, Нидерланды. С. 121–154. CiteSeerX  10.1.1.99.5364. ISBN  90-900748-8-0.
  10. ^ Й. Вагнер и И. Вираг (март 2001 г.). «Решение рэндзю». Журнал ICGA. 24 (1): 30–35. Дои:10.3233 / ICG-2001-24104. S2CID  207577292.
  11. ^ Стефан Райш (1980). «Gobang ist PSPACE-vollständig (Gomoku - PSPACE-complete)». Acta Informatica. 13: 59–66. Дои:10.1007 / bf00288536. S2CID  21455572.
  12. ^ Демейн, Эрик; Хирн, Роберт (2001). «Игры с алгоритмами: алгоритмическая комбинаторная теория игр». arXiv:cs / 0106019v2.
  13. ^ «Го-Моку (турниры ICGA)». game-ai-forum.org. Получено 2016-06-02.
  14. ^ «Чемпионат мира по компьютерному рэндзю». 5stone.net. Получено 2016-06-02.
  15. ^ «4-й чемпионат мира среди компьютерных программ». Домашняя страница японских игр Носовского. Получено 2016-06-03.
  16. ^ "Gomocup - Турнир по Гомоку AI". Гомокубок. Архивировано из оригинал на 2016-06-04. Получено 2016-06-02.
  17. ^ "Hungarian Computer Gomoku Tournament 2005 | GomokuWorld.com". gomokuworld.com. Получено 2016-06-02.
  18. ^ «2-й венгерский открытый турнир по компьютерному го-моку». sze.hu. Получено 2016-06-03.
  19. ^ "Первый турнир AI vs. Human (11 ноября 2006 г.) | Gomocup". gomocup.org. Получено 2016-06-02.
  20. ^ "AI vs. Člověk 2011 | Чешская федерация piškvorek a renju". piskvorky.cz. Получено 2016-06-02.
  21. ^ «Рудольф Дупски против Исиня». AIEXP.
  22. ^ «Рудольф Дупски против Иксин 2017». Facebook.

дальнейшее чтение

  • Five-in-a-Row (Renju) для начинающих и продвинутых игроков ISBN  4-87187-301-3

внешняя ссылка