An AI problem is described by the environment the program works in, and textbooks sort that environment along six properties: observable or partly hidden, predictable or random, static or changing, one-shot or sequential, known or unknown rules, and one agent or many. The more a problem sits on the hard side of each pair, the less a simple lookup or a fixed rule can solve it.
Key takeaways
- The standard checklist comes from the textbook Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig and is taught in university courses, including the University of Waterloo's CS 486/686.
- Crossword puzzles and chess are easy on several properties, while poker, medical diagnosis, and driving are hard on most of them.
- A single problem can be labeled differently depending on how it is modeled, so the labels are a way to ask questions, not a fixed ruling.
- Hard properties do not make a problem unsolvable. They change which method fits, for example search, probability, or learning from experience.
The six questions that classify a problem
A lecture on agents from the University of Waterloo's CS 486/686 course, based on chapters 2.1 to 2.3 of the Russell and Norvig textbook, frames each property as a question about the agent and its surroundings. The Waterloo lecture slides give these definitions.
- Observability: can the agent determine the state of the world from what it senses? If many states fit one observation, the environment is partially observable.
- Determinism: given the current state and an action, is the next state completely determined? If several next states are possible, the environment is stochastic.
- Static or dynamic: does the environment change while the agent is working on it?
- Episodic or sequential: does the current action affect future actions? If so, the problem is sequential.
- Known or unknown: does the agent know all the rules of the environment?
- Single or multiple agents: does the agent treat other agents as part of the background, or model them and reason strategically about them?
The slides add that an environment is called uncertain if it is either not fully observable or not deterministic. The textbook itself, now in its fourth US edition according to the book's companion site, covers the same ideas in chapter 2.
Reading the table: easy and hard environments
The table below applies the six questions to five well-known problems. The labels are an illustrative classification in the textbook style, not measurements. The Waterloo slides pose several of them as class questions, including chess against poker for determinism and crossword puzzles against image classification for episodic versus sequential.
| Problem | Observability | Determinism | Changes while acting | Episodic or sequential | Agents |
|---|---|---|---|---|---|
| Crossword puzzle | Full | Deterministic | Static | Sequential | Single |
| Chess | Full | Deterministic | Static | Sequential | Multi |
| Poker | Partial | Stochastic | Static | Sequential | Multi |
| Classifying one image | Full | Deterministic | Static | Episodic | Single |
| Medical diagnosis | Partial | Stochastic | Dynamic | Sequential | Single |
The pattern explains why programs mastered chess long before they could drive. Driving is partially observable (a pedestrian behind a truck is hidden), stochastic, dynamic, sequential, and shared with other agents. In the Waterloo slides, the question of whether a self-driving car is single-agent or multi-agent gets the answer that it depends, which shows how modeling choices can move a problem between labels.
A small worked example of the stochastic property
Suppose a game lets a player roll one fair six-sided die and score the number shown. In a deterministic game the player could pick the outcome, but here every action leads to six possible next states, each with probability one in six. A planner cannot plan for one outcome. It reasons about the expected score, which is (1 + 2 + 3 + 4 + 5 + 6) divided by 6, or 3.5 points. A rule such as "if the score is 3, do X" is replaced by a choice that is best on average.
Now add partial observability. If the die is rolled behind a screen and only a noisy sensor reports the result, the agent must also keep track of how likely each state is, given what it has seen. Most real systems, from weather forecasting to spam filtering, combine both kinds of uncertainty, which is why probability appears throughout the field.
What each hard property demands from a method
- Partial observability: the system needs memory or a belief about hidden state, since one observation is not enough.
- Stochastic outcomes: plans must be judged on expected results or worst cases, not on a single predicted path.
- Dynamic environments: decisions have a time limit, because the world moves while the agent thinks.
- Sequential problems: early actions affect later ones, so the system must weigh long-term consequences.
- Unknown rules: the agent has to learn how the environment behaves, usually from data or trial and error.
- Multiple agents: other actors may cooperate or compete, so their likely choices become part of the problem.
These demands are why no single technique solves every AI problem. A method that is well suited to a fully observable, deterministic puzzle can fail in a setting with hidden information and other players.
FAQ
Who defined these properties?
They are standard in the field's best-known textbook, Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, and in university courses based on it. Different courses use slightly different lists, for example adding or dropping the known versus unknown pair.
Does a hard environment mean the AI cannot work there?
No. It means the method has to match the problem. Systems operate in partially observable, stochastic settings, but they need probabilistic reasoning or learning, and their performance is usually less certain than in a puzzle with fixed rules.
Can one problem have more than one correct label?
Yes. How a problem is modeled decides the labels. A driving system that treats other cars as scenery behaves as a single agent, while one that predicts their intentions is treating the road as multi-agent.
Is this the same as problem formulation?
No. Formulation defines the states, actions, and goal of a specific task. Classifying the environment is a step before that, and it helps decide which kind of formulation and method is realistic.
Related reading
- Identifying and addressing problems in AI research
- Why toy problems have limits in AI research
- How AI is applied to complex problems
- Problem space complexity in AI
More in AI Basics.
Last verified: October 2026
Sources
- Artificial Intelligence: A Modern Approach, 4th US edition, Russell S, Norvig P, Pearson, chapter 2 (companion site at the University of California, Berkeley)
- Lecture 2: Agents and Task Environments, CS 486/686 Introduction to Artificial Intelligence, Gao A, University of Waterloo, spring 2019