Подключить6 - Connect6

Подключить6
Крупный план игры Connect 6.jpg
Игра Connect6
Игроки2
Время установкиНастройка не требуется
Время игры10–60 мин.
Случайный шансНикто
Требуются навыкиСтратегия, Наблюдение

Подключить6 (Китайский : 六 子 棋; Пиньинь: liùzǐqí; Китайский : 連 六 棋;Японский: 六 目 並 べ; Корейский: 육목) введен в 2003 г. профессором И-Чен Ву на кафедре компьютерных наук и информационной инженерии, Национальный университет Цзяо Дун в Тайвань, это двое игроков стратегическая игра похожий на Гомоку.[1]

Два игрока, черный и белый, поочередно кладут два камня своего цвета, соответственно черный и белый, на пустые пересечения Идти -подобная доска, за исключением того, что черные (первый игрок) кладут один камень только на первый ход. Выигрывает тот, кто первым получит шесть или более камней подряд (по горизонтали, вертикали или диагонали).

Правила

Правила Connect6 очень просты и похожи на традиционную игру в Гомоку:

  • Игроки и камни: есть два игрока. Черные играют первыми, а белые - вторыми. Каждый игрок играет с камнями соответствующего цвета, как в Го и Гомоку.
  • Игровое поле: в Connect6 используется квадратная доска, состоящая из ортогональных линий, на каждом пересечении которых может находиться один камень. Теоретически игровое поле может быть любого конечного размера от 1 × 1 (только целые числа) или бесконечного размера. Однако на слишком маленьких досках может отсутствовать стратегия (доски меньше 6 × 6 - это автоматические розыгрыши), а очень большие или бесконечные доски практически не используются. Доски 19 × 19 Go могут быть самыми удобными. Для более длительной и сложной игры другой рекомендуемый размер - 59 × 59 или девять досок го, выложенных плиткой в ​​большем квадрате (с использованием линий соединения между досками в качестве дополнительных линий сетки).
  • Ход игры: черные играют первыми, кладя один черный камень на одно пересечение. Впоследствии белые и черные по очереди кладут два камня на две разные незанятые клетки каждый ход.
  • Победитель: побеждает игрок, который первым получит шесть или более камней подряд (по горизонтали, вертикали или диагонали). (Это отход от Гомоку, где это должно быть точно пять подряд.)

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

Справедливость

В принципе, даже некоторые сложные игры нечестны: либо первый, либо второй игрок имеет преимущество. (Математически доказано, что такие игры, как Гомоку, дают преимущество тому или иному игроку; сложные игры, такие как шахматы обычно слишком сложны для полного анализа.) Херик, Уитервейк и Рийсвейк дают неформальное определение справедливости (Herik, Uiterwijk, and Rijswijck, 2002) следующим образом: игра считается честной, если она закончилась ничьей и у обоих игроков есть примерно равные возможности для совершения ошибок. Исходя из этого, утверждается, что Connect6 справедлива в следующих смыслах:

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

Однако это свидетельство не является окончательным.

Сложность

Если Connect6 использует бесконечную доску, оба пространство состояний и сложности игрового дерева также бесконечны. Вместо этого предположите, что используется доска го. Сложность игрового дерева для него по-прежнему намного выше, чем в Гомоку и Рэндзю, поскольку при размещении двух камней возможно гораздо больше ходов, а именно п(п−1) / 2 хода возможны, где п - количество незанятых клеток перед ходом. Однако сложность в пространстве состояний в значительной степени не изменилась, поскольку любая легальная позиция в одной игре будет также допустима в другой. Основываясь на стандартах Херика, Хунтьенса и Рейсвейка, пространство состояний сложность Connect (19,19,6,2,1) 10172, то же самое, что и в Го или Гомоку. Если используется доска большего размера, сложность намного выше, так как количество ходов увеличивается экспоненциально с размером доски; она должна быть такой же, как две другие игры на доске того же размера.

Теперь давайте исследуем игровое дерево сложность. Предположим, что средняя продолжительность игры все еще равна 30, как и оценка для Гомоку (Allis 1994). Тогда количество сеток, выбранных для размещения одного камня, составляет около 300, а количество вариантов одного хода - около или 45000. Таким образом, сложность игрового дерева составляет около ≈ 10140, намного выше, чем для Гомоку. В качестве альтернативы, если предположить, что общее количество размещенных камней (вместо количества ходов) такое же, как и для Гомоку, то средняя продолжительность игры составляет примерно 15. Тогда сложность игрового дерева примерно равна ≈ 1070, того же порядка величины, что и для Гомоку, приведенного в Allis 1994. Опять же, если используется большая доска, эта сложность становится намного выше.

История

Основное направление текущей разработки Connect6 началось с презентации профессора И-Чен Ву. Поскольку правила игры просты, считается, что некоторые раньше думали о них. Например, один утверждает: идея игры (китайское название «六 子 棋») появилась в Интернете примерно в 1999 году сначала на популярном китайском BBS-сайте bbs.tsinghua.edu.cn, а затем на популярном китайском BBS-сайте bbs. mit.edu (сейчас www.mitbbs.com). Однако до того, как профессор Ву представил игру Connect6, записей об играх Connect6 не существовало и не обсуждались. История профессора Ву такова.

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

Весной 2004 г. владелец ученик профессора Ву, Дэй-Йен Хуанг, присоединился к проекту Ву как его магистерская работа. В первом квартале 2005 года они завершили первую программу Connect6 AI, которая уже может превзойти большинство игроков. Затем команда Ву позволила его программе ИИ играть сама.

В 2005 году команда Ву написала доклад, представленный на 11-й конференции по достижениям в компьютерных играх (ACG11), проходившей в Тайбэй, Тайвань, 2005.

В сентябре 2005 года ThinkNewIdea Limited построила первый игровой сервер Connect6.

С 20 по 21 сентября 2005 г. игра освещалась многими СМИ в Тайвань.

Программа NCTU6, переписанная профессором Ву, выиграла золото в турнире Connect6 на 11-я компьютерная олимпиада.

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

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

  1. ^ Kung, H.T .; Робинсон, Джон Т. (июнь 1981 г.). «Об оптимистических методах управления параллелизмом». Транзакции ACM в системах баз данных. 6 (2): 213. CiteSeerX  10.1.1.101.8988. Дои:10.1145/319566.319567.

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