Paddor och grodor

Ett exempel på det kombinatoriska spelet Toads And Frogs

Det kombinatoriska spelet Toads and Frogs är ett partisanspel som uppfunnits av Richard Guy . Detta matematiska spel användes som ett introduktionsspel i boken Winning Ways for your Mathematical Plays .

Känd för sin enkelhet och elegansen i sina regler, är Toads-and-Frogs användbar för att illustrera huvudkoncepten för kombinatorisk spelteori. I synnerhet är det inte svårt att utvärdera enkla spel som bara involverar en padda och en groda, genom att konstruera spelträdet för startpositionen. Det allmänna fallet med att utvärdera en godtycklig position är dock känt för att vara NP-hårt. Det finns några öppna gissningar om värdet av några anmärkningsvärda positioner.

En enspelarversion av spelet har också övervägts.

Regler

Paddor och grodor spelas på en 1 × n remsa av rutor. När som helst är varje ruta antingen tom eller upptagen av en enda padda eller groda. Även om spelet kan börja med vilken konfiguration som helst, är det vanligt att börja med att paddor upptar på varandra följande rutor längst till vänster och grodor som upptar på varandra följande rutor längst till höger på remsan.

När det är vänsterspelarens tur att flytta, kan de antingen flytta en padda en ruta till höger, till en tom ruta, eller "hoppa" en padda två rutor till höger, över en groda, till en tom ruta. Det är inte tillåtet att hoppa över en tom ruta, en padda eller mer än en ruta. Analoga regler gäller för höger: vid en tur kan högerspelaren flytta en groda till vänster till ett närliggande tomt utrymme, eller hoppa en groda över en enda padda till en tom ruta omedelbart till vänster om paddan. Enligt den normala spelregeln som är konventionell för kombinatorisk spelteori, förlorar den första spelaren som inte kan röra sig på sin tur.

Notation

En position av Paddor-och-grodor kan representeras med en sträng med tre tecken: $T$ för en padda, $F$ för en groda och $\square$ för ett tomt utrymme . Till exempel representerar strängen $T\square \square F$ en remsa med fyra rutor med en padda på den första och en groda på den sista.

I kombinatorisk spelteori kan en position beskrivas rekursivt i termer av dess alternativ, det vill säga de positioner som vänsterspelaren och högerspelaren kan flytta till. Om vänster kan flytta från en position $P$ till positionerna $L_{1}$ , $L_{2}$ , ... och höger till positionerna ${\ displaystyle R_{1}}$ , ${\displaystyle R_{2}} , ..., då$ skrivs positionen ${\displaystyle P} konventionellt$ $P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.$

I denna notation, till exempel, $T\square \square F=\{\square T\square F|T\square F\square \}$ . Det betyder att Vänster kan flytta en padda en ruta åt höger, och Höger kan flytta en groda en ruta åt vänster.

Spelteoretiska värden

Det mesta av forskningen kring Paddor-och-grodor har handlat om att bestämma de spelteoretiska värdena för vissa speciella Paddor-och-grodor-positioner, eller att bestämma om några särskilda värden kan uppstå i spelet.

Vinnande sätt för dina matematiska pjäser visade först många möjliga värden. Till exempel, :

T\square \square F=0

TF\square \square =1

T\square F\square ={\frac {1}{2}}

TFT\square F=\{0|0\}=\star

T\square TFF=\{0|\star \}=\uparrow

1996 bevisade Jeff Erickson att för alla dyadiska rationella tal q (som är de enda talen som kan uppstå i ändliga spel), finns det en Padda-och-grodor-positioner med värdet q. Han hittade också en explicit formel för några anmärkningsvärda positioner, som ${\displaystyle T^{a}\square ^{b}F} ,$ och formulerade sex gissningar om värdena för andra positioner och spelets hårdhet .

Dessa gissningar underblåste ytterligare forskning. Jesse Hull bevisade gissning 6 år 2000, som säger att det är NP-svårt att bestämma värdet på en godtycklig Padda-och-grodor-position. Doron Zeilberger och Thotsaporn Aek Thanatipanonda bevisade gissningar 1, 2 och 3 och hittade ett motexempel till gissning 4 2008. Gissning 5, den sista fortfarande öppen, säger att T a ◻ b F a { $} \square ^{b}F^{a}}$ är ett oändligt litet värde, för alla (a, b) utom (3, 2).

Enspelarpussel

Det är möjligt för en omgång Paddor och Grodor att sluta tidigt. En pusselversion för en spelare av spelet Toads and Frogs, publicerad 1883 av Édouard Lucas , kräver en sekvens av drag som börjar i standardstartpositionen som varar så länge som möjligt och slutar med alla paddor till höger och alla av grodorna till vänster. Dragen krävs inte för att växla mellan paddor och grodor.