A Story about a lonely All-Knowing Being
All-Knowing Being kidnapped you and placed you inside its home. You are well fed and have everything you need. The thing is, you can't leave and you must play a game of your choice with the Being each day to entertain it for few hours or more.
As you were about to ask it politely, if you can leave at once, it knew and answered before you even had a chance to speak: "I see, and I knew that that day would've come and will come. The day you manage to beat me at a game, will be your last day here." Then it slowly and sadly returned to its room as the night was falling.
But just before it closed the door, you asked silently: "Promise?" - It replied just a moment before closing the doors: "I would never lie to a friend."
The next morning you wanted to play rock, paper, scissors hoping you can get lucky. But the Being knew every move that you will make and had beaten you each and every single time, since it's all-knowing of course.
You had in mind to play a simple tic-tac-toe since you knew you can't lose at such a simple game. But it would always end in a draw since the Being knows how to play each such game perfectly. But you were smart, and decided to challenge it to a Connect Four since the first player can always force a win if it plays perfectly, and you have all the time in the world to practice.
The second morning, the Being had already sticked a new "fair game rule" on the game board: "If the game is played in turns, a set of rounds should be played where each player takes a role of both the first and the second player. The true winner is the one who can win as both the first and the second player. This is to ensure that the game is fair for both players"
And so you won as the first player yes, but you needed to also win as the second player and thus your plan had failed yet again.
Now as the third morning came, you thought that perhaps it should be a game of pure chance. A coin toss! But yet again, for it to be considered a "fair" game, If one tosses a coin, the other calls the heads/tails or the other way around. When you tossed the coin, it knew the outcome even before the toss so you were helpless. But if it tossed the coin it also knew exactly how to "undetectably" force a coin to land on a side it preferred. And no, it didn't conisdered this a "cheat" since even a powerful slow motion camera could not capture and prove its dirty trick.
You thought, that there isn't any hope. Since it knows everything, it can easily find a way to prevent you from winning. Even if you found a game you can easily win every time, it could know a way to undetectably and secretly make you play a wrong move and you wouldn't even realize you were distracted!
And so as one of the many mornings was rising yet again, you were already accepting your destiny to stay here forever. But you noticed the Being being sad and worried, and then it said: "I knew this day had to come. Of course I did. I had to know. I know everything."
And you stood there confused. "Is this the day I am set free? But how could it be? I haven't even thought of a specific game to play for today." But suddenly your heart started jumping wildly. "I KNOW IT. HOW COULD I HAVE BEEN SO BLIND?"
"Being!" you shouted.
"I CHALLENGE YOU TO A GAME OF..."
The puzzle question is, to come up with the game that had set you free by the end of that final day.
I have a specific solution in mind that is required to solve the puzzle, but if you have your own "thinking outside of the box" solution or a clever way to trick the Being, that would be interesting.
NOTE: (One of the ways you can "think outside of the box")
The game you propose doesn't need to be a real life game already existing somewhere. You can come up with your own game, and as long as the Being considers it "fair" (If it's fair when played between 2 random humans, there is no reason it shouldn't be fair).
NOTE: Mithrandir had a interesting possibility for a solution, but in order to "win", you can't just win by the rules of the played game. You need to "beat" the Being in the game overall. That means if multiple "wins" can be achieved, they are merely counted as points. Thus his solution does not quite fit. Also, do not omit the fact that the Being defines "the fair game", but also don't misunderstand that fact either. This note is just to make the puzzle more clear.
NOTE: Philip Schiff also had an idea, but it does not fit. If your game is a set of games and the goal is to lose most games, winning a game in the set will not be considered a win. Problem here is the definition of a win. The true "win" is acquired by satisfying the win condition of the overall game. The overall game here is the set of games itself. Same case as the win as the first player in a Connect Four as mentioned in the story. It does not count since the overall game is being defined as a set of the two or more proposed games to make it "fair".
NOTE: A game is not really a game if you are "not playing it", thus a "Pure chance game" isn't actually a game. You need to have at least some interaction to be considered a playable game. And if there is interaction, being gets a chance to "cheat".
Since the puzzle itself caused many confusions and misunderstanding, I decided to drop some hints and sleep on it (I actually mentioned this somewhere in the comments I think.):
To beat it you need to use the $2$ things you know about against it.
It can't lie to you, since you are its "friend".
It knows everything, since it is all-knowing.
Message to Viewers
You people had some nice thinking outside of the box solutions so far, and I think I wrongly tried to declare them all "not fitting" by putting up all sorts of specific constrains. You can say I was trying to "force" you to think of the specific solution that combines the both hints in a single game. I should've stayed more open minded perhaps. Anyway, a comment on the hints:
I guess anything that uses the "knowledge" and the fact that the being can't cheat by lying, thus can't "not know something" can work perfectly fine against it.
The real solution is based on that and could actually even be a really interesting game in real life among $2$ or more players.