The key issue is the ordering of auxiliaries in English.
(Subject) + Modal + PerfectMarker + ProgressiveMarker + PassiveMarker + (MainVerb) + (...)
An example of all the auxiliary positions being used is:
We must have been being taught English grammar.
Negatives occur after the element they are most relevant to (often the first). Since must is a modal, it occurs in the first slot. But this blocks any other modals from occurring there. Adding not runs into the conundrum of meaning you already mentioned. You could attempt to insert another expression of necessity later in the sentence, but having multiple such words often changes the semantics in odd ways. For example:
We must not have to play a game.
(Italics to indicate that most speakers would emphasize "not") It seems right at first, but this expresses that you believe (or you've come to the conclusion) that we don't have to play. This is not precisely the same thing, and the sentence is a little odd as well.
Also you are right: you cannot generally say "We don't must" as the dummy and emphatic forms of "do" cannot occur with any auxiliaries, and even if they could, they could not occur before must. (The 'lexical' do still can, but this occupies the main verb slot, as in "We must not do that.")
Thus our only real choice is to reword the sentence and lose must. Generally the most native-sounding choice is to use a periphrastic modal like "have to". (Note that periphrastic modals occur in the main verb slot, as they have not fully grammaticalized into real modals. Yet.) I think the choice the other respondents both used sounds the best:
We don't have to play a game.