Yea, I noticed his only tag was "nyancat" on that particular video lol.
My idea of relevance is if I search for something (game + part one), I would expect at the very least the first page to only be just part one videos of whatever game I was searching for. You're right about Pewdiepie's part one being the top result, and that's fine and all considering the search was for part one videos on a specific game, I just didn't know that watch time also played a huge factor in what YouTube considers "relevant" to a search.
Another thing I noticed is that a few gamers out there (maybe literally just a few, or a lot, I didn't search too far into it since I was tired) tend to leave the tags from a part one video in the other parts that follow. For example, one guy's walkthrough of a game had X number of videos, and regardless of which video I was watching on his channel on that particular game, all the tags where still the same, so part eight would have the part one tag still in it, and no tag for part eight. Is that something that's frowned upon, or should I just use all the best tags I can for my part one videos and never change them throughout the X amount of videos it takes me to finish a walkthrough?