#
# Global Variable
#   
directKing := [[-1,  1], [0,  1], [1,  1], 
               [-1,  0],          [1,  0],
               [-1, -1], [0, -1], [1, -1]]:
directRook := [[1, 0], [-1, 0], [0, 1], [0, -1]]:

#
# Main Function
#   Board Format: [width, height, side, 
#                  [wkCol, wkRow], [wrCol, wrRow], [bkCol, bkRow]]
# ??? optimize by move ordering
rook := proc(input)
    local board, depth;

    # Check Input
    if checkInput(input) <> "" then
        return checkInput(input);
    fi;

    # Process
    board := [input[1], input[2], 1, input[3], input[4], input[5]];
    depth := 1;

    while evalWBoard(board, depth) = 0 do
        depth := depth+2;
    od;

    return sprintf("W wi %d.", (depth+1)/2);
end:

#
# Check Input
#
checkInput := proc(board)
    if nops(board) <> 5 then
        return "Input 5 parameters";
    elif board[1] < 2 or board[2] < 2 or board[1]*board[2] < 6 then
        return "Minimum size is 3 x 2";
    elif board[3][1] < 1 or board[3][1] > board[1]
         or board[3][2] < 1 or board[3][2] > board[2]
         or board[4][1] < 1 or board[4][1] > board[1]
         or board[4][2] < 1 or board[4][2] > board[2]
         or board[5][1] < 1 or board[5][1] > board[1]
         or board[5][2] < 1 or board[5][2] > board[2] then
        return "Piece out of Board";
    elif board[3] = board[4] or board[3] = board[5] or board[4] = board[5] 
then
        return "Duplicate Position";
    elif max(abs(board[3][1]-board[5][1]), 
             abs(board[3][2]-board[5][2])) <= 1 then
        return "King Attachment";
    else
        return "";
    fi;
end:

#
# Evaluate White Move Board
#
evalWBoard := proc(board, depth)
    option remember;

    local ret, moveList, i, score;

    if board[5] = board[6] then     # White Rook is captured
        return 0;
    else                            # Find Winning Move
        ret      := -1;
        moveList := genMove(board);

        for i from 1 while i <= nops(moveList) and ret < 1 do
            score := -evalBBoard(makeMove(board, moveList[i]), depth-1);

            if score > ret then
                ret:= score;
            fi;
        od;

        return ret;
    fi;
end:

#
# Evaluate Black Move Board
#
evalBBoard := proc(board, depth)
    option remember;

    local ret, moveList, i, score;

    moveList := genMove(board);

    if nops(moveList) = 0 then
        if board[6][1] = board[5][1] 
           or board[6][2] = board[5][2] then    # Checkmate
            return -1;  
        else                                    # Stalemate
            return 0;   
        fi;
    elif depth = 0 then                         # Unknown Result
        return 0;       
    else                                        # Find Surviving Move
        ret := -1;

        for i from 1 while i <= nops(moveList) and ret < 0 do
            score := -evalWBoard(makeMove(board, moveList[i]), depth-1);

            if score > ret then
                ret:= score;
            fi;
        od;

        return ret;
    fi;
end:

#
# Make Move
#
makeMove := proc(board, move)
    option remember;

    local ret;

    ret := board;

    ret[move[1]] := move[2];
    ret[3]       := ret[3] mod 2 + 1;   # Swap Side
    
    return ret;
end:

#
# Generate Move
#   Move Format: [kind, [toCol, toRow]]
#
genMove := proc(board)
    option remember;

    if board[3] = 1 then
        return [op(genWKMove(board)), op(genWRMove(board))];
    else
        return genBKMove(board);
    fi;
end:

#
# Generate White King Move
#
genWKMove := proc(board)
    option remember;

    local ret, direct, posWK, posWR, posBK;

    ret   := [];
    posWR := board[5];
    posBK := board[6];

    for direct in directKing do
        posWK := [board[4][1]+direct[1], board[4][2]+direct[2]];
        
        if posWK[1] >= 1 and posWK[1] <= board[1]
           and posWK[2] >= 1 and posWK[2] <= board[2]
           and posWK <> posWR 
           and max(abs(posWK[1]-posBK[1]), abs(posWK[2]-posBK[2])) > 1 
then
            ret := [op(ret) , [4, posWK]];
        fi;
    od;

    return ret;
end:

#
# Generate White Rook Move
#
genWRMove := proc(board)
    option remember;

    local ret, direct, posWK, posWR, posBK;

    ret   := [];
    posWK := board[4];
    posBK := board[6];

    ret := [];

    for direct in directRook do
        posWR := [board[5][1]+direct[1], board[5][2]+direct[2]];
        
        while posWR[1] >= 1 and posWR[1] <= board[1]
              and posWR[2] >= 1 and posWR[2] <= board[2]
              and posWR <> posWK and posWR <> posBK do
            ret := [op(ret) , [5, posWR]];

            posWR := [posWR[1]+direct[1], posWR[2]+direct[2]];
        od;
    od;

    return ret;
end:

#
# Generate Black King Move
#
genBKMove := proc(board)
    option remember;

    local ret, direct, posWK, posWR, posBK;

    ret   := [];
    posWK := board[4];
    posWR := board[5];

    for direct in directKing do
        posBK := [board[6][1]+direct[1], board[6][2]+direct[2]];
        
        if posBK[1] >= 1 and posBK[1] <= board[1]
           and posBK[2] >= 1 and posBK[2] <= board[2]
           and (not (posBK[1] = posWR[1] xor posBK[2] = posWR[2])
                or (posBK[1] = posWR[1] and posBK[1] = posWK[1] 
                    and ((posWK[2] > posBK[2] and posWK[2] < posWR[2]) 
                         or (posWK[2] > posWR[2] and posWK[2] < 
posBK[2])))
                or (posBK[2] = posWR[2] and posBK[2] = posWK[2] 
                    and ((posWK[1] > posBK[1] and posWK[1] < posWR[1]) 
                         or (posWK[1] > posWR[1] and posWK[1] < 
posBK[1]))))
           and max(abs(posBK[1]-posWK[1]), abs(posBK[2]-posWK[2])) > 1 
then
            ret := [op(ret) , [6, posBK]];
        fi;
    od;

    return ret;
end: