5
1

Гекс - интереснейшая математическая игра на ромбической доске, имеющей гексагональную сетку (см. Википедию и/или iggamecenter.com). Ее изобретатели - математики Пит Хейн (в Дании,1942) и Джон Нэш (в США, 1948). Кроме того, проходила еще информация, что ранее в Гекс играли студенты университета в США на кафельном полу во время перерывов между лекциями. В старые времена (ориентировочно 60-70-е годы) проводились чемпионаты мира по игре в Гекс.

Известны следующие свойства игры Гекс.

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

  2. Если у сколь угодно большого поля укоротить одну сторону лишь на 1 и за счет этого облегчить «немного» задачу 2-му игроку в порядке компенсации за дискриминацию в игре, то у 2-го игрока, соединяющего две сближенные стороны, появляется простейшая выигрышная стратегия, определяющая очередной ход 2-го игрока только по последнему ходу, сделанному 1-м игроком. Используя эту стратегию, К. Шеннон подшучивал над друзьями, мастерами игры в Гекс, с легкостью их обыгрывая с помощью «думающей машины», начиная 2-м, при этом он негласно использовал «слегка» деформированную доску.

Доказательство существования выигрышной стратегии 1-го игрока основывается на факте невозможности в игре Гекс ничьей. При этом идея доказательства «проще-некуда» и приводится в разных источниках. Однако я не встречал (возможно, искал без упорства) доказательство факта невозможности ничьих. Для этого нужно (необходимо и достаточно), чтобы выполнялись два свойства гекс-поля:

1) Если линия 1 и линия 2 соединяют пары различных противоположных сторон, то они пересекаются.

2) Пусть $%(a,c) $% и $% (b,d) $% – пары противоположных сторон гекс-поля. Тогда если закрасить ячейки гекс-поля произвольным образом в красный и синий цвета, то (либо стороны $%a,c $% будут соединены красным цветом, либо стороны $%b,d $% будут соединены синим цветом) И (либо стороны $%a,c$% будут соединены синим цветом, либо стороны $%b,d$% будут соединены красным цветом).

Вопросы:
1. Известно что-либо о доказательстве этих утверждений и как их можно доказать?
2. Возможно, есть новая информация о сложности выигрышного алгоритма игры?

задан 12 Ноя '14 3:26

изменен 15 Ноя '14 13:07

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
4

Когда я читал в детстве про эту игру (видимо, у Гарднера), то мне тоже показалось, что факт отсутствия ничьих не вполне очевиден. С доказательством, которое где-либо было написано, я до сей поры не сталкивался, но меня устраивало следующее рассуждение, базирующееся на наглядно-очевидных соображениях. Выглядело оно так: пусть противоположные стороны ромба выкрашены в красный цвет (одна пара сторон) и синий цвет (другая пара). Пусть также доска произвольным способом полностью заставлена красными или синими фишками. Можно считать, что поля покрашены в красный или синий цвет. Начинаем формировать два множества точек: красное и синее. Изначально красное множество состоит из двух сторон ромба, и аналогично для синего. Допустим, что к красной стороне примыкает красный 6-угольник. Присоединяем его к красному множеству. Его граница имеет многоугольную форму, и к ней могут примыкать красные 6-угольники. Добавляем их, пока это возможно, расширяя множество. Если оно дойдёт до противоположной границы, то всё доказано. Аналогично поступаем с синим множеством. Если никакое из них не дошло до границы, то смотрим на то, что возникает "между" границами. Из устройства гексагональной решётки становится ясно, что такого быть не может.

Само рассуждение обладает не очень высокой степенью убедительности, поэтому возникает потребность в более строгом рассуждении, и очень хорошо, что Вы подняли этот вопрос. Насколько я знаю, источников с полноценным доказательством имеется не так много, но они есть. Вот две ссылки: эта и эта. Текст там один и тот же, но вторая имеет вид опубликованной статьи, а первая более удобна для чтения чисто технически.

Доказательство можно кратко пересказать. Строится граф, вершины которого -- это узлы гексагональной решётки. Рёбра проводятся на границе двух 6-угольников разного цвета. По углам ромба добавлены 4 вспомогательные вершины, и они соединены ребром с вершиной решётки. Можно считать, что эти рёбра лежат на границах внешних красной и синей областей.

Рассмотрим любую из вершин графа. Она имеет валентность не более двух. Это ясно из того, что в вершине сходятся три 6-угольника, и два из них одноцветны. Кроме того, все вершины внутри имеют валентность 2 или 0, а добавленные вершины имеют валентность 1. Структура такого графа хорошо понятна, и в нём вершины валентности 1 должны быть как-то соединены попарно путями в этом графе, но не по диагонали. После того, как эти соединения нарисованы, а это дизъюнктные простые пути, становится ясно, кто выиграл. То есть между путями появляется "коридор" какого-то из цветов. Интересно, что здесь ответ можно получить не зрительно, а чисто "машинно".

Что касается стратегий, то мне кажется, что общих фактов тут не известно, а для полей малого размера я нашёл некоторое обсуждение здесь, но там всё носит чисто технический характер, поэтому я как следует не вникал.

ссылка

отвечен 12 Ноя '14 5:32

И мне тоже показалось, что факт отсутствия ничьих в книге Гарднера не вполне очевиден.

(12 Ноя '14 11:46) EdwardTurJ

@falcao, спасибо за ответ, который пояснил мне ситуацию по поднятому вопросу. Я, сомневался, может, я что-то недопонимаю, т. к. обычно описание сводилось к фразе: «поскольку в игре не может быть ничьих, то…». На то, что этот факт не тривиален, наталкивали мысли о несоответствии топологических свойств обычного квадрата в $% \mathbb R^2 $% и гекс-поля при устремлении числа ячеек в бесконечность. Как я понимаю, в обычном квадрате свойство 2 не выполняется.

(12 Ноя '14 12:38) Urt

А из каких соображений он не вполне очевиден? На правильном хекс поле всегда нечётное кол-во ячеек, потому ничья невозможна

(13 Июл '15 11:41) Isaev

@Isaev: а какое отношение к этому имеет нечётность? Там ведь нужно наличие "цепочки" от одного края к другому. А это надо доказывать.

(13 Июл '15 11:47) falcao
1

Вот тут есть детальное обсуждение весьма близкой по духу задачи (про короля и ладью), и похоже, что с ней примерно та же проблема - наглядные соображения имеют недостаточную строгость. http://forum.academ.org/lofiversion/index.php?t48610.html

(13 Июл '15 12:04) knop
1

Вот еще та же задача о короле и ладье, со ссылками на решения. http://sasja.shap.homedns.org/Uroki/Mosbory/2013o/Korol-ladja.html

(13 Июл '15 12:06) knop

@knop: да, это во многом аналогичная задача. На форуме про неё тоже спрашивали, но ссылку я сейчас не помню.

P.S. Нашёл ссылку.

(13 Июл '15 12:12) falcao

@falcao, а, это другая игра... я думал вы о http://www.learn4good.com/games/arcade/hexagon.htm там классическая доска в виде шестиугольника из шестиугольников без отверстий

(13 Июл '15 12:13) Isaev
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,508
×281
×78

задан
12 Ноя '14 3:26

показан
1579 раз

обновлен
13 Июл '15 12:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru