Artificial intelligence solves problems in three main ways: it searches through possible moves, it checks combinations against constraints, or it learns a rule from examples and trials. A 2007 Science paper showed that search, run for almost two decades, settled the game of checkers as a draw, and a 2016 paper reported that a constraint solver settled a question about Pythagorean triples. Which way fits depends on how the problem is written down, not on how hard it feels.
Key takeaways
- Search tries sequences of actions, constraint solving rules out impossible combinations, and learning builds a procedure from data or from trial and error.
- Checkers has roughly 5 x 10^20 possible positions, and the published solution reports that perfect play by both sides ends in a draw.
- A SAT solver proved that the natural numbers cannot be split into two parts without one part containing a Pythagorean triple, using a proof of almost 200 terabytes.
- AlphaDev, a reinforcement learning agent, found short sorting routines that were added to the LLVM standard C++ library.
- None of the three methods is general: each needs the task stated precisely enough that a program can test an answer.
Search: trying actions until a goal test passes
A search program starts from a state, lists the actions available, and follows them until a goal is reached. The hard part is size. Checkers is a small game on a board, yet it has about 5 x 10^20 positions, and a research team used dozens of computers almost continuously from 1989 to work through them. Their paper, Checkers Is Solved, appeared in Science in 2007 and reports that perfect play from both sides leads to a draw.
The result is a proof, not an estimate. The program did not guess that the game is drawn; the paper reports that perfect play ends in a draw. That is also why the method does not carry over to tasks with no fixed rules, since a search needs a definition of every legal action and a test for success.
Constraints: ruling out whole families of answers
A constraint solver treats a problem as a set of rules that every answer must satisfy. A SAT solver works on true-or-false variables, and it cuts away large groups of candidates the moment a rule is broken.
A small illustrative example shows the idea. Color each of the numbers 1 to 5 either red or blue, with the rule that 3, 4, and 5 may not all share a color, because 3 squared plus 4 squared equals 5 squared. There are 2^5, or 32, colorings. The rule forbids those where 3, 4, and 5 match, which is 2 choices for that shared color times 4 choices for numbers 1 and 2, so 8 colorings are removed and 24 remain. A solver reasons the same way over millions of variables.
That is the structure of the Boolean Pythagorean triples problem. Marijn Heule, Oliver Kullmann, and Victor Marek applied a method called cube-and-conquer, which took about two days on an 800-core cluster. Their paper reports a proof that is almost 200 terabytes in size, with a compressed certificate of 68 gigabytes that others can use to check it.
Learning: building the procedure instead of writing it
Learning methods start without a hand-written procedure. In the AlphaDev work, published in Nature in June 2023, the authors framed the search for faster sorting code as a single-player game and trained a deep reinforcement learning agent to play it. The agent found small sorting routines that beat the human-written benchmarks, and the routines were integrated into the LLVM standard C++ sort library.
Even here a precise test does the judging. The agent is rewarded only because a program can measure whether the sorted output is correct and how fast the code runs. Learning replaces the human who writes the procedure; it does not replace the need for a score.
Matching a method to a problem
| Method | Question it asks | Case in this article | Main limit |
|---|---|---|---|
| Search | Which sequence of actions reaches the goal? | Checkers, solved as a draw in 2007 | Needs fixed rules and enough computing time |
| Constraint solving | Does any answer satisfy all the rules? | Pythagorean triples, 2016 proof | Proof too large for a person to read |
| Learning | What procedure scores best on a test? | AlphaDev sorting routines, 2023 | Depends on a measurable reward |
Checklist before calling a task a good fit
- Can every allowed action or rule be written down without ambiguity?
- Is there a test that a computer can run to say whether an answer is correct?
- Is the number of possibilities small enough to search, or can rules prune it?
- If a learned system is proposed, is there data or a simulator to train it on?
- Can a person check the result, or is only the program able to?
FAQ
Is problem solving the same as machine learning?
No. Search and constraint solving need no training data. They are older than most learning methods, and the checkers and Pythagorean triples results above used neither a neural network nor a learned model.
Why did checkers take so long to solve?
The game has about 5 x 10^20 positions, and the authors report using dozens of computers almost continuously from 1989 until the 2007 announcement.
Can a proof be trusted if no person can read it?
The authors extracted a compressed 68-gigabyte certificate so that others can reconstruct the proof and check it with software. Trust then rests on the checking software, since no person can read 200 terabytes.
Does solving a game show that AI can solve real-world problems?
Only in part. Games have fixed rules and a clear end. Real tasks usually lack both, so a game result shows what a method can do under ideal conditions.
Related reading
- Worked examples of problem formulation
- AI applied to complex problems and efficiency
- How navigation is framed as an AI problem
- Route optimization and the traveling salesman problem
More in AI Basics.
Last verified: October 2026
Sources
- Checkers Is Solved, Schaeffer J et al., Science 317(5844), 2007
- Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer, Heule MJH, Kullmann O, Marek VW, SAT 2016, arXiv 1605.00723
- Faster sorting algorithms discovered using deep reinforcement learning, Mankowitz DJ et al., Nature 618, 2023