In the "easy" version of the hat-guessing problem, there are n prisoners (say, 100) facing forward in a line, wearing hats with colors from a set $H$ in a sequence decided by the warden. Each can only see the hats of those in front of them. The prisoners try to guess, in order, their own hat color, taking into account what they can see and all previous guesses, and each prisoner gets to go free if they guess correctly. It's well-known that for $|H| = 2$, there is a strategy so all but the first go free, which works for any finite number of colors.
In the "hard" variant, there are $\omega$ prisoners, who do not get to hear any previous guesses, but famously if choice holds they have a strategy where all but finitely many go free.
However, for a variant of the easy version of the problem, I came across the following statement:
Its interesting to notice that a larger number of hat colors poses no problem here. For any set of hat colors $H$, the prisoners can pick an abelian group structure on $H$. Then, the first prisoner guesses the ‘sum’ of all the hat colors he can see. The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color.
$H$ is not said to be finite, and the existence of a group structure (or even cancellative magma) on every non-empty set is equivalent to choice, which ordinarily wouldn't be a problem except that the article seems to imply otherwise, which raises the interesting question of whether a modified version of this statement can hold without choice. Implementing this strategy by the prisoners (I think) also only requires a cancellative magma on $H$, but I'm not sure, in either case, if only one-sided cancellative suffices. In any case, does the existence of any equally successful alternative strategy at all for all possible $H$ require choice, and how much? In $ZF+ \neg C$, given any $H$ is there a strategy so that for any sequence of $n$ hat colors from $H$, all but one guesses correctly?
Fascinatingly, the "easiest" case is when H is not merely infinite but uncountably infinite.
Namely, if H becomes uncountably infinite, the number of prisoners can scale up to countably infinite without breaking the problem at all. This is because the set of all sequences of real numbers has cardinality equal to that of the real numbers themselves, meaning that once you've assigned all (uncountably infinite) colors to real numbers, you can create a bijection from the reals to every single sequence of reals. This way, when the person in the back announces a color, everyone in front of them immediately knows their own hat color before anyone else must announce anything at all because the sequence itself was fully encoded in the color the person announced. This assertion does not rely on the axiom of choice in any way.
When H is countably infinite, this indeed becomes more of a "sum and subtract" game as indicated in the original quote in a fairly easy-to-understand way that also does not require choice (let's ignore my previous note about countably many prisoners and only focus on the finitely many prisoners presented in the actual problem).
When H is finite, you can just perform a standard modulus for the sum (that is, modulo |H|).
You seem to be imagining the axiom of choice as necessary for the warden to select hats to place in the first place, but that... simply isn't a relevant part of the problem? The interest lies in the solution, not the problem statement. The problem statement doesn't change even if the actual hats were chosen long in advance: the prisoners are merely presented with their potential hat colors in advance.