Solution 1.
As you’ve already mentioned, you can use terms, but – it will cause some redundancy, because for every post you’ll have to create a term. And you’ll have to maintain this post-term connection later on.
Solution 2.
On the other hand, you can use Custom Fields. So for every Guide and Tutorial you can add Custom Field like “related_game_id” and store the ID of related game in that field.
You can use Advanced Custom Fields and its Relation field to make some nicer interface for editing these relations.
Solution 3.
But there is one more way of achieving this. You can remove CPT Game and add Custom Taxonomy Game.
Then you can add this taxonomy to Guides, Tutorials, and all other post types and use description of a term to edit Game info.