How to keep bots from skewing a game's results

I'm building a game that will pair up users (1 on 1) anonymously and randomly online. I don't want users to flood the system with bots that will skew the results. As an example, if this was a fighting game, a user could make it such that it's much easier to win against one of these bots than it would to win against another real player. How would you solve this problem? Would you find a way to block bots in the first place? Or, perhaps, you'd look to make the match-ups truly random? Maybe only allowing registered users to play would help in terms of tracking points earned. I'm sure there are other options I'm not considering. How would you solve this problem?