![Whiteboard-style illustration showing tree structures, graphs, and algorithm concepts](https://aivoyagerimages.blob.core.windows.net/blog-images/ai-algorithms-search-games-illustration.png) # The Algorithms Behind AI: How Games, Search, and Decisions Actually Work _Understanding the building blocks that power everything from chess computers to self-driving cars._ ## What you'll learn - How trees and graphs structure AI problem-solving - The difference between blind search and intelligent heuristics - Why expert systems paved the way for modern machine learning - How algorithms like min-max and AlphaGo changed game-playing forever ## Introduction — The hidden engine of AI When you think about AI, you might picture ChatGPT writing poetry or self-driving cars navigating traffic. But beneath these impressive capabilities lies something fundamental: algorithms. An algorithm is simply a sequence of operations that solves a problem. Just like a recipe guides you through making tea (pour water, heat it, steep the bag), algorithms guide computers through complex decisions. The difference? AI algorithms handle problems so intricate that humans would need years to solve them, if we could solve them at all. In this post, we're going on a journey through the algorithmic foundations of AI. No heavy math required, just clear explanations of how intelligent systems actually make decisions. ## The data-algorithm relationship Here's a truth about AI that often gets overlooked: having the right algorithm matters more than having lots of data.[1] Think of it this way. You could have the world's best ingredients, but without a good recipe, your meal will be mediocre. Similarly, you need the right algorithm to make data work correctly. Even intelligent automation requires proper analysis. You won't find machines that know what's appropriate and can completely cut out human intervention. This is why understanding algorithms is essential. Self-improving or autonomous learning systems, also known as machine learning systems, are already a significant area of research and development in AI.[2] ## Understanding trees and graphs — The roadmap of AI decisions Before AI can make decisions, it needs a way to represent possibilities. This is where trees and graphs come in. ### Trees: Following branches to find answers Imagine you're planning a road trip. From your starting point (the root), you have multiple route options (branches). Each choice leads to new options until you reach your destinations (leaves). That's exactly how a tree works in AI.[3] Trees have a single root node, the starting point for processing. Connected to the root are either branches or leaves. A leaf node is an ending point for the tree. Branch nodes support either other branches or leaves. The relationship between nodes is critical, without these parent-child connections, discussions of trees could become quite confusing. ### Graphs: When paths get complicated A graph is a sort of tree extension. Unlike a binary tree, a graph node can have more than one or two connections. In fact, graph nodes often have a multitude of connections, and nodes can connect in any direction, not just from parent to child.[3] Think about a city's street network. Each intersection is a node, and each street is a connection. Unlike a tree where you only move from parent to child, graphs let you explore in any direction. This flexibility makes graphs perfect for modeling real-world problems like GPS navigation or social networks. Graphs can include: - **Directionality:** Some connections work in only one direction (like one-way streets) - **Weights:** Connections can have different "costs" representing distance, time, or fuel consumption - **Cycles:** You can return to nodes you've visited before (which trees don't allow) ## Traversing the graph — How AI searches for solutions Once you have a structure representing possible states, you need a way to search through it. The order of your search determines what kind of algorithm you're using. ### Uninformed search: Exploring without a map Uninformed search (also called blind search) explores the state space without additional information except for the graph structure itself.[3] Here are two common approaches: **Breadth-first search (BFS):** Begins at the graph root and explores every node that attaches to the root. It then searches the next level, exploring each level in turn until it reaches the end. BFS explores the graph in a systematic way, exploring vertices around the starting vertex in a circular fashion. **Depth-first search (DFS):** Begins at the graph root and then explores every node from the root down a single path to the end. It then backtracks and begins exploring the paths not taken in the current search path until it reaches the root again.[4] Think of BFS as exploring a building floor by floor, while DFS is like following one hallway all the way to the end before trying another. ### Informed search: Using intelligent shortcuts The real power of AI comes from informed (heuristic) search. A heuristic finds or discovers a useful method of traversing the graph based on rules of thumb (such as expert systems) or algorithms that use low-cost approaches.[3] It's like being lost in an unknown city and having people tell you a certain way to reach your hotel, but with no precise instructions. Because this search is informed (even though it isn't precise), it can estimate the remaining cost to go from a particular state to a solution. Here are the common heuristic search algorithms: **Best-first search:** An evaluation function assists in the search by determining the desirability of expanding a particular node based on the costs of the nodes that follow. The costs of each node are stored in a queue or another memory structure. This works much like BFS or DFS but with foreknowledge of node costs. **Greedy search:** Like a best-first search, the path to follow is informed by node costs. However, the greedy search looks only one node ahead, which saves processing time but doesn't always guarantee an optimal solution. **A* search:** This is an expansion of the best-first search, which uses two costs: the cost to move from the starting point to another given position in the graph and the cost to move from that given node on the graph to the final destination.[5] ### Local search and heuristics — Escaping complexity A lot goes on behind the state-space search approach. In the end, no machine, no matter how powerful, can enumerate all the possibilities that spring from a complex situation.[6] Consider checkers, a relatively simple game. It has 500 billion billion possible board positions. It took 18 years, using powerful computers, to compute all 500 billion billion possible moves. For more complex problems, you need local search. Local search is a general problem-solving approach composed of a large range of algorithms that help you escape the exponential complexities of many NP problems.[6] Local search algorithms iteratively improve from a starting state, moving one step at a time through neighboring solutions in the state space until they can no longer improve the solution. Here's how local search works: 1. Start with an existing situation (it could be the present situation or a random or known solution) 2. Search for a set of possible new solutions within the current solution's neighborhood, which constitutes the candidates' list 3. Determine which solution to use in place of the current solution based on the output of a heuristic that accepts the candidates' list as input 4. Continue performing steps 2 and 3 until you see no further solution improvement, which means you have the best solution available Popular local search heuristics include: **Hill climbing:** Relies on the observation that as a ball rolls down a valley, it takes the steepest descent. When a ball climbs a hill, it tends to take the most direct upward direction to reach the top, which is the one with the greatest inclination. **Twiddle (coordinate descent algorithms):** Similar to hill-climbing algorithms but explores all possible directions. It concentrates the search in the direction of the neighborhood that works best. As it does so, it calibrates its step, slowing down as it finds the discovery of better solutions difficult, until it reaches a stop. **Simulated annealing:** Takes its name from a metallurgical technique that heats metal and then slowly cools it for cold working and to remove crystalline defects. Local search replicates this technique by viewing the solution search as an atomic structure that changes to improve its workability. The temperature is the game changer in the optimization process: Just as high temperatures make atoms of a material relax, high temperatures in a local search algorithm induce relaxation of the objective function, allowing it to prefer worse solutions over better ones. **Taboo search:** Uses memorization to remember which parts of the neighborhood to explore. When it seems to have found a solution, it tends to try to retrace to other possible paths that it didn't try in order to ascertain the best solution.[7] ## Playing games — The birth of competitive AI AI's ability to play games represents both AI's current functionality and future opportunities. This is the case with adversarial games, in which one player wins and the other loses, or with any similar situation (games) in which one player pursues an objective that conflicts with the goals of others.[8] ### The min-max approximation Imagine tic-tac-toe (or the film WarGames, if you've seen it). The super-computer wonders "Can I win this game?" If you use a state-space search, you won't ever lose. You have nine cells to fill with X's and O's for each player. The first one to place three marks in a row (horizontal, vertical, or diagonal) wins. When building a state-space tree for the game, each level of the tree represents a game turn. The end nodes represent the final board state and determine victory, draw, or defeat, and AI propagates the scores to the upper nodes and branches using minimax summation until reaching the starting node.[8] The idea is to propagate the values of traverse the tree: When it's AI's turn, you sum the maximum value (probably because AI has to retrieve many nodes), you sum the maximum result from the game. When it's the adversary's turn, you sum the minimum value instead. At the end, you extract a tree whose branches are qualified by scores. When it's the AI's turn, it chooses its move based on the branch whose value is the highest, because it implies expanding nodes with the highest possibility to win. This approach is called the min-max approximation. Ronald Rivest, from the computer science laboratory at MIT, introduced it in 1987. Since then, this algorithm and its variants have powered many competitive games, along with recent game-playing advances, such as AlphaGo from Google DeepMind.[9] Sometimes you hear about alpha-beta pruning as connected to min-max approximation. Alpha-beta pruning is a smart way to propagate values up the tree hierarchy in complex state spaces limiting computations. Not all games feature compact state-space trees; when branches number in the trillions, you need to prune them and shorten your calculations. ## From expert systems to machine learning — The evolution of intelligence ### The MYCIN legacy Before machine learning dominated AI, expert systems were the first attempt to escape the realm of hard-coded algorithms and create more flexible and smart ways to solve real-life problems.[10] Expert systems, or systems that use rules to make decisions, were designed to replicate human expertise. The idea at the core of expert systems was simple and well-suited at a time when storing and dealing with lots of data in computer memory was still costly.[10] An example of one of the first systems of this kind is MYCIN, a system to diagnose blood-clotting diseases or infections caused by bacteria, such as bacteremia (when bacteria infect the blood) and meningitis (inflammation of the membranes that protect the brain and spinal cord).[11] MYCIN recommended the correct dosage of antibiotics by using well over 500 rules, which it relied on, when needed, on the doctor using the system. When there wasn't enough information available (for instance, lab tests were missing), MYCIN then started a consultative dialogue by asking relevant questions to reach a confident diagnosis and therapy. Written in Lisp as a doctoral dissertation by Edward Shortliffe at Stanford University, MYCIN took more than five years to complete, and it performed better than any junior doctor, reaching the elevated diagnosis accuracy of an experienced doctor.[11] ### How expert systems worked Generally, expert systems of the time were made of two distinct components: knowledge base and inference engine.[10] **The knowledge base** retains knowledge as a collection of data in the form of if-then statements (with if involving one or multiple conditions and then involving conclusion statements). These single conditions and then form rules differentiating between instances, (single events or facts), classes, and subclasses, which all could be manipulated using Boolean or sophisticated first-order logic, which is composed of more possible operations. **The inference engine** is a set of instructions that tell the system how to manipulate the conditions based on the Boolean logic set of operators such as AND, OR, and NOT. Using this logic set, TRUE or FALSE symbolic conditions can combine into complex reasoning. (When TRUE, a rule is triggered or, technically, "fired"; when FALSE, the rule doesn't apply.) Because the system was made at the core of a series of ifs (conditions) and thens (conclusions), and was nested and structured in layers, acquiring initial information helped rule out some conclusions while also helping the system interact with the user concerning information that could lead to an answer. Common operations by expert systems included: **Forward chaining:** Available evidence triggered a series of rules and excluded others at each stage. The system initially concentrated on rules that could trigger an end conclusion by firing. This approach is clearly data-driven.[10] **Backward chaining:** The system evaluates every possible conclusion and tries to prove each of them on the basis of the evidence available. This goal-driven approach helps determine which questions to pose and excludes entire sets of goals. MYCIN, described earlier, used backward chaining; progressing from hypothesis backward to evidence is a common strategy in medical diagnosis.[11] **Conflict resolution:** If a system reaches more than one conclusion at the same time, the system favors the conclusion that has certain characteristics (in terms of impact, risk, or other factors). Sometimes, the system consults the user and the resolution is realized based on user evaluations.[10] ### Why expert systems faded Expert systems witnessed their twilight at the end of the 1980s, and their development stopped, mostly for the following reasons:[10] 1. The logic and symbolism of such systems proved limited in expressing the rules behind a decision, leading to the creation of custom systems that is, falling back again on hard-coding rules with classical algorithms. 2. For many challenging problems, expert systems became so complex and intricate that they lost their appeal in terms of feasibility and economic cost. 3. Because data was becoming more diffuse and available, it made little sense to struggle to carefully interview, gather, and distill rare expert knowledge when the same (or even better) knowledge could be sifted from data. Expert systems still exist. You can find them used in credit scoring, fraud detection, and other fields with the imperative to not just provide an answer but also clearly and transparently state the rules behind the decision in a way that the system user deems acceptable (as a subject expert would do).[10] ## Discovering the learning machine — The modern revolution All the algorithmic examples given earlier in this chapter are associated with AI because they're smart solutions that are repetitive and well-delimited yet complex problems requiring smart solutions. They require an architect who studies the problem and chooses the right algorithm to solve it.[12] The problem and its solution is characteristic of how you can safely program an AI to solve Sudoku puzzles. You can even train the algorithm. For instance, learning the problem and its solution occurs once within the algorithm. Because learning the problem this is because you can safely program an AI to solve Sudoku puzzles. You can even train the algorithm. Unfortunately, not all problems can rely on a Sudoku-like solution. Real-life problems are never set in simple perfect information and well-defined action. Consider the problem of finding a fraudster cheating on insurance claims or the problem of diagnosing a medical disease. You have to contend with these factors:[12] - **A large set of rules and possibilities:** The number of possible frauds is incredibly high; many diseases have similar symptoms. - **Missing information:** Fraudsters can conceal information; doctors often rely on incomplete information (examinations may be missing). - **Problem rules aren't immutable:** Fraudsters discover new ways to arrange swindles or frauds; new diseases arise or are discovered. To solve such problems, you can't use a predetermined approach; instead, you need a flexible approach and must accumulate useful knowledge to face any new challenge. In other words, you continue learning, as humans do throughout their lives to cope with a changing and challenging environment. ### Machine learning: The game changer Machine learning is part of the world of AI. Solutions capable of learning directly from data with no preprocessing to construct symbols arose a few decades before expert systems. Some were static as symbols arose a few decades before expert systems; and still others tried to generate nature; others imitated nature in various ways; and still others tried to generate autonomously symbolic logic in the form of rules from raw information.[13] Machine learning deals with problems that humans don't know how to detail into steps but that humans naturally solve. An example of such a problem is discerning faces in images or understanding certain words in a spoken discussion. Though machine learning is mentioned in almost every chapter of this book, Chapters 6 and 7 are devoted to disclosing how major machine learning algorithms work, especially deep learning and AI applications that reaches the news headlines powering the new wave of AI almost every day.[13] ### AlphaGo: When AI learned to master intuition The role of machine learning in the new wave of AI algorithms is to in part replace and in part supplement, existing algorithms. Machine learning works with activities that require intelligence from a human point of view but that aren't easy to formalize as a precise sequence of steps.[14] A clear example of this role is the mastery displayed by a Go expert that understands, at a glance, the threats and opportunities of a board configuration and intuitively grasps the right moves.[14] Go is an incredibly complex game for an AI. Chess has an average of 35 possible moves to evaluate on a board, and a game usually spans more than 80 moves, whereas a game of Go has about 240 moves to evaluate, and a game usually spans more than 240 moves. No computer presently exists in the world to create a complete state space for a game of Go.[14] Google's DeepMind team in London developed AlphaGo, a program that has defeated a number of top-ranked Go players. Rather than only rely on an algorithmic approach based on searching an immense state space, the program instead uses the following strategies:[14] - **A smart-search method based on random tests** of a possible move. The AI applies a DFS multiple times to determine whether the first outcome found is a positive or negative estimate (to explore the complete and partial state space). - **A deep-learning algorithm** processes an image of the board (at a glance) and derives both the best possible move in that situation (the algorithm is called the policy network) and an estimate of how likely the AI is to win the game by using that move (the algorithm is called the value network). - **A capability to learn** by seeing completed games by Go experts and by playing against itself. One version of the program, called AlphaGo Zero, can learn all by itself, with no human examples. This learning capability is called reinforcement learning, a powerful technique that combines search algorithms with machine learning to create truly intelligent systems.[15] ## Conclusion — Algorithms are the foundation Understanding algorithms doesn't diminish the magic of AI, it reveals the brilliant engineering that makes it work. From simple tree searches to sophisticated heuristics, from expert systems that captured human knowledge to machine learning that discovers patterns on its own, algorithms are the foundation upon which all AI is built. The next time you see a self-driving car navigate traffic or watch AlphaGo defeat a master player, you'll know the hidden engine powering those decisions: carefully crafted algorithms working with data to solve problems that once seemed impossible. ## Key takeaways - Algorithms are sequences of operations that solve problems; AI algorithms tackle complexity humans cannot manage alone. - Trees and graphs structure how AI represents and explores possibilities. - Uninformed search (BFS, DFS) explores systematically; informed search (heuristics) uses shortcuts to find solutions faster. - Local search helps escape computational explosions in complex problems. - The min-max approximation powers game-playing AI from tic-tac-toe to modern systems. - Expert systems captured human knowledge in rules; machine learning discovers patterns from data. - Modern AI combines classical algorithms with machine learning for unprecedented capabilities. ## Glossary - **Algorithm:** A sequence of operations that solves a problem. - **Tree:** A data structure with a root node and branches connecting to child nodes. - **Graph:** An extension of trees where nodes can connect in any direction with multiple connections. - **BFS (Breadth-First Search):** Explores level by level from the starting point. - **DFS (Depth-First Search):** Follows one path to completion before backtracking. - **Heuristic:** A rule of thumb or shortcut that guides intelligent search. - **A* search:** An informed search using both cost-to-reach and cost-to-goal estimates. - **Local search:** Algorithms that improve solutions iteratively by exploring nearby alternatives. - **Min-max approximation:** An algorithm for game-playing that maximizes AI's advantage while minimizing the opponent's. - **Expert system:** Rule-based AI that captures human expertise in if-then statements. - **Machine learning:** AI that discovers patterns and improves from data without explicit programming. - **Reinforcement learning:** Learning through trial and error, reward and punishment. ## References [1] Russell, S., & Norvig, P. (2020). *Artificial Intelligence: A Modern Approach* (4th ed.). Pearson. Website [2] Jordan, M. I., & Mitchell, T. M. (2015). Machine learning: Trends, perspectives, and prospects. *Science*, 349(6245), 255-260. DOI [3] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press. MIT Press [4] Tarjan, R. (1972). Depth-first search and linear graph algorithms. *SIAM Journal on Computing*, 1(2), 146-160. DOI [5] Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. *IEEE Transactions on Systems Science and Cybernetics*, 4(2), 100-107. DOI [6] Pearl, J. (1984). *Heuristics: Intelligent Search Strategies for Computer Problem Solving*. Addison-Wesley. [7] Glover, F., & Laguna, M. (1997). *Tabu Search*. Kluwer Academic Publishers. DOI [8] Russell, S., & Norvig, P. (2020). Chapter 5: Adversarial Search. In *Artificial Intelligence: A Modern Approach*. Website [9] Silver, D., et al. (2016). Mastering the game of Go with deep neural networks and tree search. *Nature*, 529(7587), 484-489. DOI [10] Jackson, P. (1998). *Introduction to Expert Systems* (3rd ed.). Addison-Wesley. [11] Shortliffe, E. H. (1976). *Computer-Based Medical Consultations: MYCIN*. Elsevier. [12] Domingos, P. (2012). A few useful things to know about machine learning. *Communications of the ACM*, 55(10), 78-87. DOI [13] Mitchell, T. M. (1997). *Machine Learning*. McGraw-Hill. [14] Silver, D., et al. (2017). Mastering the game of Go without human knowledge. *Nature*, 550(7676), 354-359. DOI [15] Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.). MIT Press. Free PDF --- Stay curious and keep exploring. — [André Barnard](/about), AI Explorer

The Algorithms Behind AI: How Games, Search, and Decisions Actually Work

Super Simple Summary

Enjoyed the post? Share it!