Gå med i Five

Startrutan.

Efter ett drag.

Efter fyra drag.

Spelet slutar när inga fler segment kan ritas på rutnätet.

Join Five (även känt som Morpion solitaire, Cross 'n' Lines eller Line Game ) är ett papper- och pennspel för en eller två spelare, spelat på ett plusformat rutnät av prickar. Spelets ursprung är troligen i norra Europa. Referenser till spelet dök upp först i franska publikationer på 1970-talet. Utöver att spelas för rekreation har spelet varit föremål för teoretiska studier och datorsökningar efter lösningar.

Hur man spelar

Ett första rutnät med punkter ritas; en kvadrat med 4x4 punkter, med en rektangel på 4x3 tillagd på varje sida. Det första krysset beskrivs i vissa versioner av spelet.

Under varje varv, rita en rak linje som är exakt fem "prickar" lång, så att:

Ingen del av den nya linjen kan spåra någon del av en tidigare ritad linje. I den skisserade versionen kan linjen fortsätta en befintlig linje (de får inte överlappa).
Exakt en av de fem prickarna som täcks av den nya linjen saknas i rutnätet innan linjen dras. Denna saknade punkt (som kan vara i vardera änden av den nya linjen, eller någonstans i mitten) dras också under vändningen.
I den enda skisserade versionen, om ingen ny punkt behövs när linjen dras, kan punkten sparas och användas i senare vändningar.

Med andra ord, gör en femsegmentslinje av fyra punkter och rita in den femte (såvida den inte sparas för att rita två punkter i senare varv).

Poängsättning

Spelet slutar när inga fler segment kan ritas på rutnätet.

I tvåspelarversionen vinner den sista spelaren som drar ett linjesegment. I enspelarversionen uppnås poäng genom att räkna antalet dragna segment eller genom att beräkna den totala arean av rutnätet i slutet av spelet.

I den skisserade versionen är antalet genomförda varv poängen. Detta hålls vanligtvis i schack med hjälp av räkningsmärken . Det är okänt om detta kan fortsätta på obestämd tid, men spelet blir allt svårare (upp till en viss punkt?) när det ursprungliga rutnätet har använts helt.

Strategi

Strategin skiljer sig beroende på om spelet spelas ensam eller mot en motståndare. I det första fallet är drag optimerade för det maximala antalet möjliga varv; i det andra fallet är målet att vara "ineffektiv" med dragval för att begränsa motståndarens tillgängliga drag.

Variationer

Reglerna kan varieras genom att kräva linjer med 4 markerade punkter i rad istället för 5, med en reducerad startkonfiguration. Dessutom tillåter inte den "osammanhängande" varianten av spelet att två parallella linjer delar en slutpunkt, medan standardversionen för "touching" tillåter detta.

Register och datorsökningar

För den "berörande" versionen av spelet med linjer som består av 5 markerade punkter, etablerades det nuvarande rekordet på 178 linjer 2011 den 12 augusti, med hjälp av en Monte-Carlo-sökning av algoritmen Christopher Rosin. Detta är åtta drag mer än det tidigare rekordet från 1976 på 170 linjer. Rekordet från 1976 gjordes för hand, och datorsökningar hade inte kunnat närma sig detta rekord trots betydande framsteg, förrän i augusti 2010 när Christopher Rosin använde en Monte-Carlo-sökning för att få ett resultat av 172 drag, vilket översteg rekordet från 1976, och 178 flyttar ett år senare.

För den "osammanhängande" versionen av spelet med linjer som består av 5 markerade punkter har rekordet på 82 linjer erhållits genom datorsökning, också hittat av Christopher Rosin. Tidigare rekord på 80 linjer hittades 2008 av Tristan Cazenave. En 67-stegslösning hittades 2020 med en AlphaZero- liknande metod.

Teori

Generalized Morpion solitaire, där startkonfigurationen kan vara vilken ändlig uppsättning av markerade punkter som helst, är en medlem av den NP-hårda klassen av problem för vilka ingen effektiv beräkningsmetod för att hitta en optimal lösning är känd. Även problemet med att hitta en ungefär optimal lösning för generaliserad Morpion patiens är NP-svårt.

För standardversionerna av Morpion solitaire finns det inga oändligt stora lösningar; övre gränser har bevisats på det maximala antalet rader som kan erhållas.

externa länkar