I always viewed the expression "to beat a game" as being equivalent to "to watch a movie" or "to read a book;" in other words, a simple expression of completion. But on further examination, it's really just an extension of the meaning "beat" in sentences like "I beat Johnny (at checkers)." Johnny is the challenger (and the one who was beaten) and checkers is the challenge. When you say "I beat the game," "the game" is the challenger and the challenge. Notice that "beat" has two internal arguments: there's what I'm going to be ad-hoc calling the <challenger> argument and then there's an optional <challenge> theta role. You can just say "I beat Johnny" - it's not required to express what it was you beat him at. You also can't express the <challenge> role by itself: "*I beat at checkers." As such, when you say "I beat the game," "the game" itself is occupying the <challenger> role. This is interesting; perhaps the fact that, in video games that are 1-player, you face up against an AI, contributes to viewing the game itself as a challenger.
But what about the <challenge> role? Notice that you can't really express it with video games: *I beat Super Mario 64 at the game. That's a borderline nonsensical sentence. It seems redundant, like saying *the town mayor of Mobile. Since you cannot overtly express the <challenge> role like that, I'm suggesting that "the game" is somehow also occupying the <challenge> role. It would make sense to consider the game itself the challenge, and that's probably the more intuitive view of what a game is as opposed to considering it a challenger.
Not all games can be beat, however. It's weird to say something like "I beat Tetris."* Assuming a player who was perfect at playing the game, you could play Tetris into infinity. There isn't what I'm calling a "natural end" to the game. Now, if you were playing a version of Tetris that had some sort of a 1P mode that had 10 levels and you finished that final level, you could say something like "I beat Tetris." But notice that we had to specify a special version of Tetris - Tetris, as we normally think of it, is not "beatable." A lot of arcade games like this. As an example, I love Galaga, and I once spent an entire card of Dave & Buster's points on getting the high score at Galaga. I played for so long that the game stopped introduced new levels and started repeating old levels. Every time you got a game over, you could continue from where you left off if you put in more points. In this case, the only thing stopping you from playing was the amount of points you had. Given an infinite amount of credits, you could play Galaga forever - the game will simply continue repeating old levels. As such, you cannot beat a game like Galaga.
Compare this with Super Mario Bros. This game, no matter how good you are at it, must come to an end. Once you beat Bowser and rescue the princess, the game is over - it is in a "beaten" state. All it takes for a game to be "beatable" is for the game itself to end after you win. The winning is important - Tetris ends if you lose, but that doesn't count because "beating" requires that you win, that you complete whatever requirements the game is making of you. Causing the game to end because you fail the requirements it makes of you does not count as "beating" it anymore than losing at Super Mario Bros. counts as "beating" it.
You can't beat non-video games. "I beat Monopoly" isn't really acceptable either because the game itself can't be a challenger. You can beat someone at Monopoly, of course, but Monopoly itself can't be beaten (once again, exceptions made for a video game version of Monopoly that has some kind of a story mode with a concrete end). You can't beat "Red Light Green Light." Even in games where there is no other challenger, like Solitaire, it doesn't work: #I beat Solitaire. Playing with real cards or the Windows version makes no difference. And "I beat baseball," once again, is nonsensical.
You can win at all of these games. If you win at Monopoly, or Red Light Green Light, or Solitaire, it means that you are good at these games - you habitually win at them. "I won at Solitaire," you can say. "Winning," however, seems less restrictive than "beating." You can metaphorically extend the meaning to non-game things like "to win at cooking," despite cooking not being a game and not having rules that determine winners and losers.
You can certainly win at video games, but the context in which it is used is not the same as "beating." If you won at Super Smash Bros., it means you won some particular battle, either against an AI or another player, but it does not - and cannot - mean you beat the game. You can't "win at" a particular mode, either, although you can "beat" a mode. For example, Bayonetta has a difficulty level called 'Infinite Climax'. you can beat Infinite Climax, but if you "win at Infinite Climax," it can only mean that you're good at playing on that difficulty level, not that you finished the game on that difficulty level.
The talk of difficulty levels also notes something interesting about "beat." You can say you "beat hard mode," but you can also say you "beat the game on hard mode." You can extend this even further by having separate challengers and challenges: "I beat Anna at Ultra Game on hard mode." Is this "on X" an adjunct or an argument? It seems to me that in "I beat Anna at Smash on Hyrule Temple," on Hyrule Temple is an adjunct expressing (virtual) location. Can on hard mode be considered an adjunct expressing manner? I'm not entirely sure, and the difference between arguments and adjuncts can be pretty hard to tell sometimes.
Another neat thing: boss battles (and enemies in general) are treated the same as games. It's "I beat Zangief," not "I beat Zangief at a battle." AI opponents are also both the challenger and the challenge (compare "I beat Johnny at Street Fighter").