What data structure might this game use?
A hashtable is asymptotically optimal.  Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces).  Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space.  You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal.  Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors.  But speaking pragmatically: I expect a hashtable will be fine.  The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.