The video game I've restarted the most is...

*begin drum roll*

*end stupid and unnecessary drum roll*

The Legend Of Zelda: Ocarina Of Time!!
Why? Mainly, because the boss battles are AWESOME. If only it was like The Legend Of Zelda: Majora's Mask, where you could refight the bosses as many times as you wanted (also, too bad the bosses in MM weren't as good as the ones in OOT).