I think it totally depends on the nature of the game, and what you're trying to validate. If it's a very rules- or system-based game (like Slay the Spire) then you might start with a paper prototype to experiment with the logic before writing any code. If it's very narrative-driven (like Gone Home) then storyboards are probably a good starting point. If it's all about tight action (like Street Fighter) then you might to dig into code immediately (probably with placeholder assets) so you can experience how it feels in motion. (And of course most games involve all of these to some extent, but that doesn't mean there's not a primary motivating element.)
One thing I tried recently was mocking up screenshots of potential games. I showed them to a few friends and asked what they would conclude about the game if they saw the screenshot on Steam (you can actually imply quite a bit about mechanics and pacing with just a still image). It was a good way to get some feedback and experiment with a few different approaches without having to actually build anything.
To me the core thing is that I know I'm going to have to iterate and inevitably throw some things out, so I try make it as painless as possible to throw things out in the early stages before I'm more settled on what the game actually is.