Стратегия парного сочетания
Эта статья в значительной степени или полностью основана на одном источнике . ( январь 2019 г. ) |
В позиционной игре стратегия пар — это стратегия, которую игрок может использовать, чтобы гарантировать победу или, по крайней мере, заставить сыграть вничью. Она основана на разделении позиций на игровой доске на непересекающиеся пары. Всякий раз, когда противник выбирает позицию в паре, игрок выбирает другую позицию в той же паре.
Пример
Рассмотрим вариант крестиков-ноликов 5 на 5. Мы можем создать 12 попарно непересекающихся пар позиций на доске, обозначенных ниже как 1,...,12: [1] : 3
| 11 | 1 | 8 | 1 | 12 |
| 6 | 2 | 2 | 9 | 10 |
| 3 | 7 | * | 9 | 3 |
| 6 | 7 | 4 | 4 | 10 |
| 12 | 5 | 8 | 5 | 11 |
Обратите внимание, что центральный элемент (обозначенный *) не принадлежит ни одной паре; он не нужен в этой стратегии.
Каждая горизонтальная, вертикальная или диагональная линия содержит по крайней мере одну пару. Поэтому для форсирования ничьей можно использовать следующую стратегию пар: "всякий раз, когда ваш противник выбирает элемент пары i , выбирайте другой элемент пары i ". В конце игры у вас есть элемент каждой выигрышной линии. Таким образом, вы гарантируете, что другой игрок не сможет выиграть.
Поскольку оба игрока могут использовать эту стратегию, игра заканчивается вничью.
Этот пример обобщается ниже для произвольной игры Maker-Breaker . В такой игре цель Maker — занять весь выигрышный набор, а цель Breaker — не допустить этого, завладев элементом в каждом выигрышном наборе.
Стратегия сопряжения для Maker
Стратегия пар для Maker требует набора пар элементов, таких что: [1] : 119
- Все пары попарно не пересекаются;
- Каждый набор, содержащий хотя бы один элемент из каждой пары, содержит некоторый выигрышный набор.
Всякий раз, когда Breaker выбирает элемент пары, Maker выбирает другой элемент той же пары. В конце набор Maker содержит по крайней мере один элемент из каждой пары; по условию 2 он занимает весь выигрышный набор (это верно даже когда Maker ходит вторым).
В качестве примера рассмотрим игровое поле, содержащее все вершины в идеальном бинарном дереве, кроме корня. Выигрышные множества — это все пути от листа до одного из двух дочерних элементов корня. Мы можем разбить элементы на пары, соединив каждый элемент с его родственным элементом. Стратегия пар гарантирует, что Maker выиграет, даже если будет ходить вторым. Если Maker ходит первым, он может выиграть, даже если игровое поле также содержит корень: на первом шаге он просто выбирает корень, а с этого момента играет по вышеприведенной стратегии пар.
Стратегия парного использования для Breaker
Стратегия парного соединения для Breaker требует набора пар элементов, таких как:
- Все пары попарно не пересекаются;
- Каждый выигрышный набор содержит как минимум одну пару.
Всякий раз, когда Maker выбирает элемент пары, Breaker выбирает другой элемент той же пары. В конце Breaker имеет элемент в каждой паре; по условию 2 у него есть элемент в каждом выигрышном наборе.
Пример такой стратегии парного сочетания для игры в крестики-нолики размером 5 на 5 показан выше. [1] : 2–3 показывают другие примеры для игры в крестики-нолики размером 4x4 и 6x6.
Другой простой случай, когда у Брейкера есть стратегия пар, — это когда все выигрышные наборы попарно не пересекаются и их размер составляет не менее 2.
Ссылки
- ^ abc Хефец, Дэн; Кривелевич Михаил ; Стоякович, Милош; Сабо, Тибор (2014). Позиционные игры . Семинары в Обервольфахе. Том. 44. Базель: Биркхойзер Верлаг ГмбХ. ISBN 978-3-0348-0824-8.
