I hope you're not actually playing physically.
You're much better off using a program like YGOpro or DEVpro. All the cards ever, impossible to cheat (thanks to a fully automated system), and regular updates regarding new cards and banlists. Not to mention you're always able to find someone to play with and can do so from anywhere with an internet connection. Includes a handy AI mode too for testing decks.
There's also complete control over the UI (GUI? How shit looks, basically). Change any and all textures (you could even change every single card texture to Dio's screaming visage if you felt like it) as well as all sound files in the game (including songs and SFX).
It's the fun without the hassle/ paying $80 for Frog the Jam.
Other than that, I enjoy playing it with friends. Nothing can quite compete to getting out a dozen and one Gem-Knights out in a single wombo-combo. I've also seen some crazy shit done with Fables.
Regarding a CYOA game, eh, don't think it's a good idea. YGO is stupidly complex, and to make duel decisions one would have to know the rules before hand. I don't think many do on this site, and trying to teach someone that MST doesn't negate and what spell speed is would just take up so much time that it's not worth the effort. Although a story revolving around cards sounds interesting... maybe something akin to Hand of Fate?