An industry-track experience report on bin-packing heuristics, Double DQN with ARC episodic replay, and an honest CPU/GPU acceleration study — from one shared Swift 6 substrate.
We present an industry-track experience report on the design, debugging, and empirical evaluation of a pluggable Tetris artificial-intelligence (AI) workbench implemented as a portable Swift 6 package. The system unifies classical evaluation heuristics (Dellacherie, El-Tetris), multi-ply search (beam search, expectimax, Monte Carlo), an exact offline dynamic-programming solver, a family of agents derived directly from one-dimensional bin-packing strategies (First/Best/Worst/Next Fit), and a deep-reinforcement-learning agent: a Double Deep Q-Network (Double DQN) over board afterstates whose experience replay is governed by the Adaptive Replacement Cache (ARC). We report three results of practical interest. First, a single coordinate-enumeration defect in the placement-search routine silently restricted every agent to two of four rotations and roughly the left two-thirds of the playfield, capping all agents at zero cleared lines; isolating and fixing it raised a representative heuristic from 0 to 198+ cleared lines under an identical budget. Second, framing placement selection as online bin packing yields a Best-Fit agent that is competitive with state-of-the-art hand-tuned heuristics (within 0.5% of El-Tetris over 1000-piece games), while First/Worst/Next Fit reproduce the known ordering from packing theory. Third, a controlled CPU-versus-GPU study shows that for the small, branchy workloads in this domain a vectorized CPU backend (Accelerate/BLAS) dominates a Metal/MPS GPU backend at every batch size tested (up to 9× over scalar CPU, and ~2× over the GPU even at large batches), so the system defaults to CPU and exposes GPU as an opt-in throttled path.
Contributions
Five claims, one workbench
01 · §III
Modular architecture
Heuristic, search, exact-DP, bin-packing, and deep-RL agents share one protocol, one placement-search routine, one feature extractor, and one benchmark harness — with a headless mode and an ncurses terminal UI.
02 · §IV-B
Bin-packing agents
Placement selection recast as one-dimensional online packing. Best Fit rivals hand-tuned heuristics; First/Worst/Next Fit reproduce the classical packing-theory order.
03 · §IV-C
Double DQN with ARC replay
Afterstate value learning with Double Q targets. ARC governs what to keep; TD-error priority governs what to replay. Trainable by self-play or by watching a human in the TUI.
04 · §VII
Honest CPU/GPU study
A reproducible micro-benchmark over scalar CPU, Accelerate/BLAS, and Metal/MPS. Accelerate wins at every batch size; GPU is opt-in and throttled.
05 · §V
Shared-code root-cause analysis
A placement-enumeration defect masked every agent at zero lines. Fixing it restored the full action set (~11 → ~34 candidates) and 198+ lines under the same budget.
§III · System architecture
System at a glance
A unified Swift 6 substrate hosts heuristic, search, exact-DP, bin-packing, and deep-RL agents behind one protocol — making benchmarks fair and defects visible across every algorithm.
Each arrow is a build import. All agent families live in TetrisAI and share TetrisCore’s board model and placement search — so a defect in shared code affects every agent.
§IV · Agent families
One protocol, five families
Every agent implements TetrisAIAlgorithm and reasons over the same legal-move set. A placement is a (rotation, column) pair; P ≈ 34 after the enumeration fix, on a 10 × 22 well.
Heuristic
Dellacherie, El-Tetris, genetic / linear policy
Θ(P · WH)
One-ply linear evaluation over ~20 board features.
Search
Beam search, expectimax, Monte Carlo
Θ(D · B · P · WH)
Multi-ply planners sharing the same feature evaluator.
Bin packing
First, Best, Worst, and Next Fit
Θ(P · WH)
Rows as width-10 bins; contact, holes, and closed bins as fit.
Deep RL
Double DQN + ARC episodic replay
Θ(P · N)
11→48→24→1 MLP, from-scratch Adam, no external ML dependency.
Offline DP
Memoized exact solver
O(K · P · M)
Short-horizon optimality reference; Demaine et al. hardness.
Bin-packing fit
Each row is a width-10 bin. Fit is contact against blocks, walls, or the floor, plus newly created holes and completed rows. All variants prefer closing a full bin, then waste-free landings.
Best Fitmaximize contact
First Fitleftmost waste-free
Next Fitresume from last column
Worst Fitminimize contact
Double DQN + ARC
Value over afterstates, 11→48→24→1 MLP with ReLU, Adam from scratch. The next afterstate is selected with the online network and evaluated with a target network. ARC (T1/T2 plus ghost lists B1/B2) decides retention; TD-error priority decides replay.
Self-play learning curve: 0 → best of 26 lines across 12 short games (150-piece cap, average 5.2 lines/game) as ε-greedy exploration decays — confirming the pipeline, not a new line-count record.
§VI · Experimental evaluation
Gameplay benchmark
Headless run: 5 games per agent, 1000-piece cap, level 1, seed 7. Mean ± one standard deviation. One-ply and learned-weight controllers cluster near 398 lines with 100% survival. Bin Best-Fit trails El-Tetris by about 4 lines (~1%). First/Next/Worst Fit reproduce the classical packing order. Multi-ply search agents are omitted here because per-move cost makes a 1000-piece sweep impractical on a laptop without GPU batching.
Gameplay benchmark average lines, standard deviation, survival, and best score by agent
Agent
Tier
Avg. lines
± SD
Survival
Best
El-Tetris
sota
398.4
0.8
100%
399
Genetic Weights
sota
398.2
1.1
100%
399
Tactical Strategy (1-ply)
sota
398.2
1.0
100%
399
Linear Policy
sota
398.0
0.9
100%
399
Flat Stack
sota
397.8
1.3
100%
399
Lorenzen Flat
sota
397.6
1.0
100%
399
Variable Column Beam
sota
397.6
1.2
100%
399
Multi-Column Tower
sota
397.4
1.4
100%
399
Variable Column Stack
sota
397.2
1.8
100%
398
Dellacherie
classic
394.6
2.1
100%
398
Bin Best-Fit
classic
394.2
2.0
100%
398
Bin Next-Fit
classic
15.2
4.3
0%
25
Greedy Height
baseline
13.8
3.6
0%
21
Bin First-Fit
classic
10.4
2.8
0%
15
Random
baseline
0.4
0.5
0%
1
Bin Worst-Fit
classic
0.0
0.0
0%
0
§V · Shared-code defect
The bug that hid all performance
During benchmarking every agent — including strong heuristics — cleared zero lines and topped out after roughly 30 pieces. The fault was in shared placement enumeration: absolute coordinates already included the spawn offset, so pieces piled on the left; rotations 2 and 3 produced negative vertical offsets and never spawned. Agents’ internal simulations were self-consistent with the buggy world, which is why the error was invisible until measured against cleared lines.
Effect of the placement-enumeration fix on El-Tetris, seed 7
Metric
Before
After
Candidate placements / move
~11
~34
Rotations generated
2
4
Reachable columns
left ~2/3
full width
Lines cleared (500-piece cap)
0
198+
Pieces survived
~31
500 (cap)
Table: El-Tetris, seed 7, 500-piece cap. Control-versus-experiment across tiers (5 games, 1000-piece cap) shows every agent except Random jumping from zero to hundreds of lines after the fix.
§VII · CPU / GPU acceleration
Accelerate only if it actually accelerates
The only dense kernel is the value network’s batched forward pass. Three backends implement Y = ReLU?(XWᵀ + b): a scalar CPU loop, Accelerate/BLAS (cblas_sgemm), and Metal Performance Shaders. A typical Tetris decision evaluates ~34 afterstates — deep in the regime where GPU dispatch overhead dominates. The system defaults to CPU and treats GPU as an opt-in, throttled path.
Dense forward, ms/iter (in = out = 48) · log scale · lower is better
Scalar CPU Accelerate GPU (MPS)* batch 34 ≈ a typical move
At batch 34
18× vs CPU
Accelerate 0.0026 ms vs scalar 0.0469 ms. GPU is 0.5543 ms — about 210× slower than Accelerate on the real workload.
Peak speedup
9× over scalar
Accelerate wins at every batch, including 16,384, and remains ~2× faster than GPU at large batches. Auto mode micro-benchmarks once per workload shape and memoizes the winner.
§VIII · Lessons learned
Reusable engineering takeaways
01
Global symptoms implicate shared code
When every agent fails identically, suspect the common substrate — enumeration, features, simulation — before tuning any single agent.
02
Self-consistent bugs are the most dangerous
The enumerator and landing routine shared the same defect, so agents’ internal models matched the buggy world. The error was invisible until measured against cleared lines.
03
Coordinate conventions deserve tests
Height, hole, and landing-height definitions hinge on which axis points where. Encode them once and assert them.
04
Acceleration is an empirical question
Adopt a GPU only when a controlled benchmark on the real workload shows a win. For small, branchy, or low-batch kernels a vectorized CPU path is frequently faster.
05
Render defensively
In a single-buffer terminal UI, one out-of-bounds write can erase an entire frame. Clip all output to the live viewport.
Full paper
Read and download the PDF
The industry-track experience report is published here. Source code in the private repository is not distributed — only this paper is public. The artifact reproduces every table in the PDF.
S. S. Chandra, “Engineering a Pluggable Tetris AI Workbench: Bin-Packing Heuristics, Double DQN with ARC Episodic Replay, and an Honest CPU/GPU Acceleration Study,” Industry-track experience report, Sapana Micro Software, Pittsburg, KS, USA.