The infinite hat problem is a great puzzle. If you have a strong math background, you should try solving it before reading my solution below!

Here’s my strategy for the wizards: first, they agree on an ordering of themselves. Each wizard can be indexed by a natural number, since there are countably many of them. They then consider the set of all possible hat configurations $S$ with respect to that ordering. By the well-ordering theorem (which is equivalent to the axiom of choice) a well-ordering of $S$ exists; the wizards also agree on a specific well-ordering.

Note that this step is non-constructive because it relies on the axiom of choice. That is, such a well-ordering exists but there may not be a way to explicitly construct it. The point of the note about assuming the axiom of choice was a tip-off that the wizards need to make their decision based off of a set whose existence is only ensured by the axiom of choice.

Once the well-ordering has been chosen the wizards are ready to receive their hats. Once they are able to see everyone else’s hat, they each construct a subset $T$ of $S$ which contains the hat configurations which differ from the configuration they can see in only finitely many hats. The lack of knowledge about a wizard’s own hat is irrelevant to this construction, since that lack of knowledge only changes the configuration they see in finitely many hats. In particular, for every wizard their subset $T$ will consist of the true configuration along with all configurations which differ from the true configuration in finitely many hats, and therefore be the same for all wizards.

Now that all the wizards have constructed the same $T\subset S$, they use the well-ordering of $S$ to find the least element of $T$, and everyone guesses the hat colour which they have in the least element. Since every element of $T$ differs from the true configuration in finitely many hats, the configuration that the wizards guess will also differ in finitely many hats. Thus almost all wizards will choose correctly.

I heard about the problem on a list of good logic puzzles compiled by Philip Thomas. I purposely haven’t read his solution yet, since I didn’t want that to influence me while writing down my solution.