Najkrótsza gra halma dla dwóch graczy

19

W grze w szachy możliwe jest zakończenie gry po 4 ruchach (po 2 każdy) z głupcem .

Twoim celem jest znalezienie Fool's Mate of Halma : dwuosobowej gry Halma, która minimalizuje liczbę rozegranych tur.

Istnieje ponad 10 56 stanów kart i widziałem, że współczynnik rozgałęzienia przekracza 1000, więc są szanse, że nikt nie znajdzie optymalnego rozwiązania. Zamiast tego próbujesz znaleźć najlepsze możliwe rozwiązanie.

Powinieneś przesłać listę ruchów oraz kod użyty do wygenerowania tych ruchów.

Wyjaśnienie gry

Halma jest podobna do chińskich warcabów, ale gra się na kwadratowej planszy 16 * 16.

Początkowo plansza wygląda następująco:

Tablica startowa

Celem gry jest przeniesienie wszystkich pionków na pozycje początkowe pionów przeciwnika.

Podczas tury gracz może:

  • Przejdź kolejkę

  • Przenieś jeden ze swoich pionków na sąsiednie puste miejsce. Sąsiednie przestrzenie obejmują przekątne.

  • Weź jeden ze swoich pionków i wykonaj dowolną liczbę razy: Przeskocz pion na sąsiedni pion, lądując na polu naprzeciwko skoczka.

Oto przykład ilustrujący 2. typ ruchu.

Skacze

Zasady

Prześlij listę legalnych ruchów, które zakończą grę.

Prześlij dowolny kod użyty do wygenerowania listy.

Jeśli uzyskasz lepszy wynik z kodu innej osoby, opublikuj wynik w komentarzu lub edytuj jego post z nowymi wynikami.

Każdy ruch musi albo Noneprzejść turę, albo (x1,y1,x2,y2)przenieść kawałek, gdzie (x1,y1)znajdują się współrzędne elementu do przesunięcia i (x2,y2)są celem tego elementu (w przypadku ruchów skoku ignoruj ​​współrzędne pośrednie). Współrzędne zaczynają się (0,0)w lewym górnym rogu. Współrzędne x zwiększają się w prawo, współrzędne y zwiększają się w dół. Ruchy powinny być oddzielone znakami nowej linii.

Możesz użyć tego skryptu python, aby zweryfikować swoje ruchy. Służy python halma_verify.py < filedo weryfikacji wejść file.

Najkrótsza lista wygrywa.

optimization board-game puzzle-solver pudełko kartonowe
źródło
6
niektóre dyskusji technicznych ruchów i roztwór w 47 ruchów: arxiv.org/pdf/0803.1245.pdf
SeanC

Odpowiedzi: