ur tidus needs to b at least level 16, then ur chance of obtaining it corresponds to the level he is at. i.e if he is lv16, then there is a 16% chance it will be available to be obtained. so technically, if he's lv20 u'll need to play a max of 5 matches to get it (although this is just theoretical, chances are this won't happen!) there's not really any much more you can do except lvl up.