In 1986, Bates and a friend, David Wilt, who he knew because they sang in the same choir, the Alexandria Harmonizers, started the company Challenge, Inc. to explore the possibilities of creating interactive fiction games. Needing an engine for these games, Bates reached out to the "Zork" publisher, Infocom, to see about licensing their fiction engine Z-machine. Several weeks later, Infocom and Challenge had worked out a development deal, with Bates doing the design/writing, the coding being done by two contract programmers from Paragon Systems, and the publishing/marketing being done under the Infocom name. Bates envisioned a game series entitled "Immortal Legends", with his first two published game designs being the interactive fiction titles ' (1988) and ' (1989), on which he was both designer and writer. A third game about Robin Hood was never finished because Infocom was dissolved by its parent company Activision in 1989.