Course contentsShow
← Computer Science
Lesson 2731 of 2,87261. AI and Search AlgorithmsFree lesson

State Representation Strategies

Choosing effective data structures to represent states for different problem domains like puzzles and games.

State Representation Strategies

What you'll learn: How to choose the right data structures to encode problem states efficiently for search algorithms.

Why Representation Matters

In AI search problems—like solving puzzles, playing games, or planning routes—every state must be stored in memory and compared to others. The way you represent these states directly impacts memory usage, speed, and whether your algorithm succeeds at all.

Think of it like choosing how to pack a suitcase: you could throw everything in loose, fold items into cubes, or use compression bags. Each approach affects how much fits and how quickly you can find what you need.

Core Principles

Compactness: Use minimal memory. For an 8-puzzle (sliding tiles), don't store a full 2D array with metadata—a single array of 9 integers suffices.

Uniqueness: Each distinct state should map to one representation. If the same logical state has multiple encodings, you'll waste time exploring duplicates.

Fast Operations: Your representation must support quick state transitions (generating successors) and comparisons (checking if you've reached a goal). Hashing and equality checks should be efficient.

Domain-Appropriate: A chess board might use a bitboard (64-bit integers for piece positions) for speed, while a pathfinding grid could use coordinate tuples (x, y).

Common Patterns

  • Arrays/Lists: Simple puzzles (8-puzzle, Rubik's cube positions)
  • Tuples/Immutable structures: When states need hashing for visited sets
  • Matrices: Grid worlds, cellular automata
  • Graphs: Network problems, social connections
  • Bitsets: Compact representation when state is binary flags

Example Contrast

For tic-tac-toe: storing "Player X has pieces at positions..." as a list is verbose. A 9-element array or even a single integer (encoding board as base-3 digits) is far more efficient.

Key Takeaway: The right state representation balances memory efficiency, computational speed, and problem semantics—choose data structures that make state generation and comparison operations fast and unambiguous.