def test_long_game_tree_search(self):
        player = MCTSPlayerMixin(DummyNet())
        endgame = go.Position(
            board=TT_FTW_BOARD,
            n=MAX_DEPTH-2,
            komi=2.5,
            ko=None,
            recent=(go.PlayerMove(go.BLACK, (0, 1)),
                    go.PlayerMove(go.WHITE, (0, 8))),
            to_play=go.BLACK
        )
        player.initialize_game(endgame)

        # Test that an almost complete game
        for i in range(10):
            player.tree_search(num_parallel=8)
        self.assertNoPendingVirtualLosses(player.root)
        self.assertGreater(player.root.Q, 0) 

def test_extract_data_resign_end(self):
        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game()
        player.tree_search()
        player.play_move((0, 0))
        player.tree_search()
        player.play_move(None)
        player.tree_search()
        # Black is winning on the board
        self.assertEqual(player.root.position.result(), go.BLACK)
        # But if Black resigns
        player.set_result(go.WHITE, was_resign=True)

        data = list(player.extract_data())
        position, pi, result = data[0]
        # Result should say White is the winner
        self.assertEqual(result, go.WHITE)
        self.assertEqual(player.result_string, "W+R") 

def test_is_eyeish(self):
        board = test_utils.load_board('''
            .XX...XXX
            X.X...X.X
            XX.....X.
            ........X
            XXXX.....
            OOOX....O
            X.OXX.OO.
            .XO.X.O.O
            XXO.X.OO.
        ''')
        B_eyes = coords_from_kgs_set('A2 A9 B8 J7 H8')
        W_eyes = coords_from_kgs_set('H2 J1 J3')
        not_eyes = coords_from_kgs_set('B3 E5')
        for be in B_eyes:
            self.assertEqual(go.is_eyeish(board, be), BLACK, str(be))
        for we in W_eyes:
            self.assertEqual(go.is_eyeish(board, we), WHITE, str(we))
        for ne in not_eyes:
            self.assertEqual(go.is_eyeish(board, ne), None, str(ne)) 

def test_place_stone_opposite_color(self):
        board = test_utils.load_board('X........' + EMPTY_ROW * 8)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(WHITE, coords.from_kgs('B9'))
        self.assertEqual(len(lib_tracker.groups), 2)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('A9')], go.MISSING_GROUP_ID)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('B9')], go.MISSING_GROUP_ID)
        self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs('A9')], 1)
        self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs('B9')], 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'A9')]]
        white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B9')]]
        self.assertEqual(black_group.stones, coords_from_kgs_set('A9'))
        self.assertEqual(black_group.liberties, coords_from_kgs_set('A8'))
        self.assertEqual(black_group.color, BLACK)
        self.assertEqual(white_group.stones, coords_from_kgs_set('B9'))
        self.assertEqual(white_group.liberties, coords_from_kgs_set('C9 B8'))
        self.assertEqual(white_group.color, WHITE) 

def test_merge_multiple_groups(self):
        board = test_utils.load_board('''
            .X.......
            X.X......
            .X.......
        ''' + EMPTY_ROW * 6)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(BLACK, coords.from_kgs('B8'))
        self.assertEqual(len(lib_tracker.groups), 1)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('B8')], go.MISSING_GROUP_ID)
        sole_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B8')]]
        self.assertEqual(sole_group.stones,
                         coords_from_kgs_set('B9 A8 B8 C8 B7'))
        self.assertEqual(sole_group.liberties,
                         coords_from_kgs_set('A9 C9 D8 A7 C7 B6'))
        self.assertEqual(sole_group.color, BLACK)

        liberty_cache = lib_tracker.liberty_cache
        for stone in sole_group.stones:
            self.assertEqual(liberty_cache[stone], 6, str(stone)) 

def test_passing(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=coords.from_kgs('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=1,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=(PlayerMove(BLACK, None),),
            to_play=WHITE,
        )
        pass_position = start_position.pass_move()
        self.assertEqualPositions(pass_position, expected_position) 

def test_flipturn(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=coords.from_kgs('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=tuple(),
            to_play=WHITE,
        )
        flip_position = start_position.flip_playerturn()
        self.assertEqualPositions(flip_position, expected_position) 

def load_board(string):
    reverse_map = {
        'X': go.BLACK,
        'O': go.WHITE,
        '.': go.EMPTY,
        '#': go.FILL,
        '*': go.KO,
        '?': go.UNKNOWN
    }

    string = re.sub(r'[^XO\.#]+', '', string)
    assert len(string) == go.N ** 2, "Board to load didn't have right dimensions"
    board = np.zeros([go.N, go.N], dtype=np.int8)
    for i, char in enumerate(string):
        np.ravel(board)[i] = reverse_map[char]
    return board 

def handle_node(pos, node):
    'A node can either add B+W stones, play as B, or play as W.'
    props = node.properties
    black_stones_added = [coords.from_sgf(
        c) for c in props.get('AB', [])]
    white_stones_added = [coords.from_sgf(
        c) for c in props.get('AW', [])]
    if black_stones_added or white_stones_added:
        return add_stones(pos, black_stones_added, white_stones_added)
    # If B/W props are not present, then there is no move. But if it is present and equal to the empty string, then the move was a pass.
    elif 'B' in props:
        black_move = coords.from_sgf(props.get('B', [''])[0])
        return pos.play_move(black_move, color=go.BLACK)
    elif 'W' in props:
        white_move = coords.from_sgf(props.get('W', [''])[0])
        return pos.play_move(white_move, color=go.WHITE)
    else:
        return pos 

def test_long_game_tree_search(self):
        player = MCTSPlayerMixin(DummyNet())
        endgame = go.Position(
            board=TT_FTW_BOARD,
            n=MAX_DEPTH-2,
            komi=2.5,
            ko=None,
            recent=(go.PlayerMove(go.BLACK, (0, 1)),
                    go.PlayerMove(go.WHITE, (0, 8))),
            to_play=go.BLACK
        )
        player.initialize_game(endgame)

        # Test that an almost complete game
        for i in range(10):
            player.tree_search(num_parallel=8)
        self.assertNoPendingVirtualLosses(player.root)
        self.assertGreater(player.root.Q, 0) 

def test_extract_data_resign_end(self):
        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game()
        player.tree_search()
        player.play_move((0, 0))
        player.tree_search()
        player.play_move(None)
        player.tree_search()
        # Black is winning on the board
        self.assertEqual(player.root.position.result(), go.BLACK)
        # But if Black resigns
        player.set_result(go.WHITE, was_resign=True)

        data = list(player.extract_data())
        position, pi, result = data[0]
        # Result should say White is the winner
        self.assertEqual(result, go.WHITE)
        self.assertEqual(player.result_string, "W+R") 

def test_is_eyeish(self):
        board = test_utils.load_board('''
            .XX...XXX
            X.X...X.X
            XX.....X.
            ........X
            XXXX.....
            OOOX....O
            X.OXX.OO.
            .XO.X.O.O
            XXO.X.OO.
        ''')
        B_eyes = coords_from_kgs_set('A2 A9 B8 J7 H8')
        W_eyes = coords_from_kgs_set('H2 J1 J3')
        not_eyes = coords_from_kgs_set('B3 E5')
        for be in B_eyes:
            self.assertEqual(go.is_eyeish(board, be), BLACK, str(be))
        for we in W_eyes:
            self.assertEqual(go.is_eyeish(board, we), WHITE, str(we))
        for ne in not_eyes:
            self.assertEqual(go.is_eyeish(board, ne), None, str(ne)) 

def test_place_stone_opposite_color(self):
        board = test_utils.load_board('X........' + EMPTY_ROW * 8)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(WHITE, coords.from_kgs('B9'))
        self.assertEqual(len(lib_tracker.groups), 2)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('A9')], go.MISSING_GROUP_ID)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('B9')], go.MISSING_GROUP_ID)
        self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs('A9')], 1)
        self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs('B9')], 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'A9')]]
        white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B9')]]
        self.assertEqual(black_group.stones, coords_from_kgs_set('A9'))
        self.assertEqual(black_group.liberties, coords_from_kgs_set('A8'))
        self.assertEqual(black_group.color, BLACK)
        self.assertEqual(white_group.stones, coords_from_kgs_set('B9'))
        self.assertEqual(white_group.liberties, coords_from_kgs_set('C9 B8'))
        self.assertEqual(white_group.color, WHITE) 

def test_merge_multiple_groups(self):
        board = test_utils.load_board('''
            .X.......
            X.X......
            .X.......
        ''' + EMPTY_ROW * 6)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(BLACK, coords.from_kgs('B8'))
        self.assertEqual(len(lib_tracker.groups), 1)
        self.assertNotEqual(
            lib_tracker.group_index[coords.from_kgs('B8')], go.MISSING_GROUP_ID)
        sole_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B8')]]
        self.assertEqual(sole_group.stones,
                         coords_from_kgs_set('B9 A8 B8 C8 B7'))
        self.assertEqual(sole_group.liberties,
                         coords_from_kgs_set('A9 C9 D8 A7 C7 B6'))
        self.assertEqual(sole_group.color, BLACK)

        liberty_cache = lib_tracker.liberty_cache
        for stone in sole_group.stones:
            self.assertEqual(liberty_cache[stone], 6, str(stone)) 

def test_same_friendly_group_neighboring_twice(self):
        board = test_utils.load_board('''
            XX.......
            X........
        ''' + EMPTY_ROW * 7)

        lib_tracker = LibertyTracker.from_board(board)
        captured = lib_tracker.add_stone(BLACK, coords.from_kgs('B8'))
        self.assertEqual(len(lib_tracker.groups), 1)
        sole_group_id = lib_tracker.group_index[coords.from_kgs('A9')]
        sole_group = lib_tracker.groups[sole_group_id]
        self.assertEqual(sole_group.stones,
                         coords_from_kgs_set('A9 B9 A8 B8'))
        self.assertEqual(sole_group.liberties,
                         coords_from_kgs_set('C9 C8 A7 B7'))
        self.assertEqual(captured, set()) 

def test_passing(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=coords.from_kgs('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=1,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=(PlayerMove(BLACK, None),),
            to_play=WHITE,
        )
        pass_position = start_position.pass_move()
        self.assertEqualPositions(pass_position, expected_position) 

def test_flipturn(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=coords.from_kgs('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=tuple(),
            to_play=WHITE,
        )
        flip_position = start_position.flip_playerturn()
        self.assertEqualPositions(flip_position, expected_position) 

def load_board(string):
    reverse_map = {
        'X': go.BLACK,
        'O': go.WHITE,
        '.': go.EMPTY,
        '#': go.FILL,
        '*': go.KO,
        '?': go.UNKNOWN
    }

    string = re.sub(r'[^XO\.#]+', '', string)
    assert len(string) == go.N ** 2, "Board to load didn't have right dimensions"
    board = np.zeros([go.N, go.N], dtype=np.int8)
    for i, char in enumerate(string):
        np.ravel(board)[i] = reverse_map[char]
    return board 

def simulate_many_games(policy1, policy2, positions):
    """Simulates many games in parallel, utilizing GPU parallelization to
    run the policy network for multiple games simultaneously.

    policy1 is black; policy2 is white."""

    # Assumes that all positions are on the same move number. May not be true
    # if, say, we are exploring multiple MCTS branches in parallel
    while positions[0].n <= POLICY_CUTOFF_DEPTH + POLICY_FINISH_MOVES:
        black_to_play = [pos for pos in positions if pos.to_play == go.BLACK]
        white_to_play = [pos for pos in positions if pos.to_play == go.WHITE]

        for policy, to_play in ((policy1, black_to_play),
                                (policy2, white_to_play)):
            all_move_probs = policy.run_many(to_play)
            for i, pos in enumerate(to_play):
                move = select_weighted_random(pos, all_move_probs[i])
                pos.play_move(move, mutate=True)

    for pos in positions:
        simulate_game_random(pos)

    return positions 

def test_is_move_reasonable(self):
        board = load_board('''
            .XXOOOXXX
            X.XO.OX.X
            XXXOOOXX.
            ...XXX..X
            XXXX.....
            OOOX....O
            X.OXX.OO.
            .XO.X.O.O
            XXO.X.OO.
        ''')
        position = Position(
            board=board,
            to_play=BLACK,
        )
        reasonable_moves = pc_set('E8 B3')
        unreasonable_moves = pc_set('A9 B8 H8 J7 A2 J3 H2 J1')
        for move in reasonable_moves:
            self.assertTrue(is_move_reasonable(position, move), str(move))
        for move in unreasonable_moves:
            self.assertFalse(is_move_reasonable(position, move), str(move)) 

def test_is_eyeish(self):
        board = load_board('''
            .XX...XXX
            X.X...X.X
            XX.....X.
            ........X
            XXXX.....
            OOOX....O
            X.OXX.OO.
            .XO.X.O.O
            XXO.X.OO.
        ''')
        B_eyes = pc_set('A2 A9 B8 J7 H8')
        W_eyes = pc_set('H2 J1 J3')
        not_eyes = pc_set('B3 E5')
        for be in B_eyes:
            self.assertEqual(go.is_eyeish(board, be), BLACK, str(be))
        for we in W_eyes:
            self.assertEqual(go.is_eyeish(board, we), WHITE, str(we))
        for ne in not_eyes:
            self.assertEqual(go.is_eyeish(board, ne), None, str(ne)) 

def test_place_stone_opposite_color(self):
        board = load_board('X........' + EMPTY_ROW * 8)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(WHITE, pc('B9'))
        self.assertEqual(len(lib_tracker.groups), 2)
        self.assertNotEqual(lib_tracker.group_index[pc('A9')], go.MISSING_GROUP_ID)
        self.assertNotEqual(lib_tracker.group_index[pc('B9')], go.MISSING_GROUP_ID)
        self.assertEqual(lib_tracker.liberty_cache[pc('A9')], 1)
        self.assertEqual(lib_tracker.liberty_cache[pc('B9')], 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[pc('A9')]]
        white_group = lib_tracker.groups[lib_tracker.group_index[pc('B9')]]
        self.assertEqual(black_group.stones, pc_set('A9'))
        self.assertEqual(black_group.liberties, pc_set('A8'))
        self.assertEqual(black_group.color, BLACK)
        self.assertEqual(white_group.stones, pc_set('B9'))
        self.assertEqual(white_group.liberties, pc_set('C9 B8'))
        self.assertEqual(white_group.color, WHITE) 

def test_merge_multiple_groups(self):
        board = load_board('''
            .X.......
            X.X......
            .X.......
        ''' + EMPTY_ROW * 6)
        lib_tracker = LibertyTracker.from_board(board)
        lib_tracker.add_stone(BLACK, pc('B8'))
        self.assertEqual(len(lib_tracker.groups), 1)
        self.assertNotEqual(lib_tracker.group_index[pc('B8')], go.MISSING_GROUP_ID)
        sole_group = lib_tracker.groups[lib_tracker.group_index[pc('B8')]]
        self.assertEqual(sole_group.stones, pc_set('B9 A8 B8 C8 B7'))
        self.assertEqual(sole_group.liberties, pc_set('A9 C9 D8 A7 C7 B6'))
        self.assertEqual(sole_group.color, BLACK)

        liberty_cache = lib_tracker.liberty_cache
        for stone in sole_group.stones:
            self.assertEqual(liberty_cache[stone], 6, str(stone)) 

def test_capture_multiple_groups(self):
        board = load_board('''
            .OX......
            OXX......
            XX.......
        ''' + EMPTY_ROW * 6)
        lib_tracker = LibertyTracker.from_board(board)
        captured = lib_tracker.add_stone(BLACK, pc('A9'))
        self.assertEqual(len(lib_tracker.groups), 2)
        self.assertEqual(captured, pc_set('B9 A8'))

        corner_stone = lib_tracker.groups[lib_tracker.group_index[pc('A9')]]
        self.assertEqual(corner_stone.stones, pc_set('A9'))
        self.assertEqual(corner_stone.liberties, pc_set('B9 A8'))

        surrounding_stones = lib_tracker.groups[lib_tracker.group_index[pc('C9')]]
        self.assertEqual(surrounding_stones.stones, pc_set('C9 B8 C8 A7 B7'))
        self.assertEqual(surrounding_stones.liberties, pc_set('B9 D9 A8 D8 C7 A6 B6'))

        liberty_cache = lib_tracker.liberty_cache
        for stone in corner_stone.stones:
            self.assertEqual(liberty_cache[stone], 2, str(stone))
        for stone in surrounding_stones.stones:
            self.assertEqual(liberty_cache[stone], 7, str(stone)) 

def test_passing(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=pc('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=1,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=(PlayerMove(BLACK, None),),
            to_play=WHITE,
        )
        pass_position = start_position.pass_move()
        self.assertEqualPositions(pass_position, expected_position) 

def test_flipturn(self):
        start_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=pc('A1'),
            recent=tuple(),
            to_play=BLACK,
        )
        expected_position = Position(
            board=TEST_BOARD,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=tuple(),
            to_play=WHITE,
        )
        flip_position = start_position.flip_playerturn()
        self.assertEqualPositions(flip_position, expected_position) 

def cmd_q_heatmap(self, arguments):
        sort_order = list(range(self._game.size * self._game.size + 1))
        reverse = True if self._game.root.position.to_play is go.BLACK else False
        sort_order.sort(
            key=lambda i: self._game.root.child_Q[i], reverse=reverse)
        return self.heatmap(sort_order, self._game.root, 'child_Q') 

def cmd_spin(self, arguments):
        for i in range(50):
            for j in range(100):
                self._game.tree_search()
            moves = self.cmd_nextplay(None).lower()
            moves = moves.split()
            colors = "bw" if self._game.root.position.to_play is go.BLACK else "wb"
            moves_cols = " ".join(['{} {}'.format(*z)
                                   for z in zip(itertools.cycle(colors), moves)])
            print("gogui-gfx: TEXT", "{:.3f} after {}".format(
                self._game.root.Q, self._game.root.N), file=sys.stderr, flush=True)
            print("gogui-gfx: VAR", moves_cols, file=sys.stderr, flush=True)
        return self.cmd_nextplay(None) 

def translate_gtp_colors(gtp_color):
    if gtp_color == gtp.BLACK:
        return go.BLACK
    elif gtp_color == gtp.WHITE:
        return go.WHITE
    else:
        return go.EMPTY 

def set_result(self, winner, was_resign):
        self.result = winner
        if was_resign:
            string = "B+R" if winner == go.BLACK else "W+R"
        else:
            string = self.root.position.result_string()
        self.result_string = string