Most problems can be described in terms of making a series of choices. For example, sorting involves a series of choices about how to move items around. Ideally, you know in advance what the right choice is. If you're buying a car, you start by doing research and then choose the car based on your research:
information → decision
Unfortunately, many problems, such as finding one's way in a maze, involve delayed feedback. You first make the decision and then find out later if it was the right decision. The order is reversed:
decision → information
In the absence of advance information, we're left with exploration. We try things, back up, and try other things until we find something that works:
decision → information → decision → information → ...
Keeping track of what we have and haven't tried, avoiding trying things we don't need to try, and choosing the best next thing to try is a lot of work. Programming it can be error-prone. A large chunk of a typical undergraduate AI course is devoted to managing that bookkeeping.1
Clairvoyance
Programming would be easier if your computer was a Jedi. You'd tell it the options available, and the force would whisper in its ear which option to choose. In computer science, this is known as nondeterministic choice and is a useful/good thing. However, many other things in CS are also referred to as nondeterminism, and all of those are bad. Moreover, the name fails to communicate its value. So I'll use the tongue-in-cheek term clairvoyance in place of nondeterminism.
Structure of this section
In this section, we'll show you have to use languages that behave as if they're clairvoyant.
For those of you who are already programmers, we'll begin with NDScript, a sort of JavaScript-subset with the minimum possible clairvoyance features added into it. Being simpler, it makes it easier for us to describe some of the underlying theory. And it lets you directly execute the kinds of nondeterministic algorithms frequently found in textbooks and the academic literature. This section moves quickly and assumes some computer science background. So skip it if you aren't a programmer.
Then we'll continue with Step, a much more flexible and powerful language. Start here if you're not an experienced programmer. Step is more like the clairvoyant languages that are in common use. It combines features of both logic programming and planners. Both these languages are open source and can be used easily in a Unity or Godot game.