We use a state-of-the-art optimization algorithm combined with a careful methodology to find optimal anti-reflective coatings. Our results show that ultra thin structures (less than $300 ,nm$ thick) outperform much thicker gradual patterns as well as traditional interferential anti-reflective coatings. These optimal designs actually combine a gradual increase of the refractive index with patterns meant to leverage interferential effects. Contrarily to gradual patterns, they do not require extremely low refractive index materials, so that they can actually be fabricated. Using a cheap and easily deployable vapor deposition technique, we fabricated a 4-layer anti-reflective coating, which proved very efficient over the whole visible spectrum despite a total thickness of only 200 nm.