Mission Impossible

One of the basic realities of life is that if something is easy, it's already been done. In the grand scheme of things, all unsolved problems are hard problems. While that might not have been true 300 years ago, the advancements of widespread education and information technology have made it easy to find potentially talented individuals and make sure everyone knows about their work. The result of that for almost every technological problem you can think of, either someone has solved it already or it's very difficult.

So what do you do when you need to do something that hasn't been done before and it turns out the problem is very hard? How do you break an impossible problem into something solvable? While there's no right or wrong way to go about this, there are three basic approaches you can use. Assume that the objective of a perfect solution is either practically or literally impossible, and you just want the best solution that's actually feasible.

#1: Improve on an existing base

The concept here is to focus on the small, incremental progress you can achieve rather than the large, difficult end objective. This is the approach I took when solving the general high level goal selection in BrainWorks. Bots must constantly decide what they are most interested in doing. Should they track down a target or look for more players? In capture the flag, should they defend their flag or get the opponent's? I confess I've added nothing revolutionary to this logic, and the correct choice is something even experienced human players have trouble making. Instead I just added a few pieces of additional logic to help the bots decide. BrainWorks bots will consider tracking down a target it's recently heard but not seen, for example. It's not algorithmically amazing but it's progress and that's what matters.

#2: Break the problem into pieces and only do some of them

I used this approach when designing the item pickup code. Roughly stated, the implemented algorithm is to estimate how many points the bot would get if it were to pick up different items and it selects the item that gives the most points. While the item selection is reasonably good, there's a lot of corners cut for the purpose of reducing complexity. How valuable is a personal teleporter anyway? BrainWorks just values it at 0.6 points and calls it a day, but clearly such an item is far more useful in some situations than others. And the estimations of where enemies are likely to be are based on proximity to items, not on actual geographic locations (like being in a specific room or a hallway). The estimates aren't remotely perfect, but they are still good enough for the purpose they serve: a rough estimate of what item the bot should pick up next. Designing this code wasn't even possible without ignoring all the truly hard parts of item pickup.

#3: Accept defeat and deal with the consequences

This is essentially The Attitude of the Knife. Sometimes things just don't work out and can't be fixed, and all you can do is accept that reality and handle the consequences as best you can. This was the approach I took for the navigation code in BrainWorks. As I've mentioned before, the navigation tables have huge issues on anything other than a flat, two dimensional map. While I'd love to solve this problem and I'm certain I could do it, I just didn't have enough time to tackle it. There were a few clearly bad navigation decisions (such as jumping between ledges) that I wrote code to manually fix, but those were essentially stopgap measures.

While it's not ideal, there's nothing wrong with accepting defeat against hard problems. After all, you aren't the only person in the world who couldn't solve the problem.