This paper presents a novel class of information-theoretic strategies for solving the game of Mastermind, achieving state-of-the-art performance among known heuristic methods. The core contribution is the application of a weighted entropy heuristic, based on the Belis-Guias, u framework, which assigns context-dependent utility values to each of the possible feedback types. A genetic algorithm optimization approach discovers interpretable weight patterns that reflect strategic game dynamics. First, I demonstrate that a single, fixed vector of optimized weights achieves a remarkable 4.3565 average guesses with a maximum of 5. Building upon this, I introduce a stage-weighted heuristic with distinct utility vectors for each turn, achieving 4.3488 average guesses with a maximum of 6, approaching the theoretical optimum of 4.3403 by less than 0.2%. The method retains the computational efficiency of classical one-step-ahead heuristics while significantly improving performance through principled information valuation. A complete implementation and all optimized parameters are provided for full reproducibility.