WIDTH, HEIGHT = 7, 6
INFINITY = float('inf')

SEARCHDEPTH = 4

THREEWEIGHT = 1.0
TWOWEIGHT = 0.1
ONEWEIGHT = 0.01
HEIGHTPENALTY = 0.2

N = (0, 1)
S = (0, -1)
W = (-1, 0)
E = (1, 0)

SW = (-1, -1)
NW = (-1, 1)
SE = (1, -1)
NE = (1, 1)


def tuple_add(t1, t2):
    return (t1[0]+t2[0], t1[1]+t2[1])

def reverse_dir(direction):
    return (-direction[0], -direction[1])

class WallError(Exception):
    pass

class Pointer(object):
    def __init__(self, board_ins, x=0, y=0):
        self.x = x
        self.y = y
        self.brd = board_ins

    @property
    def position(self):
        return (self.x, self.y)

    @position.setter
    def position(self, pos):
        w=self.brd.width
        h=self.brd.height

        if 0 <= pos[0] < w and 0 <= pos[1] < h:
            self.x, self.y = pos
        else:
            raise WallError, ('No such position:', pos)

    def advance(self, direction):
        self.position = tuple_add(self.position, direction)

    @property
    def contents(self):
        return self.brd.field(self.position)

    @property
    def voids_beneath(self):
        return self.y-self.brd.chips[self.x]

    def copy(self):
        return Pointer(self.brd, self.x, self.y)

    def has_room(self, direction, n):
        x = self.x+direction[0]*n
        y = self.y+direction[1]*n
        w = self.brd.width
        h = self.brd.height

        return 0 <= x < w and 0 <= y < h

    def home(self):
        self.position=(0,0)

class Board(object):
    def __init__(self, w, h, turn=1, reps=None):
        self.array = [[0]*h for i in range(w)]
        self.turn = turn
        self.width = w
        self.height = h
        self.chips = [0]*w
        self.lastplayed = 0

        self.optimcols = range(w/4, 3*w/4)+range(w/4)+range(3*w/4, w)
        self.eval_values = [0, ONEWEIGHT, TWOWEIGHT, THREEWEIGHT, INFINITY]
        self.height_coeff = 1-HEIGHTPENALTY

        if reps is None:
            self.reps = {1:'X',
                        -1:'O',
                         0:'_'}
        else:
            self.reps = reps

    def field(self, x=0, y=0):
        if isinstance(x, tuple):
            x, y = x
        return self.array[x][y]

    def play(self, col=None):
        if col is None:
            col = self.lastplayed
        if not 0 <= col < self.width:
            raise WallError, 'No such column'
        if self.chips[col] < self.height:
            self.chips[col] += 1
            self.array[col][self.chips[col]-1] = self.turn
            self.turn = -self.turn
            self.lastplayed = col
        else:
            raise WallError, 'Column full.'

    def unplay(self, col=None):
        if col is None:
            col = self.lastplayed
        if not 0 <= col < self.width:
            raise WallError, 'No such column'
        if self.chips[col] > 0:
            self.turn = -self.turn
            self.array[col][self.chips[col]-1] = 0
            self.chips[col] -= 1
        else:
            raise WallError, 'Column empty.'

    def empty_and_players(self, player=None):
        if player is None:
            player=self.turn
        for x in self.optimcols:
            for y in range(self.height):
                if self.array[x][y] in (player, 0):
                    yield Pointer(self, x, y)

    def possible_moves(self):
        for x in range(self.width):
            if self.chips[x] < self.height:
                yield x

    def is_full(self):
        return sum(self.chips) == self.width*self.height

    def evaluate(self, player=0):
        player = player or -self.turn
        dirs = [N, NW, W, SW, S, SE, E, NE]
        score = 0
        try:
            for i in [-1, 1]:
                self.evaluated_array = [[list() for k in range(self.height)]
                                        for j in range(self.width)]
                for field in self.empty_and_players(player*i):
                    x, y = field.position
                    for direction in dirs:
                        if ((1 or direction not in self.evaluated_array[x][y]) and
                            field.has_room(direction, 3)):
                            assert field.contents!=-player*i
                            score+=self._evaluate_seq(field, direction, player*i)*i
                            field.position = (x,y)
                            if score == INFINITY or score == -INFINITY:
                                raise StopIteration
        except StopIteration:
            pass
        return score

    def _evaluate_seq(self, pointer, direction, player):
        filled = 0
        first_zero_h = None
        last_zero_h = None
        assert pointer.contents in (player, 0)
        for i in range(4):
            if pointer.contents == -player:
                return 0
            elif pointer.contents == 0:
                last_zero_h = pointer.voids_beneath
                if first_zero_h is None:
                    first_zero_h = last_zero_h
            elif pointer.contents == player:
                filled += 1
            if i < 3:
                pointer.advance(direction)

        score = self.eval_values[filled]
        x, y = pointer.position
        self.evaluated_array[x][y].append(reverse_dir(direction))

        if score == INFINITY:
            return score
        elif not score:
            return score

        heightw = self.height_coeff ** min(first_zero_h, last_zero_h)
        return score * heightw

    def get_best_move(self, search_depth, fp=None, alpha=-INFINITY, beta=INFINITY):
        if fp is None:
            fp = self.turn
        max_ = (-INFINITY, 0)
        player = -self.turn
        if search_depth == 0:
            max_ = (self.evaluate(fp), 0)
        else:
            for col in self.possible_moves():
                self.play(col)
                cur = -self.get_best_move(search_depth-1, -fp, -beta, -alpha)[0]
                self.unplay(col)
                max_ = max((cur, col), max_)
                alpha = max(alpha, cur)
                if alpha >= beta:
                    break
        return max_

    def __str__(self):
        out = ''
        for row in range(self.height-1, -1, -1):
            out += '\n|'
            for col in range(self.width):
                out += self.reps[self.array[col][row]]+'|'
        out += '\n ' + ' '.join([str(i) for i in range(self.width)])
        return out



m = Board(WIDTH, HEIGHT,-1)
while not (abs(m.evaluate()) == INFINITY or m.is_full()):
    if m.turn==-1:
        where=int(raw_input('Your turn: '))
        m.play(where)
        print m
    else:
        print 'My turn...'
        m.play(m.get_best_move(SEARCHDEPTH)[1])
        print m

b = m.evaluate(1)
if b == -INFINITY:
    print 'You won.'
elif b == INFINITY:
    print 'You lost.'
else:
    print 'A tie.'