Recent developments in the field of model-based RL have proven successful in a range of environments, especially ones where planning is essential. However, such successes have been limited to deterministic fully-observed environments. We present a new approach that handles stochastic and partially-observable environments. Our key insight is to use discrete autoencoders to capture the multiple possible effects of an action in a stochastic environment. We use a stochastic variant of Monte Carlo tree search to plan over both the agent's actions and the discrete latent variables representing the environment's response. Our approach significantly outperforms an offline version of MuZero on a stochastic interpretation of chess where the opponent is considered part of the environment. We also apply our method on DeepMind Lab, a complex first-person 3D environment with partial observability. We show that the model generates consistent and high-fidelity rollouts over a large number of timesteps without error accumulation artifacts, outperforming state-of-the-art variational autoencoder-based models.