Over the last two decades, crystal structure prediction methods based on first-principles calculations have reached full maturity, and became an invaluable instrument to determine the properties of materials in conditions that are hard to measure. In particular, at the extreme pressures found in planetary cores, the usual rules of chemistry break down in ways that defy the intuition built at ambient conditions. In this talk, I will first discuss how this forbidden chemistry can be understood at a fundamental level, and how crystal structure prediction can enable us to do genuine predictions in spite of a lack of intuition. I will then illustrate a few examples from my original research work in which structure prediction was instrumental: the formation of the densest hydrogen clathrate hydrate, and the synthesis of high-temperature conventional superconductors.