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.

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.