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_only_check_game_end_once(self):
        # When presented with a situation where the last move was a pass,
        # and we have to decide whether to pass, it should be the first thing
        # we check, but not more than that.

        white_passed_pos = go.Position(
        ).play_move((3, 3)  # b plays
                    ).play_move((3, 4)  # w plays
                                ).play_move((4, 3)  # b plays
                                            ).pass_move()  # w passes - if B passes too, B would lose by komi.

        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game(white_passed_pos)
        # initialize the root
        player.tree_search()
        # explore a child - should be a pass move.
        player.tree_search()
        pass_move = go.N * go.N
        self.assertEqual(player.root.children[pass_move].N, 1)
        self.assertEqual(player.root.child_N[pass_move], 1)
        player.tree_search()
        # check that we didn't visit the pass node any more times.
        self.assertEqual(player.root.child_N[pass_move], 1) 

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 test_make_dataset_from_sgf(self):
        with tempfile.NamedTemporaryFile() as sgf_file, \
                tempfile.NamedTemporaryFile() as record_file:
            sgf_file.write(TEST_SGF.encode('utf8'))
            sgf_file.seek(0)
            preprocessing.make_dataset_from_sgf(
                sgf_file.name, record_file.name)
            recovered_data = self.extract_data(record_file.name)
        start_pos = go.Position()
        first_move = coords.from_sgf('fd')
        next_pos = start_pos.play_move(first_move)
        second_move = coords.from_sgf('cf')
        expected_data = [
            (
                features.extract_features(start_pos),
                preprocessing._one_hot(coords.to_flat(first_move)),
                -1
            ), (
                features.extract_features(next_pos),
                preprocessing._one_hot(coords.to_flat(second_move)),
                -1
            )]
        self.assertEqualData(expected_data, recovered_data) 

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_only_check_game_end_once(self):
        # When presented with a situation where the last move was a pass,
        # and we have to decide whether to pass, it should be the first thing
        # we check, but not more than that.

        white_passed_pos = go.Position(
        ).play_move((3, 3)  # b plays
                    ).play_move((3, 4)  # w plays
                                ).play_move((4, 3)  # b plays
                                            ).pass_move()  # w passes - if B passes too, B would lose by komi.

        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game(white_passed_pos)
        # initialize the root
        player.tree_search()
        # explore a child - should be a pass move.
        player.tree_search()
        pass_move = go.N * go.N
        self.assertEqual(player.root.children[pass_move].N, 1)
        self.assertEqual(player.root.child_N[pass_move], 1)
        player.tree_search()
        # check that we didn't visit the pass node any more times.
        self.assertEqual(player.root.child_N[pass_move], 1) 

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 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_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 test_is_move_suicidal(self):
        board = load_board('''
            ...O.O...
            ....O....
            XO.....O.
            OXO...OXO
            O.XO.OX.O
            OXO...OOX
            XO.......
            ......XXO
            .....XOO.
        ''')
        position = Position(
            board=board,
            to_play=BLACK,
        )
        suicidal_moves = pc_set('E9 H5')
        nonsuicidal_moves = pc_set('B5 J1 A9')
        for move in suicidal_moves:
            assert(position.board[move] == go.EMPTY) #sanity check my coordinate input
            self.assertTrue(position.is_move_suicidal(move), str(move))
        for move in nonsuicidal_moves:
            assert(position.board[move] == go.EMPTY) #sanity check my coordinate input
            self.assertFalse(position.is_move_suicidal(move), str(move)) 

def replay_position(position):
    '''
    Wrapper for a go.Position which replays its history.
    Assumes an empty start position! (i.e. no handicap, and history must be exhaustive.)

    for position_w_context in replay_position(position):
        print(position_w_context.position)
    '''
    assert position.n == len(position.recent), "Position history is incomplete"
    metadata = GameMetadata(
        result=position.result(),
        handicap=0,
        board_size=position.board.shape[0]
    )
    go.set_board_size(metadata.board_size)

    pos = Position(komi=position.komi)
    for player_move in position.recent:
        color, next_move = player_move
        yield PositionWithContext(pos, next_move, metadata)
        pos = pos.play_move(next_move, color=color)
    # return the original position, with unknown next move
    yield PositionWithContext(pos, None, metadata) 

def test_passing(self):
    start_position = Position(
        utils_test.BOARD_SIZE,
        board=TEST_BOARD,
        n=0,
        komi=6.5,
        caps=(1, 2),
        ko=coords.from_kgs(utils_test.BOARD_SIZE, 'A1'),
        recent=tuple(),
        to_play=BLACK,
    )
    expected_position = Position(
        utils_test.BOARD_SIZE,
        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(
        utils_test.BOARD_SIZE,
        board=TEST_BOARD,
        n=0,
        komi=6.5,
        caps=(1, 2),
        ko=coords.from_kgs(utils_test.BOARD_SIZE, 'A1'),
        recent=tuple(),
        to_play=BLACK,
    )
    expected_position = Position(
        utils_test.BOARD_SIZE,
        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 test_long_game_tree_search(self):
    player = MCTSPlayerMixin(utils_test.BOARD_SIZE, DummyNet())
    endgame = go.Position(
        utils_test.BOARD_SIZE,
        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_action_flipping(self):
    np.random.seed(1)
    probs = np.array([.02] * (
        utils_test.BOARD_SIZE * utils_test.BOARD_SIZE + 1))
    probs += np.random.random(
        [utils_test.BOARD_SIZE * utils_test.BOARD_SIZE + 1]) * 0.001
    black_root = MCTSNode(
        utils_test.BOARD_SIZE, go.Position(utils_test.BOARD_SIZE))
    white_root = MCTSNode(utils_test.BOARD_SIZE, go.Position(
        utils_test.BOARD_SIZE, to_play=go.WHITE))
    black_root.select_leaf().incorporate_results(probs, 0, black_root)
    white_root.select_leaf().incorporate_results(probs, 0, white_root)
    # No matter who is to play, when we know nothing else, the priors
    # should be respected, and the same move should be picked
    black_leaf = black_root.select_leaf()
    white_leaf = white_root.select_leaf()
    self.assertEqual(black_leaf.fmove, white_leaf.fmove)
    self.assertEqualNPArray(
        black_root.child_action_score, white_root.child_action_score) 

def clear(self):
        if self.position and len(self.position.recent) > 1:
            try:
                sgf = self.to_sgf()
                with open(datetime.datetime.now().strftime("%Y-%m-%d-%H:%M.sgf"), 'w') as f:
                    f.write(sgf)
            except NotImplementedError:
                pass
            except:
                print("Error saving sgf", file=sys.stderr, flush=True)
        self.position = go.Position(komi=self.komi)
        self.initialize_game(self.position) 

def initialize_game(self, position=None):
        if position is None:
            position = go.Position()
        self.root = MCTSNode(position)
        self.result = 0
        self.result_string = None
        self.comments = []
        self.searches_pi = []
        self.qs = [] 

def test_tree_search_failsafe(self):
        # Test that the failsafe works correctly. It can trigger if the MCTS
        # repeatedly visits a finished game state.
        probs = np.array([.001] * (go.N * go.N + 1))
        probs[-1] = 1  # Make the dummy net always want to pass
        player = MCTSPlayerMixin(DummyNet(fake_priors=probs))
        pass_position = go.Position().pass_move()
        player.initialize_game(pass_position)
        player.tree_search(num_parallel=1)
        self.assertNoPendingVirtualLosses(player.root) 

def test_is_move_suicidal(self):
        board = test_utils.load_board('''
            ...O.O...
            ....O....
            XO.....O.
            OXO...OXO
            O.XO.OX.O
            OXO...OOX
            XO.......
            ......XXO
            .....XOO.
        ''')
        position = Position(
            board=board,
            to_play=BLACK,
        )
        suicidal_moves = coords_from_kgs_set('E9 H5')
        nonsuicidal_moves = coords_from_kgs_set('B5 J1 A9')
        for move in suicidal_moves:
            # sanity check my coordinate input
            assert(position.board[move] == go.EMPTY)
            self.assertTrue(position.is_move_suicidal(move), str(move))
        for move in nonsuicidal_moves:
            # sanity check my coordinate input
            assert(position.board[move] == go.EMPTY)
            self.assertFalse(position.is_move_suicidal(move), str(move)) 

def test_legal_moves(self):
        board = test_utils.load_board('''
            .O.O.XOX.
            O..OOOOOX
            ......O.O
            OO.....OX
            XO.....X.
            .O.......
            OX.....OO
            XX...OOOX
            .....O.X.
        ''')
        position = Position(board=board, to_play=BLACK)
        illegal_moves = coords_from_kgs_set('A9 E9 J9')
        legal_moves = coords_from_kgs_set('A4 G1 J1 H7') | {None}
        for move in illegal_moves:
            with self.subTest(type='illegal', move=move):
                self.assertFalse(position.is_move_legal(move))
        for move in legal_moves:
            with self.subTest(type='legal', move=move):
                self.assertTrue(position.is_move_legal(move))
        # check that the bulk legal test agrees with move-by-move illegal test.
        bulk_legality = position.all_legal_moves()
        for i, bulk_legal in enumerate(bulk_legality):
            with self.subTest(type='bulk', move=coords.from_flat(i)):
                self.assertEqual(
                    bulk_legal, position.is_move_legal(coords.from_flat(i)))

        # flip the colors and check that everything is still (il)legal
        position = Position(board=-board, to_play=WHITE)
        for move in illegal_moves:
            with self.subTest(type='illegal', move=move):
                self.assertFalse(position.is_move_legal(move))
        for move in legal_moves:
            with self.subTest(type='legal', move=move):
                self.assertTrue(position.is_move_legal(move))
        bulk_legality = position.all_legal_moves()
        for i, bulk_legal in enumerate(bulk_legality):
            with self.subTest(type='bulk', move=coords.from_flat(i)):
                self.assertEqual(
                    bulk_legal, position.is_move_legal(coords.from_flat(i))) 

def test_move_with_capture(self):
        start_board = test_utils.load_board(EMPTY_ROW * 5 + '''
            XXXX.....
            XOOX.....
            O.OX.....
            OOXX.....
        ''')
        start_position = Position(
            board=start_board,
            n=0,
            komi=6.5,
            caps=(1, 2),
            ko=None,
            recent=tuple(),
            to_play=BLACK,
        )
        expected_board = test_utils.load_board(EMPTY_ROW * 5 + '''
            XXXX.....
            X..X.....
            .X.X.....
            ..XX.....
        ''')
        expected_position = Position(
            board=expected_board,
            n=1,
            komi=6.5,
            caps=(7, 2),
            ko=None,
            recent=(PlayerMove(BLACK, coords.from_kgs('B2')),),
            to_play=WHITE,
        )
        actual_position = start_position.play_move(coords.from_kgs('B2'))
        self.assertEqualPositions(actual_position, expected_position) 

def test_is_game_over(self):
        root = go.Position()
        self.assertFalse(root.is_game_over())
        first_pass = root.play_move(None)
        self.assertFalse(first_pass.is_game_over())
        second_pass = first_pass.play_move(None)
        self.assertTrue(second_pass.is_game_over()) 

def test_replay_position(self):
        sgf_positions = list(sgf_wrapper.replay_sgf(NO_HANDICAP_SGF))
        initial = sgf_positions[0]
        self.assertEqual(initial.result, go.WHITE)

        final = sgf_positions[-1].position.play_move(
            sgf_positions[-1].next_move)

        # sanity check to ensure we're working with the right position
        final_board = test_utils.load_board('''
            .OXX.....
            O.OX.X...
            .OOX.....
            OOOOXXXXX
            XOXXOXOOO
            XOOXOO.O.
            XOXXXOOXO
            XXX.XOXXO
            X..XOO.O.
        ''')
        expected_final_position = go.Position(
            final_board,
            n=62,
            komi=6.5,
            caps=(3, 2),
            ko=None,
            recent=tuple(),
            to_play=go.BLACK
        )
        self.assertEqualPositions(expected_final_position, final)
        self.assertEqual(final.n, len(final.recent))

        replayed_positions = list(go.replay_position(final, 1))
        for sgf_pos, replay_pos in zip(sgf_positions, replayed_positions):
            self.assertEqualPositions(sgf_pos.position, replay_pos.position) 

def test_action_flipping(self):
        np.random.seed(1)
        probs = np.array([.02] * (go.N * go.N + 1))
        probs = probs + np.random.random([go.N * go.N + 1]) * 0.001
        black_root = MCTSNode(go.Position())
        white_root = MCTSNode(go.Position(to_play=go.WHITE))
        black_root.select_leaf().incorporate_results(probs, 0, black_root)
        white_root.select_leaf().incorporate_results(probs, 0, white_root)
        # No matter who is to play, when we know nothing else, the priors
        # should be respected, and the same move should be picked
        black_leaf = black_root.select_leaf()
        white_leaf = white_root.select_leaf()
        self.assertEqual(black_leaf.fmove, white_leaf.fmove)
        self.assertEqualNPArray(
            black_root.child_action_score, white_root.child_action_score) 

def test_add_child(self):
        root = MCTSNode(go.Position())
        child = root.maybe_add_child(17)
        self.assertIn(17, root.children)
        self.assertEqual(child.parent, root)
        self.assertEqual(child.fmove, 17) 

def test_add_child_idempotency(self):
        root = MCTSNode(go.Position())
        child = root.maybe_add_child(17)
        current_children = copy.copy(root.children)
        child2 = root.maybe_add_child(17)
        self.assertEqual(child, child2)
        self.assertEqual(current_children, root.children) 

def test_dont_pick_unexpanded_child(self):
        probs = np.array([0.001] * (go.N * go.N + 1))
        # make one move really likely so that tree search goes down that path twice
        # even with a virtual loss
        probs[17] = 0.999
        root = MCTSNode(go.Position())
        root.incorporate_results(probs, 0, root)
        leaf1 = root.select_leaf()
        self.assertEqual(leaf1.fmove, 17)
        leaf1.add_virtual_loss(up_to=root)
        # the second select_leaf pick should return the same thing, since the child
        # hasn't yet been sent to neural net for eval + result incorporation
        leaf2 = root.select_leaf()
        self.assertIs(leaf1, leaf2) 

def add_stones(pos, black_stones_added, white_stones_added):
    working_board = np.copy(pos.board)
    go.place_stones(working_board, go.BLACK, black_stones_added)
    go.place_stones(working_board, go.WHITE, white_stones_added)
    new_position = Position(board=working_board, n=pos.n, komi=pos.komi,
                            caps=pos.caps, ko=pos.ko, recent=pos.recent, to_play=pos.to_play)
    return new_position