Is there a better way to update varibles in a loop than constantly cloning?

code review
1

Hello, I am new to Rust and so I've been practicing by creating a simple tic-tac-toe game. I implemented a simple alpha-beta pruning algorithm for the opponent's ai implemented as follows:

    fn alpha_beta(
        &self,
        player: &Player,
        depth: u32,
        alpha: &MoveScoreTurns,
        beta: &MoveScoreTurns,
    ) -> MoveScoreTurns {
        // Base case
        if depth == 0 || self.game_status != GameStatus::StillPlaying {
            return MoveScoreTurns {
                score: self.game_status,
                turns_to_win: depth,
                player_move: Point { x: 0, y: 0 },
            };
        }

        match player {
            Player::X => {
                let mut value = MoveScoreTurns::MIN;
                let mut new_alpha = alpha.clone();
                let mut new_value;
                for blank_square in &self.blank_squares_set {
                    let mut new_board = self.clone();
                    new_board.insert(blank_square, player.square_type());
                    new_value = new_board.alpha_beta(&player.other(), depth - 1, &new_alpha, beta);
                    new_value.player_move = *blank_square;
                    value = std::cmp::max(value.clone(), new_value.clone());
                    if new_value > *beta {
                        break;
                    }
                    // _new_alpha = std::cmp::max(alpha.clone(), value.clone());
                    new_alpha = std::cmp::max(value.clone(), new_alpha.clone());
                }
                value.clone()
            }
            Player::O => {
                let mut value = MoveScoreTurns::MAX;
                let mut new_beta = beta.clone();
                let mut new_value;
                for blank_square in &self.blank_squares_set {
                    let mut new_board = self.clone();
                    new_board.insert(blank_square, player.square_type());
                    new_value = new_board.alpha_beta(&player.other(), depth - 1, alpha, &new_beta);
                    new_value.player_move = *blank_square;
                    value = std::cmp::min(value.clone(), new_value.clone());
                    if new_value < *alpha {
                        break;
                    }

                    new_beta = std::cmp::min(value.clone(), new_beta.clone());
                }
                value.clone()
            }
        }
    }

While this works I feel that there should be a better way of doing this. I have two main questions.

  1. Is there a way to reduce the number of calls to .clone()?
  2. There is a lot of code duplication between the two match branches. Is there a way to reduce this?

I apologize in advance if this is a topic better suited for help rather than code review, but I figured since I am asking for assistance when it comes to refactoring rather than writing, this would be the place to go.

2

Is there a reason why MoveScoreTurns simply isn’t Copy? That would immediately let you ditch most of the clone calls.

2 Likes
3

Try to make some of your data types Copy. For example, from its use, it seems that MoveScoreTurns is a simple numerical value: if that's the case you can simply derive Copy an avoid some of the clone() calls.

Other changes may require you to change the algorithm. For example I see that you clone() the whole board inside a for. It is not a problem because given the size of the board (3x3) you get a maximum of 9 clones but if you want to avoid the clones and write more efficient code try to rewrite the algorithm in a way that does not require a clone of the board to calculate the score.

Also, you can put the common code in a separate function.

2 Likes
4

I guess there are a few reasons.

  1. I have found it helpful in learning to have to be explicit when copying items. This has helped me to better understand the concepts of borrowing, moving, lifetimes, and such.
  2. In reading the book and in my experimentation it seems that there is an emphasis on performance. I think this has given me a false idea that copying/cloning should be avoided at all costs. (How can I think about this concept in a more helpful way?)
  3. I forgot that that was a possibility :sweat_smile:
5

Remember that references are Copy. So even when you're "borrowing" things, you're still copying the reference. And thus copying can't be bad by itself.

You might be interested in the responses in this recent thread as well:

6 Likes
6

Thanks for the help! That clarifies things for me!

1 Like
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.