Satisfaction Part 2

As I mentioned yesterday, one of the weaknesses of a work-to-schedule AI approach, with an exponentially growing search space, is that you can easily spend most of your time on an analysis that never ends up getting used. After all, if at each search depth you take more time than all of the previous depths put together, there’s no point starting a search in the whole second half of your allotted time.

It’s possible to make an even stronger statement if you know roughly how quickly your search time is increasing. Suppose T is the time needed to finish the final search, and each search takes r times as long as the one before. Then, the total time for all of them is:

Geometric series

… which, as you have surely not forgotten since taking precalculus, is our old friend the geometric series, and totals to about T(r/r-1). So, the final search takes up roughly a fraction of r-1/r of the total time.

For example, for the final search to take up the second half of the allotted time (as suggested above), your search time only has to be growing by a puny factor of 2. With more realistic growth factors, it just gets worse, and my limited tests suggest that a pretty reasonable factor (basically, the typical number of legal moves available among board positions at the end of the search tree) is something like 12 or 15.

Believe it or not, then, if we’re allowing the Salta AI, say, 6 seconds to think of the best answer it can, there’s probably no point in starting any deeper analyses after the first 0.5 seconds or so. At that point, it’s probably already started the greatest search depth it’s ever going to finish, and it may not even finish the one it’s already working on. So you might as well finish up what you’re doing and hand in your test, so to speak.

This optimization will also be in version 1.0. Watch the little progress meter, and you’ll sometimes see it go quickly from partly full to finished, even in situations that don’t allow it to know that it has a truly optimal solution. What’s happening is that it knows, even if its current plan isn’t perfect, that it doesn’t have time to think about it any harder and actually finish.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.