Frequency-resolved optical gating (FROG) is widely used to measure ultrashort laser pulses, also providing an excellent indication of pulse-shape instabilities by disagreement between measured and retrieved FROG traces. FROG, however, requires -- but currently lacks -- an extremely reliable pulse-retrieval algorithm. So, this work provides one. It uses a simple procedure for directly retrieving the precise pulse spectrum from the measured trace. Additionally, it implements a multi-grid scheme, also quickly yielding a vastly improved guess for the spectral phase before implementing the entire measured trace. As a result, it achieves 100% convergence for the three most common variants of FROG for pulses with time-bandwidth products as high as 100, even with traces contaminated with noise. Here we consider the polarization-gate (PG) and transient-grating (TG) variants of FROG, which measure amplified, UV, and broadly tunable pulses. Convergence occurs for all of the >20,000 simulated noisy PG/TG FROG traces considered and is also faster.