Comment so just don't solve it (Score 1) 169
So in other words, you're pointing out that you could just not solve it, not come up with the optimum move each time based on expected value. Instead, you could settle for a "good enough" move and sometimes you'd get lucky. This is true.
you stated:
stochastic:
best: np-hard, not perfect, quality unknown
other: polynomial, good average
You called the first algorithm "best", acknowledging that the best (best long- term average) is NP-hard. The other can't be better than the best (by definition) , so the problem of finding the best moves remains NP-hard. Sure you could have a simpler algorithm that comes up with reasonable moves, but it'll always be beaten by the NP-hard in the long term.