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_normal_end(self):
        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game()
        player.tree_search()
        player.play_move(None)
        player.tree_search()
        player.play_move(None)
        self.assertTrue(player.root.is_done())
        player.set_result(player.root.position.result(), was_resign=False)

        data = list(player.extract_data())
        self.assertEqual(len(data), 2)
        position, pi, result = data[0]
        # White wins by komi
        self.assertEqual(result, go.WHITE)
        self.assertEqual(player.result_string, "W+{}".format(player.root.position.komi)) 

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_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_same_opponent_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(WHITE, coords.from_kgs('B8'))
        self.assertEqual(len(lib_tracker.groups), 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'A9')]]
        self.assertEqual(black_group.stones, coords_from_kgs_set('A9 B9 A8'))
        self.assertEqual(black_group.liberties, coords_from_kgs_set('C9 A7'))

        white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B8')]]
        self.assertEqual(white_group.stones, coords_from_kgs_set('B8'))
        self.assertEqual(white_group.liberties, coords_from_kgs_set('C8 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 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_normal_end(self):
        player = MCTSPlayerMixin(DummyNet())
        player.initialize_game()
        player.tree_search()
        player.play_move(None)
        player.tree_search()
        player.play_move(None)
        self.assertTrue(player.root.is_done())
        player.set_result(player.root.position.result(), was_resign=False)

        data = list(player.extract_data())
        self.assertEqual(len(data), 2)
        position, pi, result = data[0]
        # White wins by komi
        self.assertEqual(result, go.WHITE)
        self.assertEqual(player.result_string, "W+{}".format(player.root.position.komi)) 

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_same_opponent_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(WHITE, coords.from_kgs('B8'))
        self.assertEqual(len(lib_tracker.groups), 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'A9')]]
        self.assertEqual(black_group.stones, coords_from_kgs_set('A9 B9 A8'))
        self.assertEqual(black_group.liberties, coords_from_kgs_set('C9 A7'))

        white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
            'B8')]]
        self.assertEqual(white_group.stones, coords_from_kgs_set('B8'))
        self.assertEqual(white_group.liberties, coords_from_kgs_set('C8 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 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 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_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_same_opponent_group_neighboring_twice(self):
        board = load_board('''
            XX.......
            X........
        ''' + EMPTY_ROW * 7)

        lib_tracker = LibertyTracker.from_board(board)
        captured = lib_tracker.add_stone(WHITE, pc('B8'))
        self.assertEqual(len(lib_tracker.groups), 2)
        black_group = lib_tracker.groups[lib_tracker.group_index[pc('A9')]]
        self.assertEqual(black_group.stones, pc_set('A9 B9 A8'))
        self.assertEqual(black_group.liberties, pc_set('C9 A7'))

        white_group = lib_tracker.groups[lib_tracker.group_index[pc('B8')]]
        self.assertEqual(white_group.stones, pc_set('B8'))
        self.assertEqual(white_group.liberties, pc_set('C8 B7'))

        self.assertEqual(captured, set()) 

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 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 = [pc(coords) for coords in props.get('AB', [])]
    white_stones_added = [pc(coords) for coords 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 = pc(props.get('B', [''])[0])
        return pos.play_move(black_move, color=go.BLACK)
    elif 'W' in props:
        white_move = pc(props.get('W', [''])[0])
        return pos.play_move(white_move, color=go.WHITE)
    else:
        return pos 

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)
  if len(string) != BOARD_SIZE ** 2:
    raise ValueError("Board to load didn't have right dimensions")
  board = np.zeros([BOARD_SIZE, BOARD_SIZE], dtype=np.int8)
  for ii, char in enumerate(string):
    np.ravel(board)[ii] = reverse_map[char]
  return board 

def test_is_eyeish(self):
    board = utils_test.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(
          utils_test.BOARD_SIZE, board, be), BLACK, str(be))
    for we in W_eyes:
      self.assertEqual(go.is_eyeish(
          utils_test.BOARD_SIZE, board, we), WHITE, str(we))
    for ne in not_eyes:
      self.assertEqual(go.is_eyeish(
          utils_test.BOARD_SIZE, board, ne), None, str(ne)) 

def test_place_stone_opposite_color(self):
    board = utils_test.load_board('X........' + EMPTY_ROW * 8)
    lib_tracker = LibertyTracker.from_board(utils_test.BOARD_SIZE, board)
    lib_tracker.add_stone(WHITE, coords.from_kgs(utils_test.BOARD_SIZE, 'B9'))
    self.assertEqual(len(lib_tracker.groups), 2)
    self.assertNotEqual(
        lib_tracker.group_index[coords.from_kgs(
            utils_test.BOARD_SIZE, 'A9')], go.MISSING_GROUP_ID)
    self.assertNotEqual(
        lib_tracker.group_index[coords.from_kgs(
            utils_test.BOARD_SIZE, 'B9')], go.MISSING_GROUP_ID)
    self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs(
        utils_test.BOARD_SIZE, 'A9')], 1)
    self.assertEqual(lib_tracker.liberty_cache[coords.from_kgs(
        utils_test.BOARD_SIZE, 'B9')], 2)
    black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
        utils_test.BOARD_SIZE, 'A9')]]
    white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
        utils_test.BOARD_SIZE, '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_same_opponent_group_neighboring_twice(self):
    board = utils_test.load_board('''
      XX.......
      X........
    ''' + EMPTY_ROW * 7)

    lib_tracker = LibertyTracker.from_board(utils_test.BOARD_SIZE, board)
    captured = lib_tracker.add_stone(WHITE, coords.from_kgs(
        utils_test.BOARD_SIZE, 'B8'))
    self.assertEqual(len(lib_tracker.groups), 2)
    black_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
        utils_test.BOARD_SIZE, 'A9')]]
    self.assertEqual(black_group.stones, coords_from_kgs_set('A9 B9 A8'))
    self.assertEqual(black_group.liberties, coords_from_kgs_set('C9 A7'))

    white_group = lib_tracker.groups[lib_tracker.group_index[coords.from_kgs(
        utils_test.BOARD_SIZE, 'B8')]]
    self.assertEqual(white_group.stones, coords_from_kgs_set('B8'))
    self.assertEqual(white_group.liberties, coords_from_kgs_set('C8 B7'))

    self.assertEqual(captured, set()) 

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 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