Anda diberi kotak Hubungkan 4 yang terisi sebagian (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

(Input dapat diberikan sebagai array 1D atau 2D dan sebagai huruf atau angka, dll.)

Asumsikan bahwa

• X memulai permainan.
• Belum ada yang menang.
• Pemain mungkin belum bermain dengan baik sampai sekarang, tetapi sekarang dan seterusnya mereka berdua akan menggunakan strategi yang optimal.
• Grid input tidak salah.

Anda harus menampilkan nilai tunggal yang menunjukkan pemain mana yang menang (atau seri)

Tantangan golf kode; jadi kode terpendek menang. Program Anda tidak harus benar-benar menghitung output dalam jumlah waktu yang wajar, tetapi Anda harus dapat membuktikan bahwa output akan diperoleh dengan benar dalam jumlah waktu yang terbatas.

Perl, 119 118 117 byte

Termasuk +4 untuk -0p

Berikan papan yang dirotasi dengan spasi pada STDIN (gravitasi menarik batu ke kanan)

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

Mencetak 3jika pemain bergerak menang, 1jika pemain bergerak kalah dan 2seri.

Pada perl yang lebih lama Anda dapat menggunakan literal ^Suntuk mendapatkan satu byte. Jika Anda tidak keberatan dengan inefisiensi ekstrim, Anda dapat $$_||=mengabaikan (tabel transposisi) dan mendapatkan 6 byte lebih banyak. Jika Anda membiarkannya keluar, $_=itu akan menunjukkan tempat untuk bermain alih-alih hasilnya (bermain 1dan menang jika ada, bermain 2dan menggambar jika ada satu atau bermain di mana saja 3dan kalah)

Membangun dan mengevaluasi pohon minimax lengkap. Anda akan kehabisan memori dan waktu kecuali papan sudah diisi dengan cukup baik.