1 - 1 / 2^k

There is a simple and elegant proof for the upper bound, i.e. it's impossible to come up with a strategy with winning probability > 1 - 1 / 2^k.