Вам предоставляется частично заполненная сетка 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

(Ввод может быть представлен в виде 1D или 2D массива, а также букв или цифр и т. Д.)

Предположить, что

• Х начал игру.
• Никто еще не победил.
• Игроки, возможно, не играли хорошо до сих пор, но теперь они оба будут использовать оптимальные стратегии.
• Входная сетка не является неисправной.

Вы должны вывести единственное значение, которое указывает, какой игрок выигрывает (или ничья)

Код гольф-вызов; так короткий код выигрывает. Ваша программа не должна фактически вычислять выходные данные в разумные сроки, но вы должны быть в состоянии доказать, что выходные данные будут получены правильно за конечное время.

Perl 119 118 117 байт

Включает +4 для -0p

Дайте повернутую доску, дополненную пробелами на STDIN (гравитация тянет камни вправо)

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

Выводит 3, выигрывает 1ли игрок на ходу, проигрывает ли игрок на ходу и 2на ничью.

На старых perls вы можете использовать литерал, ^Sчтобы получить один байт. Если вы не возражаете против крайней неэффективности, вы можете опустить $$_||=(таблицу транспонирования) и получить еще 6 байтов. Если вы пропустите, $_=он покажет вам, где играть вместо результата (играйте 1и выигрывайте, если таковой имеется, играйте 2и тяните, если есть, или играйте на любом 3и проигрывайте)

Строит и оценивает полное минимаксное дерево. Вам не хватит памяти и времени, если доска уже не будет достаточно хорошо заполнена.