#!/usr/bin/env python3
"""
Whale Shogi XBoard-compatible engine
======================================
Rules:  https://en.wikipedia.org/wiki/Whale_shogi
Board:  6×6
Goal:   Capture the opponent's White Whale
Author: Generated for XBoard / WinBoard protocol v2

Piece movements (Black's "forward" = higher row numbers):
  W - White Whale  : steps 1 in any of the 8 directions            (King)
  G - Grey Whale   : slides forward; slides diagonally backward
  P - Porpoise     : steps 1 square sideways (left or right)
  K - Killer Whale : slides orthogonally; steps diagonally          (Dragon King)
  N - Narwhal      : jumps 2 squares forward; steps backward/sideways
  H - Humpback     : steps diagonally (all 4); steps backward
  B - Blue Whale   : steps forward, backward, diagonally-forward
  D - Dolphin      : steps 1 forward; if on farthest rank, slides diagonally backward

Drop rules:
  • Porpoise is never dropped – when captured it instantly promotes
    to Killer Whale and is held in hand as K.
  • Dolphin cannot be dropped on the farthest rank.
  • Dolphin cannot be dropped in a file that already has ≥ 2 friendly dolphins.
  • Dolphin cannot be dropped to give immediate checkmate ("dolphin-drop mate").
"""

import sys
import random
import re

# ── Colour constants ──────────────────────────────────────────────────────────
BLACK, WHITE = 0, 1

# ── Piece-type constants ──────────────────────────────────────────────────────
WW = 1   # White Whale  (king)
PP = 2   # Porpoise     (promotes to Killer Whale on capture)
HH = 3   # Humpback
GG = 4   # Grey Whale
NN = 5   # Narwhal
BB = 6   # Blue Whale
DD = 7   # Dolphin
KK = 8   # Killer Whale (promoted Porpoise)

P2C = {WW: 'W', PP: 'P', HH: 'H', GG: 'G', NN: 'N', BB: 'B', DD: 'D', KK: 'K'}
C2P = {v: k for k, v in P2C.items()}

# Approximate piece values for evaluation (White Whale = ∞ treated as 10 000)
VALUE = {WW: 10000, KK: 8, GG: 6, NN: 5, HH: 4, BB: 4, PP: 3, DD: 1}

# ── Coordinate helpers ────────────────────────────────────────────────────────

def sq2str(col: int, row: int) -> str:
    """(col 0-5, row 0-5)  →  'a1' … 'f6'"""
    return chr(ord('a') + col) + str(row + 1)


def str2sq(s: str):
    """'a1' → (col=0, row=0),  'f6' → (col=5, row=5)"""
    return ord(s[0]) - ord('a'), int(s[1]) - 1


# ── Board ─────────────────────────────────────────────────────────────────────

class Board:
    """
    cells[row][col]  =  (piece_type, colour)  |  None
    row 0 = rank 1 = Black's back rank
    row 5 = rank 6 = White's back rank
    """

    __slots__ = ('cells', 'hands', 'to_move')

    # ── Construction / reset ──────────────────────────────────────────────────

    def __init__(self):
        self.cells: list = [[None] * 6 for _ in range(6)]
        self.hands: dict = {BLACK: [], WHITE: []}
        self.to_move: int = BLACK
        self._setup()

    def _setup(self):
        # Black – rank 1 (row 0):  H G W P N B
        for col, piece in enumerate([HH, GG, WW, PP, NN, BB]):
            self.cells[0][col] = (piece, BLACK)
        # Black – rank 2 (row 1):  six dolphins
        for col in range(6):
            self.cells[1][col] = (DD, BLACK)
        # White – rank 6 (row 5):  B N P W G H  (mirror of Black)
        for col, piece in enumerate([BB, NN, PP, WW, GG, HH]):
            self.cells[5][col] = (piece, WHITE)
        # White – rank 5 (row 4):  six dolphins
        for col in range(6):
            self.cells[4][col] = (DD, WHITE)

    # ── Copy ─────────────────────────────────────────────────────────────────

    def copy(self) -> 'Board':
        b = object.__new__(Board)
        b.cells   = [row[:] for row in self.cells]
        b.hands   = {BLACK: self.hands[BLACK][:], WHITE: self.hands[WHITE][:]}
        b.to_move = self.to_move
        return b

    # ── Low-level helpers ─────────────────────────────────────────────────────

    @staticmethod
    def _fwd(color: int) -> int:
        """Row-delta for 'forward' direction."""
        return 1 if color == BLACK else -1

    @staticmethod
    def _far_row(color: int) -> int:
        """Index of the farthest rank for the given colour."""
        return 5 if color == BLACK else 0

    @staticmethod
    def _inbounds(r: int, c: int) -> bool:
        return 0 <= r < 6 and 0 <= c < 6

    def _step(self, r, c, dr, dc, color, out):
        """Add one-step destination if legal."""
        r2, c2 = r + dr, c + dc
        if self._inbounds(r2, c2):
            tgt = self.cells[r2][c2]
            if tgt is None or tgt[1] != color:
                out.append((r2, c2))

    def _slide(self, r, c, dr, dc, color, out):
        """Add all slide-destinations in direction (dr,dc)."""
        r2, c2 = r + dr, c + dc
        while self._inbounds(r2, c2):
            tgt = self.cells[r2][c2]
            if tgt is None:
                out.append((r2, c2))
            elif tgt[1] != color:
                out.append((r2, c2))
                break
            else:
                break
            r2 += dr
            c2 += dc

    # ── Piece destinations (no check-filter) ─────────────────────────────────

    def get_dests(self, row: int, col: int) -> list:
        """
        Return all squares reachable by the piece at (row, col).
        Does NOT check whether the move leaves own king in check.
        """
        cell = self.cells[row][col]
        if not cell:
            return []
        piece, color = cell
        f   = self._fwd(color)
        out = []

        if piece == WW:          # King – all 8 neighbours
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr or dc:
                        self._step(row, col, dr, dc, color, out)

        elif piece == GG:        # Grey Whale: forward-slide + diag-backward-slide
            self._slide(row, col,  f,  0, color, out)
            self._slide(row, col, -f, -1, color, out)
            self._slide(row, col, -f,  1, color, out)

        elif piece == PP:        # Porpoise: step left or right
            self._step(row, col, 0, -1, color, out)
            self._step(row, col, 0,  1, color, out)

        elif piece == KK:        # Killer Whale: orthogonal-slide + diagonal-step
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                self._slide(row, col, dr, dc, color, out)
            for dr, dc in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
                self._step(row, col, dr, dc, color, out)

        elif piece == NN:        # Narwhal: jump 2f + step backward + step sideways
            r2, c2 = row + 2 * f, col
            if self._inbounds(r2, c2):
                tgt = self.cells[r2][c2]
                if tgt is None or tgt[1] != color:
                    out.append((r2, c2))            # jump ignores intermediate square
            self._step(row, col, -f,  0, color, out)
            self._step(row, col,  0, -1, color, out)
            self._step(row, col,  0,  1, color, out)

        elif piece == HH:        # Humpback: all 4 diagonals + backward
            for dr, dc in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
                self._step(row, col, dr, dc, color, out)
            self._step(row, col, -f, 0, color, out)

        elif piece == BB:        # Blue Whale: step f/b/diag-f
            self._step(row, col,  f,  0, color, out)
            self._step(row, col, -f,  0, color, out)
            self._step(row, col,  f,  1, color, out)
            self._step(row, col,  f, -1, color, out)

        elif piece == DD:        # Dolphin: step forward; on farthest rank slide diag-backward
            if row == self._far_row(color):
                self._slide(row, col, -f, -1, color, out)
                self._slide(row, col, -f,  1, color, out)
            else:
                self._step(row, col, f, 0, color, out)

        return out

    # ── Move generation ───────────────────────────────────────────────────────

    def _board_moves(self, color: int) -> list:
        moves = []
        for r in range(6):
            for c in range(6):
                cell = self.cells[r][c]
                if cell and cell[1] == color:
                    for tr, tc in self.get_dests(r, c):
                        moves.append(('mv', r, c, tr, tc))
        return moves

    def _drop_moves(self, color: int) -> list:
        moves  = []
        far    = self._far_row(color)
        pieces = list(set(self.hands[color]))
        for piece in pieces:
            for r in range(6):
                for c in range(6):
                    if self.cells[r][c] is not None:
                        continue
                    # ── Dolphin restrictions ────────────────────────────────
                    if piece == DD:
                        if r == far:
                            continue                   # not on farthest rank
                        # ≤ 1 other friendly dolphin already in this file
                        dolphins_in_file = sum(
                            1 for rr in range(6)
                            if self.cells[rr][c] == (DD, color)
                        )
                        if dolphins_in_file >= 2:
                            continue
                    moves.append(('dr', piece, r, c))
        return moves

    def legal_moves(self) -> list:
        """All legal moves for the side to move."""
        color      = self.to_move
        candidates = self._board_moves(color) + self._drop_moves(color)
        legal      = []
        for mv in candidates:
            # ── Dolphin-drop-mate restriction ────────────────────────────────
            if mv[0] == 'dr' and mv[1] == DD:
                nb = self._apply_raw(mv)
                if self._is_mated_in(nb, 1 - color):
                    continue
            # ── Must not leave own White Whale in check ──────────────────────
            nb = self._apply_raw(mv)
            kp = nb._king_pos(color)
            if kp and not nb._is_attacked(kp[0], kp[1], 1 - color):
                legal.append(mv)
        return legal

    # ── Apply a move ──────────────────────────────────────────────────────────

    def _apply_raw(self, mv) -> 'Board':
        """Apply move without legality checks; return new Board."""
        b = self.copy()
        if mv[0] == 'mv':
            _, fr, fc, tr, tc = mv
            piece, color = b.cells[fr][fc]
            tgt = b.cells[tr][tc]
            if tgt:
                cap = tgt[0]
                if cap == PP:
                    cap = KK          # Porpoise → Killer Whale in hand
                b.hands[color].append(cap)
            b.cells[fr][fc]  = None
            b.cells[tr][tc]  = (piece, color)
        else:                          # drop
            _, piece, tr, tc = mv
            color = b.to_move
            b.hands[color].remove(piece)
            b.cells[tr][tc] = (piece, color)
        b.to_move ^= 1
        return b

    apply = _apply_raw   # public alias

    # ── Check / mate helpers ──────────────────────────────────────────────────

    def _king_pos(self, color: int):
        """(row, col) of colour's White Whale, or None."""
        for r in range(6):
            for c in range(6):
                cell = self.cells[r][c]
                if cell and cell[0] == WW and cell[1] == color:
                    return r, c
        return None

    def _is_attacked(self, row: int, col: int, by_color: int) -> bool:
        """True if any piece of by_color can reach (row, col)."""
        for r in range(6):
            for c in range(6):
                cell = self.cells[r][c]
                if cell and cell[1] == by_color:
                    if (row, col) in self.get_dests(r, c):
                        return True
        return False

    def in_check(self, color: int) -> bool:
        kp = self._king_pos(color)
        return kp is None or self._is_attacked(kp[0], kp[1], 1 - color)

    @staticmethod
    def _is_mated_in(board: 'Board', color: int) -> bool:
        """True if 'color' is in check and has no legal escape on board."""
        if not board.in_check(color):
            return False
        old_tm       = board.to_move
        board.to_move = color
        for mv in board._board_moves(color) + board._drop_moves(color):
            nb = board._apply_raw(mv)
            if not nb.in_check(color):
                board.to_move = old_tm
                return False
        board.to_move = old_tm
        return True

    def winner(self):
        """Colour that has won, or None."""
        if self._king_pos(BLACK) is None:
            return WHITE
        if self._king_pos(WHITE) is None:
            return BLACK
        return None

    # ── Evaluation ────────────────────────────────────────────────────────────

    def evaluate(self) -> float:
        """Signed material score: positive = Black is ahead."""
        score = 0.0
        for r in range(6):
            for c in range(6):
                cell = self.cells[r][c]
                if cell:
                    v = VALUE[cell[0]]
                    score += v if cell[1] == BLACK else -v
        for p in self.hands[BLACK]:
            score += VALUE[p] * 0.9
        for p in self.hands[WHITE]:
            score -= VALUE[p] * 0.9
        return score

    # ── Search (alpha-beta, depth 2) ─────────────────────────────────────────

    def best_move(self, depth: int = 2):
        """Return the best move found by alpha-beta search."""
        color  = self.to_move
        moves  = self.legal_moves()
        if not moves:
            return None
        random.shuffle(moves)        # break ties / add variety
        sign       = 1 if color == BLACK else -1
        best_score = -1_000_000
        best       = moves[0]

        for mv in moves:
            nb = self._apply_raw(mv)
            w  = nb.winner()
            if w == color:
                return mv            # immediate winning capture
            score = sign * self._ab(nb, depth - 1, -1_000_000, 1_000_000)
            if score > best_score:
                best_score = score
                best       = mv

        return best

    def _ab(self, board: 'Board', depth: int, alpha: float, beta: float) -> float:
        """Alpha-beta minimax, returns score from Black's perspective."""
        w = board.winner()
        if w == BLACK:
            return  10_000.0
        if w == WHITE:
            return -10_000.0
        if depth == 0:
            return board.evaluate()
        moves = board.legal_moves()
        if not moves:
            return board.evaluate()

        if board.to_move == BLACK:
            v = -1_000_000.0
            for mv in moves:
                v     = max(v, self._ab(board._apply_raw(mv), depth - 1, alpha, beta))
                alpha = max(alpha, v)
                if beta <= alpha:
                    break
            return v
        else:
            v = 1_000_000.0
            for mv in moves:
                v    = min(v, self._ab(board._apply_raw(mv), depth - 1, alpha, beta))
                beta = min(beta, v)
                if beta <= alpha:
                    break
            return v

    # ── Move encoding / decoding ──────────────────────────────────────────────

    def move_str(self, mv) -> str:
        """Internal move tuple → XBoard string (e.g. 'c1d2' or 'K@d4')."""
        if mv[0] == 'mv':
            _, fr, fc, tr, tc = mv
            return sq2str(fc, fr) + sq2str(tc, tr)
        else:
            _, piece, tr, tc = mv
            return P2C[piece] + '@' + sq2str(tc, tr)

    def parse_move(self, s: str):
        """XBoard string → internal move tuple, or None on failure."""
        s = s.strip()
        # Drop:  P@d4  or  P*d4
        m = re.match(r'^([WPHGNBDKwphgnbdk])[@*]([a-f][1-6])$', s)
        if m:
            piece      = C2P[m.group(1).upper()]
            col, row   = str2sq(m.group(2))
            return ('dr', piece, row, col)
        # Normal move:  c1d2
        if (len(s) == 4
                and s[0].isalpha() and s[1].isdigit()
                and s[2].isalpha() and s[3].isdigit()):
            try:
                fc, fr = str2sq(s[0:2])
                tc, tr = str2sq(s[2:4])
                return ('mv', fr, fc, tr, tc)
            except (ValueError, IndexError):
                pass
        return None

    # ── Debug display ─────────────────────────────────────────────────────────

    def display(self) -> str:
        lines = ['  a  b  c  d  e  f']
        for r in range(5, -1, -1):
            row_str = f'{r+1} '
            for c in range(6):
                cell = self.cells[r][c]
                if cell is None:
                    row_str += '.  '
                else:
                    ch = P2C[cell[0]]
                    row_str += (ch.lower() + ' ') if cell[1] == WHITE else (ch + '  ')
            lines.append(row_str)
        lines.append(f'Black hand: {[P2C[p] for p in self.hands[BLACK]]}')
        lines.append(f'White hand: {[P2C[p] for p in self.hands[WHITE]]}')
        lines.append(f'Side to move: {"Black" if self.to_move == BLACK else "White"}')
        return '\n'.join(lines)


# ── XBoard protocol engine loop ───────────────────────────────────────────────

def main():
    board        = Board()
    engine_color = WHITE       # engine plays White after 'new'
    force_mode   = True        # do not auto-play until 'new' or 'go'
    move_history = []          # list of (board_before, move_str) for undo

    def out(msg: str):
        sys.stdout.write(msg + '\n')
        sys.stdout.flush()

    def engine_move():
        nonlocal board
        mv = board.best_move(depth=2)
        if mv is None:
            out('resign')
            return
        ms = board.move_str(mv)
        move_history.append((board.copy(), ms))
        board = board._apply_raw(mv)
        out('move ' + ms)
        w = board.winner()
        if w == BLACK:
            out('RESULT 0-1 {Black wins by capturing the White Whale}')
        elif w == WHITE:
            out('RESULT 1-0 {White wins by capturing the White Whale}')

    while True:
        try:
            raw = sys.stdin.readline()
        except (EOFError, KeyboardInterrupt):
            break
        if not raw:
            break

        line   = raw.strip()
        tokens = line.split()
        if not tokens:
            continue
        cmd = tokens[0]

        # ── Protocol handshake ────────────────────────────────────────────────
        if cmd == 'xboard':
            pass

        elif cmd == 'protover':
            out('feature myname="Whale Shogi Engine"')
            out('feature variants="whale-shogi"')
            out('feature usermove=1')
            out('feature reuse=1')
            out('feature done=1')

        elif cmd in ('accepted', 'rejected'):
            pass

        # ── Game control ──────────────────────────────────────────────────────
        elif cmd == 'new':
            board        = Board()
            engine_color = WHITE
            force_mode   = False
            move_history.clear()

        elif cmd == 'variant':
            pass   # accept any variant name; we only know whale-shogi

        elif cmd == 'force':
            force_mode = True

        elif cmd == 'go':
            force_mode   = False
            engine_color = board.to_move
            engine_move()

        elif cmd == 'usermove':
            if len(tokens) >= 2:
                mv = board.parse_move(tokens[1])
                if mv is not None:
                    move_history.append((board.copy(), tokens[1]))
                    board = board._apply_raw(mv)
                    if not force_mode and board.to_move == engine_color:
                        engine_move()
                else:
                    out(f'Error (illegal move): {tokens[1]}')

        # ── Undo ──────────────────────────────────────────────────────────────
        elif cmd == 'undo':
            if move_history:
                board, _ = move_history.pop()

        elif cmd == 'remove':       # take back 2 moves
            for _ in range(2):
                if move_history:
                    board, _ = move_history.pop()

        # ── Misc protocol commands ────────────────────────────────────────────
        elif cmd == 'ping':
            n = tokens[1] if len(tokens) > 1 else '0'
            out(f'pong {n}')

        elif cmd == 'result':
            pass   # game over notification; nothing to do

        elif cmd == 'setboard':
            pass   # not implemented; would need FEN parser for this variant

        elif cmd in ('hint', 'bk', 'draw', 'hard', 'easy', 'level', 'st',
                     'sd', 'nps', 'time', 'otim', 'edit', 'analyze', 'exit',
                     'computer', 'white', 'black', 'random', 'post', 'nopost',
                     'cores', 'memory', 'option'):
            pass   # silently ignore time/analysis/config commands

        elif cmd == 'quit':
            break

        else:
            # Older XBoard protocol sends raw move strings without 'usermove'
            mv = board.parse_move(cmd)
            if mv is not None:
                move_history.append((board.copy(), cmd))
                board = board._apply_raw(mv)
                if not force_mode and board.to_move == engine_color:
                    engine_move()
            # Unknown commands are silently ignored to keep the protocol clean

    sys.exit(0)


if __name__ == '__main__':
    main()