Traditional shadow maps store a single depth value per cell, leading to a binary outcome by the shadow test (either lit or in shadow), and are prone to produce aliased shadow borders. We present a new approach that produces better estimates of shadow percentages and, in combination with percentage closer filtering (PCF), reduces aliasing artifacts using smaller kernel sizes. The new algorithm extends the notions of shadow maps and shadow tests to support the representation of multiple depth values per shadow map cell, as well as multi-valued shadow tests. This new approach has the potential for hardware implementation, but can also be implemented exploiting the programmable capabilities of recent graphics cards.