Otrzymasz częściowo wypełnioną siatkę Connect 4 (7x6).

O X             
O X          
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(Dane wejściowe można podać w postaci tablicy 1D lub 2D oraz liter lub cyfr itp.)

Zakładać, że

X rozpoczął grę.
Nikt jeszcze nie wygrał.
Do tej pory gracze mogli nie grać dobrze, ale teraz obaj będą stosować optymalne strategie.
Siatka wejściowa nie jest uszkodzona.

Musisz podać jedną wartość, która wskazuje, który gracz wygrał (lub remis)

Wyzwanie golfa kodu; więc najkrótszy kod wygrywa. Twój program nie musi faktycznie obliczać wyniku w rozsądnym czasie, ale powinieneś być w stanie udowodnić, że wynik zostanie poprawnie uzyskany w skończonym czasie.

— ghosts_in_the_code
źródło

Związane z.

— Martin Ender

@ MartinBüttner Czy to oznacza, że zostanę przegłosowany, czy też dobrze jest zostawić tutaj moje pytanie?

— ghosts_in_the_code

Oznacza to tylko, że pytania są powiązane, nic więcej, nic więcej. Publikowanie linku ma na celu ukazanie wyzwań na pasku bocznym „Powiązane”, aby ludzie mogli łatwiej znaleźć powiązane wyzwania. Gdybym uznał twoje pytanie za duplikat, powiedziałbym to (lub po prostu je zamknąłem), więc nie martw się. :)

— Martin Ender

Czy „optymalna gra” jest dobrze zdefiniowana? Jeśli tak, czy możesz podać link opisujący algorytm optymalnej gry?

— Rainbolt

@Rainbolt Zostało to rozwiązane i istnieją również doskonałe algorytmy . Więcej informacji w Wikipedii .

— ghosts_in_the_code

Perl, 119 118 117 bajtów

Obejmuje +4 za -0p

Daj obróconą deskę wyłożoną spacjami na STDIN (grawitacja ciągnie kamienie w prawo)

connect4.pl
  OXXX
   XOO
    OX
  OOXX
  XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

#!/usr/bin/perl -p0
y/XO/OX/if$^S|y/X//>y/O//;$_=$$_||=/Z@{[map"|O".".{$_}O"x3,0,5..7]}/sx||s% (?! )%$_="$`X$'";do$0%eg?/1/?3:1+/2/:2

Drukuje, 3jeśli gracz, który się poruszy, wygrywa, 1jeśli gracz, który poruszy się, przegrywa i 2remis.

Na starszych perlach możesz użyć literału, ^Saby uzyskać jeden bajt. Jeśli nie masz nic przeciwko ekstremalnej nieefektywności, możesz pominąć $$_||=(tabelę transpozycji) i zyskać 6 dodatkowych bajtów. Jeśli pominiesz $_=to pokaże ci, gdzie grać zamiast wyniku (graj dalej 1i wygrywaj, jeśli taki istnieje, graj dalej 2i losuj, jeśli taki jest, lub graj na dowolnym 3i przegrywaj)

Buduje i ocenia pełne drzewo minimax. Skończy Ci się pamięć i czas, chyba że tablica jest już wystarczająco dobrze wypełniona.

— Ton Hospel
źródło

Dlaczego, u licha, ktoś głosował? Gra w golfa jest naprawdę niesamowita (gram w perla i uzyskanie takiego rozwiązania jest wyjątkowo trudne - nie jestem pewien, czy jakikolwiek inny golfista, którego znam, mógłby wymyślić ten kod). A kod ma wymagane zachowanie.

— Dada,

To powoduje ból mojego mózgu. +1!

— levelonehuman

@Dada, skąd wiesz, że odpowiedź została odrzucona? Widzę 3 jako głos ...

— RosLuP,

@RosLuP, kiedy pierwszy raz zobaczyłem ten post, miał 1 głos negatywny. Ponadto, gdy masz wystarczającą liczbę powtórzeń, możesz zobaczyć, ile głosów w górę i w dół ma post: w takim przypadku teraz ma 4 w górę i 1 w dół.

— Dada,

Określ zwycięzcę Connect 4

Perl, 119 118 117 bajtów