Chapter 2: AI Problem Solving (Part 1)

Navigating State Spaces and Planning

Many complex challenges in artificial intelligence can be formulated as formal planning problems. To solve them, computers require a structured mathematical framework consisting of four components:

• State Space: The complete set of all possible situations or configurations in a given environment.
• Transitions: The direct, allowable moves that transform the environment from one state to another.
• Costs: The relative expenditure (in time, distance, or energy) associated with each transition.
• Path: A sequence of valid transitions leading from a starting situation to a target goal.

We illustrate this framework using classical puzzles like the River Crossing dilemma and the Towers of Hanoi, but the concept comes alive when applied to traditional water management in Marwar. Consider the challenge of managing rainwater captured across a network of Johad (community ponds), Kund (underground cisterns), and Bawdi during Choumaso (the four monsoon months). Each specific water level across the village reservoirs represents a distinct state. Moving livestock between grazing areas or opening channels to irrigate agricultural fields represents a transition. The evaporation loss and physical labor involved represent the cost. Planning an optimal water distribution schedule to survive the dry months is a masterclass in state-space navigation.

Game Trees and Strategic Anticipation

When an AI interacts with an active opponent, problem-solving evolves from simple pathfinding into strategic game theory. We study how computers play games like Tic-Tac-Toe, Checkers, and Chess by constructing Game Trees. In these structures, the current board position is the root node, possible legal moves branch outward as children, and final outcomes (win, loss, or draw) reside at the terminal leaves.

In zero-sum games where one player's gain is exactly the other's loss, AI employs the Minimax Algorithm. The algorithm assumes both players play optimally: the maximizing player seeks to reach the highest terminal score (+1), while the minimizing opponent tries to force the lowest score (-1). This constant anticipation of an adversary's best counter-move is perfectly illustrated by traditional two-player strategic board games like Bagh-Bakri (Tiger and Goats), which are traditionally etched onto courtyard stones and stepwell stairs across rural Rajasthan. In this game, one player controls four tigers attempting to capture goats, while the opponent controls twenty goats attempting to surround and trap the tigers. At every turn, each player must calculate several moves ahead, assuming the adversary will make their absolute best tactical move to counter them.