In Bill and Ted's Bogus Journey (not to be confused with their most Excellent Adventure), the duo are killed and sent to Hell. On their way to an eternity of punishment, Death gives them the ability to escape their fate if they can best him in a game of their choosing. The wager seems to be an obvious one to take: If you lose, you are stuck in hell for eternity; if you win, you can leave. However, if you do not play the game, then you are still stuck in Hell without the ability to leave. In a previous dialogue (not shown in the above clip), Death boasts that he has never lost a game.
If Death really never lost a game, it is reasonable to assume he has played billions of such games (assuming billions have encountered him and wanted to leave). A variety of games are likely to have been proposed including athletic competitions (perhaps the most common up until this point in history), strategic games with full information, and even gambles. Given this, Death would have to be some sort of super athlete that makes the right move every time (perfectly rational), and wins all lotteries. Even in fair lotteries, Death could only win so many coin tosses in a row before it appears the game is rigged in his favor. As an aside, it is likely that no single player would know that he has played coin tosses before and won so many in the past, but his boast out to tip players off. Thus, unfair lotteries biased in favor of the condemned are likely to still be skewed in their actual results for Death.
Given these constraints established by the movie, the question for the viewer becomes obvious: What game would you choose to play against Death?
After some pondering, the optimal game would be one of private information--where the player can control elements outside of Death's control. As such, Death's ability to win depends on his ability to guess what the player has chosen. Given this proposition, then it appears that Bill and Ted stumbled upon the right course of action in their initial choice: Battleship. In a world where you are playing the best strategy possible without cheating, the average win using a decent algorithm averages 40 moves. If we posit that Death plays perfectly strategically without knowing what the players know, then there is room for the other player to do better than Death. So, Bill and Ted knowing he would put his ship in the J row may work out as a better strategy given their glimpse into Death's psychology. Clue, again, affords them room for private information in guessing which character committed the murder of Mr. Body. Twister, on the other hand, I lack a convincing interpretation as it is clearly a game of athletics. Perhaps Gymnasts have not challenged Death before. Though, of course, I am sure the script was written with the idea of seeing an ancient mythological being playing modern games against two relatively airheaded dudes and not with a mind towards game theory.
Given this understanding of how to beat death, and while Bill and Ted succeed in finding the right path to victory, they allow too much for error. If Death can lose at games of private information, then the best strategy is to make it a game of asymmetric private information instead of a symmetric one (technically, a symmetric, asymmetric information game) like Battleship. Simply, offering Death a game of "Guess What Number I Am Thinking Of" and making the possible set of numbers contain all numbers would make Death's ability to guess the number indistinguishable from zero. The game is much less fun, but the certainty it provides makes it an optimal choice given the symmetric alternative. For this solution to be accurate, then it means that either people have never played an asymmetric information game against Death, that his strategy was superior to his opponent's in stategy previous games and could overcome the information asymmetry, or, perhaps, he was simply boasting to dissuade would-be challengers. Also, this is what happens when you leave Comedy Central on during the day while doing house chores.