Wyzwanie polega na napisaniu funkcji minimaksa w wybranym języku, aby wygenerować następny najlepszy ruch w grze kółko i krzyżyk NxN, biorąc pod uwagę bieżący stan planszy . Dane wejściowe na planszy można zaakceptować jako Matrycę, kolekcję 2D lub cokolwiek innego, co ma dla ciebie sens, ale jest zgodne z zasadami . Wyjście jest kolejnym najlepszym ruchem dla każdej tury , w której aktualnie się znajduje , gdzie X uważa się za rozpoczęty .

Szybkie wprowadzenie do algorytmu minimax

Podstawową ideą algorytmu minimax jest wyliczenie wszystkich możliwych wyników jako DAG, a następnie zważenie ich według korzyści, jaką sekwencja ruchów ma dla gracza, kluczowana przez pierwszy wykonany ruch. Wszystkie możliwe wyniki są następnie „przenoszone” przez pierwszy ruch i są oceniane na podstawie sumy wszystkich wyników (-1 dla przegranej, 0 dla remisu i 1 dla wygranej). W implementacjach wymagających gry wielu graczy, wyliczasz wszystkie możliwe ruchy gracza oraz wszystkie możliwe reakcje przeciwników. Na przykład w grze w kółko i krzyżyk (po pierwszym ruchu) istnieje 8 możliwych pierwszych ruchów, które można wykonać, i wszystkie mogą wydawać się równe, gdy analizuje się tylko kolejną turę. Ale powtarzając wszystkie możliwe wyniki dla każdego możliwego zestawu ruchów, które dają wynik końcowy i sumując je wszystkie,

Aby uzyskać lepsze, bardziej szczegółowe i kontekstowe podsumowanie algorytmu mini-max w kategoriach kółko i krzyżyk, przeczytaj więcej tutaj: http://neverstopbuilding.com/minimax

XKCD (tylko rozwiązanie 3x3)

Zasady

• Można użyć dowolnego języka, ale nie są dozwolone żadne zewnętrzne biblioteki minimax.
• Wyjściem może być współrzędna (0-n, 0-n) lub liczba (1-n * n) wskazująca najlepszy następny ruch.
  • Oprócz tego musisz być w stanie określić, kiedy najlepszym scenariuszem jest przegrana lub remis zamiast wygranej.
  • Sposób, w jaki określasz stratę lub remis, zależy od Ciebie.
• Dane wejściowe muszą wykorzystywać tradycyjne X i O, a najpierw musisz założyć X ruchów; puste miejsca mogą być reprezentowane przez dowolne.
• Możesz założyć, że wszelkie dane wejściowe do twojego programu mają n O i n + 1 X, innymi słowy możesz założyć, że otrzymujesz dobrze uformowaną płytę.
• Obecny stan płytki musi być jedynym wejściem do twojego programu, jeśli używasz rekurencji, musisz zastosować metody pomocnicze, aby ułatwić wprowadzenie danych. Zobacz /codegolf//a/92851/59376 o wyjaśnienie.
• Każda wartość 10> = n> = 1 musi być obsługiwana; jeśli twój program „przekroczy limit czasu” dla n> 10, uważam to również za dopuszczalne, ponieważ niektóre języki mają znacznie niższą moc przetwarzania (szczególnie przy użyciu konsol obsługujących strony internetowe).

Osądzać

• Jest to gra w golfa kodowego, więc najniższa liczba bajtów w programie wygrywa, a standardowe luki są ogólnie zabronione.
• W przypadku remisu wygrywa program obsługujący największe „n”.

Przykładowe dane wejściowe

2x2

[[X,O]
 [-,-]]

Dane wyjściowe: 2 lub [0,1] (3 lub [1,1] również byłyby prawdopodobnie poprawne) (Pewna forma wskazania lokalizacji, dowolna, o ile można łatwo wyjaśnić użyty format)

3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Wyjście: -1 (strata)

Ponownie dozwolony jest dowolny żądany format wejściowy, ale należy użyć znaków X i O, podane przykłady nie miały ograniczać się do tego formatu, a jedynie inspirować.

Perl, 101 98 bajtów

Obejmuje +4dla-0p

Uruchom z wejściem na STDIN

tictactoe.pl
OXO
---
--X
^D

Wyjście jest tym samym diagramem, ale przy każdym ruchu aktualizowanym o swój status, 1reprezentuje wygraną, 2reprezentuje remis i 3reprezentuje stratę. W tym przypadku byłoby to

OXO
223
21X

więc 3 ruchy losują, 1 wygrywają i 1 przegrywają (zaktualizuję rozwiązanie, jeśli ten format wyjściowy jest niedopuszczalny, ale podstawowy kod pozostanie taki sam)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Jest to już boleśnie powolne i zużywa dużo pamięci dla pustej płyty 3 * 3 (dlaczego tak naprawdę rekurencja nie jest tak głęboka. Musi być jakiś wyciek pamięci). Dodanie zapamiętywania kosztuje 6 bajtów, ale jest znacznie rozsądniejsze:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

JavaScript (ES6), 320 294 bajtów

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Wejście

1) Tablica tablic znaków opisujących aktualną planszę, takich jak:

[['X', '-'], ['-', 'O']]

2) Liczba całkowita opisująca aktualny zwrot: 1 = X, -1 =O

Wynik

Tablica wykonana z:

• tablica opisująca najlepszy ruch w [x, y]formacie
• wynik gry jako liczba całkowita: 1 = wygrana, -1 = przegrana, 0 = remis

Przykład

W poniższym przykładzie Xwygrana jest gwarantowana poprzez grę [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

_{Dziwna gra. JEDYNIE WYGRYWAJĄCE RUCHY NIE SĄ GRAĆ.
JAK O ŁADNEJ SZACHY?}