Determine winner of Connect 4

Question

You are given a partially filled Connect 4 grid (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 can be given as a 1D or 2D array and as letters or numbers, etc.)

Assume that

• X started the game.
• Nobody has won yet.
• Players may not have played well until now, but now onwards they will both employ optimal strategies.
• Input grid is not faulty.

You must output a single value that indicates which player wins (or a draw)

Code golf challenge; so shortest code wins. Your program does not have to actual compute the output in reasonable amount of time, but you should be able to prove that the output will be obtained correctly in a finite amount of time.

Answer 1

Perl, 119 118 117 bytes

Includes +4 for -0p

Give rotated board padded with spaces on STDIN (gravity pulls stones to the right)

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

Prints 3 if player to move wins, 1 if player to move loses and 2 for a draw.

On older perls you can use a literal ^S to gain one byte. If you don't mind extreme inefficiency you can leave out the $$_||= (transposition table) and gain 6 more bytes. If you leave out the $_= it will show you where to play instead of the result (play on 1 and win if there is one, play on 2 and draw if there is one or play on any 3 and lose)

Builds and evaluates a complete minimax tree. You will run out of memory and time unless the board is already reasonably well filled.