That's a good point, entropy is only a heuristic for the thing you actually want to optimize, worst-case guesses (though it's probably a very good heuristic).

> Basically, using the entropy produces a game tree that minimises the number of steps needed in expectation

It might be even worse than that for problems of this kind in general. You're essentially using a greedy strategy: you optimize early information gain.

It's clear that this doesn't optimize the worst-case, but it might not optimize the expected number of steps either.

I don't see why it couldn't be the case that an expected-steps-optimal strategy gains less information early on, and thus produces larger sets of possible solutions, but through some quirk those larger sets are easier to separate later.