Dołącz do Piątki

Siatka startowa.

Po jednym ruchu.

Po czterech ruchach.

Gra kończy się, gdy nie można narysować więcej segmentów na siatce.

Join Five (znany również jako Morpion Solitaire, Cross 'n' Lines lub Line Game ) to gra w papier i ołówek dla jednego lub dwóch graczy, rozgrywana na siatce kropek w kształcie plusa. Początki gry sięgają prawdopodobnie północnej Europy. Wzmianki o grze po raz pierwszy pojawiły się we francuskich publikacjach w latach 70. XX wieku. Oprócz rekreacyjnego charakteru gra była przedmiotem badań teoretycznych i komputerowych poszukiwań rozwiązań.

Jak grać

Rysowana jest początkowa siatka kropek; kwadrat 4x4 kropek, z prostokątem 4x3 dodanym z każdej strony. Początkowy krzyż jest przedstawiony w niektórych wersjach gry.

Podczas każdej tury rysuj linię prostą o długości dokładnie pięciu „kropek”, tak aby:

Żadna część nowej linii nie może odtworzyć żadnej części wcześniej narysowanej linii. W wersji obrysowanej linia może być kontynuacją istniejącej linii (nie mogą na siebie zachodzić).
Przed narysowaniem linii na siatce brakuje dokładnie jednej z pięciu kropek objętych nową linią. Ta brakująca kropka (która może znajdować się na końcu nowej linii lub gdzieś pośrodku) jest również rysowana podczas tury.
W jedynej zarysowanej wersji, jeśli podczas rysowania linii nie jest potrzebna nowa kropka, kropka może zostać zapisana i może być używana w późniejszych turach.

Innymi słowy, utwórz pięcioodcinkową linię z czterech kropek i narysuj piątą (chyba, że w późniejszych turach jest zapisane, aby narysować dwie kropki).

Punktacja

Gra kończy się, gdy nie można narysować więcej segmentów na siatce.

W wersji dla dwóch graczy zwycięzcą jest gracz, który jako ostatni narysował odcinek linii. W wersji dla jednego gracza punktację uzyskuje się poprzez zliczenie liczby wylosowanych segmentów lub obliczenie całkowitej powierzchni siatki na koniec gry.

W zarysowanej wersji liczba wykonanych tur to wynik. Zwykle kontroluje się to za pomocą znaczników . Nie wiadomo, czy można to kontynuować w nieskończoność, ale gra staje się coraz trudniejsza (do pewnego momentu?), Gdy początkowa siatka zostanie całkowicie wykorzystana.

Strategia

Strategia różni się w zależności od tego, czy gra się w pojedynkę, czy z przeciwnikiem. W pierwszym przypadku ruchy są optymalizowane pod kątem maksymalnej liczby możliwych tur; w drugim przypadku celem jest bycie „nieefektywnym” przy wyborze ruchu w celu ograniczenia dostępnych ruchów przeciwnika.

Wariacje

Zasady można zmieniać, wymagając linii składających się z 4 zaznaczonych punktów w rzędzie zamiast 5, ze zmniejszoną konfiguracją początkową. Ponadto „rozłączna” odmiana gry nie pozwala dwóm równoległym liniom dzielić punkt końcowy, podczas gdy standardowa wersja „dotykająca” na to pozwala.

Rekordy i przeszukania komputerowe

Dla „dotykającej” wersji gry z liniami składającymi się z 5 zaznaczonych punktów, obecny rekord 178 linii został ustanowiony 12 sierpnia 2011 r., Korzystając z wyszukiwania Monte -Carlo przez algorytmistę Christophera Rosina. To o osiem ruchów więcej niż poprzedni rekord 170 linii z 1976 roku. Rekord z 1976 roku został sporządzony ręcznie, a wyszukiwania komputerowe nie były w stanie zbliżyć się do tego rekordu pomimo znacznego postępu, aż do sierpnia 2010 roku, kiedy Christopher Rosin użył wyszukiwania Monte-Carlo, aby uzyskać wynik 172 ruchów, przekraczający rekord z 1976 roku i 178 rusza rok później.

Dla „rozłącznej” wersji gry z liniami składającymi się z 5 zaznaczonych punktów rekord 82 linii uzyskano drogą wyszukiwania komputerowego, znalezionego również przez Christophera Rosina. Poprzedni rekord 80 linii ustanowił w 2008 roku Tristan Cazenave. W 2020 roku znaleziono 67-etapowe rozwiązanie przy użyciu AlphaZero .

Teoria

Uogólniony pasjans Morpion, w którym początkową konfiguracją może być dowolny skończony zbiór zaznaczonych punktów, należy do klasy problemów NP-trudnych, dla których nie jest znana wydajna metoda obliczeniowa znajdowania optymalnego rozwiązania. Nawet problem znalezienia w przybliżeniu optymalnego rozwiązania dla uogólnionego pasjansa Morpion jest NP-trudny.

W przypadku standardowych wersji pasjansa Morpion nie istnieją nieskończenie duże rozwiązania; górne granice zostały udowodnione na maksymalnej liczbie linii, które można uzyskać.

Linki zewnętrzne