Игра амазонок

Игра амазонок
Игроки	2
Время установки	20 секунд
Время игры	30-60 минут
Шанс	Никто
Возрастной диапазон	4+
Навыки	Тактика, стратегия, позиция

«Игра амазонок» (по-испански El Juego de las Amazonas; для двух игроков, для краткости часто называют «Амазонки») — абстрактная стратегическая игра изобретенная в 1988 году Уолтером Замкаускасом из Аргентины . ^[1] В игре перемещаются фигуры и блокируются противники с полей, причем победителем становится последний игрок, способный двигаться. Это член семейства территориальных игр, дальний родственник го и шахмат .

Игра амазонок проводится на шахматной доске 10x10 (или международной шахматной доске ). Некоторые игроки предпочитают использовать однотонную доску. Два игрока — белые и черные; У каждого игрока есть четыре амазонки (не путать с -амазонки шахматной фигурой феи ), которые начинаются на доске в конфигурации, показанной справа. Также необходим запас маркеров (шашек, покерных фишек и т. д.).

Правила

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

	а	б	с	д	и	ж	г	час	я	дж
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	а	б	с	д	и	ж	г	час	я	дж

На диаграмме показан возможный первый ход белых: d1-d6/g9, т.е. амазонка перешла с d1 на d6 и выпустила стрелку на g9.

Территория и подсчет очков

	а	б	с	д	и	ж	г	час	я	дж
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	а	б	с	д	и	ж	г	час	я	дж

Завершенная игра про амазонок. Белые только что сделали ход f1-e2/f1. Теперь у белых осталось 8 ходов, а у черных – 31.

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

Результаты иногда используются для определения ничьей в турнирах Amazons. При подсчете очков важно учитывать, что хотя количество ходов, оставшихся игроку, обычно равно количеству пустых клеток на территориях, занятых амазонками этого игрока, тем не менее возможно наличие дефектных территорий , на которых меньше ходов. слева, чем есть пустые квадраты. Самая простая такая территория — это три квадрата одного цвета, расположенные не по прямой, с амазонкой посередине (например, a1+b2+c1 с амазонкой в b2).

История

El Juego de las Amazonas была впервые опубликована на испанском языке в аргентинском журнале головоломок El Acertijo в декабре 1992 года. Утвержденный английский перевод, написанный Майклом Келлером, появился в журнале World Game Review в январе 1994 года. ^[1] Другие игровые издания также опубликовали правила, и игра собрала небольшое, но преданное количество поклонников. Интернет распространил игру более широко.

Майкл Келлер написал первую известную компьютерную версию игры на языке VAX Fortran в 1994 году. ^[2] и обновленная версия с графикой на Visual Basic в 1995 году. ^[1]^[2] проводятся турниры «Амазонки» На Компьютерной олимпиаде — серия соревнований компьютер против компьютера.

El Juego de las Amazonas (Игра амазонок) является торговой маркой Ediciones de Mente.

Вычислительная сложность

Обычно в эндшпиле доска делится на отдельные «королевские палаты», внутри каждой из которых находятся ферзи. Мы определяем простые эндшпили амазонок как эндшпили, в которых в каждой камере имеется не более одного ферзя. Определить, кто победит в простом эндшпиле амазонок, NP-сложно . ^[3] Это доказывается путем сведения его к нахождению гамильтонова пути кубического подграфа графа с квадратной сеткой .

Обобщенные амазонки (то есть определение победителя игры амазонок, сыгранной в сетке anxn, начатой из произвольной конфигурации) являются PSPACE-полными . ^[4]^[5] Это можно доказать двумя способами.

Первый способ — сократить обобщенную шестнадцатеричную позицию, которая, как известно, является PSPACE-полной, ^[6] в положение амазонок.

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

Ссылки

^ Jump up to: ^а ^б ^с Пегг, Эд (1999), Амазонки , получено 19 октября 2014 г.
^ Jump up to: ^а ^б Келлер, Майкл, «Игра амазонок» , получено 26 октября 2014 г.
^ Буро, Майкл (2000), «Простые эндшпили амазонок и их связь со схемами Гамильтона в графах кубических подсеток» (PDF) , Конференция по компьютерам и играм , стр. 250–261, doi : 10.1007/3-540-45579-5_17 .
^ Фуртак, Тимофей; Киёми, Масаси; Уно, Такеаки; Буро, Майкл (2005), «Обобщенные амазонки являются PSPACE-полными» (PDF) , IJCAI .
^ Хирн, Роберт А. (2 февраля 2005 г.), Amazons является PSPACE-полным , arXiv : cs.CC/0502013 .
^ Стефан Райш (1981). «Hex является PSPACE-полным». Акта Информатика (15): 167–191. дои : 10.1007/bf00288964 . S2CID 9125259 .

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

Мюллер, Мартин; Тегос, Теодор (2002), «Эксперименты с компьютерными амазонками», Больше игр без шансов (PDF) , MSRI Publications, vol. 42, Кембриджский университет. Пресс, стр. 243–257 .
Снацке, Раймонд Джордж (2002), «Исчерпывающий поиск среди амазонок», Еще игры без шансов (PDF) , публикации MSRI, том. 42, Кембриджский университет. Пресс, стр. 261–278 .

[chessvariants-1] Jump up to: ^а ^б ^с Пегг, Эд (1999), Амазонки , получено 19 октября 2014 г.

[Keller-2] Jump up to: ^а ^б Келлер, Майкл, «Игра амазонок» , получено 26 октября 2014 г.

[3] Буро, Майкл (2000), «Простые эндшпили амазонок и их связь со схемами Гамильтона в графах кубических подсеток» (PDF) , Конференция по компьютерам и играм , стр. 250–261, doi : 10.1007/3-540-45579-5_17 .

[4] Фуртак, Тимофей; Киёми, Масаси; Уно, Такеаки; Буро, Майкл (2005), «Обобщенные амазонки являются PSPACE-полными» (PDF) , IJCAI .

[5] Хирн, Роберт А. (2 февраля 2005 г.), Amazons является PSPACE-полным , arXiv : cs.CC/0502013 .

[6] Стефан Райш (1981). «Hex является PSPACE-полным». Акта Информатика (15): 167–191. дои : 10.1007/bf00288964 . S2CID 9125259 .

[1]

[2]

[3]

[4]

[5]

[6]