#!/usr/bin/env python3
import sys

# Board representation: 8x8 list of lists.
# '.' empty, 'x' Player 1 man, 'X' Player 1 king,
# 'o' Player 2 man, 'O' Player 2 king.
EMPTY = '.'

def init_board():
    board = [[EMPTY for _ in range(8)] for _ in range(8)]
    for r in range(8):
        for c in range(8):
            if (r + c) % 2 == 1:
                if r < 3:
                    board[r][c] = 'o'               # Player 2 pieces (top)
                elif r > 4:
                    board[r][c] = 'x'               # Player 1 pieces (bottom)
    return board

def print_board(board):
    sys.stdout.write('  a b c d e f g h\n')
    for r in range(8):
        sys.stdout.write(str(8 - r) + ' ')
        for c in range(8):
            sys.stdout.write(board[r][c] + ' ')
        sys.stdout.write(str(8 - r) + '\n')
    sys.stdout.write('  a b c d e f g h\n')

def algebraic_to_coords(s):
    if len(s) != 2:
        raise ValueError
    file = s[0].lower()
    rank = s[1]
    if file < 'a' or file > 'h' or rank < '1' or rank > '8':
        raise ValueError
    c = ord(file) - ord('a')
    r = 8 - int(rank)
    return r, c

def opponent(player):
    return 2 if player == 1 else 1

def player_pieces(player):
    return ('x', 'X') if player == 1 else ('o', 'O')

def opponent_pieces(player):
    return ('o', 'O') if player == 1 else ('x', 'X')

def forward_dir(player):
    return -1 if player == 1 else 1   # row change for a simple forward move

def is_inside(r, c):
    return 0 <= r < 8 and 0 <= c < 8

def generate_moves(board, player):
    moves = []
    opp = opponent_pieces(player)
    own = player_pieces(player)
    for r in range(8):
        for c in range(8):
            piece = board[r][c]
            if piece not in own:
                continue
            dirs = []
            if piece.islower():  # man
                dr = forward_dir(player)
                dirs = [(dr, -1), (dr, 1)]
            else:                # king
                dirs = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if is_inside(nr, nc) and board[nr][nc] == EMPTY and (nr + nc) % 2 == 1:
                    moves.append(((r, c), (nr, nc)))      # simple move
                # capture
                cr, cc = r + 2 * dr, c + 2 * dc
                if (is_inside(cr, cc) and board[cr][cc] == EMPTY and
                    board[nr][nc] in opp and (cr + cc) % 2 == 1):
                    moves.append(((r, c), (cr, cc)))      # capture move
    return moves

def apply_move(board, frm, to, player):
    fr, fc = frm
    tr, tc = to
    piece = board[fr][fc]
    dr = tr - fr
    dc = tc - fc
    captured = None
    if abs(dr) == 2 and abs(dc) == 2:
        mr, mc = fr + dr // 2, fc + dc // 2
        captured = board[mr][mc]
        board[mr][mc] = EMPTY
    board[tr][tc] = piece
    board[fr][fc] = EMPTY
    # promotion
    if piece == 'x' and tr == 0:
        board[tr][tc] = 'X'
    if piece == 'o' and tr == 7:
        board[tr][tc] = 'O'

def has_any_move(board, player):
    return bool(generate_moves(board, player))

def main():
    board = init_board()
    current = 1  # Player 1 starts
    while True:
        print_board(board)
        if not has_any_move(board, current):
            print(f'Player {opponent(current)} wins! (no moves for Player {current})')
            break
        pieces = sum(row.count(p) for row in board for p in player_pieces(current))
        if pieces == 0:
            print(f'Player {opponent(current)} wins! (no pieces left for Player {current})')
            break
        while True:
            try:
                prompt = f'Player {current} ({player_pieces(current)[0]}) move (e.g., b6 c5): '
                move_str = input(prompt).strip()
                if not move_str:
                    continue
                src_s, dst_s = move_str.split()
                fr, fc = algebraic_to_coords(src_s)
                tr, tc = algebraic_to_coords(dst_s)
                if not is_inside(fr, fc) or not is_inside(tr, tc):
                    raise ValueError
                if board[fr][fc] not in player_pieces(current):
                    print('Source does not contain your piece.')
                    continue
                if board[tr][tc] != EMPTY:
                    print('Destination not empty.')
                    continue
                dr = tr - fr
                dc = tc - fc
                if abs(dr) != abs(dc) or abs(dr) not in (1, 2):
                    print('Invalid move direction.')
                    continue
                # check simple move direction for men
                piece = board[fr][fc]
                if piece.islower():
                    if abs(dr) == 1 and dr != forward_dir(current):
                        print('Men must move forward.')
                        continue
                # capture legality
                if abs(dr) == 2:
                    mr, mc = fr + dr // 2, fc + dc // 2
                    if board[mr][mc] not in opponent_pieces(current):
                        print('No opponent piece to capture.')
                        continue
                # all good
                apply_move(board, (fr, fc), (tr, tc), current)
                break
            except ValueError:
                print('Invalid input format. Use e.g., b6 c5')
        current = opponent(current)

if __name__ == '__main__':
    main()