How do people acquire information and make decisions in an inherently complex world? We use the game Entropy Mastermind to investigate the cognitive strategies people adopt under various task conditions in situations characterized by high combinatorial complexity. N = 42 participants completed a total of 271 games, varying in incentive structure: In the speed condition, participants were incentivised for solving games quickly; in the efficiency condition, incentives were given for solutions requiring few problem solving steps; in the mixed condition, both speed and efficiency were incentivised. We found that participants adapted their problem solving strategies to the imposed constraints: In the speed condition simpler strategies were used, making feedback easy to interpret. Our results support the hypothesis that in complex environments people flexibly adjust their cognitive strategies to optimize the fit between situational requirements and their cognitive resources.