I would like to solve the problem of optimizing the packing N unit squares in a larger…
- 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?
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 -1Neural 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 betterApproach 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_generationApproach 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 passTraining 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 augmented2. 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).
- 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.
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:
-
SquarePackingNetwork: A neural network that takes a dummy input and outputs 17×3 parameters (x, y, theta) for each square.
-
get_square_corners: Computes the four corners of a rotated square given its center and orientation.
-
compute_bounding_box: Calculates the minimum square size needed to contain all packed squares.
-
soft_overlap_penalty: A differentiable penalty function that increases when squares overlap.
-
compute_loss: Combines the bounding box size (which we want to minimize) with the overlap penalty.
-
visualize_packing: Creates a visual representation of the packed squares.
-
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.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.