Перемика льна гра Ше ннона англ Shannon switching game абстрактна стратегічна гра винахідником якої є Клод Шеннон в найп

Перемика́льна гра Ше́ннона (англ. Shannon switching game) — абстрактна стратегічна гра, винахідником якої є Клод Шеннон (в найпростішому випадку в грі розглядається прямокутна решітка). Аналогічну гру незалежно винайшов (англ. David Gale), яка має назви Gale, Bridg-It, Клітка для пташки (Bird Cage).

Правила

Гравець Cut зробив 3 ходи (ребра пунктирною лінією), гравець Short зробив 4 ходи (ребра зеленого кольору)

Гра відбувається на скінченому графі з двома спеціальними (термінальними) вершинами A і B. Два гравці Short і Cut (a short cut — прямий (найкоротший) шлях) ходять по черзі. Cut своїм ходом видаляє вибране ним непофарбоване ребро. А Short своїм ходом фарбує вибране ним непофарбоване ребро з тих, що ще залишились в графі. Якщо ходи Cut зроблять граф таким, що вершини A і B стануть незв'язними, то Cut виграв. Якщо ж Short так пофарбує ребра, що вони утворять шлях від A до B, то Short виграв.

Правила гри мають ще одну інтерпретацію в термінах вузлів. А саме: дано граф G з двома термінальними вузлами s і t. Є два гравці названі Short і Cut. По черзі кожен гравець вибирає вузол графу G, не рівний s і t, який до кінця гри буде належати цьому гравцю. Гру починає Short. Він перемагає, якщо вибирає множину вузлів, яка разом з s і t утворює шлях в графі G із s в t. Cut перемагає, якщо всі вузли розподілені між гравцями, але Short не вибрав шлях в графі G із s в t.

Гравцю, який програв, надається право першого ходу в наступній грі.

Є версії перемикальної гри Шеннона для орієнтованих графів та орієнтованих матроїдів. Розв'язок для таких ігор однозначно може бути знайдений з використанням теорії матроїдів, на відміну від подібної задачі гекс, яка є важкою задачею класу PSPACE.

Алгоритм перемоги (стратегія гри)

Гра завжди закінчується після скінченної кількості ходів і один з гравців перемагає. В залежності від графу, виграє Short, Cut або той, хто ходить першим.

Гра Short і гра Cut є двоїстими; це означає, що гра може бути сформульована по-іншому так, що обидва гравці матимуть подібну мету: заволодіти певним набором ребер графу з виокремленим ребром e. Short намагається заволодіти набором ребер з e , який утворює цикл в графі, тоді як Cut намагається заволодіти набором ребер з e, який утворює розріз графу, тобто мінімальний набір ребер, який з'єднує два підграфи (робить граф незв'язним).

Примітки

Імовірно в назві гри використана багатозначна гра слів: Бріжіт, фр. Brigitte — жіноче ім'я; англ. bridge — з'єднувати мостом (Bridg(e) It — з'єднай це), долати завади, бридж (гра в карти)
Введение в теорию автоматов, языков и вычислений, 2-е издание. Издательский дом Вильямс. Сторінка 499
Stephen M. Chase (1972). An implemented graph algorithm for winning Shannon Switching Games. Communications of the ACM (Стівен М. Чейс. Здійсненний алгоритм пошуку в графі для перемоги в Перемикальній грі Шеннона. Журнал «Комунікації ACM» ). 15: 253—256. doi:10.1145/361284.361293.
Frederic Maire: «The Solution of Shannon Game» (Фредерік Мер: "Розв'язок гри Шеннона ") [ 8 квітня 2011 у Wayback Machine.], 2004

Посилання

, реалізація на Java
, онлайн гра Gale реалізована на PHP

[1] Імовірно в назві гри використана багатозначна гра слів: Бріжіт, фр. Brigitte — жіноче ім'я; англ. bridge — з'єднувати мостом (Bridg(e) It — з'єднай це), долати завади, бридж (гра в карти)

[2] Введение в теорию автоматов, языков и вычислений, 2-е издание. Издательский дом Вильямс. Сторінка 499

[3] Stephen M. Chase (1972). An implemented graph algorithm for winning Shannon Switching Games. Communications of the ACM (Стівен М. Чейс. Здійсненний алгоритм пошуку в графі для перемоги в Перемикальній грі Шеннона. Журнал «Комунікації ACM» ). 15: 253—256. doi:10.1145/361284.361293.

[4] Frederic Maire: «The Solution of Shannon Game» (Фредерік Мер: "Розв'язок гри Шеннона ") [ 8 квітня 2011 у Wayback Machine.], 2004