Displaying an ad at the beginning (of the game / level / challenge) will only irritate the player*.
The player wants to play your game, not click some stupid ad.
I would always place the ad at the end of a challenge. Let's think about it in terms of psychology.
The player clears the level:
WHOOHOOO!!! YOU'RE THE BEST!!! AMAZING!!
You are sooo AWESOME you even got a sponsorship!!
** Your victory is sponsored by: $advertisement$ **
The player fails to clear the level:
BAH!!! YOU SUCK!!!
** As a punishment, you'll have to watch this ad: $advertisement$ **
So in my view, the ad should function as either a punishment or a reward.
*For me, as a user, that would be an "uninstall flag"!