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?