tło

Mu Torere to gra, która jest jedną z dwóch znanych Maoryjczyków z Nowej Zelandii przed wpływami europejskimi. To sprawia, że ​​jest to bardzo wyjątkowa gra, ponieważ ma „obiektywne kryterium wygranej” i zasady gry, które różnią się od większości innych istniejących gier.

Rozgrywka:

Plansza jest ośmiokątem. Pomiędzy każdym sąsiadującym wierzchołkiem istnieją połączenia, a węzeł środkowy jest połączony ze wszystkimi wierzchołkami. W dowolnym momencie osiem z dziewięciu węzłów zajmują kamienie. Na początku są cztery białe kamienie i cztery czarne kamienie, z których każdy zajmuje połowę ośmiokąta, a węzeł środkowy jest pusty. Czarny porusza się pierwszy.

W każdej turze gracz może przesunąć jeden ze swoich kamieni wzdłuż jednej z 16 krawędzi z jednego węzła do pustego węzła. Kamień można przenieść z zewnętrznego węzła do węzła centralnego tylko wtedy, gdy kamień znajduje się obok kamienia przeciwnika.

Gracz przegrywa, gdy nie jest w stanie wykonać legalnego ruchu, co ma miejsce, gdy nie ma krawędzi łączącej kamień z pustym węzłem.

Oto strona internetowa, która wyjaśnia zasady (wraz ze schematem) i oferuje pewne analizy.

Wyzwanie

Twoim zadaniem jest napisanie najkrótszego programu, w którym możesz zagrać w doskonałą grę Mu Torere przeciwko ludzkiemu przeciwnikowi. Twój program powinien być w stanie wyświetlać i aktualizować planszę, wykonywać ruchy i odbierać ruchy od ludzkiego przeciwnika. Co najważniejsze, powinna zagrać w idealną grę.

Idealna gra?

Tak, idealna gra. Przeprowadziłem analizę gry i okazało się, że gra trwa nieskończenie długo, jeśli obie strony doskonale w nią grają. Oznacza to, że Twój program nigdy nie powinien przegrać. Ponadto twój program powinien być w stanie wymusić wygraną za każdym razem, gdy przeciwnik popełni błąd, który pozwala programowi wymusić wygraną. To, jak Twój program znajdzie idealny ruch, zależy od Ciebie.

Detale

Po każdym ruchu (i na początku gry) Twój program powinien wydrukować planszę. Niezależnie od tego, czy chcesz wyświetlić tablicę, musi ona pokazywać wszystkie węzły i być w pełni połączona (wszystkie 16 linii łączących powinno być narysowanych bez linii skrzyżowanych). Na początku plansza powinna mieć prawidłową pozycję początkową. Jednym ze sposobów osiągnięcia tego jest uczynienie planszy kwadratową.

w-w-w
|\|/|
b-o-w
|/|\|
b-b-b

Dwa kolory to czarny i biały lub ciemny / jasny. Plansza musi pokazywać, które węzły są zajęte przez elementy gracza, takie jak oznaczenie ich „b” lub „w”, a który węzeł jest wolny. Uczestników zachęca się (ale nie wymaga), aby plansza była bardziej graficzna niż zwykły tekst.

Twoja plansza do gry powinna mieć system numerowania, który nadaje każdemu węzłowi unikalny numer. Możesz wybrać numerację tablicy w dowolny sposób, ale należy to wyjaśnić w odpowiedzi lub w programie. Kwadratowa plansza może być ponumerowana w następujący sposób:

1-2-3
|\|/|
4-5-6
|/|\|
7-8-9

Człowiek porusza się pierwszy. Jego dane wejściowe będą jedną liczbą. Będzie to numer węzła, w którym aktualnie znajduje się przeniesiony kamień. Jeśli chcę przenieść kamień z węzła 4 do pustego węzła 5, wpiszę a 4. 5 oznacza, że ​​jest to jedyny pusty węzeł.

Załóż, że człowiek zawsze wykona legalny ruch.

Po tym, jak człowiek wykona swój ruch, należy wydrukować zaktualizowaną planszę. Gdy program podejmie decyzję o legalnym ruchu, powinien wydrukować kolejną zaktualizowaną tablicę, a następnie poczekać, aż człowiek wprowadzi kolejny ruch.

Twój program powinien zakończyć się po wygraniu.

Notatki

Obowiązują standardowe zasady gry w golfa, brak dostępu do zewnętrznych plików itp. Itp. Ponadto zamierzam nałożyć elastyczny czas 15 sekund (na rozsądnej maszynie), aby Twój program wykonał każdy ruch. Jak już wspomniano, ta gra ma możliwość tworzenia nieskończonych pętli i nie chcę, aby wyszukiwanie w głębokości najpierw wchodziło w nieskończoną pętlę.

Ruby, 390 znaków

o=->s,c{f=s=~/o/;[*0..8].select{|t|s[t]==c&&(t<1||(t+6)%8+1==f||t%8+1==f||f<1&&(s[(t+6)%8+1]!=c||s[t%8+1]!=c))}.map{|t|k=s*1;k[f]=c;k[t]=?o;k}}
v=->s,c,h{f=o[s,c];f==[]?0:h<1?1:2-f.map{|t|v[t,c>?b??b:?w,h-1]}.min}
q=->g{puts"1-2-3\n|\\|/|\n8-0-4\n|/|\\|\n7-6-5\n".tr"0-8",g;$>.flush}
q[g="obbbbwwww"]
(g.tr!?o,?b;g[gets.to_i]=?o;q[g];q[g=o[g,?w].sort_by{|q|v[q,?w,5]}[-1]])while v[g,?b,5]>0

Implementacja w Rubim, która bezpośrednio oblicza drzewo gry (co wymaga sporo kodu) i dlatego zawsze gra optymalnie. Pozycje planszy poruszają się spiralnie na zewnątrz, jak pokazano na poniższym rysunku:

1 - 2 - 3
| \ | / |
8 - 0 - 4
| / | \ |
7 - 6 - 5

bash i przyjaciele ( 463 447 znaków)

t(){ tr 0-8a-i $b$b
}
p(){ t<<E
0-1-2
|\|/|
3-4-5
|/|\|
6-7-8

E
}
g(){ b=`tr $x$e $e$x<<<012345678|t`
p
e=$x
}
b=bbbbowwww
e=4
m=0
p
while [ $m != 5 ]&&read x;do
g
m=0
for y in {0..8};do
s=0
S=05011234
grep -E "w.*($y$e|$e$y)"<<<${b:$y:1}30125876340142548746>/dev/null&&for p in wow.\*/ww wow.\*/w bbo.\*/b obb.\*/b www wbw .
do
((s++))
tr $y$e $e$y<<<3012587630/4e|t|grep $p>/dev/null&&break
done
s=${S:$s:1}
[ $s -gt $m ]&&m=$s x=$y
done
g
done

Człowiek gra jak bkomputer jako w. Pozycja na planszy jest ponumerowana jak w dokumencie tutaj u góry. Okazuje się, że heurystyka grania w idealną grę jest zaskakująco prosta.

Z drugiej strony utrata interesującej ścieżki jest dość trudna. http://ideone.com/sXJPy pokazuje najkrótsze możliwe samobójstwo przeciwko temu botowi. Zauważ, że dodatkowe 0 na końcu to sprawdzenie, czy poprawnie wychodzi z pętli.