hexapawn.py

import sys
import random

def parse_input():
    lines = [line for line in sys.stdin]
    ly, lx = int(lines[0]), int(lines[1])
    board = []

    for y in range(ly):
        line = "".join(l for l in lines[y+2] if l in ["p", "P", " "])
        board.append(('{:' + str(lx) + '}').format(line))

    return tuple(board)


def best_score(s1, s2):
    if s1 == 0:
        return s2
    if s2 == 0:
        return s1

    if (s1 < 0) == (s2 < 0):
        return min(s1, s2)
    else:
        return max(s1, s2)


def next_moves(board, white_turn):
    ally, opponent, d = ("P", "p", -1) if white_turn else ("p", "P", 1)

    lx, ly = len(board[0]), len(board)

    pawns = []
    for x in range(lx):
        for y in range(ly):
            if board[y][x] == ally:
                pawns.append((x, y))

    possible_moves = []
    for pawn in pawns:
        x, y = pawn
        if 0 <= y+d < ly:
            up_line = board[y+d]
            if up_line[x] == " ":
                possible_moves.append([(x, y), (x, y+d), " "])

            for new_x in [x-1, x+1]:
                if (0 <= new_x < lx) and (up_line[new_x] == opponent):
                    possible_moves.append([(x, y), (new_x, y+d), opponent])


    return possible_moves

def do_move(board, move):
    start, end = move[:2]

    sx, sy = start
    ex, ey = end

    board = list(board)
    board[ey] = board[ey][:ex] + board[sy][sx] + board[ey][ex+1:]
    board[sy] = board[sy][:sx] + " " + board[sy][sx+1:]

    return tuple(board)



def solve(board, white_turn=True, opp_best=0):
    global counter
    counter += 1

    key = hash((board, white_turn, opp_best))

    if key in solve.dp:
        return solve.dp[key]

    possible_moves = next_moves(board, white_turn)

    # We try the "best" move first
    # It also allow to keep the same order for the same board and so the same opp_best
    possible_moves.sort(key = lambda move : (move[1][1], move) if white_turn else (-move[1][1], move))

    wining_line = 0 if white_turn else len(board)-1
    best = 0

    for move in possible_moves:
        if (move[1][1] == wining_line) or (best == 1): # Instant win
            solve.dp[key] = 1
            return 1

        opp_min = (-best + 1) if best <= 0 else (-best - 1)
        if best_score(opp_min, opp_best) == opp_best: # Opp_best was already better than that
            solve.dp[key] = best
            return best

        next_board = do_move(board, move)

        opp_score = solve(next_board, not white_turn, best)
        score = (-opp_score + 1) if opp_score <= 0 else (-opp_score - 1)
        best = best_score(best, score)

    solve.dp[key] = best
    return best

solve.dp = dict()

counter = 0
b = parse_input()
print(solve(b))