Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-opus-4-20250514-thinking-16k· AnthropicHugging Face LMArena Human Preference 140K

I would like to solve the problem of optimizing the packing N unit squares in a larger…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Mistralmistral-small-3.1-24b-instruct-2503’s answer.
  1. User

    I would like to solve the problem of optimizing the packing N unit squares in a larger square of size K. For some value of N, this means we want to minimize the value of K.

    In order to simplify the problem. We can consider that eventually, we just need N sets of coordinates (x,y,theta). We can then use known formula to determine the maximum size, S, of all these squares that will allow them to fit in a square of size K. Then we know that the unit squares would fit in a square of size K/S.

    What's a way to solve this problem through self play and with neural networks?

  2. Claude Assistant

    To solve the problem of optimizing the packing of N unit squares in a larger square using self-play and neural networks, here are several effective approaches:

    Approach 1: Sequential Placement with Self-Play Competition

    Game Structure

    • Players: Two agents (or the same agent playing both sides) take turns placing squares
    • Objective: Each player tries to place their squares more efficiently than the opponent
    • Winner: The player whose complete configuration requires a smaller K value

    Implementation

    class PackingGame:
        def __init__(self, N):
            self.N = N  # Total squares to place
            self.player1_squares = []
            self.player2_squares = []
            self.current_player = 1
        
        def place_square(self, x, y, theta):
            # Add square to current player's configuration
            if self.current_player == 1:
                self.player1_squares.append((x, y, theta))
            else:
                self.player2_squares.append((x, y, theta))
            self.current_player = 3 - self.current_player
        
        def evaluate_terminal(self):
            # Calculate K/S for each player's configuration
            K1_over_S1 = compute_packing_efficiency(self.player1_squares)
            K2_over_S2 = compute_packing_efficiency(self.player2_squares)
            # Return reward: +1 if player 1 wins, -1 if player 2 wins
            return 1 if K1_over_S1 < K2_over_S2 else -1
    

    Neural Network Architecture

    • Input: Current partial configurations of both players
    • Policy Output: Distribution over (x, y, theta) for next square placement
    • Value Output: Expected winning probability from current position

    Approach 2: Iterative Refinement with Self-Play

    Game Structure

    • Start with a random or heuristic initial placement of all N squares
    • Agent makes iterative improvements by adjusting positions/orientations
    • Self-play: Current agent plays against previous versions

    Implementation

    class RefinementAgent:
        def __init__(self, N):
            self.N = N
            self.squares = [(random(), random(), random()*2*pi) for _ in range(N)]
        
        def refine_step(self, policy_network):
            # Select which square to adjust
            square_idx = policy_network.select_square(self.squares)
            # Get new position/orientation
            new_x, new_y, new_theta = policy_network.get_adjustment(self.squares, square_idx)
            # Update configuration
            self.squares[square_idx] = (new_x, new_y, new_theta)
            return self.evaluate_packing()
        
        def self_play_match(self, opponent_network):
            # Both agents start from same random initialization
            initial_config = self.squares.copy()
            
            # Each agent refines for T steps
            my_score = self.refine_for_T_steps(self.policy_network)
            opponent_score = opponent.refine_for_T_steps(opponent_network)
            
            return my_score < opponent_score  # Lower K is better
    

    Approach 3: Population-Based Training with Neural Networks

    Structure

    • Maintain a population of neural networks
    • Each network outputs all N (x, y, theta) coordinates directly
    • Networks compete in tournaments, best ones reproduce with mutations

    Implementation

    class DirectPackingNetwork(nn.Module):
        def __init__(self, N):
            super().__init__()
            self.N = N
            # Network that outputs 3N values (x, y, theta for each square)
            self.layers = nn.Sequential(
                nn.Linear(N, 512),
                nn.ReLU(),
                nn.Linear(512, 512),
                nn.ReLU(),
                nn.Linear(512, 3 * N)
            )
        
        def forward(self, square_index):
            # Input could be square index or global features
            output = self.layers(square_index)
            # Reshape to (N, 3) for N squares with (x, y, theta)
            positions = output.view(self.N, 3)
            # Apply sigmoid to x, y to keep in [0, 1]
            positions[:, :2] = torch.sigmoid(positions[:, :2])
            # Apply modulo to theta to keep in [0, 2π]
            positions[:, 2] = positions[:, 2] % (2 * np.pi)
            return positions
    
    class PopulationTraining:
        def __init__(self, population_size, N):
            self.population = [DirectPackingNetwork(N) for _ in range(population_size)]
        
        def tournament(self):
            scores = []
            for network in self.population:
                config = network(torch.arange(N))
                K_over_S = compute_packing_efficiency(config)
                scores.append(K_over_S)
            
            # Select best performers
            best_indices = np.argsort(scores)[:len(self.population)//2]
            
            # Create next generation
            next_generation = []
            for idx in best_indices:
                # Keep original
                next_generation.append(self.population[idx])
                # Create mutated version
                mutated = self.mutate_network(self.population[idx])
                next_generation.append(mutated)
            
            self.population = next_generation
    

    Approach 4: Differentiable Packing with Self-Play

    Key Idea

    Make the packing evaluation differentiable so we can use gradient-based optimization combined with self-play for exploration.

    class DifferentiablePackingLoss:
        def __init__(self, N):
            self.N = N
        
        def compute_loss(self, positions):
            # positions: (N, 3) tensor of (x, y, theta)
            
            # Overlap penalty (differentiable)
            overlap_loss = 0
            for i in range(N):
                for j in range(i+1, N):
                    overlap_loss += self.soft_overlap(positions[i], positions[j])
            
            # Bounding box size (differentiable approximation)
            corners = self.get_all_corners(positions)
            bbox_size = torch.max(corners.max(0) - corners.min(0))
            
            # Combined loss
            return bbox_size + 100 * overlap_loss
        
        def soft_overlap(self, square1, square2):
            # Differentiable approximation of overlap
            # Using smooth maximum functions
            pass
    

    Training Protocol

    1. Initialization

    • Start with random neural network weights
    • Use heuristic initialization (e.g., grid placement) as baseline

    2. Self-Play Loop

    def training_loop(iterations=1000):
        current_network = initialize_network()
        best_configs = []
        
        for epoch in range(iterations):
            # Self-play games
            games_data = []
            for _ in range(num_games):
                if epoch % 10 == 0:
                    # Play against random initialization
                    opponent = initialize_network()
                else:
                    # Play against recent version
                    opponent = previous_networks[-random.randint(1, 5)]
                
                game_result = play_game(current_network, opponent)
                games_data.append(game_result)
            
            # Update network
            train_network(current_network, games_data)
            
            # Evaluate and save best configurations
            best_config = evaluate_network(current_network)
            if is_better(best_config, best_configs):
                best_configs.append(best_config)
            
            # Keep history for self-play
            previous_networks.append(copy.deepcopy(current_network))
    

    3. Evaluation Metrics

    • Primary: Minimum K achieved for given N
    • Secondary: Computation time, consistency across runs

    Key Optimizations

    1. Symmetry Exploitation

    def augment_data_with_symmetries(config):
        # Generate 8 symmetric versions (4 rotations × 2 reflections)
        augmented = []
        for rotation in [0, 90, 180, 270]:
            for flip in [False, True]:
                new_config = apply_transformation(config, rotation, flip)
                augmented.append(new_config)
        return augmented
    

    2. Hierarchical Approach

    • First decide rough regions for groups of squares
    • Then optimize within each region
    • Finally, fine-tune globally

    3. Curriculum Learning

    • Start with small N (e.g., N=4)
    • Gradually increase N as the agent improves
    • Transfer learning from smaller to larger problems

    Example Training Configuration

    config = {
        'N': 16,  # Number of squares to pack
        'network_type': 'iterative_refinement',
        'population_size': 100,
        'self_play_games': 1000,
        'learning_rate': 0.001,
        'batch_size': 32,
        'mcts_simulations': 100,  # If using MCTS
        'refinement_steps': 50,
        'tournament_selection': 0.2,  # Top 20% survive
    }
    

    This approach combines the power of neural networks for learning good packing strategies with self-play for continuous improvement. The key is to balance exploration (trying new configurations) with exploitation (refining known good solutions).

  3. User

    I would like to solve the problem of optimizing the packing N unit squares in a larger square of size K. For some value of N, this means we want to minimize the value of K.

    In order to simplify the problem. We can consider that eventually, we just need N sets of coordinates (x,y,theta). We can then use known formula to determine the maximum size, S, of all these squares that will allow them to fit in a square of size K. Then we know that the unit squares would fit in a square of size K/S.

    As a first pass, let's create a neural network that considers the case of N=17. It takes in arbitrary inputs and outputs Nx3 parameters representing the N sets of coordinates. Then with the formula to determine the maximal expansion S, we can perform gradient descent to find the neural net that gives the largest possible S. Please construct the code that does this in a singular code block, using the Pytorch framework.

  4. Claude Assistant
    import torch
    import torch.nn as nn
    import torch.optim as optim
    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib.patches as patches
    
    class SquarePackingNetwork(nn.Module):
        def __init__(self, N=17, hidden_dim=512):
            super(SquarePackingNetwork, self).__init__()
            self.N = N
            
            # Network takes a dummy input and outputs N×3 parameters
            self.network = nn.Sequential(
                nn.Linear(1, hidden_dim),
                nn.ReLU(),
                nn.Linear(hidden_dim, hidden_dim),
                nn.ReLU(),
                nn.Linear(hidden_dim, hidden_dim),
                nn.ReLU(),
                nn.Linear(hidden_dim, N * 3)
            )
            
        def forward(self, dummy_input):
            # dummy_input is just a placeholder (e.g., torch.tensor([1.0]))
            output = self.network(dummy_input)
            
            # Reshape to (N, 3) for N squares with (x, y, theta)
            positions = output.view(self.N, 3)
            
            # Apply sigmoid to x, y to keep in [0, 1] range initially
            positions_xy = torch.sigmoid(positions[:, :2]) * 2 - 0.5  # Range [-0.5, 1.5]
            
            # Keep theta in [0, 2π]
            positions_theta = torch.sigmoid(positions[:, 2]) * 2 * np.pi
            
            return torch.cat([positions_xy, positions_theta.unsqueeze(1)], dim=1)
    
    def get_square_corners(x, y, theta, size=1.0):
        """Get the four corners of a square given center (x, y), rotation theta, and size."""
        # Half size
        h = size / 2
        
        # Corners relative to center (before rotation)
        corners = torch.tensor([
            [-h, -h],
            [h, -h],
            [h, h],
            [-h, h]
        ], dtype=x.dtype, device=x.device)
        
        # Rotation matrix
        cos_theta = torch.cos(theta)
        sin_theta = torch.sin(theta)
        
        # Apply rotation
        rotated_corners = []
        for corner in corners:
            rotated_x = cos_theta * corner[0] - sin_theta * corner[1] + x
            rotated_y = sin_theta * corner[0] + cos_theta * corner[1] + y
            rotated_corners.append(torch.stack([rotated_x, rotated_y]))
        
        return torch.stack(rotated_corners)
    
    def compute_bounding_box(positions):
        """Compute the bounding box size needed to contain all squares."""
        all_corners = []
        
        for i in range(positions.shape[0]):
            x, y, theta = positions[i]
            corners = get_square_corners(x, y, theta)
            all_corners.append(corners)
        
        all_corners = torch.cat(all_corners, dim=0)
        
        # Find min and max coordinates
        min_coords = torch.min(all_corners, dim=0)[0]
        max_coords = torch.max(all_corners, dim=0)[0]
        
        # Bounding box size (we want a square, so take the max dimension)
        bbox_size = torch.max(max_coords - min_coords)
        
        return bbox_size, min_coords, max_coords
    
    def soft_overlap_penalty(positions, temperature=10.0):
        """Compute a soft penalty for overlapping squares using a differentiable approximation."""
        N = positions.shape[0]
        overlap_loss = 0.0
        
        for i in range(N):
            for j in range(i + 1, N):
                # Get centers
                xi, yi, thetai = positions[i]
                xj, yj, thetaj = positions[j]
                
                # Compute distance between centers
                center_dist = torch.sqrt((xi - xj)**2 + (yi - yj)**2)
                
                # For unit squares, if centers are more than sqrt(2) apart, 
                # they definitely don't overlap (diagonal of unit square is sqrt(2))
                # We use a soft threshold
                min_safe_distance = 1.0  # Conservative estimate
                
                # Soft penalty: high when distance < min_safe_distance
                overlap_loss += torch.sigmoid(temperature * (min_safe_distance - center_dist))
        
        return overlap_loss
    
    def compute_loss(positions, overlap_weight=100.0):
        """Compute the loss for square packing (minimize bounding box + no overlaps)."""
        # Compute bounding box size
        bbox_size, min_coords, max_coords = compute_bounding_box(positions)
        
        # Compute overlap penalty
        overlap_penalty = soft_overlap_penalty(positions)
        
        # Combined loss: minimize bounding box size and overlaps
        loss = bbox_size + overlap_weight * overlap_penalty
        
        # Also return the effective K/S ratio (for monitoring)
        # S is the scaling factor, so K/S = bbox_size/1.0 = bbox_size
        return loss, bbox_size, overlap_penalty
    
    def visualize_packing(positions, title="Square Packing"):
        """Visualize the packed squares."""
        fig, ax = plt.subplots(1, 1, figsize=(8, 8))
        
        # Get bounding box
        with torch.no_grad():
            bbox_size, min_coords, max_coords = compute_bounding_box(positions)
        
        # Plot each square
        for i in range(positions.shape[0]):
            x, y, theta = positions[i].detach().cpu().numpy()
            
            # Create a square patch
            square = patches.Rectangle((-0.5, -0.5), 1, 1, 
                                       fill=True, 
                                       facecolor=plt.cm.tab20(i % 20),
                                       edgecolor='black',
                                       linewidth=1,
                                       alpha=0.7)
            
            # Add rotation and translation
            t = patches.transforms.Affine2D().rotate(theta).translate(x, y) + ax.transData
            square.set_transform(t)
            
            ax.add_patch(square)
            
            # Add square number at center
            ax.text(x, y, str(i), ha='center', va='center', fontsize=8)
        
        # Set axis limits
        margin = 0.1
        ax.set_xlim(min_coords[0].item() - margin, max_coords[0].item() + margin)
        ax.set_ylim(min_coords[1].item() - margin, max_coords[1].item() + margin)
        ax.set_aspect('equal')
        ax.grid(True, alpha=0.3)
        ax.set_title(f"{title}\nBounding Box Size: {bbox_size.item():.4f}")
        
        plt.tight_layout()
        return fig
    
    # Training code
    def train_packing_network(N=17, epochs=2000, lr=0.01, overlap_weight=100.0):
        # Initialize network
        network = SquarePackingNetwork(N=N)
        
        # Optimizer
        optimizer = optim.Adam(network.parameters(), lr=lr)
        
        # Dummy input
        dummy_input = torch.tensor([1.0])
        
        # Training history
        history = {
            'loss': [],
            'bbox_size': [],
            'overlap_penalty': []
        }
        
        # Best configuration tracking
        best_bbox_size = float('inf')
        best_positions = None
        
        for epoch in range(epochs):
            # Forward pass
            positions = network(dummy_input)
            
            # Compute loss
            loss, bbox_size, overlap_penalty = compute_loss(positions, overlap_weight)
            
            # Backward pass
            optimizer.zero_grad()
            loss.backward()
            optimizer.step()
            
            # Record history
            history['loss'].append(loss.item())
            history['bbox_size'].append(bbox_size.item())
            history['overlap_penalty'].append(overlap_penalty.item())
            
            # Track best configuration
            if bbox_size.item() < best_bbox_size and overlap_penalty.item() < 0.01:
                best_bbox_size = bbox_size.item()
                best_positions = positions.detach().clone()
            
            # Print progress
            if epoch % 100 == 0:
                print(f"Epoch {epoch:4d}: Loss={loss.item():.4f}, "
                      f"BBox={bbox_size.item():.4f}, "
                      f"Overlap={overlap_penalty.item():.4f}")
            
            # Adjust overlap weight dynamically
            if epoch % 500 == 0 and epoch > 0:
                if overlap_penalty.item() > 0.01:
                    overlap_weight *= 1.5
                    print(f"Increased overlap weight to {overlap_weight}")
        
        # Visualize final result
        with torch.no_grad():
            final_positions = network(dummy_input)
            fig = visualize_packing(final_positions, "Final Packing (N=17)")
            plt.show()
            
            if best_positions is not None:
                fig = visualize_packing(best_positions, "Best Packing (N=17)")
                plt.show()
        
        # Plot training history
        fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(10, 8))
        
        ax1.plot(history['loss'])
        ax1.set_ylabel('Total Loss')
        ax1.set_title('Training History')
        ax1.grid(True)
        
        ax2.plot(history['bbox_size'])
        ax2.set_ylabel('Bounding Box Size')
        ax2.grid(True)
        
        ax3.plot(history['overlap_penalty'])
        ax3.set_ylabel('Overlap Penalty')
        ax3.set_xlabel('Epoch')
        ax3.grid(True)
        ax3.set_yscale('log')
        
        plt.tight_layout()
        plt.show()
        
        return network, history, best_positions
    
    # Run the training
    if __name__ == "__main__":
        # Set random seed for reproducibility
        torch.manual_seed(42)
        np.random.seed(42)
        
        # Train the network
        network, history, best_positions = train_packing_network(
            N=17, 
            epochs=2000, 
            lr=0.01,
            overlap_weight=100.0
        )
        
        # Print final results
        print("\nFinal Results:")
        print(f"Best bounding box size achieved: {min(history['bbox_size']):.4f}")
        print(f"This means 17 unit squares can fit in a square of size {min(history['bbox_size']):.4f}")
    

    This code implements a neural network approach to optimize the packing of N=17 unit squares. The key components are:

    1. SquarePackingNetwork: A neural network that takes a dummy input and outputs 17×3 parameters (x, y, theta) for each square.

    2. get_square_corners: Computes the four corners of a rotated square given its center and orientation.

    3. compute_bounding_box: Calculates the minimum square size needed to contain all packed squares.

    4. soft_overlap_penalty: A differentiable penalty function that increases when squares overlap.

    5. compute_loss: Combines the bounding box size (which we want to minimize) with the overlap penalty.

    6. visualize_packing: Creates a visual representation of the packed squares.

    7. train_packing_network: The main training loop that optimizes the network parameters using gradient descent.

    The network learns to output configurations that minimize the bounding box size while avoiding overlaps. The overlap penalty is crucial to ensure valid packings, and its weight can be adjusted dynamically during training.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.