| Dobd a hidat | |
|---|---|
| Játékosok | 2 |
| Kor | 7-től felfelé |
| Felkészülés a játékra | ~1 perc |
| A parti időtartama | < 20 perc |
| A szabályok összetettsége | egyszerű |
| Stratégia szint | átlagos |
| A véletlen befolyása | hiányzó |
| Fejleszti a képességeket | stratégiai gondolkodás |
| Médiafájlok a Wikimedia Commons oldalon | |
Bridge it , bridge-it , pipeline , birdcage , Shannon kapcsolójátéka vagy Gale játéka egy absztrakt hexa típusú játék két játékos számára [1] [2] . A játékot a 20. század közepén David Gale találta fel; ugyanakkor Claude Shannon az általánosított változatot tanulmányozta. 1958-ban Martin Gardner Scientific American rovatában mutatta meg a játékot a nagyközönségnek . Bár a bridge-it papíron is lehet játszani, a Hassenfeld Brothers (jelenleg Hasbro ) műanyag játékkészleteket készített [3] .
1. Üres tábla
2. Vörösök nyernek
3. Nyerő stratégia
4. A gép „dobja a hidat” (magyarázat lent)
5. A játék "grafizálása", bemutatva a klasszikus és az általánosított változat közötti kapcsolatot
A piros és kék játékosok szegmenseket rajzolnak a színük két szomszédos pontja közé. Az nyer, akinek sikerült a hidat a tábla széléről a szélére dobni: a piros játékos vízszintesen, a kék játékos függőlegesen.
Az első játékos, ha helyesen játszanak, nyer, ezt nem konstruktívan bizonyítja a stratégia kölcsönzési módszere (a kék-első a kék-másodiktól kölcsönzi a stratégiát), figyelembe véve a tábla szimmetriáját.
Egy egyszerű és szép stratégiát először O. Gross [1] [2] javasolt . Az első lépést a 3. ábra jelöli. Amikor a második játékos áthúzza a vékony fekete vonal egyik végét, az első játékos áthúzza a másikat. Ahogy Gross fogalmaz, a stratégia „tompa fegyver a tompa játékossal szemben, ravasz a ravasz ellen, de mindkét esetben győzelemhez vezet”.
Egy ilyen stratégia a legegyszerűbb jumper- és villanykörték automatával is megvalósítható, egy ilyen automata diagramját a 4. ábra mutatja [4] . Az első lámpa a gép első lépését világítja meg, és folyamatosan világít. A fennmaradó lámpák (gépmozgások) az áthidaló aljzatokhoz (emberi mozgások) vannak csatlakoztatva, amint az a 3. ábrán látható. Amint egy személy megmozdul (egy jumpert behelyez a foglalatba), egy lámpa kigyullad, jelezve a válaszát gép. A villanykörtéket legjobban hosszúkás árnyalatokban kell elhelyezni, amelyek hidakat imitálnak. Ha egy személy hirtelen „csalódik” és átlép az automata hídján, az automata ugyanezt teszi.
Gross stratégiája a B3-34 számológép 7 lépésébe helyezhető el [5] . Mivel a stratégia nem igényel memóriát, a program egyidejű játékmenetet is futtathat .
A Gex a hasonlóság ellenére egy teljesen más játék, nyerő stratégiát találni hozzá a PSPACE teljes feladat.
Ha a bal és a jobb oldali piros élt két csúcsra húzzuk össze , a felső és alsó kék élt pedig „vezetékkel összekötjük” és egybe húzzuk, a piros és a kék rács kettős gráfokká válik . Más szóval, a piros a sík gráf csúcsait hidak nélkül köti össze , [6] a kék ugyanazon gráf lapjait (5. ábra). Lehetőség van a gráf korlátozásainak elhagyására, ha a kéket nem az oldalak összekapcsolására, hanem az élek törlésére kényszeríti. Ezért az általánosított játékszabályok a következők:
Létezik egy összekapcsolt multigráf , [7] amelyen két csúcs van jelölve A és B. A „Vágott” játékos önállóan vág ki egy élt a gráfból, a „Rövid” játékos rögzíti az élt, ami sérthetetlenné teszi a vágással szemben. A rövidvágó nyer, ha meg tudta rögzíteni az útvonalat A-ból B-be. A vágó nyer, ha elválasztja ezeket a csúcsokat [8] .
Könnyen belátható, hogy a számtól függően a "Knock", "Short" vagy az nyer, aki az első lépést teszi. Az általánosított hídnak is van egy stratégiája, amelyet a matroidok nyelvén írnak le . [9]