300000
Общее количество побед: 33073
Многоточие
Если вас просто интересует, какие ходы играть, а не зачем, то переходите к «Дереву решений» внизу. В «Указателе» ниже перечислены все термины, которые представлены в тексте и могут быть использованы в качестве краткого введения.
Основы
Терминология: Давайте введем несколько новых терминов, которые мы будем использовать для разговора об игре.
box — это небольшой квадрат с 4 соседними точками в качестве углов. Коробка может иметь 0, 1, 2, 3, 4 стороны и тогда называется 0-box, 1-box, 2-box, 3-box, 4-box.
line — это отрезок линии, соединяющий две соседние точки.
Рисование линии также называется making a move.
Если ненарисованная линия разделяет 2-бокс и 3-бокс, то рисование этой линии делает 3 вещи: она завершает 3-бокс и, таким образом, набирает очко, она меняет 2-бокс на 3-бокс, и это дает игроку еще один ход, который может быть использован для завершения нового 3-бокса. Этот вид «цепной реакции» случается очень часто.
Все соединенные 2-боксы составляют chain. Цепочка может иметь 2 конца и тогда называется линейной цепью, независимо от того, прямая это линия или нет, как
+ + +---+---+ + +---+
| | , или | |
+ + +---+---+ +---+ +
|
+---+---+показывает цепочки с 1, 2 и 4 коробками.
Цепочка также может не иметь конца, и тогда мы называем ее loopy chain или просто loop, независимо от того, выглядит ли она как круг или нет, как эта
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
В математической литературе об этой игре ход внутри цепи или на одном из ее концов называется открытие цепи.
Что произойдет, если цепочка будет открыта?
Если игрок вытягивает одну из ненарисованных линий в цепочке, как ход A1 в
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+тогда по крайней мере одна 2-я коробка становится 3-й коробкой (здесь ходят коробка выше и коробка ниже А1), а другой игрок может впоследствии завершить коробку (клетки) в 4-коробку, заработать одно или два очка и в то же время преобразовать соседнюю 2-коробку в 3-коробку (здесь коробка слева от B1 и справа от B2) в
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+Каждый раз, когда коробка завершена, игрок должен сделать еще один ход, который может быть использован для завершения следующей коробки и всех остальных коробок цепочки. После заполнения последней коробки игрок должен сделать еще один ход в другом месте, если все коробки на доске не будут заполнены.
Начальная игра
Правило 1: Самая очевидная игра заключается в том, чтобы избежать создания 3-бокса, который противник мог бы забрать, завершив его. Это простое и полезное правило, хотя оно и не идеально, как мы увидим в конце этого сайта. На каком-то этапе, когда нарисовано около половины всех линий, создание 3-бокса становится неизбежным. Что происходит потом? Поскольку цепочки с 1, 2 или ≥ 3 коробками обрабатываются по-разному, мы должны рассматривать их по отдельности.
Давайте начнем с рассмотрения цепей, имеющих только одну коробку.
Всегда ли нужно завершать одну 3-коробку, т.е. цепочку с одной коробкой?
+---+
| ?
+---+
Да, так нужно делать всегда. Возьмет ли вы коробку и после этого сделает ход А или не возьмете коробку и сыграете на А, не влияет на действия соперника, за исключением того, что либо вы, либо противник получаете коробку, поэтому лучше, чтобы вы получили коробку.
Как могут выглядеть цепочки с двумя боксами и как в них играть?
Цепочки с двумя коробками выглядят как
+---+---+ +---+---+ +---+---+
или | или | |
+---+---+ +---+ + + + +или их повернутые и зеркальные версии. Проведение там средней линии приводит к
+---+---+ +---+---+ +---+---+
| или | | или | | |
+---+---+ +---+ + + + +и в литературе называется Жестокосердный Подачка .
Всегда ли нужно брать обе коробки в таком положении?
Да, следует брать обе коробки по тем же причинам, по которым всегда следует брать цепочки из 1 коробки. Пожалуйста, убедитесь сами.
Проведение линии на границе цепочки из 2 коробок (одна из трех цепей из 2 коробок, показанных выше) приводит к
+---+---+ +---+---+ | или | | +---+---+ +---+ +
и называется Half-Hearted Handout.
Движение на границе вышеуказанных позиций приводит к
+---+---+ | | . +---+---+
Такой ход в литературе называется Double Dealing (DD). Чтобы внести ясность, существует четкое различие между следующими двумя ходами:
+---+---+ +---+---+ 1) to | +---+---+ +---+---+
и
+---+---+---+ +---+---+---+ 2) | to | | +---+---+---+ +---+---+---+
, хотя обе результирующие цепочки из 2 коробок выглядят одинаково. Большая разница заключается в том, что ход в пункте 2) завершает коробку и, таким образом, позволяет игроку снова сделать ход и сыграть DD, в то время как в пункте 1) ни одна коробка не завершена, и поэтому игрок не может играть DD. В то время как ход 2) является обычным ходом, ход 1) называется половинчатой подачкой.
Проведение линии посередине, которая завершает оба поля, называется Double-Crossed Move. Цикл всегда завершается таким ходом, но в линейной цепочке это может произойти только тогда, когда противник делает ход DD, чтобы взять контроль над ситуацией, как описано ниже. После хода DD игрока А у следующего игрока Б нет другого выбора, кроме как сделать ход в центре, сделанный с двойным скрещиванием. Хотя этот ход даст B 2 бокса, стоимость будет выше, если B будет играть следующим в более длинной цепочке, которая полностью перейдет к A. В такой ситуации игрок В, делающий двойной ход, обманывается, т.е. «дважды перекрещивается», отсюда и название этого хода.
Должен ли следующий игрок после DD всегда брать обе коробки?
Ход DD — это жертва двух коробок, потому что игрок может сначала сыграть в середине Жестокосердной Раздачи, а затем на границе и заработать таким образом две коробки. Зачем кому-то жертвовать 2 коробками? Продолжайте читать, чтобы узнать!
Такой ход, как «Половинчатая подачка» перед ДД, который дал противнику возможность принести жертву, в литературе называется сумасшедшим ходом. Этого безумного шага можно и нужно избегать. Другие безумные ходы, такие как открытие цепочки с 3 или более коробками, могут быть неизбежны.
Возвращаясь к половинчатым подачкам, всегда ли нужно брать обе коробки в таком положении? Если нет, то когда следует играть ДД на границе цепочки из 2 боксов? Попробуйте оба в играх и посмотрите, какая разница.
Рассмотрим все различия. Если кто-то берет одну коробку из цепочки из 2 коробок, то он должен взять вторую коробку, как мы нашли ранее. Если взять обе коробки, то можно получить 2 очка, но после этого нужно сделать ход куда-то еще. Это может быть дорого, потому что может потребоваться открыть цепочку с большим количеством коробок, что позволит противнику взять больше клеток. Если кто-то играет на границе, он не достраивает квадрат, и поэтому ему не нужно играть где-то еще. Но игра на границе дает следующему игроку обе коробки, как только что обсуждалось. Таким образом, возможны обе игры. К этому вопросу мы вернемся позже, чтобы определить, какой ход лучше в той или иной ситуации.
Если вам нужно открыть цепочку с 2 боксами, потому что все остальные ходы будут еще более дорогостоящими, следует ли играть в Hard-Hearted или Half-Hearted Handout?
Если один из них играет в середине цепочки (Жестокосердная Подачка), то другая сторона вынуждена взять оба бокса и после этого сделать потенциально дорогостоящий ход в другом месте:
+---+---+ +---+---+ +---+---+
→ | → | | | плюс еще где-то.
+---+---+ +---+---+ +---+---+
Если кто-то играет на краю цепи (половинчатая подачка), то он дает противнику возможность либо взять две коробки, как указано выше, либо играть на границе (ход двойной раздачи (DD)):
+---+---+ +---+---+ +---+---+
→ | → | |
+---+---+ +---+---+ +---+---+
Этот вариант игры в DD может быть очень ценным, о чем мы узнаем позже. Предоставление противнику дополнительных возможностей никогда не может быть лучшим ходом, поэтому, стремясь к оптимальной игре, никогда не следует разыгрывать половинчатую подачку при активации цепочки из 2 коробок. В неоптимальной веселой игре можно попробовать нерешительные ходы, чтобы выяснить мастерство противника или сбить с толку соперника, если он отстает (но не в том случае, если он пытается играть оптимально).
Что делать с открытыми линейными цепочками из трех и более коробок?
Если цепочка открыта, то в ней есть хотя бы один 3-бокс. Можно заполнить эту коробку и другие коробки, но нужно ли это делать?
Есть ли коробки, которые обязательно стоит брать из линейной открытой цепочки?
С одной стороны, мы хотим взять как можно больше коробок. С другой стороны, мы, возможно, не захотим платить цену за то, чтобы играть где-то еще, и тем самым открывать еще большую цепочку для соперника. Что мы обязательно должны сделать, так это взять все, кроме двух коробок, как обосновано ранее, они бесплатны, нет никакого негативного побочного эффекта. После этого можно подумать о том, чтобы взять оставшиеся 2 бокса или поиграть в DD (Double Dealing). Подробнее об этом мы поговорим ниже.
Цепочки с ≥ 3 коробками называются длинными цепочками. К ним относятся как линейные, так и петлевые цепи.
Почему у таких цепочек есть специальное название?
Если остались только длинные цепочки с минимум 3 боксами, то открытие одного из них, неважно каким образом, будет означать, что хотя бы с одной стороны хода есть как минимум 2 соседних бокса. Таким образом, другой игрок может играть в двойную игру, которая имеет решающее значение для определения оставшейся части игры.
Сколько коробок нужно, чтобы сделать петлю?
Самая маленькая возможная петля имеет 4 коробки:
+---+---+ | | + + + | | +---+---+
Если петля открыта, можно ли безопасно взять все, кроме 2 коробок, не задумываясь?
Давайте попробуем это сделать. Конечно, мы могли бы взять все 4 коробки и затем играть в другом месте, но что, если бы мы хотели избежать игры в другом месте любой ценой? Если мы возьмем две коробки, мы достигнем
+---+---+ | | +---+ + | | +---+---+
, но нам нужно будет сделать еще один ход. Поэтому мы не могли останавливаться на достигнутом, потому что все линии на границе уже проведены, поэтому мы должны продолжать двигаться до
+---+---+ | | | +---+---+ | | +---+---+
, а затем мы вынуждены сделать ход в другом месте, что, возможно, может передать противнику еще большую цепь.
Что еще мы могли бы сделать вместо этого?
Мы хотим сделать ход, который не завершает коробку, чтобы избежать необходимости играть где-то еще. Единственный возможный ход – играть в середине открытого цикла для создания
+---+---+ | | +---+---+ . | | +---+---+
Этот ход не завершает коробку, и поэтому другой игрок играет следующим. Мы будем называть этот ход Double Double Dealing (DDD). Цена – пожертвовать 4 вместо 2 коробок. Для соперника лучше всего взять 4 бокса и после этого играть в другом месте.
Что делать, если в разомкнутом контуре более 4 коробок?
Мы можем взять столько коробок, сколько захотим, до тех пор, пока мы все еще можем сделать ход, который не завершает квадрат. Это означает, что мы можем взять все, кроме 4 коробок, например, открыв
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + дает, например, + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
и взяв 8 − 4 = 4 коробки, мы получаем, например,
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
Теперь нам придется решить, взять ли оставшиеся 4 коробки или пожертвовать их сопернику, сыграв
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
Подробнее об этом позже.
В случае одной открытой цепи или маловероятного события открытия нескольких цепочек, сколько боксов можно безопасно взять, не думая о том, играть ли в DD или не играть в DD?Если есть открытые линейные и/или разомкнутые цепи, то завершаются все боксы всех этих цепочек, за исключением 2 соседних боксов одной открытой линейной цепи, или, если нет открытой линейной цепи, то за исключением 4 боксов одной из открытых цепей. После того как эти коробки будут заполнены, можно начинать задумываться о том, стоит ли играть в DD/DDD или нет.
Мы узнали, что игра начинается с более или менее случайных ходов, за исключением того, что оба игрока избегают создания 3-боксов как можно дольше, т.е. они избегают открытия цепочек. Когда это становится неизбежным, мы воспринимаем это как начало эндшпиля. Мы начинаем объяснять эндшпиль, потому что это самая простая часть всех игр.
Финал
Как и во всех других играх, чем ближе к концу, тем легче становится предсказать, кто выиграет при оптимальной игре и на сколько. Поэтому мы начинаем наш анализ с конца игры. В эндшпиле все ходы либо открытые цепочки, либо полные боксы, либо ходы DD/DDD. Когда игроку нужно открыть цепочку, то первой идеей для стратегии может быть открытие самой маленькой из доступных цепочек, чтобы дать противнику наименьшее количество коробок. Давайте попробуем это на нескольких примерах.
Пример 1
Предположим, что все коробки собраны, кроме двух цепочек по 3 и 4 коробки:
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
Игрок А, который ходит следующим, откроет более короткую цепочку (с любым ходом, например, А1), чтобы другой игрок Б забрал эту цепочку и получил 3 очка, а А получил большую цепочку с боксами после этого с количеством очков от этих двух цепочек А:В=(0+4):(3+0)=4:3.
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
Кстати, ход А1 – это то, что мы ранее определили как сумасшедший ход, ход, который дает сопернику возможность пойти на жертву. Здесь этого не избежать.
И вот что происходит на следующей диаграмме. Игрок В берет только одну коробку ходом В2 (на следующей диаграмме), затем играет двойную торговлю с В3. Затем А должен взять 2 бокса с A4, вынужден открыть большую цепочку каким-либо ходом, например, A5, а B получает оставшиеся 4 бокса с итоговым счетом A:B = (2+0):(1+4)=2:5.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+Мы видим, что в данной ситуации В выгодно пожертвовать двумя ящиками.
Пример 2
Предположим, что все коробки собраны, кроме одной цепочки с 3 коробками и одной петли с 4 коробками.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+Игрок А ходит следующим.
Случай 1: А открывает цепочку с 3 коробками.
Если после того, как А1 игрок В берет всю цепочку, то игрок А получает петлю и счет от этих двух цепочек равен А:В = (0+4):(3+0) = 4:3.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
Если после A1 игрок B играет DD, то после
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+счет от этих двух цепочек будет A:B = (2+0):(1+4) = 2:5, так и здесь B выгодно сыграть DD и достичь A:B = 2:5.
Случай 2: А открывает петлю с 4 коробками.
Если после А1 игрок В проходит весь круг, то игрок А получает более короткую цепочку, и счет от этих двух цепочек будет равен А:В = (0+3):(4+0) = 3:4.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
Если после того, как игрок A1 играет в DDD с B2, мы получаем
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+и счет из этих двух цепочек A:B = (4+0):(0+3) = 4:3. В этом случае B лучше НЕ играть в DDD и таким образом получить A:B = 3:4. Если А сначала играет в более короткой линейной цепочке, то А может обеспечить только А:В = 2:5. В то же время, когда А первым открывает большую петлю, А может достичь лучшего результата А:В = 3:4.
В чем объяснение?
Если А должен открыть длинную цепочку (с >2 коробками), то у игрока Б будет возможность сыграть DD/DDD в конце получения коробок этой цепочки и, таким образом, получить следующую цепочку, а также снова сыграть DD/DDD в этой цепочке и так далее до конца игры. Мы называем это «контролем», поскольку у игрока А никогда не будет возможности играть DD/DDD, если игрок Б этого не хочет. Что может сделать игрок А, так это сделать цену DD/DDD высокой. Если А открывает линейную цепочку, то цена за то, что В возьмет DD, равна жертве 2 коробок. Если А открывает закольцованную цепочку, то цена для В за игру в DDD составляет 4 камня. Это показывает, что при сортировке цепочек по значению, значение должно быть скорректировано путем вычитания 2 квадратов для линейных цепочек и вычитания 4 квадратов для зацикленных цепей.
Пример 3
В этом примере мы хотим узнать больше о том, в каком порядке должны открываться цепочки. Предположим, что все коробки завершены, за исключением двух линейных цепочек с 3 и 4 коробками и одной петли с 4 коробками, как здесь:
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+Игрок А ходит следующим. Понятно, что А не откроет большую линейную цепочку с 4 боксами, если есть линейная цепочка с 3 боксами.
Случай 1: А открывает цепочку с 3 коробками.
Прежде чем принять решение об оптимальной игре для игрока B, давайте проверим, какая из остальных 2 цепочек должна быть открыта первой:
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
Пусть игроки будут C и D, а C будет двигаться следующим.
Случай 1.1: C открывает цикл
+---+---+ +---+
| | |
+ + +---+ +
| C1 | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Если после C1 игрок D играет в DDD с D2, то после
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
счет из этих двух цепочек будет равен C:D = (4+0):(0+4) = 4:4. Если D не играет DDD, а берет цикл, то после
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
счет от этих двух цепочек также C:D = (0+4):(4+0) = 4:4.
Случай 1.2: C открывает цепочку из 4 коробок
+---+---+C1-+---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Если после C1 игрок D забирает всю цепочку, то после
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
счет C:D = (0+4):(4+0) = 4:4. Если после C1 игрок D играет DD с D4, то после
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+счет C:D = (2+0):(2+4) = 2:6. Лучшее, что может обеспечить D после C1, это C:D = 2:6.
Какие уроки мы извлекли из этих двух случаев?
Игроку, который играет следующим (C), лучше всего открыть цикл, достигнув C:D = 4:4, а не линейную цепочку, достигающую только C:D = 2:6. Если бы мы отсортировали цепочки по размеру − 2, чтобы решить, какую открыть первой, то (4−2) = 2 < 4 would give the correct result. We can now decide on the optimal play for B in:
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
Должен ли B взять цепочку или играть DD?
Если B берет цепочку, то после
+---+---+A9-+---+ | A7 | B10 | +A6-+A8-+---+B11+ | B5 | | | +---+---+---+B12+ B2 A1 B3 | B13 +---+---+B4-+---+
счет на этих 3 цепочках будет равен A:B = (0+4+0):(3+0+4) = 4:7. Если B играет вместо DD с B3, то после
+---+---+B9-+---+ | B7 | B10 | +B6-+B8-+---+B11+ | A5 | | | +---+---+---+B12+ B2 A1 A4 | B13 +---+---+B3-+---+
счет на этих 3 цепочках будет A:B = (2+0+4):(1+4+0) = 6:5. Таким образом, лучшее, чего может достичь В после А1, это А:В = 4:7, полученное В, если не играть в DDD. В обоих случаях мы воспользовались ранее сделанным выводом о том, что цикл должен быть открыт следующим.
Случай 2: A открывает цикл с 4 блоками:
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
Случай 2.1: B берет на себя весь цикл.
Ясно, что маленькая цепочка должна быть сыграна с DD, что приводит к тому, что
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+дает счет на этих трех цепочках A:B = (0+1+4):(4+2+0) = 5:6.
Случай 2.2: B жертвует циклом.
Опять же, маленькая цепочка должна быть сыграна с DD, что приводит к тому, что
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+дает счет на этих 3 цепочках A:B = (4+2+0):(0+1+4) = 6:5.
Что мы узнаем из кейсов 2.1 и 2.2?
Из-за высокой цены игры в DDD в цикле, лучшим для B здесь является прохождение всего цикла, достигая счета A:B = 5:6.
Что мы узнаем из случаев 1 и 2?
У нас есть две линейные цепочки с 3 и 4 коробками и петля с 4 коробками. Лучше всего, если А откроет цикл и достигнет счета А:В = 5:6. Если А открывает цепочку с 3 боксами, то получается только А:В = 4:7. Понятно, что не может быть лучше, чтобы В открывал цепочку с 4 коробками перед цепочкой с 3 коробками. Поэтому сортировать цепочки просто по размеру, чтобы определить, какие открыть дальше, не получится. Но сортировка их по размеру − 2 для линейных цепочек и размеру -4 для петлевых цепей, по-видимому, работает, потому что (4−4) = 0 < 1 = 3 − 2 indicating that the loop should be opened first.
Порядок, в котором открываются цепочки
На основе опыта, полученного из приведенных выше примеров, мы теперь решаем проблему определения порядка, в котором цепочки будут открываться и завершаться. Этот порядок цепочек будет использоваться ниже, чтобы определить, когда один из игроков будет играть DD/DDD, кто выиграет игру и с каким отрывом. Хорошая новость заключается в том, что в эндшпиле эта последовательность открытия цепочек не зависит от того, чей сейчас ход или кто играл в DD/DDD до этого. Причина в том, что в любой момент игры имеют значение только линии, которые были нарисованы, а не кем и не в каком порядке. Даже текущий счет не влияет на будущую оптимальную игру. Разделение сложной проблемы на более простые проблемы уже является успехом. В этом случае трудная задача определения того, кто какой ход делает в эндшпиле, была разделена на две проблемы: проблему порядка, в котором следует открывать цепочки, и проблему того, кто и когда играет DD/DDD. Прежде чем начать, нам нужно подумать об общей тенденции в эндшпиле.
Уменьшается или увеличивается «стоимость» открытых цепочек к концу?
Открытая цепочка отдается сопернику. Таким образом, цепочка должна иметь минимально возможную «ценность», где ценность, на первый взгляд, заключается в количестве коробок. Таким образом, в ходе эндшпиля «стоимость» открытых цепочек может только расти или оставаться неизменной, но не уменьшаться. В нашем примере выше мы увидели, что открыть цепочку с наименьшим количеством ящиков, чтобы соперник мог взять, не получается. Но мы хотим отсортировать цепочки по некоторому «значению», потому что каждый игрок хочет открыть наименее ценную цепочку для соперника. Для противника ценность цепочки состоит не только из количества коробок; Также имеет значение, подходит ли открытая цепочка для игры в ней DD/DDD. Хорошим кандидатом для такой корректировки пригодности для DD является вычитание 2 из числа коробок, если цепь представляет собой петлю. Это эквивалентно вычитанию 2 из линейных цепочек и 4 из петлевых цепей. Итак, чтобы отсортировать цепочки по 'value', мы берем 'value' = # блоков, если цепочка НЕ является циклом, и берем 'value' = # блоков − 2, если цепочка ЯВЛЯЕТСЯ циклом.
Мы начинаем с позиций на доске, где на каждой коробке нарисовано как минимум 2 стороны. Для этого мы можем сформулировать два правила, которые упорядочивают все цепочки.
Правило 2: Чтобы упорядочить цепочки, возьмите для последней цепи самую большую линейную цепь, а если линейной цепочки нет, возьмите самую большую цепь.
Обоснование Правила 2
Игрок, находящийся под контролем, не открывает цепочки и, следовательно, не сортирует цепочки. Таким образом, любой игрок, сортирующий цепочки, хочет сделать взятие или удержание контроля (т.е. разыгрывание ходов DD/DDD) для противника как можно более дорогостоящим. Переезд DD стоит 2 коробки, а ход DDD — 4 коробки. Эту цену нужно заплатить за все цепочки, кроме последней. Поэтому, чтобы максимизировать общую стоимость для соперника, при сортировке цепочек последняя цепочка должна быть по возможности линейной, а не петлей. ∎
Правило 3: Если в эндшпиле у всех коробок нарисованы хотя бы 2 стороны, то для упорядочивания всех остальных цепочек отсортируйте их по (количество коробок − 2, если это петля).
Обоснование правила 3
Сначала следует открыть 1-боксовые цепочки, затем 2-боксовые цепочки, а затем длинные цепочки. Если вычесть 2 бокса из всех линейных цепочек, то цепочка из 1 коробки будет иметь значение 1−2 = −1, а цепочка из 2 коробок — 2−2 = 0. Эти значения меньше, чем значения длинных цепей, поэтому правило вычитания 2 квадратов дает правильный результат сортировки и для коротких цепей.
Для того, чтобы следующий игрок взял или удержал контроль, ценность цепочки равна количеству ее ячеек − 2, если это линейная цепочка, и − 4, если это петля. Для сортировки цепочек получается тот же результат, если вычесть только 2 в случае цикла.
Что делать, если соперник не имеет контроля и не возьмет контроль в следующий ход? Разве противник не выиграет, если на основе этого порядка он будет двигаться следующим по разомкнутому циклу с двумя большими блоками, чем получит линейную цепочку с тем же «значением», но меньшим количеством блоков? Нет! Если противник завершит весь круг, то впоследствии, когда наступит очередь этого игрока, будет на один цикл меньше и захват управления будет на 2 бокса дешевле. ∎
Мы наблюдали этот эффект в примере 3, случай 2.1, где после того, как игрок А открывает цикл с А1, игрок Б берет на себя весь цикл, но в результате для А становится доступным взять контроль с помощью А7 и получить наилучший возможный результат.
Вышеуказанные правила понятны, если все коробки принадлежат к цепочке, т.е. если на всех коробках нарисовано хотя бы 2 стороны. Но что делать, если есть 0- и 1-боксы?
К каким сетям относятся эти коробки?
Правило 4: Чтобы установить последовательность цепочек, отсортированных по значению, выполните следующий цикл совершения ходов, пока не будет завершена вся доска.
- Откройте одну из цепочек, для которой значение (количество коробок, или, если это петля, количество коробок −2) минимально с одним исключением: Если еще есть хотя бы одна петля, соединенная или разъединенная, и если есть только одна разъединенная линейная цепочка, и если нет связанного дерева только линейных цепочек, то не открывайте последнюю разъединенную линейную цепочку.
- Завершите открытую цепочку без подсчета ящиков. Рисование линий в конце линейной цепочки может изменить 1-бокс на 2-бокс и, таким образом, либо объединить две линейные цепочки, либо отрезать петлю.
Если в эндшпиле все еще есть 0-боксы и 1-боксы, то можно думать о таком боксе как о точке, а о цепочках думать как о линиях, которые заканчиваются в таких точках или заканчиваются на краю доски, а затем получить искусственное дополнительное очко.
Точки вместе с их соединительными линиями в математике называются graph.
Исключение в Правиле 4, сформулированном на «языке графов», гласит: не размыкайте линейную цепь, соответствующую линии, отделенной от оставшегося графа, если оставшийся граф имеет разъединенную часть, содержащую цикл, и не имеет разъединенной части, которая не содержит цикла (и поэтому называется «деревом» на языке графов).
Пример 4: График типа 'T'
На квадрате 1 начертана буква 'T':
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
График, соответствующий этой доске, будет похож на T с 4 точками, где − и | в Т-образной встрече и 3 очка на 3-х концах Т.
Слева от 1-бокса находится одна из двух самых коротких цепочек. Открыв его и завершив
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
, вы увидите, что доска будет завершена путем завершения 2 цепочек, одной с 3 и одной с 9 коробками.
Пример 5: Граф типа 'P'
На коробке 1 начертана буква «P»:
+---+---+---+---+ | | + +---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
Если нарисовать сторону над 1-боксом или справа от этого бокса, то получится и откроется одна большая линейная цепочка из 12 боксов, которую никто не захочет отдавать сопернику. Проведя линию под 1-боксом, вы разделите доску на разомкнутую линейную цепочку с 4 коробками и петлю с 8 коробками.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
В Правиле 4 выше было сформулировано исключение. Пример 6 иллюстрирует это исключение.
Пример 6: График 'P' плюс несвязанная линейная цепочка
Можно открыть две линейные цепочки, одну справа и одну снизу.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
Кейс 1. Открываем сначала самую короткую цепочку
Сделан 21 ход, так что если игрок А начал, то следующий ход ходит игрок.
Если после открытия самой маленькой цепочки с помощью B1 игрок A сразу же берет управление в свои руки, мы получаем
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
и счет A:B = (1+4+6):(2+2+0) = 11:4, где (2+2+0) означает, что игрок B получает из 3 открытых цепочек в указанном порядке 2, 2 и 0 боксов. Поскольку B может открыть только 2-ю линейную цепочку с помощью B5, игрок A может оставаться под контролем с помощью A10 со стоимостью всего 2 и получить цикл бесплатно.
Кейс 2. Сначала открываем длинную линейную цепочку
После того, как B открывает длинную цепочку с B1 внизу и эта цепочка завершена, тот, кто получает последний квадрат (клетки), должен открыть цепочку. Согласно нашему Правилу 2, игрок В открывает петлю следующим ходом В8, чтобы сделать захват/удержание контроля дорогостоящим. Эта стратегия работает, потому что взятие/удержание контроля в цикле не имеет смысла для игрока А, поскольку это стоит 4 бокса, но выигрывает только 3 бокса в последней цепочке.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
Счет A:B = (4+6+0):(2+0+3) = 10:5
Если бы А не играл DD в первой цепочке:
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
, то счет A:B = (6+0+3):(0+6+0) = 9:6 был бы хуже для A. Причина в том, что игра в цикле после его открытия (B9 выше) стоит 6−3=3 очка, а захват контроля в первой длинной цепочке стоит всего 2 очка, поэтому стоит взять контроль в первой цепочке. 10:5 лучше, чем 9:6 для игрока А.
При сравнении случаев 1 и 2 и двух счетов 11:4 и 10:5 становится ясно, что игрок В должен первым открыть длинную цепочку. Причина в том, что если бы B первым открыл разорванную линейную цепочку, то цикл завершился бы последним, а это означает, что игроку A не пришлось бы платить 4 очка при игре в DDD в цикле, чтобы сохранить контроль. Мы нарушим наше предыдущее Правило 2. В общем случае можно показать, что если в разорванной цепочке есть m коробок, в соединенной линейной цепочке n коробок, а в петле есть p коробок, то игрок В, открывающий разорванную цепочку первым, дает В 4 очка из 2 DD, тогда как когда В открывает присоединенную линейную цепочку, то В получает
мин(p + max(0,m-4),min(6,m+2))
Много моментов. Наименьшее значение, которое это может принять, происходит, когда p имеет наименьшее значение, равное 4 (цикл имеет по крайней мере 4 коробки), аm имеет наименьшее значение, которое равно 3 (самая короткая длинная линейная цепочка, если бы самая короткая цепочка имела только 2 коробки, она бы мгновенно разыгралась с помощью Жестокосердного Подачки, и формула была бы другой). При p = 4 и m = 3 игрок B получит
мин(4 + макс(0,-1),мин(6,5)) = мин(4+0,5) = 4
а для p > 4 или m > 4 игрок B получит больше 4 очков.
Что делать, если есть разные цепочки с одинаковым наименьшим значением?
Если разные цепочки имеют одинаковое наименьшее значение, то наша программа использует правило для открытия связанной цепочки. Идея заключается в том, что существует вероятность того, что через эту разомкнутую цепочку становится доступной петля, что может сделать захват/удержание контроля только более дорогостоящим.
В играх обычно берут управление на себя, играя в DD/DDD в начале эндшпиля. Но если есть много цепочек с 3 боксами и лупы с менее чем 8 боксами, то, возможно, лучше не играть в DD/DDD и не брать контроль на себя. Поэтому нам нужен общий алгоритм, а не только эмпирическое правило.
Когда стоит играть в DD/DDD, а когда нет?
В литературе по игре Dots первое прохождение DD/DDD также называется захват контроля. Это означает, что игрок берет под контроль того, кто получает последнюю длинную цепочку, что может быть не то же самое, что взять под контроль игру и выиграть ее, НЕ играя в DD/DDD, как мы увидим ниже.
Когда у игрока есть возможность играть DD/DDD, то у него есть возможность поменяться ролями с противником по цене 2 очка (DD) или 4 очка (DDD). Если известно количество очков, полученных при оптимальной игре в оставшихся цепочках, то можно решить, стоит ли сейчас менять роли по цене 2 (если проигрываемая в данный момент цепочка линейная) или по цене 4 (если проигрываемая в данный момент цепочка представляет собой петлю). Вместе с заработком на текущей цепочке можно определить количество очков перед открытием текущей цепочки. Этот расчет можно выполнить в обратном направлении, начиная с конца игры, если знать последовательность открытых цепочек. Такая последовательность может быть определена по правилу 4 выше.
Правило 5: Решите, играть ли в DD/DDD или нет, используя псевдокод ниже.
В следующем псевдокомпьютерном коде переменная A — это количество очков, полученных в оставшейся части игры игроком, который открывает следующую цепочку, а переменная B — это количество очков, полученных другим игроком. Количество оставшихся коробок — А+В. Мы считаем в обратном направлении и для удобства помечаем цепочки в обратном порядке: последняя открытая цепочка в игре — цепочка 1, цепочка до этого — цепочка 2 и так далее. Текущая цепочка называется цепочкой k. Любая цепь j имеет n_j ящиков. Переменная playDD записывает, воспроизводится ли DD/DDD в цепочке j.
В следующих строках псевдокода
- (1)-(3) инициализирует 3 переменные в результате проигрывания последней цепочки.
- (4)-(22) update A, B, playDD для цепочки j, где j идет назад от предпоследней цепочки (j=2) к текущей цепочке k.
- (5)-(13) если цепочка j линейная, то стоимость равна 2
- (14)-(22) если цепочка j является циклом, стоимость равна 4
- (6)-(9), (15)-(18) если выигрыш B−A больше стоимости (2 или 4), то играем DD и уменьшаем B на стоимость и прибавьте ее к А. В любом случае B получают n_j.
(1) A = 0
(2) B = n_1
(3) playDD = ложный
(4) Для каждой цепочки j от 2 до k:
(5) Если цепочка j линейна:
(6) Если B > (A + 2):
(7) playDD = истинный:
(8) B = B + n_j - 2
(9) A = A + 2
(10) Иначе:
(11) playDD = ложный:
(12) B = A + n_j
(13) A = B
(14) Иначе → Если chain j — это цикл:
(15) Если B > (A + 4):
(16) playDD = истинный
(17) B = B + n_j - 4
(18) A = A + 4
(19) Иначе
(20) playDD = ложный
(21) B = A + n_j
(22) A = B
После этого расчета A — это счет игрока, открывшего текущую цепочку B - счет в пользу соперника и playDD говорит, должен ли соперник играть DD/DDD сейчас. ∎ (Конец Правила 5)
Этот псевдокод может показаться сложным для не-программиста, но его легко выполнить в голове, потому что он означает только проверить, перевешивает ли выгода от сохранения контроля затраты на него, т.е. затраты на игру в DD/DDD.
Вопрос для теста
Мы знаем, что в первую очередь открываются самые низкие цепочки создания стоимости. Означает ли это, что игра в DD/DDD становится более выгодной ближе к концу игры?
Другими словами, всегда ли игра в DD/DDD означает, что нужно играть до конца, так как в противном случае соперник возьмет контроль в свои руки и выиграет?
Почти во всех случаях да. Но в примере 6, случае 2 мы видели, что некоторый цикл с низкой стоимостью может быть доступен только после завершения линейных цепочек с более высокой стоимостью. Как следствие, несмотря на то, что на момент открытия цикла не было достаточного стимула играть в DDD (в последней цепочке было всего 3 бокса, в то время как DDD стоит 4 бокса), стимула было достаточно, чтобы играть в более ранний DD, стоимость которого равна всего 2.
Вопрос для теста
Предположим, что кто-то правильно оценивает, стоит ли играть в DD/DDD. Они решают, играть ли в нее и получить последнюю цепочку.
Всегда ли этот игрок будет выигрывать?
Нет. Например, предположим, что у нас есть 5 линейных цепочек по 3 коробки в каждой. Получение последней дает поощрение в виде 3 коробок, которых достаточно, чтобы заплатить по 3 ДД каждая, стоимостью 2 и получить 1 коробку. Это означает, что первая цепочка завершена целиком, и еще 3 розыгрыша DD дают очки (3+2+2+0) : (0+1+1+1+3) = 9:6 для игрока, который не получил последнюю цепочку.
Идеальны ли наши правила игры в эндшпили?
Нет. Когда на большой доске есть много цепочек, соединенных через 0-боксы и 1-боксы, то несколько из них могут иметь одинаковое количество боксов, и тогда может потребоваться более тонкая теория или поиск для выбора оптимальной, на основе которой другие цепочки станут доступны позже через завершение первых цепочек.
Правило длинной цепи
Правило 6: Первый игрок должен попытаться сделать количество точек + количество длинных линейных цепочек четным, а второй игрок должен попытаться сделать это значение нечетным.
Обоснование правила
Для начала мы введем некоторые переменные, где '#' означает 'число':
nt = # ходов (# раз, когда игрок сделал последовательные ходы)
nd = # точек
r = # рядов точек
c = # столбцов точек
nl = # линий
nb = # коробок
nc = # длинных цепей
nz = # терна, открывшего первую длинную цепочку в эндшпиле
Мы начнем с выведения отношения, известного как тождество Эйлера.
nb = (r−1)(c−1) = rc − r − c + 1
nd = rc
nl = # горизонтальных линий + # вертикальных линий
= r(c−1) + c(r−1)
= 2rc − r − c
И поэтому
nl = nb + nd − 1 .
Это отношение эквивалентно тождеству Эйлера, которое справедливо для произвольных графов, т.е. любое количество nd точек, связанных любым числом nl линий, не только вертикально и горизонтально, окружающих nf грани, где в нашем случае nf = nb + 1, потому что наша прямоугольная сетка точек имеет дополнительную окружающую грань, которая также учитывается в тождестве Эйлера:
nl − nd + 2 = nf (= nb + 1).
Далее мы подсчитываем количество ходов всей игры.
nt = nl − ((# раз, когда рисование линии завершило хотя бы 1 квадрат)
− 1 {Заполнение самого последнего ящика не дает еще одного хода.})
= nl − (nb − (# ходов, которые заполняют 2 бокса) − 1)
= nl − nb + 1 + (# ходов, которые заполняют 2 бокса)
= nd {используя наше предыдущее соотношение nl = nb + nd − 1}
+ (# DD в линейных цепочках) + (# циклов) + (# DDD в циклах)
Последняя строка является результатом того, что при завершении цикла последний ход всегда завершает два бокса, а если DDD играется в цикле, то еще один ход также завершает 2 бокса. Мы называем производное отношение
Формула количества оборотов:
nt = nd + (# DD в линейных цепочках) + (# циклов) + (# DDD в циклах)
Это точная формула, которая не основана ни на каких предположениях.
Вычисление nz — это поворот, открывающий первую длинную цепочку
После того, как первая длинная цепочка будет открыта в эндшпиле, в случае, если не будет сыграно ни DD, ни DDD, то количество оставшихся ходов будет равно количеству длинных цепочек, поскольку каждый игрок завершает одну цепочку. Следовательно, если (# из DD) = (# из DDD) = 0, то
nz {# хода, который открывает первую длинную цепочку в эндшпиле}
= nd + (# петель) − (# длинных цепей)
= nd − (# длинных линейных цепей)
Формула для nz также действительна, если воспроизводятся DD/DDD.
Оправдание:
Любая игра в DD/DDD не может изменить то, что уже происходило ранее, а именно ходы nz, которые приводят к открытию первой длинной цепи в эндшпиле. Для каждого сыгранного DD и DDD количество ходов в эндшпиле увеличивается на 1 (пожалуйста, проверьте), поэтому при вычитании количества ходов в эндшпиле из общего количества ходов (# DD) и (# DDD) будут отменены, и мы получим то же значение для nz, как если бы DD/DDD не были сыграны.
Таким образом, ни один игрок не хочет делать этот ход, т.е. первый игрок не хочет, чтобы nz было нечетным и, следовательно, хочет, чтобы nz было четным. 2×(# длинных линейных цепочек) является четным числом, поэтому добавление его к nz не изменяет, является ли nz четным или нечетным, что в конечном итоге приводит к
Правило длинной цепи: Первый игрок пытается сделать (# точек) + (# длинных линейных цепочек) даже в то время как второй игрок пытается сделать это нечетным. ∎
Неверное выведение правила длинной цепи
В некоторых публикациях об игре DOTS делаются два ненужных предположения для вывода правила длинной цепи.
1. Предположение: Если оба игрока играют в эндшпиле оптимально, то тот, кто делает последний ход, выигрывает из-за высокого значения последней и самой большой цепочки и из-за того, что ему не нужно снова ходить и открывать другую цепочку для соперника.
Таким образом, первый игрок хочет, чтобы nt = (# ходов) было нечетным, чтобы иметь возможность сделать первый и последний ход и выиграть.
2. Предположение: Все длинные цепочки, кроме последней, играются с DD/DDD. Таким образом, (# циклов) + (# DDD в циклах) является четным и может быть проигнорировано, а nt = nd + (# DD в линейных цепочках) становится nt = nd + (# длинных линейных цепочек) − 1. Следовательно, первый игрок хочет, чтобы это nt было нечетным, чтобы иметь возможность сделать последний ход, то есть когда (# точек) + (# длинных линейных цепочек) четно - правило длинной цепи. ∎
Но мы знаем, что эти два предположения не являются необходимыми для того, чтобы правило длинной цепи было истинным. Следующий пример продемонстрирует это.
Какой успех гарантирован правилом для одного игрока?
Правило длинной цепи дает необходимое и достаточное условие для принятия решения о том, какой игрок первым сыграет в первой открытой длинной цепочке в эндшпиле. Этот игрок P может выбрать, играть ли в DD/DDD или не играть. У нас 2 кейса.
Если первая длинная цепочка линейная , то в ней минимум 3 бокса, а игра в DD имеет стоимость 2 бокса.
• Если стимулом для игры в DD является <2, то игрок P не будет играть DD и заберет всю первую цепочку, а соперник получит максимум на 1 бокс больше из оставшихся цепочек, поэтому P получает в эндшпиле как минимум 3−1 = на 2 бокса больше, чем соперник.
• Если стимул равен 2, то не имеет значения, играет ли P DD или не играет DD в первой длинной цепочке и, следовательно, получает на ≥3 бокса больше в эндшпиле.
• Если стимул равен >2, то P играет DD и получает на >3 бокса больше в эндшпиле.
Если первая длинная цепочка представляет собой петлю, то в худшем случае первая цепочка имеет 4 бокса, а стимул равен 4, и тогда, независимо от того, играет ли кто-то в DDD или нет, оба игрока получат одинаковое количество очков в эндшпиле. Но если поощрение равно >4, то игра в DDD даст больше очков, а если поощрение равно <4, то не игра в DDD даст больше очков, потому что в цикле минимум 4 коробки. И если первая длинная цепочка представляет собой петлю с более чем 4 боксами, то P получит эти дополнительные очки в качестве преимущества в эндшпиле, даже если стимул равен 4.
Какова возможная разница в счете в начале эндшпиля?
• Если количество 1-цепочек четное, а количество линейных 2-цепочек четное, то разница в счете в начале эндшпиля равна нулю.
• Если количество 1-цепочек четное, а количество линейных 2-цепочек нечетное, то счет в начале эндшпиля равен 2.
• Если количество 1-цепочек нечетное, то после завершения всех 1-цепочек разница в очках равна 1. Затем каждая завершенная 2-цепочка будет переворачиваться только между обоими игроками из тех, кто лидирует на 1 бокс.
Так насколько же важно правило длинной цепи?
В каких случаях правило длинной цепи не определяет результат?
Какого правила тогда следует придерживаться?
Пример 7: Тестирование правила в необычной ситуации
В следующем матче игрок А начинает игру. На этой доске было сделано нечетное число 5×3 = 15 ходов. Ход 16 откроет первую длинную цепочку, которая удовлетворяет выведенной нами формуле: 16 = (# точек) − (# линейной длинной цепи) = 20 − 4. Тот, кто сделает этот ход, в данном случае игрок Б, проиграет, если игрок А сыграет ДД соответствующим образом.
+-B-+ + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
Игрок А начал, и игрок Б должен был открыть цепочку.
Сколько наберет счет, если будет сыграно три DD?
Если А играет DD 3 раза, то итоговый счет А:В = 6:6.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
Счет в последних 3 цепочках 5:4, поэтому играть в DD в первой цепочке и платить 2 очками за получение одного очка не оптимально.
Какой счет начисляется при игре на двух DD?
Для А лучше взять всю первую цепочку и получить итоговый счет А:В = 7:5.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Какое предположение о неправильном выводе правила длинной цепи нарушено?
Оба предположения были нарушены. А выигрывает, но не получает последнюю цепочку. DD не разыгрывается в каждой длинной линейной цепочке.
Действует ли правило длинной цепи для этой оптимальной игры?
Получаем (# точек) + (# длинных линейных цепочек) = 20 + 4 = 24, что четно, и первый игрок выигрывает, как и предсказывает правило. Так что это правило лучше, чем альтернативное доказательство с ненужными предположениями и неправильными толкованиями.
Вопрос для теста
Требуется ли для оптимальной игры либо играть в DD/DDD, ЛИБО не играть в DD/DDD?
Нет, оба могут быть одинаково хороши. Имея только две длинные цепочки по 3 бокса, А должен сыграть DD, дав счет A:B = 4:2.
+-B-+ + +---+---+ | | | | A | A | + + + +---+---+ | | | → | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
Таким образом, стимулом играть в DD перед этими двумя цепочками является 4 − 2 = 2, что равно стоимости игры в DD. Таким образом, обе пьесы дают одинаковый счет: A:B = (0+1+3):(3+2+0) = 4:5 = (2+2+0):(1+1+3)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
Вопрос для теста
Может ли случиться так, что при оптимальной игре игроки постоянно начинают и перестают играть в DD/DDD?
Да. Выше мы видели, как добавление цепочки из 3 коробок изменило счет с 4:2 на 4:(2+3) = 4:5. Стимул играть в DD перед этими 3 цепочками будет равен 5−4 = 1 < 2, что меньше, чем стоимость игры в DD, которая равна 2. Следовательно, с четырьмя цепочками по 3 бокса, первая не будет играть с DD. Если бы была еще одна цепочка с 3 боксами, счет стал бы (4+3):5 = 7:5 = (4+1):(5+2), поэтому стимул играть вторым в 5 цепочках из 3 боксов был бы 7−5 = 2, поэтому игра DD была бы нормальной, давая в обоих случаях счет (2+5):(1+7) = 7:8 = 7: (3+5).
+-B-+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Добавив больше цепочек с 3 коробками, можно получить больше изменений между игрой и неигрой DD.
Выполняется ли правило длинной цепи?
Читателю рекомендуется ознакомиться с правилом длинной цепи с большим количеством примеров, в которых используются циклы.
Пример 8: Применение правила длинной цепи
На this website Дэвида Уилсона показана следующая позиция, которая имеет всего один ход для победы следующего игрока.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
Кто бы выиграл, если бы оба игрока следовали нашим правилам эндшпиля?
Эта доска имеет четное количество точек и четное количество длинных цепочек. В последней длинной цепочке не будет разыгран ход DD, поэтому обычно будет разыграно нечетное количество ходов DD, и поэтому # очков + # DD нечетно, поэтому количество ходов нечетное, поэтому первый игрок получит последнюю цепочку и выиграет. Это соответствует «Правилу длинной цепи»: «Первый игрок должен попытаться сделать # точек + # длинных (линейных) цепочек четными, а второй игрок должен попытаться сделать их нечетными».
Что может сделать 2-й игрок?
2-й игрок не может изменить количество точек, а скорее количество ходов DD, пожертвовав 2 бокса и сделав ход, обозначенный как B, который является единственным выигрышным ходом, который есть у 2-го игрока в данной ситуации:
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +Этот ход уменьшает количество длинных цепочек с 2 до 1 и, таким образом, делает # точек + # длинных (линейных) цепочек нечетными и, таким образом, позволяет 2-му игроку выиграть с преимуществом в одно очко вместо этого проигрыша с разницей в одно очко.
Как могла бы продолжаться игра?
Следующие вариации приводят к A:B = 4:5, то есть к победе B в 1 очко.
+A8-+B4-+A5-+ B9 | B13 B14 +A3-+A12+---+ A11 B10 B15 B16 +---+---+---+ | B A2 A7 +A1-+---+B6-+ +A5-+A10+B6-+ B13 | B9 A11 +A12+A3-+---+ B4 B14 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+ +A5-+B4-+B6-+ A10 | B13 B14 +B9-+A13+---+ A11 A3 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+
Этот шаг нарушает самое первое Правило 1 о том, чтобы не создавать 3-боксы, если в этом нет необходимости. Насколько плохо это нарушение Правила 1?
Это нарушение Правила 1 не менее странно, чем игра в ДД. Как мы выяснили ранее, это нормально играть в DD и платить цену в 2 очка за то, чтобы поменяться ролями. Так что эта жертва минимальна и хороша, если она имеет тот же эффект, что и прием DD.
В вышеуказанной части этой страницы были введены технические термины и сформулированы правила. Эндшпиль подробно описан, и для первой части игры правило длинной цепи дает руководство. Если вы хотите узнать больше о первой части игры, пожалуйста, проверьте [2] и [3] в Справочниках. Следующее дерево решений обобщает эту веб-страницу.
Дерево решений
Чтобы ссылки ниже работали, нужно развернуть текст выше, нажав
- Если есть хотя бы одна 3-коробка (коробка, которую можно укомплектовать), то определите все цепочки, которые прикреплены ко всем этим 3-коробкам.
- Если одна из этих цепочек линейна и имеет хотя бы 2 соседних блока, то заполните все боксы из всех линейных и всех закольцованных цепочек, кроме этих двух соседних блоков этой одной линейной цепочки. Затем анализируйте, играть ли DD и либо играть DD, либо заполнить последние 2 коробки.
- Если все открытые цепочки имеют длину 1 или являются петлевыми, то сначала завершите все открытые цепочки длиной 1, а если есть хотя бы одна открытая цепочка петли, то завершите все открытые цепочки, за исключением последних 4 коробок одной из открытых цепей. Затем анализируйте, играть ли в DDD или заполнить последние 4 поля.
- Если нет коробки, которую можно заполнить, то
- Если каждый ход будет создавать 3-бокс, то
- Если самая короткая цепочка - это цепочка из 2 цепей
+---+---+ +---+---+
, где 2 ненарисованные линии могут быть где угодно, но не в одном и том же поле, то играйте в середине, чтобы достичь (в данном случае):+---+---+ | +---+---+ - Else, определите следующую цепочку для открытия и играйте в любом месте этой цепочки.
- Если самая короткая цепочка - это цепочка из 2 цепей
- Если есть ход, который не создает 3-бокс, то
- Если в игре будет не более 1 длинной цепочки (линейной или петлевой), например, потому что прямоугольник из точек маленький или тонкий, то ходы DD/DDD не будут сыграны, и тогда игрок, делающий последний ход, выигрывает, и из-за Формулы Количества Ходов, первый игрок должен попытаться сделать сумму # точек + # петель нечетной, а второй игрок четной. Поскольку символ # точек фиксирован, можно попытаться получить только четное или нечетное количество циклов. Если это невозможно, то измените того, кто играет первым.
- если понятно, что в игре будет как минимум две длинные цепочки, но непонятно сколько, то следуйте Правилу длинной цепи и в качестве первого игрока попытайтесь сделать # точек + # длинных линейных цепочек четными, а в качестве второго игрока попытайтесь сделать сумму нечетной, иначе
- Если понятно, сколько длинных линейных цепочек выпадет в игре, и если правило длинной цепи предсказывает проигрыш в игре, то подумайте о том, чтобы сделать жертвенный ход, чтобы уменьшить количество длинных линейных цепочек.
- Если каждый ход будет создавать 3-бокс, то
Ссылки
[1] Википедия: Точки и квадраты, см. другие ссылки там.
[2] Берлекамп, Элвин Р.; Конвей, Джон Х.; Гай, Ричард К. (1982), «Глава 16: Точки и коробки», Выигрышные способы для ваших математических игр, том 2: В частности, игры, Academic Press, стр. 507–550.
[3] Берлекамп, Элвин (2000), Игра в точки и коробки: сложная детская игра, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Уилсон, Дэвид, Результаты анализа точек и коробок, Университет Висконсина
Индекс
Чтобы ссылки ниже работали, нужно развернуть текст выше, нажав
- # ...
- количество ...
- Box
- маленький квадрат с 4 соседними точками в качестве углов
- ?-Box
- 0-box, 1-box, 2-box, 3-box, 4-box - это коробки, на которых нарисованы 0, 1, 2, 3, 4 стороны.
- Chain
- последовательность, состоящая из соединенных 2-блоков. Существуют цепочки linear и loopy цепочки.
- Double-Crossed Move
- ход, который завершает сразу два соседних блока. Он разыгрывается сразу после хода Double Dealing в линейной цепочке или когда loop завершен.
- DD
- аббревиатура от Double Dealing
- DDD
- аббревиатура от Double Dealing
- Double Dealing
- ход, ведущий к
- Double Double Dealing
- ход в середине открытого цикла с 4 оставшимися боксами, создавая, например,
+---+---+ +---+---+---+---+ | | | | | +---+---+ или +---+---+---+---+ или | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ или +---+---+ + | | | | +---+---+ +---+- Эндшпиль
- финальная стадия игры, которая начинается, когда становится неизбежным создание 3-бокса на следующем ходу
Тождество Эйлера — общее отношение для любого графа на плоскости, а не только в игре с точками, где линии не пересекаются: (# линий) − (# точек) + 2 = (# граней) где грани включают в себя 'внешнее лицо', так для нас (# граней) = (# коробок) + 1.- Граф
- понятие в математике, в котором ряд точек соединен рядом линий
- Жестокосердный раздаточный материал
- рисование средней линии в
+---+---+ +---+---+ +---+---+ или | или | | +---+---+ +---+ + + + +или их повернутых и зеркальных версиях, в результате чего получаются+---+---+ +---+---+ +---+---+ | или | | или | | | +---+---+ +---+ + + + +или их повернутые и зеркальные версии- Половинчатый раздаточный материал
- Рисование линии на границе цепи с двумя коробками, ведущими к
+---+---+ +---+---+ | или | | +---+---+ +---+ +
- Line
- отрезок линии, соединяющий две соседние точки по горизонтали +---+ или по вертикали
- Линейная цепь
- цепь, которая имеет 2 конца, не обязательно прямые
- Правило длинной цепи
- Первый игрок должен попытаться сделать # из точек + # из длинных цепочек четными, а второй игрок должен попытаться сделать это значение нечетным.
- Длинная цепь
- цепь с ≥ 3 коробками
- Безумный ход
- ход, дающий противнику возможность принести жертву
- Loop
- аббревиатура от loopy chain
- Loopy chain
- a chain without ends
- Перемещение
- рисование линии
- Number of Turn Formula
- точная формула, дающая количество ходов в игре, которая является основой для правила длинной цепи и которая полезна для небольшого количества точек, чтобы решить, быть ли первому игроку или нет
- Размыкание цепи
- выполнение хода внутри цепи или на одном из ее концов (если это линейная цепь) и создание таким образом 3-бокса.
- Правило 1
- Самая очевидная игра заключается в том, чтобы избежать создания 3-box, который соперник мог бы забрать, заполнив его.
- Правило 2
- Для упорядочивания цепочек возьмите для последней цепи самую большую длинную линейную цепь, а если длинной линейной цепи нет, то возьмите самую большую петлю.
- Правило 3
- Если в эндшпиле у всех коробок выпало хотя бы 2 стороны, то для упорядочивания всех остальных цепочек отсортируйте их по (# коробок) − 2 (если это цикл).
- Правило 4
- Чтобы установить последовательность цепочек, отсортированных по значению для следующего игрока, сначала с наименьшим значением, выполните последовательность ходов (см. text) до тех пор, пока вся доска не будет завершена.
- Правило 5
- Используйте предоставленный псевдокод (см. text), чтобы решить, играть ли в DD/DDD или нет.
- Правило 6
- Относится к Правило длинной цепи
- Захват управления
- то же самое, что и игра DD/DDD, что, как важный побочный эффект, дает возможность повторять игру DD/DDD в следующих цепочках
- Turn
- последовательность последовательных ходов одного игрока
Следите за обновлениями или подписывайтесь на них: