index doesn't work properly
I am not a MySQL expert (or even a user!) but the ideal index for your query appears to be as shown below:

create table `single` (
  `game_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` mediumint(9) NOT NULL,
  `stage` tinyint(4) NOT NULL,
  `highscore` bigint(20) unsigned NOT NULL,
  `played_date` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`game_id`),
  KEY `user_id_stage` (`stage`,`user_id`, `highscore`)
)


The plan I get is:



See the SQLfiddle