naive_hexapawn_any_size.py

from copy import deepcopy

__X = 0   # Empty space
__W = -1  # Direction of White
__B = 1   # Direction of Black

line_no = int(input())
pawn_no = int(input())

board = []

for i in range(0, line_no):
    line_str = str(input())
    l = []
    for j, c in enumerate(line_str):
        if c == 'p':  # black
            l.append(__B)
        elif c == 'P':  # white
            l.append(__W)
        else:
            l.append(__X)
    while len(l) < pawn_no:
        l.append(__X)
    board.append(l)


def reach_end(config):
    fst = config[0]
    lst = config[line_no - 1]

    return min(fst) == -1 or max(lst) == 1


def move(config, player, idx_from, jdx_from, expected, idx_to, jdx_to):
    if 0 <= idx_to <= line_no-1 and 0 <= jdx_to <= pawn_no-1 and expected == config[idx_to][jdx_to]:
        new_c = deepcopy(config)
        new_c[idx_from][jdx_from] = __X
        new_c[idx_to][jdx_to] = player
        return new_c
    return None


def move_front(config, player, l, c):
    to_i = l + player
    return move(config, player, l, c, __X, to_i, c)


def move_left(config, player, l, c):
    to_i = l + player
    to_j = c - 1
    return move(config, player, l, c, -player, to_i, to_j)


def move_right(config, player, l, c):
    to_i = l + player
    to_j = c + 1
    return move(config, player, l, c, -player, to_i, to_j)


def get_configs_from(config, player):
    configs = []
    values = []
    for l in range(0, line_no):
        for c in range(0, pawn_no):
            pawn = config[l][c]
            if pawn == player:
                ahead = move_front(config, player, l, c)
                left = move_left(config, player, l, c)
                right = move_right(config, player, l, c)
                if ahead is not None:
                    configs.append(ahead)
                    values.append(calc_state(ahead, -player))
                if left is not None:
                    configs.append(left)
                    values.append(calc_state(left, -player))
                if right is not None:
                    configs.append(right)
                    values.append(calc_state(right, -player))
    return configs, values


def calc_state(config, player):
    if reach_end(config):
        return 0

    (configs, values) = get_configs_from(config, player)

    return calc_val(values)


# Nega max
def calc_val(values):
    if not values:
        return 0
    only_neg = [x for x in values if x <= 0]
    if only_neg:
        return 1 - (max(only_neg))
    return - (max(values) + 1)


print(calc_state(board, __W))