You see the old game state --> new game state pattern a lot in functionally written games, but something about that has always seemed off to me. The functional retrogames series of posts (starts at http://prog21.dadgum.com/23.html ) summed up the issue well I think,
When I first mused over writing a game in a purely functional style, this had me stymied. One simple function ends up possibly changing the entire state of the world? Should that function take the whole world as input and return a brand new world as output? Why even use functional programming, then?
Judging from later parts of James Hague's series, he was working with Erlang which doesn't seem to have this feature. He also complains of lacking a good map structure — not a problem with Clojure.
It reminds me of my own (tiny) roguelike-in-clojure experiment: http://thomcc.github.com/dunjeon/
I remember having a great deal with trouble dealing with the lack of immutable cyclic data structures in Clojure, and not wanting to use an atom with atoms for the recursive parts, though there's probably more ways to make it work that I wasn't clever enough to think of :)
But what if we wanted a more ncurses type UI, with persistent indicators of the score, current location, etc, and some chrome around them? The impetus to do some kind of change-based incremental updating of the display would get strong, I would think. How is this generally handled in functional-reactive type UIs?
However, doing that wastes CPU cycles that you can use for other fun stuff in the game. In particular, monster AI will easily soak up any cycles you want to throw at it, and the more you can, the more interesting your enemies will be.
AI code can easily eat any free cycles you want to give it: you can always crank up your pathfinding distance or the number of turns your AI looks ahead.
The problem space of a roguelike is massively larger than chess and that can certainly keep a supercomputer busy.