--- title: "Informed vs uninformed; min-max; alpha-beta" subject: "Artificial Intelligence" chapter: 3 key: "semester_6/artificial_intelligence:informed-uninformed-minmax-alphabeta" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/informed-uninformed-minmax-alphabeta site: BCT Engineering --- # Informed vs uninformed; min-max; alpha-beta Artificial Intelligence · Chapter 3: Search Techniques - Asked in: 2071 Magh, 2+4+3 marks - Video: [1. MiniMax Search Algorithm Solved Example | Min Max Search Artificial Intelligence by Mahesh Huddar](https://www.youtube.com/watch?v=tDv7lrklaQE) — Mahesh Huddar - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/informed-uninformed-minmax-alphabeta - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3 ## Question How is informed search different from uninformed search? Explain the min-max algorithm with a suitable example, and also discuss how alpha-beta is different from the min-max algorithm. ## Short answer Informed search uses a heuristic h(n); uninformed search uses only the problem definition. Min-max backs up leaf values with MAX taking the maximum child and MIN the minimum, yielding the optimal move. Alpha-beta pruning returns the same result while skipping branches with alpha >= beta, cutting time to O(b^(m/2)) in the best case. ## Answer #### Informed vs uninformed search | Basis | Uninformed (blind) search | Informed (heuristic) search | |---|---|---| | Knowledge | Only the problem definition | Uses a heuristic h(n), the estimated cost to the goal | | Strategy | Expands nodes in a fixed order | Expands the most promising node first | | Efficiency | Slow, explores many nodes | Faster, explores fewer nodes | | Examples | BFS, DFS, uniform-cost | Greedy best-first, A*, hill climbing | #### Min-max algorithm Min-max is a **game-tree search** for two-player, zero-sum games (chess, tic-tac-toe). **MAX** tries to maximise the utility and **MIN** (the opponent) tries to minimise it. The algorithm generates the game tree to some depth, evaluates the leaf nodes with a utility function, and backs the values up: MAX nodes take the **maximum** of their children, MIN nodes take the **minimum**. At the root MAX picks the move with the highest backed-up value (it assumes the opponent plays optimally). **Example** (leaf values shown at the bottom): ```text MAX [5] / \ MIN [5] MIN [0] / \ / \ MAX[5] MAX[9] MAX[2] MAX[0] / \ / \ / \ / \ 3 5 6 9 1 2 0 -1 ``` - MAX nodes: max(3,5)=5, max(6,9)=9, max(1,2)=2, max(0,-1)=0. - MIN nodes: min(5,9)=5, min(2,0)=0. - Root MAX: max(5,0)=**5**, so MAX chooses the left move. Time complexity O(b^m), space O(b·m) (depth-first), where b = branching factor and m = depth. #### How alpha-beta differs from min-max Alpha-beta pruning gives **the same result as min-max but skips branches that cannot affect the final decision**. It keeps two values: **α** = best (highest) value found so far for MAX, **β** = best (lowest) value found so far for MIN. A branch is pruned when α ≥ β. In the example above: in the left MIN node, the first MAX child gives 5, so β = 5. In the second MAX child the first leaf is 6, which is already ≥ β, so MIN will never choose this child and the leaf 9 is **pruned**. In the right MIN node, the first MAX child gives 2, so this MIN node is worth at most 2, which is ≤ α = 5 (MAX already has 5 on the left); its second child (leaves 0, -1) is **pruned**. Only 5 of the 8 leaves are examined, yet the answer is still 5. | Basis | Min-max | Alpha-beta | |---|---|---| | Nodes examined | All nodes up to the depth limit | Fewer nodes, prunes useless branches | | Result | Optimal value | Same optimal value | | Time (best case) | O(b^m) | O(b^(m/2)) with good move ordering | | Depth in same time | d | about 2d | | Extra data | None | Two parameters α and β | ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How are values backed up in the min-max algorithm? A. MAX nodes take the minimum and MIN nodes take the maximum B. MAX nodes take the maximum of children and MIN nodes take the minimum C. All nodes take the average D. All nodes take the leaf value on the left Answer: B. MAX tries to maximise utility and MIN to minimise it, so each takes the corresponding extreme of its children. (Key point: Min-max backup rule) 2. What does MAX assume about the opponent at the root? A. The opponent plays randomly B. The opponent plays optimally C. The opponent always passes D. The opponent plays the same as MAX Answer: B. MAX picks the move with the highest backed-up value assuming MIN also plays optimally. (Key point: Min-max assumption) 3. How does alpha-beta differ from min-max? A. It gives a different, approximate answer B. It gives the same result but prunes branches that cannot affect the decision C. It examines more nodes to be safe D. It works only for single-player games Answer: B. Alpha-beta returns the same optimal value as min-max while skipping irrelevant branches. (Key point: Alpha-beta vs min-max) 4. When is a branch pruned in alpha-beta? A. When alpha < beta B. When alpha ≥ beta C. When the node is a leaf D. When the depth is odd Answer: B. If α (best for MAX so far) ≥ β (best for MIN so far), the remaining children cannot change the outcome. (Key point: Pruning condition) ## Related in Artificial Intelligence - [Informed vs blind search; DFS vs BFS](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-vs-blind-search-dfs-bfs) — Artificial Intelligence, chapter 3 ## Related in other subjects - [Alpha versus beta testing](https://www.bctengineer.com/question.md?key=semester_5%2Fsoftware_engineering%3Aalpha-vs-beta) — Software Engineering, chapter 8 - [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4× - [Short note: Max-flow min-cut theorem](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Amax-flow-min-cut-theorem) — Discrete Structure, chapter 4, asked 6× - [Define αmax, αmin, insertion loss and gain](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Adefine-amax-amin-insertion-loss) — Filter Design, chapter 1, asked 2×