Sprouts: A zseniális ceruzajáték, amit Cambridge-ben találtak fel

Bevezetés

A Sprouts az egyik legelegánsabb játék, amit valaha kitaláltak. **1967. február 21-én** találták fel egy délutáni teázás során a Cambridge-i Egyetem Tiszta Matematika és Matematikai Statisztika Tanszékén, Angliában. Két matematikus — **John Horton Conway** és **Michael Stewart Paterson** — éppen ötleteket vázoltak egy papírlapon, amikor rábukkantak egy megtévesztően egyszerű szabályrendszerre, amely évtizedekre lekötötte a matematikusokat, rejtvényrajongókat és alkalmi játékosokat.

Annak ellenére, hogy semmi többre nincs szükség hozzá, mint egy ceruzára és egy papírfecnire, a Sprouts rendkívüli **matematikai mélységet** rejt. Minden játék kapcsolódik a **gráfelmélethez**, a modern matematika egyik legfontosabb ágához. A pontok csúcsok, a görbék élek, és az a korlátozás, hogy a vonalak nem keresztezhetik egymást, azt jelenti, hogy minden Sprouts pozíció egy **síkgráf**. Az a szabály, hogy minden pontnak legfeljebb három kapcsolata lehet, a maximális csúcsfok háromnak felel meg, és az Euler-képlet a síkgráfokra garantálja, hogy minden játéknak végül véget kell érnie.

A Sprouts-ot az teszi figyelemre méltóvá, hogy szabályainak egyszerűsége és stratégiájának komplexitása ellentétben áll egymással. Egy gyerek kevesebb mint egy perc alatt megtanulhatja játszani, mégis a játék több mint fél évszázada ellenáll a teljes matematikai elemzésnek. Számítógépes tudósok megoldották a Sprouts-ot kis számú kezdőpont esetén, de egy általános képlet, amely meghatározza a nyertest bármely kezdőpozícióra, továbbra is a **kombinatorikus játékelmélet** egyik nyitott problémája.

Amire szükséged van

A Sprouts egyik legnagyobb vonzereje, hogy gyakorlatilag semmire sincs szükség a játékhoz. Itt van a teljes felszereléslista:

• Egy lap papír — bármilyen méret megfelelő, de egy standard A4-es vagy levélméretű lap ideális egy 3 pontos játékhoz. Használjon nagyobb lapot vagy egy alátét hátulját több kezdőpontos játékokhoz.
• Egy ceruza vagy toll — a ceruza előnyösebb, mert a játéktábla zsúfolttá válhat, és óvatosan szeretné rajzolni a vonalakat. Egy vékony hegyű toll is jól működik.

Ez tényleg minden. Nincs tábla, nincs kocka, nincs kártya, nincs alkalmazás. A Sprouts tökéletes játék egy váróterembe, egy hosszú vonatútra, egy csendes otthoni estére vagy egy tantermi szünetre. Gyakran említik az egyik legjobb játékként, amit **abszolút semmilyen felszerelés nélkül játszhatsz, azon kívül, amit bármely zsebben vagy íróasztalfiókban megtalálsz**.

Beállítás

Egy Sprouts játék beállítása körülbelül öt másodpercet vesz igénybe:

1. Rajzoljon n pontot a papírra Helyezzen el néhány pontot (úgynevezett „foltot”) a papír egy üres területére. A **standard játék 3 ponttal kezdődik**, durva háromszög alakban elrendezve, bőséges hellyel közöttük. Bármennyi ponttal kezdhet, de a 3 a hagyományos kiindulópont, és **6-8 lépéses** játékot eredményez — tökéletes a szabályok elsajátításához.
2. Hagyjon bőséges helyet Győződjön meg róla, hogy a pontok jól elkülönülnek, és bőséges üres papír veszi körül őket. Ahogy a játék halad, a görbék a meglévő vonalak között fognak fonódni, és a tábla egyre zsúfoltabbá válik. A jól elhelyezett pontokkal kezdve van helye a manőverezésre.
3. Döntse el, ki kezd A játékosok bármilyen megegyezéses módszerrel eldöntik, ki kezdi a játékot — pénzfeldobással, kő-papír-ollóval, vagy egyszerűen felváltva játékról játékra. Versenyző Sprouts-ban az első vagy második lépés jelentős előnyt jelenthet a kezdőpontok számától függően.

Hogyan kell játszani

A játékosok felváltva lépnek. Minden körben a játékosnak pontosan két műveletet kell végrehajtania: rajzolnia kell egy görbét, majd elhelyeznie egy új pontot. Itt vannak a teljes szabályok:

1. Rajzoljon egy görbét, amely összeköt bármely két pontot (vagy egy hurkot egy pontból önmagába) A görbe bármilyen alakú lehet — egyenes, ívelt, hurkolt — mindaddig, amíg egy élő ponton kezdődik és egy másik élő ponton végződik (vagy ugyanazon a ponton, hurkot képezve). A két végpont lehet ugyanaz a pont vagy különböző pontok.
2. A görbe NEM keresztezhet semmilyen létező vonalat, és nem haladhat át semmilyen ponton Ez a Sprouts alapvető korlátozása. Az új görbének az összes korábban rajzolt vonal körül kell haladnia anélkül, hogy érintené vagy keresztezné azokat, és nem haladhat át semmilyen létező ponton (csak pontokon kezdődhet és végződhet).
3. Helyezzen egy ÚJ pontot valahova az éppen megrajzolt görbére Miután megrajzolta a görbét, jelöljön meg egy új pontot bárhol rajta. Ez az új pont két szegmensre osztja a görbét. Az új pont azonnal „élő” és használható a jövőbeli körökben — de már **3 elérhető kapcsolatából 2-t felhasznált** (egyet a görbe minden egyes szegmensére, amelyen ül), így csak **1 fennmaradó kapcsolata** van.
4. Egy pont „halott”, ha 3 vonal érinti Minden pont — legyen az az eredeti kezdőpontok egyike, vagy egy játék közben létrehozott pont — legfeljebb **3 kapcsolattal** rendelkezhet (3 vonalvégpont érinti). Amint egy pont eléri a 3 kapcsolatot, **telítettnek** vagy „halottnak” nevezik, és nem használható végpontként a jövőbeli görbékhez. Hasznos a halott pontokat kis kereszttel megjelölni vagy bekarikázni a nyomon követés érdekében.
5. Az a játékos NYER, aki az UTOLSÓ érvényes lépést teszi A játék akkor ér véget, amikor már nem tehető érvényes lépés — azaz, amikor lehetetlen bármilyen görbét rajzolni két élő pont közé anélkül, hogy keresztezne egy létező vonalat. A **normál játék konvenciója** (a standard szabály) szerint az a játékos a nyertes, aki az utolsó sikeres lépést tette. Az a játékos veszít, aki a körében nem tud lépni.

A Sprouts négy megtörhetetlen szabálya

Játékidő és matematikai tulajdonságok

A Sprouts egyik legszebb aspektusa, hogy játékidejét egy pontos matematikai képlet korlátozza. Egy **n kezdőponttal** induló játék esetében:

• A játék mindig **legalább 2n lépésig** tart
• A játék mindig **legfeljebb 3n − 1 lépésig** tart
• A játék **garantáltan befejeződik** — matematikailag lehetetlen, hogy egy Sprouts játék örökké tartson

A bizonyítás az elérhető kapcsolatok teljes számának megszámolásán alapul. Kezdetben **n pont** van, mindegyik **3 elérhető kapcsolattal**, ami összesen **3n** kapcsolódási pontot ad. Minden lépés pontosan **2 kapcsolatot** használ fel (egyet a görbe mindkét végpontján), és létrehoz **1 új pontot** **1 elérhető kapcsolattal**. Így minden lépés pontosan **1-gyel** csökkenti az elérhető kapcsolatok teljes számát. A játék akkor ér véget, amikor már nem lehet két elérhető kapcsolatot összekötni egy nem keresztező görbével, aminek be kell következnie, mielőtt az elérhető kapcsolatok száma nullára csökken.

A standard **3 pontos játék** esetében ez azt jelenti:

• Minimum: 6 lépés
• Maximum: 8 lépés

Ez a szűk tartomány is hozzájárul ahhoz, hogy a 3 pontos Sprouts ilyen jól kiegyensúlyozott játék. Elég hosszú a stratégiai mélységhez, de elég rövid ahhoz, hogy gyorsan lejátsszák — a legtöbb játék **5-15 perc** alatt befejeződik, gondolkodási idővel együtt.

Stratégia

A Sprouts stratégiája sokkal mélyebb, mint amit az egyszerű szabályok sugallnak. Íme a kulcsfontosságú fogalmak, amelyek elválasztják a tapasztalt játékosokat a kezdőktől:

A régiók megértése

Ahogy a görbéket rajzolják a papírra, azok a játéktér területét **különálló régiókra** osztják — meglévő vonalakkal és a papír szélével határolt zárt területekre. Minden régió lényegében egy független aljáték. Az élő pontok egy régión belül csak más, ugyanazon régión belüli pontokhoz kapcsolódhatnak (mivel egy görbe nem keresztezheti a határvonalakat). Az egyes régiókon belüli elérhető lépések megszámolása az összes Sprouts stratégia alapja.

A fennmaradó lépések számának ellenőrzése

Mivel a nyertes az a játékos, aki az **utolsó** lépést teszi, a fennmaradó lépések teljes száma határozza meg, ki nyer. Ha Önön a sor, és **páratlan számú lépés maradt**, akkor nyerő pozícióban van (feltételezve a tökéletes játékot). Ha **páros számú**, akkor az ellenfél van előnyben. A kulcsfontosságú stratégiai képesség az olyan lépések megtétele, amelyek az Ön javára módosítják a fennmaradó játék paritását (páros/páratlan jellegét).

Grundy-értékek és kombinatorikus játékelmélet

Komoly játékosok számára a Sprouts elemezhető a kombinatorikus játékelmélet **Sprague-Grundy tételével**. Minden Sprouts pozíciónak van egy **Grundy-értéke** (más néven nim-értéke), és egy kombinált pozíció Grundy-értéke az önálló régiók Grundy-értékeinek nim-összege (XOR). Amikor a teljes pozíció Grundy-értéke **0**, a pozíció vesztes a soron lévő játékos számára; amikor **nem nulla**, a pozíció nyerő. A gyakorlatban a Grundy-értékek táblán való kiszámítása rendkívül nehéz, de a koncepció megértése segít az intuíció fejlesztésében.

Stratégiai tippek kezdőknek

Számítógépes elemzés

A Sprouts teljes számítógépes elemzését elvégezték kis számú kezdőponttal induló játékok esetében. Az eredmények egy mintázatot mutatnak (bár még nem bizonyították, hogy minden n-re érvényes):

A mintázat úgy tűnik, egy 6 periódusú ciklust követ: a második játékos nyer n = 0, 1, 2 (mod 6) esetén, és az első játékos nyer n = 3, 4, 5 (mod 6) esetén. Ezt a sejtést számítógéppel ellenőrizték körülbelül **n = 44** értékig, de a formális bizonyítás továbbra is nehezen elérhető.

Vizuális példa: Egy 3 pontos játék

Íme egy teljes 3 pontos játék bemutatása, amely megmutatja, hogyan fejlődik a tábla több lépésen keresztül. A pontok A, B és C betűvel vannak jelölve a tisztaság kedvéért.

Variánsok

A Sprouts számos variánst inspirált, mindegyik a maga csavarjával az eredeti szabályokon:

Misère Sprouts

A Misère Sprouts-ban a szabályok megegyeznek a normál Sprouts-szal, egy kritikus különbséggel: az a játékos **veszít**, aki az **utolsó lépést** teszi, ahelyett, hogy nyerne. Ez a nyerési feltétel megfordítása alapvetően megváltoztatja a stratégiát. A játékosoknak most meg kell próbálniuk rákényszeríteni ellenfelüket az utolsó lépés megtételére. A normál Sprouts-ban nyerő pozíciók Misère-ben vesztesek lehetnek, és fordítva. A Misère Sprouts-ot is elemezték számítógéppel, és az eredmények eltérő mintázatot mutatnak az első és második játékos győzelmeire vonatkozóan a normál változathoz képest.

Brussels Sprouts

A Brussels Sprouts-ot John Conway találta fel a Sprouts humoros kiegészítőjeként. Pontok helyett a játék **keresztekkel (+)** kezdődik. Minden keresztnek **4 ága** van, és minden ág egy elérhető kapcsolódási pontnak számít (a normál Sprouts-ban pontonként 3 helyett). Amikor egy játékos görbét rajzol, annak két szabad ágat kell összekötnie, és egy új keresztet (egy vonallal a görbén keresztül) helyeznek el a vonalon, létrehozva **2 új szabad ágat**.

Annak ellenére, hogy stratégiai játéknak tűnik, a Brussels Sprouts valójában egy **előre meghatározott játék**: **n kereszttel** kezdve a játék **mindig** pontosan **5n − 2 lépésig** tart, függetlenül attól, hogyan játszanak a játékosok. Ez azt jelenti, hogy a nyertes teljes mértékben attól függ, hogy az 5n − 2 páratlan vagy páros. 2 kezdő kereszttel a játék 8 lépésig tart, és a második játékos nyer. Conway állítólag élvezte, hogy gyanútlan ellenfeleket hívott ki Brussels Sprouts-ra, ismerve az eredményt, mielőtt az első lépés megtörtént volna.

Star Sprouts

A Star Sprouts-ban a játékosok különböző kezdő konfigurációkkal kezdenek az egyszerű, elszigetelt pontok helyett. A kezdőpontok tartalmazhatnak már vonalakkal összekötött pontokat, létrehozva előre létező régiókat már az első lépéstől. Ez a variáns változatosabb nyitó pozíciókat tesz lehetővé, és felhasználható annak vizsgálatára, hogyan befolyásolják a különböző gráfstruktúrák a játékmenetet.

Sprouts felületeken

Az igazán matematikai kalandvágyók számára a Sprouts játszható más felületeken is, nem csak sík papírlapon. Egy **tóruszon** (egy fánk felületén, ami papíron szimulálható úgy, hogy a felső és alsó éleket, valamint a bal és jobb éleket összekötöttnek tekintjük) való játék drámaian megváltoztatja a játékot, mert a görbéknek több helyük van manőverezni anélkül, hogy kereszteznék egymást. A Sprouts egy **Klein-palackon** vagy egy **projektív síkon** még furcsább topológiai lehetőségeket vezet be.

A Conway és Paterson történet

A Sprouts feltalálása az egyik legbájosabb történet a rekreációs matematikában. 1967 februárjában **John Horton Conway** fiatal kutató volt a Gonville and Caius College-ban, Cambridge-ben, és már akkor hírnevet szerzett magának generációjának egyik legkreatívabb matematikusként. **Michael Stewart Paterson** doktorandusz volt ugyanabban a tanszéken. A ketten teáztak és matematikai játékokról beszélgettek — ami Conway egész életen át tartó szenvedélye volt —, amikor pontokat és vonalakat kezdtek rajzolni papírra.

A Sprouts szabályai gyorsan, szinte teljesen kialakultak. Conway később felidézte, hogy a játék feltalálását követő órákon belül az egész tanszék játszott vele. A papírok tele voltak Sprouts pozíciók kusza hálóival. Az előadásokat megzavarták. A játék futótűzként terjedt Cambridge-ben. Conway a feltalálást az egyik legboldogabb matematikai pillanatának nevezte — az izgalmat, hogy valami valóban újat fedezett fel, ami egyszerre volt egyszerű, gyönyörű és mély.

Conway a 20. század egyik legünnepeltebb matematikusává vált, híres az **Élet játékáról** (egy sejtautomata), a **szürreális számokról**, a **Monstrous Moonshine** sejtésről és tucatnyi más hozzájárulásáról. Mindig különleges vonzalommal viseltetett a Sprouts iránt, gyakran játszotta kollégáival és diákjaival. 2020 áprilisában hunyt el, de az általa feltalált játékok — köztük a Sprouts — továbbra is örömet szereznek az új generációknak.

Paterson, aki a Warwicki Egyetemen elismert karriert futott be az elméleti számítástechnika területén, a Sprouts feltalálását a tiszta **együttműködési szerencse** pillanataként írta le — két elme játszott egy ötlettel, amíg valami csodálatos nem született.

Miért szeretik a matematikusok a Sprouts-ot

A Sprouts több okból is különleges helyet foglal el a matematikában:

• Ez egy kapu a gráfelmélethez. A Sprouts intuitív, gyakorlati bevezetést nyújt a csúcsokhoz, élekhez, síkbeliséghez és a csúcsfok fogalmához. Azok a diákok, akik Sprouts-ot játszanak, gráfelméletet művelnek anélkül, hogy észrevennék.
• Mély, megoldatlan problémákhoz kapcsolódik. Az a sejtés, hogy melyik játékos nyer bármely adott számú kezdőpont esetén, továbbra is bizonyítatlan. A játék a kombinatorikus játékelmélet, a topológia és a számítási komplexitás metszéspontjában helyezkedik el.
• Bemutatja az egyszerű szabályok és a komplex viselkedés közötti szakadékot. A Sprouts az emergent komplexitás egyik legtisztább példája — egy olyan rendszer, ahol hihetetlenül egyszerű szabályok rendkívül nehezen elemezhető viselkedést eredményeznek.
• Mindenki számára elérhető. Sok matematikai játékkal ellentétben, amelyek speciális felszerelést vagy kiterjedt beállítást igényelnek, a Sprouts-ot bárki, bárhol, azonnal játszhatja. Ez hatékony oktatási eszközzé teszi az általános iskolától az egyetemig.
• Valóban szórakoztató. Sok matematikai játék érdekes fejtörőként, de nem különösebben élvezetes játszani. A Sprouts mindkettőre képes — egy mély matematikai objektum és egy valóban lebilincselő kétjátékos játék feszültséggel, meglepetéssel és egy jól lejátszott lépés elégedettségével.

Martin Gardner, a Scientific American legendás rekreációs matematikai rovatvezetője, 1967 júliusi rovatában mutatta be a Sprouts-ot, mindössze hónapokkal a feltalálása után. Gardner cikke bevezette a játékot a világ közönségének, és megszilárdította helyét a nagy matematikai játékok panteonjában. Azt írta, hogy a Sprouts „az utóbbi idők legjelentősebb új ceruza-papír játéka” volt, egy ítélet, amelyet csak megerősített a játék által inspirált évtizedes matematikai kutatás.

Gyakran Ismételt Kérdések