In complex environments, agents must be able to cooperate with previously unknown team-mates, and hence dynamically learn about other agents in the environment while searching for optimal actions. Previous works employ Monte Carlo Tree Search approaches. However, the search tree increases exponentially with the number of agents, and only scenarios with very small team sizes have been explored. Hence, in this paper we propose a history-based version of UCT Monte Carlo Tree Search, using a more compact representation than the original algorithm. We perform several experiments with a varying number of agents in the level-based foraging domain, an important testbed for ad-hoc teamwork. We achieve better overall performance than the state-of-the-art and better scalability with team size. Additionally, we contribute an open-source version of our system, making it easier for the research community to use the level-based foraging domain as a benchmark problern for ad-hoc teamwork.