Most of that state only has to exist on the server, which in turn doesn't really have to figure out visibility and doesn't necessarily even need textures.

The world pieces are a very specific set of permutations, which could easily be loaded in to a graphics card's memory at the start of the game. All you are really tracking are which pieces are where, and by the game's nature, there aren't that many pieces or positions they can be in...