Shannon değiştirme oyunu - Shannon switching game

Shannon anahtarlama oyunu bir olan bağlantı oyunu tarafından icat, iki oyuncu için Amerikan matematikçi ve elektrik mühendisi Claude Shannon , "bilgi teorisinin babası" İki oyuncu keyfi kenarlarını boyama sırayla 1951. önce bir süre grafiğinde . Bir oyuncunun amacı, renklerinin kenarlarının bir yolu ile iki seçkin köşeyi birbirine bağlamaktır. Diğer oyuncu, bunun yerine rengini kullanarak (veya eşdeğer olarak kenarları silerek) bunu önlemeyi amaçlar. Oyun genellikle dikdörtgen bir ızgara üzerinde oynanır ; Oyunun bu özel durumu, 1950'lerin sonlarında Amerikalı matematikçi David Gale tarafından bağımsız olarak icat edildi ve Gale veya Bridg-It olarak biliniyor .

Kurallar

Oyuncu Kesme 3 tur (noktalı kenarlar), oyuncu Kısa 4 tur (yeşil kenarlar) aldı.

Oyun , A ve B olmak üzere iki özel düğüm ile sonlu bir grafik üzerinde oynanır . Grafiğin her kenarı renklendirilebilir veya kaldırılabilir. İki oyuncuya Kısa ve Kes ve alternatif hamleler denir . Cut'ın dönüşünde Cut, kendi seçtikleri renksiz bir kenarı grafikten siler. Short'un dönüşünde Short, grafikte hala herhangi bir kenarı renklendirir. Cut, grafiği A ve B'nin artık bağlı olmadığı bir grafik haline getirmeyi başarırsa Cut kazanır. Kısa bir renkli yolu oluşturmak için yönetirse A için B , Kısa kazanır. Oyun her zaman sınırlı sayıda hamleden sonra sona erer ve iki oyuncudan birinin kazanması gerekir. Kısa, Kes veya ilk hareket eden oyuncunun herhangi bir grafikte kazanan bir stratejinin varlığı garanti edilir.

Kısa ve kesin oyunlar ikilik vardır; yani oyun, her iki oyuncunun da aynı amacı olacak şekilde yeniden ifade edilebilir: seçkin kenar e ile belirli bir kenar kümesini güvenceye almak . Kısa çalışır kenar seti sağlamak için o e kadar bir yapan devre kesme kenar seti sağlamak için çalışır iken, bu konuda e bir cutset, iki bağlantı kenarlarının en az bir dizi oluşturur subgraphs .

Varyantlar

Yönlendirilmiş bir grafik ve yönlendirilmiş bir matroid üzerinde oynanan Shannon anahtarlama oyununun versiyonları teorik amaçlar için tanımlanmıştır; ancak buna karşılık gelen hiçbir ticari oyun yayınlanmadı.

fırtına

Gale'de kırmızı galibiyet

Amerikalı matematikçi David Gale tarafından icat edilen ve Martin Gardner'ın Scientific American Ekim 1958'deki sütununda açıklanan bu oyunda , farklı renklerde iki ızgara ızgarası bir ofsette üst üste bindirilir. Bir oyuncu, bir ızgara üzerinde dikey olarak bitişik noktaları birleştirir ve diğer oyuncu diğerini kullanır. Bir oyuncu, ızgarasının üstünü alta bağlamaya çalışırken, diğeri sol tarafını sağa bağlamaya çalışır. Oyun, dikdörtgen bir ızgarada oynanan Shannon değiştirme oyununa eşdeğerdir. Beraberlik sonuçlanamaz; ilk oyuncu her zaman doğru oyunla kazanabilir.

Planı uygulayan ticari bir tahta oyunu 1960 yılında Hassenfeld Brothers tarafından Bridg-It adı altında pazarlandı . Oyun, iki aralıklı 5x6 dikdörtgen kaide ızgarası (bir set sarı, diğeri kırmızı), her biri 20 kırmızı ve sarı plastik köprüden oluşan iki set ve bunları monte etmek için eşleşen mandallardan oluşan plastik bir tahtadan oluşuyordu. Oyuncular, bir oyuncu, tahtanın oyuncunun rengiyle işaretlenmiş iki zıt tarafını birleştirene kadar, eşleşen renkteki herhangi iki bitişik kaide üzerine bir köprü yerleştirir. Oyunun bir çeşidi talimatlarda açıklanmıştır: her oyuncu sınırlı sayıda köprü alır, örneğin 10. Tüm köprüler yerleştirildiğinde hiçbir oyuncu kazanmazsa, sırası gelen oyuncu, kazanana kadar köprülerinden birini yeniden konumlandırabilir. Sonuçlar. Oyun uzun süredir üretimden kalkmış durumda.

Game elektronik bir uygulama Gale mevcuttur Ludii Oyunları Portal .

Diğer oyunlarla ilişki

Shannon değiştirme oyunu, Maker-Breaker oyununun özel bir durumu olarak görülebilir, burada Maker için kazanma paternleri yolları birbirine bağlar.

Zayıf bağlantılı bir bağlantı oyunu olan Hex , altıgenlerden oluşan bir ızgarada oynanır ve 6 bağlantılıdır. Genelleştirilmiş Hex, Shannon oyunu gibi bir grafik üzerinde oynanır, ancak Hex'te kenarları renklendirmek yerine oyuncular köşeleri renklendirir. Bu oyunlar tamamen farklı yapı ve özelliklere sahiptir.

Dikdörtgen bir dizi nokta (veya grafik kağıdı) üzerinde kağıt ve kalemle oynanan bir başka bağlantı oyunu, çocukların " noktalar ve kutular " oyunudur . Oyuncular, herhangi iki bitişik noktayı birbirine bağlayan dikey veya yatay bir çizgide dönüşümlü çizim yapar. Bir çizgi bir kareyi tamamladığında, oyuncu kareye paraf eder. Tüm çizgiler doldurulduktan sonra en çok kareyi alan oyuncu kazanır.

Gale'nin Qua adlı bir uzantısı, N 3 hücre ızgarasından oluşan bir 3D oyun tahtası küpü üzerinde üç oyuncu tarafından oynanır . N, oyun tahtası küpünün kenarlarındaki hücre sayısına eşit tek bir sayıdır. İlk Qua Cube oyun tahtası düzeni ve kuralları, Board Game Geek girişinde açıklanmıştır.

hesaplama karmaşıklığı

1964'te matroid teorisini kullanan herhangi bir oyun için yönsüz anahtarlama oyunu için açık bir çözüm bulundu . Short , kalan seçilmemiş kenarların iki ayrık alt kümesinin bulunduğu bir konumu hedeflemelidir, öyle ki iki alt kümeden herhangi biri iki farklı köşeyi birbirine bağlayacaktır. Eğer kısa bu özelliğe sahip bir konumda sonuçları, bu bir hamle yapabilir Kısa bakılmaksızın diğer oyuncu ne yaptığının kazanabilirsiniz; Aksi takdirde, Cut kazanabilir.

PSPACE zor olabilen diğer bazı bağlantı oyunlarından farklı olarak , yönsüz anahtarlama oyunu için en uygun hareketler, hareket başına polinom zamanında bulunabilir . Grafikten tarafından seçilen kenarları ayrılmasından sonra Cut seçtiği kenarları ve sözleşme Kısa , ortaya çıkan grafik, a, küçük başlangıç grafiğin. Her biri farklı köşeleri birbirine bağlayan iki ayrık ağacın varlığını test etme problemi, polinom zamanında çözülebilen bir matris bölümleme problemi olarak gösterilebilir. Alternatif olarak, aynı problemi ağ akış algoritmalarını kullanarak da çözmek mümkündür .

Ayrıca bakınız

  • TwixT , kare ızgarada farklı ve daha zor bir bağlantı oyunu

Referanslar

  1. ^ Gardner, M. (1961). İkinci Scientific American Matematiksel Bulmacalar ve Saptırmalar Kitabı . NY: Simon ve Schuster. s. 86-87.
  2. ^ a b Lehman, Alfred (1964). "Shannon değiştirme oyununun bir çözümü". Endüstri ve Uygulamalı Matematik Derneği Dergisi . 12 (4): 687–725. doi : 10.1137/0112059 . JSTOR  2946344 . MR  0173250 .
  3. ^ Hayward, Ryan B.; van Rijswijck, Jack (2006). "Hex ve kombinatorik" . Ayrık Matematik . 306 (19–20): 2515–2528. doi : 10.1016/j.disc.2006.01.029 . MR  2261917 .
  4. ^ Stephen M. Chase (1972). "Shannon Anahtarlama Oyunlarını kazanmak için uygulanan bir grafik algoritması". ACM'nin İletişimi . 15 (4): 253–256. doi : 10.1145/361284.361293 . S2CID  21110956 .
  5. ^ Hamidoune, Yahya Ould; Las Vergnas, Michel (1986). "Grafikler ve matroidler üzerinde yönlendirilmiş anahtarlama" . Kombinatoryal Teori Dergisi . B Serisi. 40 (3): 237–239. doi : 10.1016/0095-8956(86)90083-3 .
  6. ^ Claudio, AP; Fonseca, S.; Sequeira, L.; Silva, IP (2015). "Shannon anahtarlama oyunu ve yönlendirilmiş varyantlar". Bourguignon'da J.-P.; Jeltsch, R.; Pinto, AA; Viana, M. (ed.). Dinamik, Oyunlar ve Bilim: Uluslararası Konferans ve Advanced School Planet Earth, DGS II, Portekiz, 28 Ağustos–6 Eylül 2013 . Matematik Bilimlerinde CIM Serisi. Springer. s. 187–199. doi : 10.1007/978-3-319-16118-1_10 . ISBN'si 978-3-319-16117-4.
  7. ^ Bridg-o en BoardGameGeek
  8. ^ "Ka" . BoardGameGeek . 2020-08-28 alındı .
  9. ^ Even, S. (Ekim 1976). "Polinom Uzayında Tamamlanan Bir Kombinatoryal Problem" . ACM Dergisi . 23 (4): 710–719. doi : 10.1145/321978.321989 . S2CID  8845949 .
  10. ^ Reisch, Stefan (1981). "Hex ist PSPACE-vollständig". Acta Bilişim . 15 (2): 167–191. doi : 10.1007/BF00288964 . MR  0599616 . S2CID  9125259 .

Dış bağlantılar

  • Grafik Oyunu , Shannon anahtarlama oyununun bir Java uygulaması