I am a heavy user of the Axiom of Choice and I am comfortable with the consequences of it. My take on this riddle is that it is not about the Axiom of Choice (nor probability), but about impracticability of the proposed strategy. (Thus my cognitive dissonance is resolved.)

Imagine how possibly anybody could make paper instructions out of this strategy or how possibly anybody could perform this strategy in a finite time. In the real world, any single action takes a positive time. Even a mathematician can perform at most countably many actions in a finite time. However, the proposed strategy is uncountable and hence not practicable in a finite time.  (I believe that one can really prove that there is no practicable (=countable) strategy to answer this riddle.) No wonder one can foresee the future if they has the ability of doing what cannot be done in a finite time.

I am a heavy user of the Axiom of Choice and I am comfortable with the consequences of it. My take on this riddle is that there is no problem with the proposed strategy as Mathematics, but it is unrealistic because it is impossible to implement it in reality, as I argue below. Axiomatic Mathematics is all about (non-)existence of sets with such and such properties and the way of implementing it is not a part of it. More precisely, the trick of this thought experiment is not in the Axiom of Choice nor in the way probability is used, but in covertly assuming an ability to do the impracticable. Thus the riddle is not as counter-intuitive (to me) as it may appear.

Imagine how possibly anybody could make paper instructions out of this strategy or how possibly anybody could perform this strategy in a finite time. In the real world, any single action takes a positive time. Even a mathematician can perform at most countably many actions in a finite time. However, the proposed strategy requires uncountably many actions and hence not practicable in a finite time.  (I believe that one can actually prove that there is no practicable (=countable) strategy to solve this riddle.) It is not a big surprise that one can foresee the unseeable if they has the ability of doing what cannot be done in a finite time.

By the way, the Axiom of Choice has real applications to our daily life. For example, countable additivity of the Lebesgue measure is used almost everywhere in differential equations. It may be possible but will be unnecessarily painful to develop a theory for continuous objects without the Axiom of Choice.