# def comet(mvs, pcs, recdepth, maxrecdepth):
#     options = []
#     curxp = xp_diff(mvs[0][0].color, pcs)
#     intro = '// ' + ('-' * (recdepth * 2)) + ' COMET: '
#     if DEBUG_OUTPUT:
#         print(intro + '{} opts'.format(len(mvs)))
#     else:
#         print(' ' * recdepth + '*')
#     if len(mvs) == 1:
#         tmp, xp, oma = can_move_piece(mvs[0][0], mvs[0][1][0], mvs[0][1][1], pcs, aimode=True)
#         if DEBUG_OUTPUT:
#             print(intro + 'one opt ({} -> {}) - xp {}'.format(num_to_chess_coord(
#                                                                                               mvs[0][0].x,
#                                                                                               mvs[0][0].y),
#                                                                                           num_to_chess_coord(
#                                                                                               mvs[0][1][0],
#                                                                                               mvs[0][1][1]),
#                                                                                               xp))
#         return 0, xp
#     if recdepth == maxrecdepth:
#         if DEBUG_OUTPUT:
#             print(intro + 'unable to continue analysis; maximum recursion depth exceeded;'
#                           ' xp set to current xp ({})'.format(curxp))
#         return 0, curxp
#     for m in mvs:
#         if m[0].type != KING:
#             break
#     else:
#         # Check if possible to check or checkmate
#         for n in range(len(mvs)):
#             tmp, xp, oma = can_move_piece(mvs[n][0], mvs[n][1][0], mvs[n][1][1], pcs, aimode=True)
#             if type(oma) == bool and oma:
#                 return n, xp
#
#         for n in range(len(mvs)):
#             tmp, xp, oma = can_move_piece(mvs[n][0], mvs[n][1][0], mvs[n][1][1], pcs, aimode=True)
#             if xp - curxp >= 2:
#                 return n, xp
#         # / Check if possible to check or checkmate /
#         myking = m[0]
#         for p in pcs:
#             if p.color != myking.color and p.type == KING:
#                 otherking = p
#         if myking.resist >= 6:
#             mv = select_move_toward(myking, otherking, mvs)
#         else:
#             mv = select_move_away(myking, otherking, mvs)
#         a, x, c = can_move_piece(myking, mvs[mv][1][0], mvs[mv][1][1], pcs, aimode=True)
#         return mv, x
#     for i in range(len(mvs)):
#         tmp, xp, oma = can_move_piece(mvs[i][0], mvs[i][1][0], mvs[i][1][1], pcs, aimode=True)
#         if type(oma) == bool and oma:
#             turn = i
#             if DEBUG_OUTPUT:
#                 print(intro + 'opt {} ({} -> {}) leads to victory, xp counted as inf; exiting analysis'.format(i,
#                                                                                                num_to_chess_coord(
#                                                                                                    mvs[i][0].x,
#                                                                                                    mvs[i][0].y),
#                                                                                                num_to_chess_coord(
#                                                                                                    mvs[i][1][0],
#                                                                                                    mvs[i][1][1])))
#                 xp = INF
#                 return i, INF
#
#         elif type(oma) != bool and len(oma) == 1:
#             bpcs = []
#             for p in pcs:
#                 bpcs.append(copy.deepcopy(p))
#
#             if DEBUG_OUTPUT:
#                 print(intro + 'analyzing our opt {} ({} -> {})...'.format(i,
#                                                                    num_to_chess_coord(
#                                                                        mvs[i][0].x,
#                                                                        mvs[i][0].y),
#                                                                    num_to_chess_coord(
#                                                                        mvs[i][1][0],
#                                                                        mvs[i][1][1])))
#
#             move_piece(mvs[i][0], mvs[i][1][0], mvs[i][1][1], bpcs)
#             if DEBUG_OUTPUT:
#                 print(intro + 'fc; one opponent opt ({} -> {})'.format(num_to_chess_coord(
#                                                                     oma[0][0].x,
#                                                                     oma[0][0].y),
#                                                                 num_to_chess_coord(
#                                                                     oma[0][1][0],
#                                                                     oma[0][1][1]
#                                                                 )))
#             move_piece(oma[0][0], oma[0][1][0], oma[0][1][1], bpcs)
#
#             newmv = get_all_moves(mvs[0][0].color, bpcs)
#             if type(newmv) != bool:
#                 tmptmp, xp = comet(newmv, bpcs, recdepth + 1, maxrecdepth)# if maxrecdepth - recdepth >= 1 else -1, curxp
#                 if DEBUG_OUTPUT:
#                     print(intro + 'analysis of opt {} finished; xp {}'.format(i, xp))
#                 if xp == INF:
#                     if DEBUG_OUTPUT:
#                         print(intro + 'checkmate detected, exiting analysis')
#                     return i, INF
#             else:
#                 if DEBUG_OUTPUT:
#                     print(intro + 'opt {} leads to defeat/stalemate, xp counted as -inf'.format(i))
#                 xp = -INF
#
#         elif type(oma) != bool and get_piece_by_coords(oma[0][1][0], oma[0][1][1], pcs) is not None:
#             bpcs = []
#             for p in pcs:
#                 bpcs.append(copy.deepcopy(p))
#
#             if DEBUG_OUTPUT:
#                 print(intro + 'analyzing opt {} ({} -> {})...'.format(i,
#                                                                       num_to_chess_coord(
#                                                                           mvs[i][0].x,
#                                                                           mvs[i][0].y),
#                                                                       num_to_chess_coord(
#                                                                           mvs[i][1][0],
#                                                                           mvs[i][1][1])))
#
#             move_piece(mvs[i][0], mvs[i][1][0], mvs[i][1][1], bpcs)
#             if DEBUG_OUTPUT:
#                 print(intro + 'fc; {} opponent opts'.format(len(oma)))
#             xps = []
#             for q in range(len(oma)):
#                 nbpcs = []
#                 for p in bpcs:
#                     nbpcs.append(copy.deepcopy(p))
#                 if DEBUG_OUTPUT:
#                     print(intro + 'analyzing opponent opt {} ({} -> {})'.format(q, num_to_chess_coord(
#                                                                             oma[0][0].x,
#                                                                             oma[0][0].y),
#                                                                             num_to_chess_coord(
#                                                                                 oma[0][1][0],
#                                                                                 oma[0][1][1]
#                                                                             )))
#                 move_piece(oma[q][0], oma[q][1][0], oma[q][1][1], nbpcs)
#
#                 newmv = get_all_moves(mvs[0][0].color, nbpcs)
#                 if type(newmv) != bool:
#                     if maxrecdepth - recdepth >= 1:
#                         t, xpn = comet(newmv, nbpcs, recdepth + 1, maxrecdepth)
#                         if DEBUG_OUTPUT:
#                             print(intro + 'analysis of opponent opt {} finished; xp {}'.format(q, xpn))
#                     else:
#                         xpn = curxp
#                         if DEBUG_OUTPUT:
#                             print(intro + 'unable to analyze opponent opt {}; maximum recursion depth exceeded;'
#                                           ' xp set to current xp ({})'.format(q, xpn))
#
#                 else:
#                     if DEBUG_OUTPUT:
#                         print(intro + 'opponent opt {} leads to defeat/stalemate, xp counted as -inf'.format(q))
#                     xpn = -INF
#
#                 xps.append(xpn)
#
#             xp = min(xps)
#             if DEBUG_OUTPUT:
#                 print(intro + 'analysis of opt {} finished, final possible xps {}'.format(i, xps))
#                 print(intro + 'min xp {}'.format(xp))
#
#         # elif type(oma) != bool and len(oma) == 2:
#         #     bpcs = []
#         #     for p in pcs:
#         #         bpcs.append(copy.deepcopy(p))
#         #
#         #     if DEBUG_OUTPUT:
#         #         print(
#         #             intro + 'semi-analyzing opt {} ({} -> {})...'.format(i,
#         #                                                                                          num_to_chess_coord(
#         #                                                                                              mvs[
#         #                                                                                                  i][0].x,
#         #                                                                                              mvs[
#         #                                                                                                  i][0].y),
#         #                                                                                          num_to_chess_coord(
#         #                                                                                              mvs[
#         #                                                                                                  i][
#         #                                                                                                  1][
#         #                                                                                                  0],
#         #                                                                                              mvs[
#         #                                                                                                  i][
#         #                                                                                                  1][
#         #                                                                                                  1])))
#         #
#         #     move_piece(mvs[i][0], mvs[i][1][0], mvs[i][1][1], bpcs)
#         #     t, xp = comet(oma, bpcs, -1, -1)
#         #     move_piece(oma[t][0], oma[t][1][0], oma[t][1][1], bpcs)
#         #     xp = xp_sum(mvs[0][0].color, bpcs)
#         #     if DEBUG_OUTPUT:
#         #         print(intro + 'semi-analysis of opt {} finished; xp {}'.format(i, xp))
#
#         elif DEBUG_OUTPUT:
#             print(intro + 'opt {} ({} -> {}) - not fc, xp {}'.format(i,
#                                                                        num_to_chess_coord(mvs[i][0].x, mvs[i][0].y),
#                                                                        num_to_chess_coord(mvs[i][1][0], mvs[i][1][1]),
#                                                                        xp))
#         options.append(xp)
#     else:
#         m = max(options)
#         turns = [i for i in range(len(options)) if options[i] == m]
#         turn = random.choice(turns)
#         if DEBUG_OUTPUT:
#             print(intro + 'final opts {}'.format(str(options).replace('100000000000000000000', 'inf')))
#
#     if DEBUG_OUTPUT:
#         print(intro + 'selected opt {}'.format(turn))
#
#     return turn, max(options)
# def get_piece_by_coords(x, y, pieces):
#     for piece in pieces:
#         if piece.x == x and piece.y == y:
#             return piece
#     return None
#
# def get_index_by_coords(x, y, pieces):
#     for i in range(len(pieces)):
#         if pieces[i].x == x and pieces[i].y == y:
#             return i
#     return None
# def get_moves_by_offset(diags, x, y, board):
#     stopped = [False] * 4
#     ret = []
#
#     for i in range(1, max(BOARD_X, BOARD_Y)):
#         for d in range(4):
#             if not stopped[d]:
#                 p = board[x + diags[d][0] * i, y + diags[d][1] * i]
#                 if p is not None:
#                     stopped[d] = True
#                     if p.color != self.color:
#                         ret.append((p.x, p.y))
#                 else:
#                     ret.append((self.x + diags[d][0] * i, self.y + diags[d][1] * i))
#     return ret
# def is_check(color, pieces):
#     return get_all_moves(not color, pieces, has_king_cpt=True)
#
# def is_under_attack_of(piece1, piece2, pieces):
#     allm = get_all_moves(True, pieces) + get_all_moves(False, pieces)
#     allm = [x for x in allm if x[0] == piece1 and x[1][0] == piece2.x and x[1][1] == piece2.y]
#     return not len(allm) == 0
#
# def can_move_piece(piece, x2, y2, pieces, aimode=False):
#     pieces_back = []
#
#     for p in pieces:
#         pieces_back.append(copy.deepcopy(p))
#
#     p1 = get_index_by_coords(piece.x, piece.y, pieces_back)
#     p2 = get_index_by_coords(x2, y2, pieces_back)
#
#     xp = 0
#
#     if p1 is None:
#         raise Exception('No such piece')
#     if p2 is not None:
#         xp += pieces_back[p2].type.capture_price
#         pieces_back.pop(p2)
#         if p1 > p2:
#             p1 -= 1
#
#     pieces_back[p1].x = x2
#     pieces_back[p1].y = y2
#
#     ret = not is_check(pieces_back[p1].color, pieces_back)
#
#     xp += CHECK_XP if is_check(not piece.color, pieces_back) else 0
#     xp = TURN_XP if xp == 0 else xp
#     pieces_back[p1].add_xp(xp)
#
#     total_xp = xp_diff(piece.color, pieces_back)
#
#     if aimode:
#         return ret, total_xp, get_all_moves(not piece.color, pieces_back) # total_xp = difference between sum of xp of pcs
#                                                                           # of this color and pieces of the opp color
#     else:
#         return ret
#
# def move_piece(piece, x2, y2, pieces):
#     global pawn_prom
#     p1 = get_index_by_coords(piece.x, piece.y, pieces)
#     p2 = get_index_by_coords(x2, y2, pieces)
#
#     xpsum = 0
#
#     if p1 is None:
#         raise Exception('No such piece')
#     if p1 == p2:
#         raise Exception('Can\'t move piece to previous location')
#     if p2 is not None:
#         xpsum += pieces[p2].type.capture_price
#         pieces.pop(p2)
#         if p1 > p2:
#             p1 -= 1
#
#     if pieces[p1].type == PAWN and pawn_prom:
#         print(LANGUAGE.phrases.PROMOTION_CHOICE)
#         typ = input()
#         if typ == '1':
#             pieces[p1] = Piece(p1.color, ROOK, x2, y2, moved=True)
#         elif typ == '2':
#             pieces[p1] = Piece(p1.color, BISHOP, x2, y2, moved=True)
#         elif typ == '3':
#             pieces[p1] = Piece(p1.color, KNIGHT, x2, y2, moved=True)
#         else:
#             pieces[p1] = Piece(p1.color, QUEEN, x2, y2, moved=True)
#     else:
#         pieces[p1].x = x2
#         pieces[p1].y = y2
#
#     xpsum += CHECK_XP if is_check(not piece.color, pieces) else 0
#     xpsum = TURN_XP if xpsum == 0 else xpsum
#     pieces[p1].add_xp(xpsum)
#
# def get_all_moves(color, pieces, has_king_cpt=False, has_mob_cpt=False):
#     ret = []
#     captures = []
#     res = []
#     for p in pieces:
#         if p.color == color:
#             rt, cpt = p.get_moves(pieces)
#             ret.extend([(p, x) for x in rt])
#             captures.extend([(p, x) for x in cpt])
#             for x, y in cpt:
#                 if get_piece_by_coords(x, y, pieces).type == KING:
#                     return True
#                 if get_piece_by_coords(x, y, pieces).type == MOB and has_mob_cpt:
#                     return True
#
#     if has_king_cpt or has_mob_cpt:
#         return False
#
#     # --- Check all capture variants for checks
#     popped = []
#
#     for i in range(len(captures)):
#         b = can_move_piece(captures[i][0], captures[i][1][0], captures[i][1][1], pieces)
#         if not b:
#             popped.append(captures[i])
#
#     for p in popped:
#         captures.remove(p)
#
#     if len(captures) == 0:
#         # --- Same with ret
#         popped = []
#
#         for i in range(len(ret)):
#             b = can_move_piece(ret[i][0], ret[i][1][0], ret[i][1][1], pieces)
#             if not b:
#                 popped.append(ret[i])
#
#         for p in popped:
#             ret.remove(p)
#
#         res = ret
#     else:
#         res = captures
#
#     if len(res) == 0:
#         return is_check(color, pieces)
#     else:
#         return res
# def change_back(v):
#     global curon
#
#     v = False
#     if v:
#         curon = not curon
#
#         if curon:
#             print('\033[47m', end='')
#         else:
#             print('\033[0m', end='')
# def power(type):
#     if type == PAWN:
#         return 1
#     if type == KNIGHT:
#         return 2
#     if type == BISHOP:
#         return 3
#     if type == ROOK:
#         return 4
#     if type == QUEEN:
#         return 5
#     if type == KING:
#         return 6
#     if type == AMAZON:
#         return 7
#
# def select_move_toward(p1, p2, mvs):
#     xd, yd = abs(p1.x - p2.x), abs(p1.y - p2.y)
#     resindex = -1
#     resval = -INF
#     for m in range(len(mvs)):
#         nx, ny = abs(mvs[m][1][0] - p2.x), abs(mvs[m][1][1] - p2.y)
#         change = xd - nx + yd - ny
#         if change > resval:
#             resval = change
#             resindex = m
#
#     return resindex
#
# def select_move_away(p1, p2, mvs):
#     xd, yd = abs(p1.x - p2.x), abs(p1.y - p2.y)
#     resindex = -1
#     resval = -INF
#     for m in range(len(mvs)):
#         nx, ny = abs(mvs[m][1][0] - p2.x), abs(mvs[m][1][1] - p2.y)
#         change = nx - xd + ny - yd
#         if change > resval:
#             resval = change
#             resindex = m
#
#     return resindex
#
# def escape_capture_of(mob, piece1, pieces):
#     variants = [(-1, 0), (1, 0), (0, -1), (0, 1)]
#     ret = []
#     for v in variants:
#         pieces_back = []
#         for p in pieces:
#             pieces_back.append(copy.deepcopy(p))
#         move_piece(mob, mob.x + v[0], mob.y + v[1], pieces_back)
#         if not is_under_attack_of(piece1, mob, pieces_back):
#             ret.append(v)
#     return ret
#
# def get_all_mobs(pieces):
#     return [x for x in pieces if x.type == MOB]
#
# def can_move_piece(self, p1, x, y, return_details=False):
    #     board_c = copy.copy(self)
    #
    #     p2 = self[x, y]
    #     board_c.pieces.pop((self[p1].x, self[p1].y))
    #
    #     xp = 0
    #
    #     if p1 is None:
    #         raise Exception('No such piece')
    #     if p2 is not None:
    #         xp += board_c.pieces_l[p2].type.capture_price
    #         self.remove(p2)
    #         if p1 > p2:
    #             p1 -= 1
    #
    #     board_c[p1].x = x
    #     board_c[p1].y = y
    #
    #     ret = not self.is_check(board_c.pieces_l[p1].color)
    #
    #     xp += CHECK_XP if self.is_check(not board_c.pieces_l[p1].color) else 0
    #     xp = TURN_XP if xp == 0 else xp
    #     board_c.pieces_l[p1].add_xp(xp)
    #
    #     total_xp = board_c.xp_diff(board_c.pieces_l[p1].color)
    #
    #     if return_details:
    #         mv, cpt = self.get_all_moves()
    #         return ret, total_xp, mv[int(not board_c.pieces_l[p1].color)], cpt[int(not board_c.pieces_l[p1].color)]
    #         # total_xp = difference between sum of xp of pcs
    #         # of this color and pieces of the opp color
    #     else:
    #         return ret
#
# def move_to_chess(piece, x, y, pieces):
#     if piece.type == PAWN:
#         if piece.x == x:
#             ret = num_to_chess_coord(x, y)
#         else:
#             ret = LINES[piece.x] + LINES[x]
#     else:
#         if get_piece_by_coords(x, y, pieces) is None:
#             ret = piece.type.abbr + num_to_chess_coord(x, y)
#         else:
#             ret = piece.type.abbr + ':' + num_to_chess_coord(x, y)
#     return ret
#
# bool1 = len(t) != 2 or len(t[0]) != 2 or len(t[1]) != 2 or \
                #         t[0][0] not in LINES[:BOARD_X] or t[1][0] not in LINES[:BOARD_X] or \
                #         t[0][1] not in string.digits or t[1][1] not in string.digits