Regularity of the Space

• One key to searching in these virtual spaces is that they are somewhat regular.
• That is, one state is similar to ones nearby.
• In continuous value spaces this is essential. In discrete value spaces it allows for algorithms that are faster.
• For example if the state space has three inputs and one output, and the output is the sum of the inputs, then it is entirely regular. (It's easy to find the best result here even with continuous value states.)
• Why is navigation regular? Euclidian distance.
• Can you think of a state space that is not regular? (Lottery, chaos)
• If a state space is not regular but is discrete and finite, you can just do an exhaustive search.
• Continuous value spaces can't be searched exhaustively.
• So, what do you do about searching for good places to shoot from?
• You probably do an exhaustive coarse search using the evaluation function, then use hill-climbing around the best ones.
• You might also want to interleave this with finer grain search to find other good solutions.