You Get What You Need

stopwatchIf I recently taught my AI to despair, then currently I’m teaching it satisfaction.

See, a planning AI is often about look-ahead. The more turns in the future it can consider, the smarter its answer is apt to be. But, of course, that takes time – exponentially increasing time, in fact. So, how far ahead can you afford to look, and still finish on a tolerable schedule?

The solution in the current Salta Champ is almost pure work-to-schedule. You set yourself a time limit, and you keep solving your problem over and over at successively greater search depth until you run out of time. Then you return the best solution you’ve found so far.

This is fine and all, but you often and up wasting a lot of your allotted time. Because the time increases exponentially with search depth, you tend to spend more time on each search than on all of the previous searches put together. On the one hand, this is why you don’t mind doing those early searches that you’ll probably just discard. On the other, you’re likely to spend a lot of your time on your final search depth – the one you never get to finish before the whistle blows. Which you are also just going to discard.

Even in the current version, you can already see a partial solution to this. Notice, the next time the AI has only a single legal move available, that it doesn’t sit and ponder. Normally, in the method I’ve described, it would spend time considered all sorts of future situations that all happen to start with that one forced move. But, as Henry II said in The Lion in Winter, there’s no sense asking if the air is good if there’s nothing else to breathe. So the AI notices the forced move, and calls time’s-up itself.

This method can be applied any time you’re able to decide that your current best solution isn’t apt to get any better. This can be hard in many cases. But pathfinding – the process of taking a single piece and driving it somewhere around obstacles – isn’t necessarily one of them. Not when your board is small, and your obstacles aren’t moving around much. It’s easy in our board to know what the shortest possible path distance is. It’s simply the Manhattan distance between your two points (in the orthogonal representation of the board, that is).

So, as soon as you find a set of moves that opens up a minimal-distance path for your target piece (since you know what the minimal possible distance is) you’re basically done. Sure, there may be other moves at the same search depth that put the pieces involved in better positions. If a piece has to move out of the way, after all, which direction should it move? So you finish out your search at that depth to resolve that. But you’re not going to find yourself a shorter path by moving any more pieces around first.

And this, my friends, is what I did last night. Turns out the game almost never needs its whole (four second) allotment of time in the late game, so it’s now blazingly fast by comparison. It’ll be in version 1.0.

Leave a Reply

Your email address will not be published.

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