Higher octane fuel shouldn't give you any more power; it just prevents pre-ignition. If your engine is very high compression and needs high octane fuels, then usually something like an anti-knock sensor is going to be present to cut engine performance--retard timing, I think?--if you have the wrong fuel in your car.

OTOH, a less energy-dense fuel like pure alcohol can increase power because you can increase compression in the engine even more than you could with high grade gasoline. That means that you can get more benefit from turbo- or super-charging.

IIRC, most fuel injected cars can now make some kind of adjustment to the fuel:air mix if you're at high altitude so that it shouldn't be an issue (unless you're at altitudes outside of their range of adjustment). Carbureted engines can not do that.