Values don’t change as they should because of recursion depth

I am making checkers. I encountered quite a big problem. The code below describes cells king can move on. 1 cell is 100×100. He starts from (550, 50). This picture describes current_battlefield:

And this dict describes what moves AI will take

king_attack_moves = {
  (350, 650): [
    (550, 450), 
    (650, 350)
  ], 
  (150, 450): [
    (350, 650)
  ], 
  (550, 50): [
    (150, 450), 
    (50, 550)
  ], 
  (50, 550): [
    (250, 750)
  ]
}

The king is a purple checker and he has to eat right now. So, about the actual problem. If you look carefully to the king_attack_moves you will get that code doesn’t find a way from cell with center at (250,750) to cells (550,450) and (650,350).

I got that the problem is enemy_positions. It doesn’t clear itself after each branch. But it doesn’t have to, because later I will use it, so it shold not be corrupted. This is the reason why I made temp_enemy_pos. But I stuck with it now.

I have been working for 1.5 days already and I still can’t understand the reason why temp_enemy_pos doesn’t go back to initial value, while it should be because of different recursion depths. So, what temp_enemy_pos actually should be

[(250, 350)]
[(250, 350), (250, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(450, 550), (150, 650)]
[(450, 550), (150, 650)]
[(450, 550), (150, 650)]

and what it is

[(250, 350)]
[(250, 350), (250, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550)]
[(250, 350), (250, 550), (450, 550), (150, 650)]
[(250, 350), (250, 550), (450, 550), (150, 650)]
[(250, 350), (250, 550), (450, 550), (150, 650)]

I am sorry for all these troubles. Unfortunately, I’m a newbie so I cannot express it shorter. I hope, that at least I was able to make this understandable

Code:

def king_choose_attack(previous_cell_cord, enemy_checkers_keys, our_checkers_keys, cell_const, enemy_positions, temp_enemy_pos,
                       go_right_up=True,
                       go_left_down=True, go_right_down=True):
    king_attack_moves = {}
    cut_array = []
    if go_right_up:
        i = 1
        was_enemy_on_way_right_up = False
        # while current cell exist
        while (previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n) in black_cells_keys:
            # if current cell has enemy checker
            if (previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n) in enemy_checkers_keys and (
                    previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n) not in enemy_positions:
                # if next cell exist and empty
                if (previous_cell_cord[0] + (i + 1) * n, previous_cell_cord[1] - (i + 1) * n) in black_cells_keys and (
                        previous_cell_cord[0] + (i + 1) * n,
                        previous_cell_cord[1] - (i + 1) * n) not in enemy_checkers_keys and (
                        previous_cell_cord[0] + (i + 1) * n,
                        previous_cell_cord[1] - (i + 1) * n) not in our_checkers_keys:
                    enemy_positions.append((previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n))
                    temp_enemy_pos += [(previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n)]
                    was_enemy_on_way_right_up = True

                # if next cell doesn't exist or not empty
                else:
                    break

            elif (previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n) in our_checkers_keys:
                break

            # if checker already had been eaten and current cell is empty
            elif was_enemy_on_way_right_up and (
                    previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n) not in our_checkers_keys:
                cut_array.append((previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n))

                # get info related to new branch
                print(temp_enemy_pos)
                p_enemy_positions, p_king_attack_moves = king_choose_attack(
                    (previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n),
                    enemy_checkers_keys, our_checkers_keys,
                    (previous_cell_cord[0] + i * n, previous_cell_cord[1] - i * n), enemy_positions, temp_enemy_pos,
                    go_right_up=False,
                    go_left_down=False)
                king_attack_moves.update(p_king_attack_moves)
                enemy_positions = p_enemy_positions
                print(temp_enemy_pos)
                # если можно сходить
                king_attack_moves[cell_const] = cut_array
            i += 1

    if go_right_down:
        i = 1
        was_enemy_on_way_right_down = False

        # while current cell exist
        while (previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n) in black_cells_keys:
            # if current cell has enemy checker
            if (previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n) in enemy_checkers_keys and (
                    previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n) not in enemy_positions:
                # if next cell exist and empty
                if (previous_cell_cord[0] + (i + 1) * n, previous_cell_cord[1] + (i + 1) * n) in black_cells_keys and (
                        previous_cell_cord[0] + (i + 1) * n,
                        previous_cell_cord[1] + (i + 1) * n) not in enemy_checkers_keys and (
                        previous_cell_cord[0] + (i + 1) * n,
                        previous_cell_cord[1] + (i + 1) * n) not in our_checkers_keys:
                    enemy_positions.append((previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n))
                    temp_enemy_pos += [(previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n)]
                    was_enemy_on_way_right_down = True


               # if next cell doesn't exist or not empty
                else:
                    break

            elif (previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n) in our_checkers_keys:
                break

            # if checker already had been eaten and current cell is empty
            elif was_enemy_on_way_right_down and (
                    previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n) not in our_checkers_keys:
                cut_array.append((previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n))

                # get info related to new branch
                print(temp_enemy_pos)
                p_enemy_positions, p_king_attack_moves = king_choose_attack(
                    (previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n),
                    enemy_checkers_keys, our_checkers_keys,
                    (previous_cell_cord[0] + i * n, previous_cell_cord[1] + i * n), enemy_positions, temp_enemy_pos,
                    go_right_down=False)
                king_attack_moves.update(p_king_attack_moves)
                enemy_positions = p_enemy_positions
                print(temp_enemy_pos)

                king_attack_moves[cell_const] = cut_array
            i += 1
    if go_left_down:
        i = 1
        was_enemy_on_way_left_down = False
        # while current cell exist
        while (previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n) in black_cells_keys:

            # if current cell has enemy checker
            if (previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n) in enemy_checkers_keys and (
                    previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n) not in enemy_positions:
                # if next cell exist or empty
                if (previous_cell_cord[0] - (i + 1) * n, previous_cell_cord[1] + (i + 1) * n) in black_cells_keys and 
                        (previous_cell_cord[0] - (i + 1) * n,
                         previous_cell_cord[1] + (i + 1) * n) not in enemy_checkers_keys and 
                        (previous_cell_cord[0] - (i + 1) * n,
                         previous_cell_cord[1] + (i + 1) * n) not in our_checkers_keys:
                    enemy_positions.append((previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n))
                    temp_enemy_pos += [(previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n)]
                    was_enemy_on_way_left_down = True

                # if next cell doesn't exist or not empty
                else:
                    break

            # if current cell has our checker
            elif (previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n) in our_checkers_keys:
                break

            # if checker already had been eaten and current cell is empty
            elif was_enemy_on_way_left_down and (
                    previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n) not in our_checkers_keys:
                cut_array.append((previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n))
                print('temp_enemy_pos', temp_enemy_pos)
                # get info related to new branch
                p_enemy_positions, p_king_attack_moves = king_choose_attack(
                    (previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n),
                    enemy_checkers_keys, our_checkers_keys,
                    (previous_cell_cord[0] - i * n, previous_cell_cord[1] + i * n), enemy_positions, temp_enemy_pos,
                    go_right_up=False,
                    go_left_down=False)
                print(temp_enemy_pos)
                king_attack_moves.update(p_king_attack_moves)
                enemy_positions = p_enemy_positions
                king_attack_moves[cell_const] = cut_array
            i += 1
    return enemy_positions, king_attack_moves
n = 100
previous_cell_cord = (550, 50)
white_checkers_keys = [(650.0, 550.0), (150.0, 650.0), (750.0, 650.0), (50.0, 750.0), (450.0, 750.0), (650.0, 750.0),
                       (350, 450), (250, 350), (250, 550), (450, 550)]
black_checkers_keys = [(150.0, 50.0), (350.0, 50.0), (750.0, 50.0), (50.0, 150.0), (250.0, 150.0), (650.0, 150.0),
                       (150.0, 250.0), (550.0, 250.0), (750.0, 250.0), (550, 50)]
black_cells_keys = [(150.0, 50.0), (350.0, 50.0), (550.0, 50.0), (750.0, 50.0), (50.0, 150.0), (250.0, 150.0),
                    (450.0, 150.0), (650.0, 150.0), (150.0, 250.0), (350.0, 250.0), (550.0, 250.0), (750.0, 250.0),
                    (50.0, 350.0), (250.0, 350.0), (450.0, 350.0), (650.0, 350.0), (150.0, 450.0), (350.0, 450.0),
                    (550.0, 450.0), (750.0, 450.0), (50.0, 550.0), (250.0, 550.0), (450.0, 550.0), (650.0, 550.0),
                    (150.0, 650.0), (350.0, 650.0), (550.0, 650.0), (750.0, 650.0), (50.0, 750.0), (250.0, 750.0),
                    (450.0, 750.0), (650.0, 750.0)]
white_positions, king_attack_moves = king_choose_attack(
    previous_cell_cord,
    white_checkers_keys,
    black_checkers_keys, previous_cell_cord, [], [])

Answer

This is a classic kind of bug. The problem is that you pass enemy_positions. Which means that the object is shared between the recursive call and the previous. So what happens in the recursive call is seen in the parent.

You either need to .copy() it, or else you need to manually fix it back to being the previous on the way out of the call. Of the two, .copy() is much more expensive but also simpler and more reliable.